Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Approximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periods
Author(s): Grigoriu, Liliana
Type: Book Part
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.
Subject(s): multiprocessor scheduling
availability constraints
fixed jobs
uniform processors
worst-case approximation
nonsimultaneous machines
maximum completion time
Issue Date: 29-Nov-2019
Date Available: 7-May-2020
Language Code: en
DDC Class: 004 Datenverarbeitung; Informatik
Sponsor/Funder: TU Berlin, Open-Access-Mittel - 2020
Book Title: Scheduling Problems - New Applications and Trends
Editor: Da Rosa Righi, Rodrigo
Publisher: IntechOpen
Publisher DOI: 10.5772/intechopen.89694
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
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