Associate Professor Tsung-Che Chiang

Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692    Fax: +886-2-29322378    Email

Tsung-Su Yeh and Tsung-Che Chiang, Domain heuristics for evolutionary scheduling of no-wait flow shops, Proc. of IEEE International Conferences on Cybernetics and Intelligent Systems and IEEE International Conference on Robotics, Automation and Mechatronics (CIS-RAM), pp. 215 - 220, Bangkok, Thailand, Nov. 18-20, 2019.

Full text: Official version

Download problem instances and solutions

Abstract

This paper addresses a multiobjective no-wait flow shop scheduling problem (MO-NWFSP) by a memetic algorithm (MA). The objective is to minimize makespan and maximum tardiness in a Pareto way. In the local search part of MA, we incorporate two domain heuristics into the shaking step and the neighborhood function. Before doing local search to a solution in the population, a tail-shaking operator is applied, in which we tend to move jobs with shorter total processing time to the end. During local search, we tend to adjust the processing orders of jobs whose constituted sub-sequence leads to longer machine idle time. Performance of the proposed heuristics was verified by numerical experiments on self-generated instances based on the well-known Taillard’s data set. Results showed that the proposed heuristics helped to improve solution quality.