A Cross Entropy-Genetic Algorithm for m-Machines No-Wait Job-ShopScheduling Problem

作     者：Budi Santosa Muhammad Arif Budiman Stefanus Eko Wiratno 

作者机构：不详 

出 版 物：《Journal of Intelligent Learning Systems and Applications》 (智能学习系统与应用（英文）)

年 卷 期：2011年第3卷第3期

页      面：171-180页

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 081101[工学-控制理论与控制工程] 0811[工学-控制科学与工程] 071102[理学-系统分析与集成] 081103[工学-系统工程] 

主　　题：No-Wait Job Shop Scheduling Cross Entropy Genetic Algorithm Combinatorial Optimization 

摘      要：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.