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.
Liangchi Zhang, Chunliang Zhang and Zichen Chen
M. H. Liu et al., "Genetic Algorithm Based on Simulation for Single Machine Scheduling Problem with Setup Times", Advanced Materials Research, Vols. 328-330, pp. 404-407, 2011