Scheduling with processing set restrictions: PTAS results for several variants

Leah Epstein and Asaf Levin

International Journal of Production Economics, 2011, vol. 133, issue 2, 586-595

Abstract: 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).

Keywords: Scheduling; Approximation; scheme (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S092552731100199X
Full text for ScienceDirect subscribers only

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:eee:proeco:v:133:y:2011:i:2:p:586-595

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().