کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427771 | 686555 | 2011 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times](/preview/png/427771.png)
We consider the on-line version of the single machine unbounded parallel-batching scheduling with delivery times of jobs. Each jobʼs information, such as processing time pjpj and delivery time qjqj, is not known in advance and becomes known at its arrival time. Once the processing of a job is completed, we deliver it to the destination. Here, the time is continuous. The objective is to minimize the time by which all jobs have been delivered. In this paper, we consider job system with large delivery times, i.e., qj⩾pjqj⩾pj, for each job JjJj. We provide an on-line algorithm with a competitive ratio (5+1)/2≈1.618 and show that any on-line algorithm has a competitive ratio of at least (3+1)/2≈1.366.
► On-line scheduling on a batch machine with large delivery times is considered.
► Any on-line algorithm for this problem has a competitive ratio of at least 3+12.
► An on-line algorithm with a competitive ratio 5+12 is provided.
Journal: Information Processing Letters - Volume 111, Issues 21–22, 15 November 2011, Pages 1048–1053