Abstract
We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n 2 +mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case. © 2015 Operational Research Society Ltd.
| Original language | English |
|---|---|
| Pages (from-to) | 516-523 |
| Journal | Journal of the Operational Research Society |
| Volume | 66 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 5 Mar 2015 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
This research was supported in part by the Research Grants Council of Hong Kong under grant PolyU5236/09E.
Research Keywords
- equal processing time jobs
- inclusive processing sets
- parallel machines
- Scheduling