Flow Shop No-Wait Scheduling with Sequence Dependent Setup Times and Release Dates

We consider the problem of scheduling no-wait jobs, with release dates and sequence dependent setup times, on a flow shop to minimize the makespan. We show that this problem is equivalent to the asymmetric traveling salesman problem with additional visiting time constraints. For this latter problem we give a mathematical formulation and two lower bounds. Two heuristic algorithms for solving the scheduling problem are proposed. Performance analysis of both lower bounds and heuristics on randomly generated test problems are carried out.