Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-9978
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
Language Code: en
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.
URI: https://depositonce.tu-berlin.de/handle/11303/11089
http://dx.doi.org/10.14279/depositonce-9978
Issue Date: 29-Nov-2019
Date Available: 7-May-2020
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): multiprocessor scheduling
availability constraints
fixed jobs
uniform processors
worst-case approximation
nonsimultaneous machines
makespan
maximum completion time
unavailability
Sponsor/Funder: TU Berlin, Open-Access-Mittel - 2020
License: https://creativecommons.org/licenses/by/3.0/
Book Title: Scheduling Problems - New Applications and Trends
Editor: Da Rosa Righi, Rodrigo
Publisher: InTech
Publisher Place: IntechOpen
Publisher DOI: 10.5772/intechopen.89694
Series: London
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
grigoriu_liliana_2019.pdf
Format: Adobe PDF | Size: 283.29 kB
DownloadShow Preview
Thumbnail

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons