کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141787 | 957091 | 2008 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times](/preview/png/1141787.png)
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.
Journal: Discrete Optimization - Volume 5, Issue 4, November 2008, Pages 685–699