Optimization of Job Shop Scheduling with Transportation Time Using Genetic Algorithm

Authors:

Sunil Kumar (Manav Rachna International University, Faridabad)

Rakesh Kr. Phanden (Maharishi Markandeshwar University, Sadopur)

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

Keywords: Job Shop Scheduling, Genetic Algorithm,Transportation Time, Makespan

Abstract:

Efficiency in Job Shop Scheduling plays an important role when a large number of jobs and machines are considered. The high complexity of the problem makes it hard to find the optimal solution within reasonable time in most cases. This work deals with the Job Shop Scheduling (JSS) using Genetic Algorithm (GA). For a job-shop scheduling, ‘n’ number of jobs on ‘m’ number of machines processed through an assured objective function to be minimized.Objective of this present work is to minimize the makespan (The total time between the starting of the first operation and the ending of the last operation, is termed as the makespan). The input parameters are operation time and operation sequence for each job in the machines provided.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 proposed genetic algorithm with certain operating parameters is applied to the two case studies taken from literature. The results obtained from our study have shown that the proposed algorithm can be used as a new alternative solution technique for finding good solutions to the complex Job Shop Scheduling problems with shortest processing time and transportation time.

References:

[1] Ren Qing-dao-er-ji and Wang Yuping (2013). A new hybrid genetic algorithm for job shop scheduling problem. Computers & Operations Research 39:2291–2299.

[2] Sadrzadeh Amir (2013). To Solving the job shop scheduling problem via a modified PSO. Technical Journal of Engineering and Applied Sciences TJEAS Journal-2013-3-1/59-64.

[3] Sierra María R., Mencía Carlos, and Mencía Ramiro Mencía (2013). A new schedule generation schemes for the job-shop problem with operators. J Intell ManufDOI10.1007/s10845-013-0810-6.

[4] Zhang Rui, Song Shiji, and Wu Cheng (2013). “A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem”. Int J Adv Manuf Technol 67:5–17

[5] Li J., Pan Q., Xie S., and Jun-qing S. Wang (2012).A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems.Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. VI, No. 2 (June), pp. 286-296

[6] Teekeng Wannaporn, and Thammano Arit (2012).Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Computer Science 12:122 – 128.

[7] Zhang Guohui, Gao Liang, and Shi Yang (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications 38. 3563–3573.

[8] 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.

[9] Defersha Fantahun M. and Chen Mingyuan (2010). A parallel genetic algorithm for a flexible job-shop scheduling problem with sequence dependent setups. Int J Adv Manuf Technol 49:263–279

[10] Lei Deming (2010). Solving fuzzy job shop scheduling problems using random key genetic algorithm. Int J Adv Manuf Technol 49:253–262.

[11] Sun Liang, Cheng, Xiaochun, and Liang Yanchun (2010). To Solving for Job Shop Scheduling Problem Using Genetic Algorithm with Penalty Function, International Journal of Intelligent Information Processing Volume 1, Number 2.

[12] Zhang Rui, Wu Cheng (2010). A hybrid approach (HA) to large-scale job shop scheduling. Appl Intell 32: 47–59.

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

[14] Jinwei Gu, Xingsheng Gu (2009). A novel parallel quantum genetic algorithm for stochastic job shop scheduling. Journal of Mathematical Analysis and Applications J. Math. Anal.Appl. 355 63–81.

[15] Rossi Andrea and Boschi Elena (2009). A hybrid heuristic (HH) method to solve the parallel machines job-shop scheduling problem. Advances in Engineering Software 40:118–127.

[16] Chaoyong Zhang & Yunqing Rao (2008). An effective hybrid genetic algorithm for the job shop scheduling problem. Int J Adv Manuf Technol 39:965–974.

[17] Yong Ming Wang (2008). A two-stage genetic algorithm for large size job shop scheduling problems. Int J Adv Manuf Technol. 39:813–820.

[18] Jie Gao, Mitsuo Gen and Linyan Sun (2006). Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. J Intell Manuf 17:493–507.

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

[20] Omar, M., Baharum, A., & Hasan, Y. A. (2006). A job-shop scheduling problem (jssp) using genetic algorithm (ga). Regional conference on Mathematics, Statics and Applications, University Sains Malasiya, Penang, 13-15 June 2006.

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

[22] 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.

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

[24] Pinedo, M., (2001) Scheduling: Theory, Algorithms, and Systems, Prentice Hall, New York.

[25] Amico Delland Trubian Marco (1993). Annals of Operations Research - A Special issue on Taboo Search. Volume 41 Isse 1-4, Pages 231-252.

[26] Garey, M. R., & Johnson, D. S. (1979). Computer and intractability: A guide to the theory of NP-completeness. San Francisco: W.H. Freeman.

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