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