A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

✍ Scribed by Gerhard J. Woeginger

• Publisher: Springer US
• Year: 1998
• Tongue: English
• Weight: 100 KB
• Volume: 1
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/(sici)1099-1425(199808)1:2<79::aid-jos7>3.0.co;2-o

✦ Synopsis

We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of the job next to come and hence is sequence independent. The objective to to find a sequence of jobs that minimizes the time by which all jobs are delivered. The best polynomial-time approximation algorithm that was previously known for this problem is due to Zdrza"ka and has a worst-case guarantee of . In this paper, we demonstrate the existence of a polynomial time approximation scheme for the problem.