Abstract
We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds.
Original language | English (US) |
---|---|
Pages (from-to) | 3947-3955 |
Number of pages | 9 |
Journal | Theoretical Computer Science |
Volume | 411 |
Issue number | 44-46 |
DOIs | |
State | Published - Oct 25 2010 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science
Keywords
- Inclusive processing set
- Makespan minimization
- NP-hard
- Nested processing set
- Nonpreemptive scheduling
- Polynomial-time approximation algorithm
- Tree-hierarchical processing set