MULTIMODAL OPTIMIZATION OF JOB-SHOP SCHEDULING PROBLEMS USING A CLUSTERING-GENETIC ALGORITHM BASED APPROACH - Zou, Pan; Rajora, Manik; Liang, Steven Y (International Journal of Industrial Engineering: Theory, Applications and Practice, 2019)
Though ample work has been done in optimization of job shop scheduling problems (JSSPs), very few techniques can satisfy the requirement of modern day workshop i.e. providing multiple schedules that achieve the desired goal. These techniques also do not provide a good balance between converging to the optimal solution while finding multiple optimal solutions. To overcome this obstacle, a new algorithm is proposed, by combining k-means clustering algorithm and Genetic Algorithm (GA), for the multimodal optimization of JSSPs. In the proposed algorithm, k-means clustering algorithm is first utilized to cluster the individuals of every generation into different clusters, based on some machine sequence related features under the assumption that different global optima will have different features. Next the adapted genetic operators are applied to the individuals belonging within the same cluster with the aim of searching for global optima within each cluster independently. The performance of the proposed algorithm is measured by its application to the multimodal optimization of benchmark JSSPs and comparing its performance against other multimodal optimization algorithms. The results of the case studies show that the algorithm has better average optimal value and is also capable of finding multiple optimal solutions.