Scheduling Parallel Jobs to Minimize Makespan
| dc.contributor.author | Johannes, Berit | |
| dc.date.accessioned | 2021-12-17T10:18:27Z | |
| dc.date.available | 2021-12-17T10:18:27Z | |
| dc.date.issued | 2001 | |
| dc.description.abstract | We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a pre-specified, job-dependent number of machines when being processed. Our main result is the following. The makespan of a (non-preemptive) schedule constructed by any listscheduling algorithm is within a factor of 2 of the optimal preemptive makespan. This gives the best known approximation algorithms for both the preemptive and the non-preemptive variant of the problem, improving upon previously known performance guarantees of 3. We also show that no listscheduling algorithm can achieve a better performance guarantee than 2 for the non-preemptive problem, no matter which priority list is chosen. Since listscheduling also works in the online setting in which jobs arrive over time and the length of a job becomes only known when it completes, the main result yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. In this context, no listscheduling algorithm has a constant competitive ratio. We present the first online algorithm for scheduling parallel jobs with a constant competitive ratio. We also prove a new information-theoretic lower bound of 2:25 for the competitive ratio of any deterministic online algorithm for this model. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15972 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14745 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | scheduling | en |
| dc.subject.other | makespan | en |
| dc.subject.other | approximation algorithms | en |
| dc.subject.other | listscheduling | en |
| dc.subject.other | parallel jobs | en |
| dc.subject.other | multiprocessor tasks | en |
| dc.subject.other | online algorithms | en |
| dc.title | Scheduling Parallel Jobs to Minimize Makespan | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2001, 723 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |