Approximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periods
| dc.contributor.author | Grigoriu, Liliana | |
| dc.date.accessioned | 2020-05-07T08:22:43Z | |
| dc.date.available | 2020-05-07T08:22:43Z | |
| dc.date.issued | 2019-11-29 | |
| dc.description.abstract | We survey results that address the problem of non-preemptive scheduling on parallel machines with fixed jobs or unavailability periods with the purpose of minimizing the maximum completion time. We consider both identical and uniform processors, and also address the special case of scheduling on nonsimultaneous parallel machines, which may start processing at different times. The discussed results include polynomial-time approximation algorithms that achieve the best possible worst-case approximation bound of 1.5 in the class of polynomial algorithms unless P = NP for scheduling on identical processors with at most one fixed job on each machine and on uniform machines with at most one fixed job on each machine. The presented heuristics have similarities with the LPT algorithm or the MULTIFIT algorithm and they are fast and easy to implement. For scheduling on nonsimultaneous machines, experiments suggest that they would perform well in practice. We also include references to the relevant work in this area that contains more complex algorithms. We then discuss the main methods of argument used in the approximation bound proofs for the simple heuristics, and comment upon current challenges in this area by describing aspects of related practical problems from the automotive industry. | en |
| dc.description.sponsorship | TU Berlin, Open-Access-Mittel - 2020 | en |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/11089 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-9978 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by/3.0/ | en |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
| dc.subject.other | multiprocessor scheduling | en |
| dc.subject.other | availability constraints | en |
| dc.subject.other | fixed jobs | en |
| dc.subject.other | uniform processors | en |
| dc.subject.other | worst-case approximation | en |
| dc.subject.other | nonsimultaneous machines | en |
| dc.subject.other | makespan | en |
| dc.subject.other | maximum completion time | en |
| dc.subject.other | unavailability | en |
| dc.title | Approximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periods | en |
| dc.type | Book Part | en |
| dc.type.version | publishedVersion | en |
| dcterms.bibliographicCitation.booktitle | Scheduling Problems - New Applications and Trends | en |
| dcterms.bibliographicCitation.doi | 10.5772/intechopen.89694 | en |
| dcterms.bibliographicCitation.editor | Da Rosa Righi, Rodrigo | |
| dcterms.bibliographicCitation.originalpublishername | IntechOpen | en |
| dcterms.bibliographicCitation.originalpublisherplace | London | 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 |