Scheduling with processing set restrictions: PTAS results for several variants |
| |
Authors: | Leah Epstein Asaf Levin |
| |
Institution: | a Department of Mathematics, University of Haifa, 31905 Haifa, Israel b Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |
|