Permutation flowshop scheduling with time lag constraints and makespan criterion. (June 2018)

• Record Type: Journal Article
• Authors: Wang, Bailin; Huang, Kai; Li, Tieke
• Is Part Of: Computers & industrial engineering. Volume 120(2018)
• Page Start: 1
• Page End: 14
• Publication Date: 2018-06
• Subjects: Scheduling -- Permutation flowshop -- Time lags -- Constructive heuristic -- Reversibility; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.04.021
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Prove that the proposed scheduling problem has the reversibility property. Effectively construct an initial solution based on a transformation of the makespan. Present an insertion mechanism for solution construction. Use the reversibility property to improve time complexity and solution quality. Abstract: A permutation flowshop with time lag constraints requires that the time lag between consecutive operations of a job must be in the given interval. In this study, the scheduling of such flowshop with makespan minimization objective is investigated. We prove that this problem has the reversibility property, and present a two-stage constructive heuristic with time complexity O( n 2 m ), where n and m are the numbers of jobs and machines, respectively. The first stage generates a rank of jobs based on an equivalent formulation of the makespan, and the second stage constructs a schedule through an insertion mechanism. We apply the reversibility property to reduce the time complexity of insertion procedures in both two stages, and find a better solution by solving both the original problem and its reversed problem. To verify the effectiveness and efficiency of this heuristic, we compare its performance to the mixed integer linear programming (MILP) formulation of this problem for small-scale problems, and conduct a comprehensive computational study on the Taillard's benchmark.