کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420654 | 683966 | 2008 | 11 صفحه PDF | دانلود رایگان |
In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time.We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input.In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine.
Journal: Discrete Applied Mathematics - Volume 156, Issue 5, 1 March 2008, Pages 719–729