The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times

In this paper, we consider scheduling problems on a single machine in a sequence dependent setup environment. For these problems, we introduce several integer programming formulations of varying size and strength. Computational experiments conducted on instances of 1|sij|∑Cj1|sij|∑Cj (i.e. minimizing total flow time on a single machine under sequence dependent setup times) and 1|sij|∑Tj1|sij|∑Tj (i.e. minimizing 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|sij|∑Cj1|sij|∑Cj and 1|sij|∑Tj1|sij|∑Tj having up to 50 and 45 jobs respectively.