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 vertical bar s(ij)vertical bar Sigma C-j (i.e. minimizing total flow time on a single machine under sequence dependent setup times) and 1 vertical bar s(ij)vertical bar Sigma T-j (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 vertical bar s(ij)vertical bar Sigma C-j and 1 vertical bar s(ij)vertical bar Sigma T-j having up to 50 and 45 jobs respectively. (c) 2008 Elsevier B.V. All rights reserved.