Flow shop no-wait scheduling with sequence dependeent 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 algo rithms for solving the scheduling problem are proposed. Performance analysi s of both lower bounds and heuristics on randomly generated test problems a re carried out.