Minimizing Makespan in Scheduling Jobs with Sequence Dependent Setup Times

In this work, we study the problem of machine scheduling n jobs with setups. This means that the execution of each job operation consists of two phases: the setup phase and the processing phase. In particular, we suppose that setups are sequence dependent, that is the setup time of a job operation on a given machine is dependent on that job and on the job processed immediately before it. Obviously, for each job operation, the processing phase can start only after the completion of the setup phase. We consider two machine environments: the single machine, and the no-wait flow shop environments with m machines. In particular, in the latter case, each job requires to process a chain of m operations in m dedicated machines, that is the h-th operation of each job has to be executed in the h-th machine. In the flow shop environment, we assume that for each job, a single processing phase can be performed at a time, while the setup phases of its operations can overlap, and can also be performed simultaneously with an operation processing phase of that job. Moreover, each machine can execute a setup phase or a processing phase of an operation at a time, without interruption. The no-wait constraint forces the processing phases of each job to be executed from start to finish without interruptions either on or between machines; this occurs, for example, in a production process where there is no intermediate buffer between machines. Moreover, we analyze the case in which for each job a ready time is given. The objective is to find a schedule of the jobs minimizing the maximum job completion time (i.e., the makespan). We show that in both cases the problem can be formulated as a special case of the asymmetric traveling salesman problem with additional visiting time constraints. For this latter problem we give a mathematical formulation and lower bounds. As the problem is NP-hard, large practical problem instances require heuristic approaches to be solved. 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.