Permutation flowshop scheduling with time lag constraints and makespan criterion

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(n2m), 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.