Developing a job shop scheduling system through integration of graphic user interface and genetic algorithm

详细信息    查看全文

• 作者：Jun Woo Kim
• 关键词：Job shop scheduling problem ; Precedence constrained sequencing problem ; Candidate order based genetic algorithm ; Graphic user interface ; Scheduling system
• 刊名：Multimedia Tools and Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：74
• 期：10
• 页码：3329-3343
• 全文大小：826 KB
• 参考文献：1.Abdelmaguid R (2010) Representations in genetic algorithm for the job shop scheduling problem: a computational study. J Softw Eng Appl 3:1155鈥?162View Article
  2.Ahmed ZH (2010) Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. Int J Biom Bioinforma 3:96鈥?05
  3.Altiparmak F, Gen M, Lin L, Karaoglan I (2009) A steady state genetic algorithm for multi-product supply chain network design. Comput Ind Eng 56:521鈥?37View Article
  4.Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. Oper-Res-Spektrum 17:87鈥?2View Article MATH
  5.Brucker P, Schile R (1990) Job-shop scheduling with multi-purpose machines. Computing 45:369鈥?75View Article MATH MathSciNet
  6.Cheng R, Gen M, Tsujimura Y (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms 鈥?I. Representation. Comput Ind Eng 4:983鈥?97View Article
  7.Fang HL, Ross P, Corne D (1993) A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems, In: The 5th International Conference on Genetic Algorithms, 375-382
  8.Holland JH (1975) Adaptation in Natural and Artificial Systems, University of Michigan Press
  9.Kammer M, Akker MVD, Hoogeveen H (2011) Identifying and exploiting commonalities for the job-shop scheduling problem. Comput Oper Res 38:1556鈥?561View Article MathSciNet
  10.Kim JW (2012) A simple job shop scheduling game for industrial engineering students. J Futur Game Technol 2:165鈥?71
  11.Kim JW (2013) Candidate order based genetic operators for sequencing problems. International Conference on Intelligence Fusion, In, pp 12鈥?3
  12.Kowalczyk R (1997) Constrained consistent genetic algorithms. IEEE International Conference on Evloutionary Computation, In, pp 343鈥?48
  13.Kozen D (1992) The design and analysis of algorithms, Springer
  14.Lee HP, Carter JN (2006) A modified Giffler and Thompson genetic algorithm on the job shop scheduling problem. MATEMATIKA 22:91鈥?07
  15.Lenstra JK, Kan AR (1978) Complexity of scheduling under precedence constraints. Oper Res 26:22鈥?5View Article MATH
  16.Muth JF, Thompson GL (1963) Industrial scheduling. Prentice Hall, New Jersey
  17.Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35:3202鈥?212View Article MATH
  18.Poon PW, Carter JN (1995) Genetic algorithm crossover operators for ordering applications. Comput Oper Res 22:135鈥?47View Article MATH
  19.Ruiz-Vanoye JA, Diza-Parra O, Zavala-Diaz JC (2011) Compexity indicators applied to the job shop scheduling problem to discriminate the best algorithm. Int J Comb Optim Probl Inform 2:25鈥?1
  20.Starkweather T, MacDaniel S, Mathias KE, Whitely LD, Whitley C (1991) A comparison of genetic sequencing operators, In: The 4th International Conference on Genetic Algorithms, 69-76
  21.Werner F (2011) Genetic algorithms for shop scheduling problems: a survey. http://鈥媤ww.鈥媘ath.鈥媢ni-magdeburg.鈥媎e/鈥媬werner/鈥媝reprints/鈥媝11-31.鈥媝df . Accessed 24 June 2013
  22.Yamada T, Nakano R (1992) A genetic algorithm applicable to large-scale job-shop problems. Parallel Probl Solving from Nat 2:281鈥?90
  23.Zhang Z, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 38:3562鈥?573
  
• 作者单位：Jun Woo Kim (1)
  
  1. Department of Industrial and Management Systems Engineering, Dong-A University, 840, Hadan 2-dong. Saha-gu, Busan, 604-714, South Korea
  
• 刊物类别：Computer Science
• 刊物主题：Multimedia Information Systems
  Computer Communication Networks
  Data Structures, Cryptology and Information Theory
  Special Purpose and Application-Based Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7721

文摘

Job shop scheduling problem is one of the well known hardest combinatorial optimization problems that has a wide range of industrial application domains. Due to the NP-hardness of job shop scheduling problem, meta heuristic search methods such as genetic algorithm have been widely applied to find the good schedules, however, solving the precedence constrained sequencing problems such as JSP is still challenging for genetic algorithms. Moreover, the genetic algorithms for the precedence constrained sequencing problems have been often problem dependent or constraint specific, and the user experiences are not considered in developing them. To address these issues, this paper aims to develop a graphic user interface based job shop scheduling system that searches the good schedules by using the candidate order based genetic algorithm. The candidate order based genetic algorithm enable our scheduling system to handle a wide range of precedence constrained sequencing problems conveniently, and the users can construct various sequencing problems via simple graphic user interfaces. For illustration, our system is applied to classical JSP and its variant, and the experiment results reveal the promising applicability of the system.