Optimization of Job Shop Scheduling Using Genetic Algorithm

Authors:

Sunil Kumar (Manav Rachna International University, Faridabad)

Dr. R.V. Singh (Manav Rachna International University, Faridabad)

Keywords: Job Shop Scheduling, Genetic algorithm, Shortest Processing Time, and Makespan.

Abstract:

The Job-Shop Scheduling Problem (JSSP) is considered as one of the difficult combinatorial optimization problems and treated as a member of Non Polynomial problem class. The present work aims to develop a genetic algorithm based approach to solve the Job Shop scheduling problem. Operation based representation is used to decode the schedule in the algorithm. Two point crossover and flip inverse mutation is used in this algorithm. The algorithm is encoded and developed in MATLAB Software. The input parameters are operation time and operation sequence for each job in the machines provided. The Objective of this present work is to minimize the makespan. The experimental results show that the proposed GA, as compared to earlier GA, not only improves the quality of solutions but also reduces the overall computational time.

References:

[1]. Lenstra, J.K.; Kan, A.H.G.R.; Brucker, P (1977). “Complexity of machine scheduling problems”. Ann. Discret. Math.,1,343–362.

[2]. Baker KR (1974). “Introduction to Sequencing and Scheduling”. Wiley, New York.

[3]. Brucker P, Thiele O (1996). “A branch & bound method for the general shop problem with sequence dependent setup-times”. OR Spektrum;18: pp.145–161.

[4]. Liu, M., Dong, M. Y., & Wu, C. An iterative layered Taboo search algorithm for complex job shop scheduling problem.Chinese Journal of Electronics, 2005,14(3), pp.519–523.

[5]. Liu, T. K., Tsai, J. T., & Chou, J. H (2006). “Improved genetic algorithm for the job-shop scheduling problem”. International Journal of Advanced Manufacturing Technology, 27(9–10), pp. 1021– 1029.

[6]. Diaz-Santillan, E., & Malave, C. O (2004). “Simulated annealing for parallel machine scheduling with split jobs and sequence dependent set-ups”.International Journal of Industrial Engineering– Theory Applications and Practice, 11(1), pp. 43–53.

[7]. Asadzadeh Leila, and Zamanifar Kamran (2010). “An agent-based parallel approach for the job shop scheduling problem with genetic algorithms”, Mathematical and Computer Modeling 52.1957-1965.

[8]. Gholami M., and M. Zandieh(2009). “Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop”.J IntellManuf 20:481–498.

[9]. GuJinwei, Gu Xing Sheng, and GuManzhan (2009). “A novel parallel quantam Genetic Algorithm for stochastic job shop scheduling.” J. Math .Anal Appl.355: 63-81.

[10]. Wang Yong Ming, Xiao Nan Feng, Yin Ho ng Li, Hu En Liang, Zhao Cheng Gui, and Jiang Yan Rong (2008). “A Two-stage genetic algorithm for large size job shop scheduling problems”. Int. J AdvManuf Techno 39:813– 820.

[11]. Mattfeld Dirk C., and Bierwirth Christian (2004). “An efficient genetic algorithm for job shop scheduling with minimization of tardiness objectives”. European Journal of Operational Research 155:616–630.

[12]. Ombuki Beatrice, and Ventresca Mario (2004). “A Local Search Genetic Algorithms for the Job Shop Scheduling Problem”.Applied Intelligence 21, 99–109, Kluwer Academic Publishers. Manufactured in The United States.

[13]. Holland, J. H. (1975). “Adaptation in Natural and Artificial Systems”. University of Michigan Press. Second edition: MIT Press, 1992.