Groupe d’études et de recherche en analyse des décisions

# The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling Problems with Sequence Dependent Setup Time

## Louis-Philippe Bigras, Michel Gamache et Gilles Savard

In this paper, we consider scheduling problems on a single machine in a sequence dependent setup environment. We introduce for these problems several integer programming formulations of various size and various strength. Computational experiments conducted on instances of $1| s_{ij}| \sum\ C_j$ (i.e. minimizing the total flow time on a single machine under sequence dependent setup times) and $1| s_{ij}| \sum\ T_j$ (i.e. minimizing the total tardiness on a single machine under sequence dependent setup times) illustrate the benefits of using stronger formulations, even though the computation of their LP relaxation is more time consuming. Incorporating these improved LP relaxation bounds, we propose an exact branch-and-bound algorithm able to solve instances of $1| s_{ij}| \sum\ C_j$ and $1| s_{ij}| \sum\ T_j$ having up to 50 and 45 jobs respectively.

, 30 pages