Scheduling on same-speed processors with at most one downtime on each machine
| Autor: | Donald K. Friesen, Liliana Grigoriu |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Downtime
Mathematical optimization Makespan LPT Job shop scheduling Computer science Applied Mathematics P versus NP problem Downtimes Worst-case bounds Polynomial algorithm Multiprocessor scheduling Machine shutdowns Scheduling (computing) Theoretical Computer Science Computational Theory and Mathematics Availability constraints Fixed jobs Completion time Shut down |
| Zdroj: | Discrete Optimization. 7(4):212-221 |
| ISSN: | 1572-5286 |
| DOI: | 10.1016/j.disopt.2010.04.003 |
| Popis: | We consider the problem of scheduling a set of independent tasks on multiple same-speed processors with planned shutdown times with the aim of minimizing the makespan. We give an LPT-based algorithm, LPTX, which yields a maximum completion time that is less than or equal to 3/2 the optimal maximum completion time or 3/2 the time that passes from the start of the schedule until the latest end of a downtime. For problems where the optimal schedule ends after the last downtime, and when the downtimes represent fixed jobs, the LPTX maximum completion time is within 3/2 of the optimal maximum completion time. In addition, we show that this result is asymptotically tight for the class of polynomial algorithms assuming that P≠NP. We also show that the bound obtained previously for a similar problem, when no more than half of the machines are shut down at the same time, for the LPT algorithm is asymptotically tight in the class of polynomial algorithms if P≠NP. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect