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                

Abstract

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.

Keywords

No-Wait Job Shop Scheduling, Cross Entropy, Genetic Algorithm, Combinatorial Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

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