A Cross Entropy-Genetic Algorithm for m-Machines No-Wait Job-ShopScheduling Problem
Budi Santosa, Muhammad Arif Budiman, Stefanus Eko Wiratno
DOI: 10.4236/jilsa.2011.33018   PDF    HTML     5,479 Downloads   10,647 Views   Citations


No-wait job-shop scheduling (NWJSS) problem is one of the classical scheduling problems that exist on many kinds of industry with no-wait constraint, such as metal working, plastic, chemical, and food industries. Several methods have been proposed to solve this problem, both exact (i.e. integer programming) and metaheuristic methods. Cross entropy (CE), as a new metaheuristic, can be an alternative method to solve NWJSS problem. This method has been used in combinatorial optimization, as well as multi-external optimization and rare-event simulation. On these problems, CE implementation results an optimal value with less computational time in average. However, using original CE to solve large scale NWJSS requires high computational time. Considering this shortcoming, this paper proposed a hybrid of cross entropy with genetic algorithm (GA), called CEGA, on m-machines NWJSS. The results are compared with other metaheuritics: Genetic Algorithm-Simulated Annealing (GASA) and hybrid tabu search. The results showed that CEGA providing better or at least equal makespans in comparison with the other two methods.

Share and Cite:

B. Santosa, M. Budiman and S. Wiratno, "A Cross Entropy-Genetic Algorithm for m-Machines No-Wait Job-ShopScheduling Problem," Journal of Intelligent Learning Systems and Applications, Vol. 3 No. 3, 2011, pp. 171-180. doi: 10.4236/jilsa.2011.33018.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] P. J. Chao-Hsien and H. Han-Chiang, “A Hybrid Genetic Algorithm for No-Wait Job Shop Scheduling Problems,” Expert Systems with Application, Vol. 36, No. 2, Part 2, 2009, pp. 5800-5806. doi:10.1016/j.eswa.2008.07.005
[2] C. J. Schuster and J. M. Framinan, “Approximative Procedures for No-Wait Job Shop Scheduling,” Operations Research Letters, Vol. 31, No. 4, 2003, pp. 308-318. doi:10.1016/S0167-6377(03)00005-1
[3] W. Bo?ejko and M. Makuchowski, “A Fast Hybrid Tabu Search Algorithm for the No-Wait Job Shop Problem,” Computers & Industrial Engineering, Vol. 56, No. 4, 2009, pp. 1502-1509. doi:10.1016/j.cie.2008.09.023
[4] R.Y. Rubinstein and D. P. Kroese, “The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization. Monte-Carlo Simulation and Machine Learning,” Springer Verlag, New York, 2004.
[5] C. F. Liaw, “An efficient Simple Metaheuristic for Minimizing the Makespan in Two-Machine No-Wait Job Shops,” Computer & Operations Research, Vol. 35, No. 10, 2008, pp. 3276-3283. doi:10.1016/j.cor.2007.02.017
[6] A. Mascis and D. Pacciarelli, “Discrete Optimization: Job-Shop Scheduling with Blocking and No-Wait Constraints,” European Journal of Operational Research, Vol. 143, No. 3, 2002, pp. 498-517. doi:10.1016/j.cor.2007.02.017
[7] J. M. Framinan and C. J. Schuster, “An Enhanced Timetabling Procedure for the No-Wait Job Shop Problem: a Complete Local Search with Memory Approach,” Computers & Operations Research, Vol. 33, No. 1, 2006, pp. 1200-1213. doi:10.1016/j.cor.2004.09.009
[8] J. Zhu, X. Li and Q. Wang, “Complete Local Search with Limited Memory Algorithm for No-Wait Job Shops to Minimize Makespan,” European Journal of Operational Research, Vol. 198, No. 2, 2009, pp. 378-386. doi:10.1016/j.ejor.2008.09.015
[9] M. Derek, “A Sequential Scheduling Approach to Combining Multiple Object Classifiers Using Cross-Entropy,” In: T. Windeatt and F. Roli, Eds., MCS 2003, LNCS 2709, Springer-Verlag, Berlin, pp. 135-145.
[10] D. P. Kroese and K. P. Hui, “Applications of the Cross-Entropy Method in Reliability Computational Intelligence,” Reliability Engineering (SCI), Vol. 40, 2007, pp. 37-82.
[11] B. Santosa and N. Hardiansyah, “Cross Entropy Method for Solving Generalized Orienteering Problem,” iBusiness, Vol. 2, No. 4, 2010, pp. 342-347.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.