Please use this identifier to cite or link to this item:
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGrigoriu, Liliana-
dc.description.abstractWe 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.sponsorshipTU Berlin, Open-Access-Mittel - 2020en
dc.subject.ddc004 Datenverarbeitung; Informatikde
dc.subject.othermultiprocessor schedulingen
dc.subject.otheravailability constraintsen
dc.subject.otherfixed jobsen
dc.subject.otheruniform processorsen
dc.subject.otherworst-case approximationen
dc.subject.othernonsimultaneous machinesen
dc.subject.othermaximum completion timeen
dc.titleApproximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periodsen
dc.typeBook Parten
tub.publisher.universityorinstitutionTechnische Universität Berlinen
dcterms.bibliographicCitation.editorDa Rosa Righi, Rodrigo-
dcterms.bibliographicCitation.booktitleScheduling Problems - New Applications and Trendsen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 283.29 kB
DownloadShow Preview

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons