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.
| Original language | English |
|---|---|
| Pages (from-to) | 516-523 |
| Number of pages | 8 |
| Journal | Journal of the Operational Research Society |
| Volume | 66 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 5 Mar 2015 |
Keywords
- equal processing time jobs
- inclusive processing sets
- parallel machines
- Scheduling
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research
- Marketing
Fingerprint
Dive into the research topics of 'Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver