Genetic Algorithm based on Simulation for Single Machine Scheduling Problem with Setup Times

摘要：

Single machine scheduling problem with setup times is proved to be an NP-hard problems, and its complexity is equivalent to the traveling salesman problem (TSP) of n cites. Integrating the advantages of simulation and genetic algorithm (GA), this paper proposes a GA based on simulation to solve this NP-hard problem. Then, it introduces how to build the simulation model and how to design chromosome coding and selection, crossover and mutation operators of GA for this special scheduling problem in details. An experiment has been carried out and the result proves that the method is feasible and should be adopted.

关键词： Single machine scheduling problem Setup times Simulation Genetic algorithm

作者: Meihong LIU Zhenhua LI Junruo CHEN

作者单位: Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology,Kunming 650093, China

会议类型: 国际会议

会议名称: 2011 International Conference on Mechatronics and Materials Processing(2011年机电一体化与材料加工国际会议 ICMMP)

会议地点: 广州

会议语种:英文

页码: 404-407

在线出版日期: 2011-11-18（万方平台首次上网日期，不代表论文的发表时间）