کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
468758 | 698251 | 2011 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On-line machine covering on two machines with local migration On-line machine covering on two machines with local migration](/preview/png/468758.png)
We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor ββ times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with β=1β=1. Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine ii, only the jobs on machine ii are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration.
Journal: Computers & Mathematics with Applications - Volume 62, Issue 5, September 2011, Pages 2336–2341