Multiprocessor Scheduling with Availability Constraints

Liliana Grigoriu ()
Additional contact information
Liliana Grigoriu: University Siegen

A chapter in Operations Research Proceedings 2012, 2014, pp 423-428 from Springer

Abstract: Abstract When scheduling on parallel machines, these may exhibit periods of unavailability, due to maintenance or failures, or due to jobs that must be executed at certain predefined times. We consider the problem of non-preemptively scheduling a given set of tasks on identical processors with periods of unavailability to minimize the maximum completion time. This problem is strongly NP-hard, thus polynomial approximation algorithms are being studied for its solution. Often considered approximation algorithms for multiprocessor scheduling and generalizations thereof are LPT (largest processing time first) and Multifit with their variants. We give a simple polynomial Multifit-based algorithm, the schedules of which end within 1.5 the maximum between the end of the optimal schedule and the latest end of a downtime when there are at most two downtimes on each machine. Even when there is at most one downtime on each machine, no polynomial algorithm can insure a better worst-case bound for this problem unless P=NP. For the case when there is at most one downtime on each machine we also present a simple LPT-based algorithm which has the same property. We also give details of the upper bound proofs.

Keywords: Multiprocessor Scheduling; Bound Proof; Maximum Completion Time; Optimal Schedule; Downtime (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-00795-3_63

Ordering information: This item can be ordered from
http://www.springer.com/9783319007953

DOI: 10.1007/978-3-319-00795-3_63

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().