Scheduling with processing set restrictions: PTAS results for several variants
We consider multiprocessor scheduling to minimize makespan. Each job has a given processing time and in addition, a subset of machines associated with it, also called its processing set. Each job has to be assigned to one machine in its set, thus contributing to the load of this machine. We study two variants of this problem on identical machines, the case of nested processing sets, and the case of tree-hierarchical processing sets. In addition, we consider uniformly related machines with a special case of inclusive processing sets, which has a clear motivation. We design polynomial time approximation schemes for these three variants. The first case resolves one of the open problems stated in the survey by Leung and Li (2008).
Year of publication: |
2011
|
---|---|
Authors: | Epstein, Leah ; Levin, Asaf |
Published in: |
International Journal of Production Economics. - Elsevier, ISSN 0925-5273. - Vol. 133.2011, 2, p. 586-595
|
Publisher: |
Elsevier |
Subject: | Scheduling Approximation scheme |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Epstein, Leah, (2011)
-
A unified approach to truthful scheduling on related machines
Epstein, Leah, (2016)
-
Scheduling with processing set restrictions : PTAS results for several variants
Epstein, Leah, (2011)
- More ...