Trajectory Scheduling Methods for minimizing total tardiness in a flowshop

Operations Research Perspectives

Jatinder N.D. Gupta¹  Haiyan Xu²  Long Chen²  Xiaoping Li² 

[1] College of Business Administration, University of Alabama in Huntsville, Huntsville, Al, USA;School of Computer Science and Engineering, Southeast University, Nanjing 211189, China;

关键词: Scheduling;    Heuristic;    Permutation flow shop;    Total tardiness;   

DOI  :  10.1016/j.orp.2014.12.001

来源: DOAJ

【 摘 要 】

In this paper, Trajectory Scheduling Methods (TSMs) are proposed for the permutation flowshop scheduling problem with total tardiness minimization criterion. TSMs belong to an iterative local search framework, in which local search is performed on an initial solution, a perturbation operator is deployed to improve diversification, and a restart point mechanism is used to select the new start point of another cycle. In terms of the insertion and swap neighborhood structures, six composite heuristics are introduced, which exploit the search space with a strong intensification effect. Based on purely insertion-based or swap-based perturbation structures, three compound perturbation structures are developed that construct a candidate restart point set rather than just a single restart point. The distance between the current best solution and each start point of the set is defined, according to which the diversification effect of TSMs can be boosted by choosing the most appropriate restart point for the next iteration. A total of 18 trajectory scheduling methods are constructed by different combinations of composite heuristics. Both the best and worst combinations are compared with three best existing sequential meta-heuristics for the considered problem on 540 benchmark instances. Experimental results show that the proposed heuristics significantly outperform the three best existing algorithms within the same computation time.

【 授权许可】

Unknown