Parallel machine scheduling with job assignment restrictions
Celia A. Glass and
Hans Kellerer
Naval Research Logistics (NRL), 2007, vol. 54, issue 3, 250-257
Abstract:
In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to $2-{1 \over 1+\lambda}$ . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)
Downloads: (external link)
https://doi.org/10.1002/nav.20202
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:wly:navres:v:54:y:2007:i:3:p:250-257
Access Statistics for this article
More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().