Modeling and Solution of Job Shop Scheduling with No-Wait Orders to Minimize Makespan: A Decomposition Approach based on Order Sequencing and Timetabling

Document Type : Research Paper


kashan university


Job shop scheduling problem with no-wait is a special case of general job shop scheduling problem where there is no waiting time between operations and within jobs. In other words, when the operation of each order starts, there is no stop. In literature of scheduling problems, this problem has been known as NP-hard problem. The proposed approach for solving such problems generally decompose the problem into two sub problems: sequencing and timetabling. In this paper, after analyzing the genetic algorithm based approaches presented in literature, we will present a new approach. After introducing the main problem and solution approaches, we will investigate the solution approaches and evaluate their limitations and advantages. Finally a GA based on the improvements will be presented which exhibits relatively high efficiency.


[1] Hall, N. G., and Sriskandarajah, C. (1996), “A Survey of Machine Scheduling Problems with Blocking and no-wait in Process”, Operations Research, Vol. 44, pp. 510–525.
[2] Mascis, A., and Pacciarelli, D.,(2002), “Job-Shop Scheduling with Blocking and no-Wait Constraints”, European Journal of Operational Research, Vol. 143, pp. 498–517.
[3] Raaymakers, W. H. M., and Hoogeven, J. A.(2000), “Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing”, European Journal of Operational Research, Vol. 126, pp.131–151.
[4] Macchiaroli, R., Mole, S., Riemma, S., and Trifililetti, L., (1996), “Design and Implementation of a Tabu Search Algorithm to Solve the no-Wait Job-Shop Scheduling Problem”. In Proceeding of the CESA’96, Lille.
[5] Schuster, C., and Framinan, J.M., (2003), “Approximative Procedures for no-Wait Job Shop Scheduling”, Operations Research Letters, Vol. 31, pp. 308–18.
[6] Brizuela, C. A., Zhao, Y., and Sannomia, N., (2001),“No-Wait and Blocking Job-Shops: Challenging Problems for GA’s”,In IEEE International Conference on Systems, Man, and Cybernetics, Tucson, Arizona, USA.
[7] Zhu, J., Li, X., and Wang, Q.,(2009), “Complete Local Search with Limited Memory Algorithm for no-Wait Job Shops to Minimize Makespan”, European Journal of Operational Research, Vol. 198, pp. 378-386.
[8] Wang, L., and Zheng, D.,(2001), “An Effective Hybrid Optimization Strategy for Job-Shop Scheduling Problems”, Computers & Operations Research, Vol. 28, pp. 585–96.
[9] Pan, J. C.-H., and Huang H.-C.,(2009), “A Hybrid Genetic Algorithm for no-Wait Job Shop Scheduling Problems”, Expert Systems with Applications, Vol. 36, pp. 5800-5806.
[10] Mokhtari, H., Abadi, INK and Zegordi, SH., (2011), “Production capacity planning and scheduling in a no-wait environment with controllable processing times: An integrated modeling approach”, Expert Systems with Applications, Vol.38, pp. 12630-12642.
[ 11 [ مخ اری، هادی، نخبی امال ت ادی، می ی امین ناأری محمدر ا، ) 1392 (، "مدلسازی ا لحلیلی م له رنامه ریزی ظرفیت
زمانبندی لیلید یکپارچه: اس خراج اراظ پااین طراای ی الگیری م شامه اراظ اارا"، مجله ملمی-پژ ه ی مهندسی
أنایع مدیریت لیلید، د ره 24 ، شماره 2 ، أیحه 139 - 118
[12] Goyal, S. K., (1975), “Job-Shop Sequencing Problem with no Wait in Process”, International Journal of Production Research, Vol. 13, pp. 197–206, 197.
[13] Framinan, J.M., and Schuster, C.,(2006), “An Enhanced Timetabling Procedure for the no-Wait Job Shop Problem: A Complete Local Search Approach”, Computers & Operations Research, Vol. 331, pp. 1200–1213.
[14] Schuster, C., (2006), “No-Wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems”, Mathematical Methods of Operations Research, Vol. 63, pp. 473–491.