کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482083 | 1446124 | 2010 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Parallel machine scheduling with nested processing set restrictions Parallel machine scheduling with nested processing set restrictions](/preview/png/482083.png)
We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes ajaj and bjbj; i.e., job j can only be scheduled on machines aj,aj+1,…,bjaj,aj+1,…,bj. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2-1/m2-1/m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively.
Journal: European Journal of Operational Research - Volume 204, Issue 2, 16 July 2010, Pages 229–236