Approximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periods

dc.contributor.authorGrigoriu, Liliana
dc.date.accessioned2020-05-07T08:22:43Z
dc.date.available2020-05-07T08:22:43Z
dc.date.issued2019-11-29
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.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/11089
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-9978
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/3.0/en
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.othermakespanen
dc.subject.othermaximum completion timeen
dc.subject.otherunavailabilityen
dc.titleApproximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periodsen
dc.typeBook Parten
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.booktitleScheduling Problems - New Applications and Trendsen
dcterms.bibliographicCitation.doi10.5772/intechopen.89694en
dcterms.bibliographicCitation.editorDa Rosa Righi, Rodrigo
dcterms.bibliographicCitation.originalpublishernameIntechOpenen
dcterms.bibliographicCitation.originalpublisherplaceLondonen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
grigoriu_liliana_2019.pdf
Size:
283.29 KB
Format:
Adobe Portable Document Format
Description:
Collections