The two-machine sequence dependent flowshop scheduling problem (Q1081528)

This paper considers the static two-machine flowshop scheduling problem where the setup times of jobs depend on immediately preceding jobs and shows that the problem is NP-complete. It is shown that permutation schedules for this problem do not always minimize makespan. Conditions are specified which will prove the optimality of a permutation schedule. Four efficient approximate algorithms are proposed to find approximate schedules for the problem and are empirically evaluated to assess their effectiveness in finding a minimum makespan permutation schedule.