کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427877 | 686571 | 2011 | 5 صفحه PDF | دانلود رایگان |
We address a variant of scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of 1.781, and show a lower bound of 1.686 for any online algorithm.
► We address a scheduling problem with a speed-up resource to minimize makespan on two identical machines.
► For the offline version, we present an FPTAS.
► For the online version list, we propose an on-line algorithm with competitive ratio of 1.781.
► A lower bound of 1.686 for any online algorithm is shown.
Journal: Information Processing Letters - Volume 111, Issue 17, 15 September 2011, Pages 831–835