Article ID: | iaor201525429 |
Volume: | 66 |
Issue: | 3 |
Start Page Number: | 516 |
End Page Number: | 523 |
Publication Date: | Mar 2015 |
Journal: | Journal of the Operational Research Society |
Authors: | Li Chung-Lun, Li Qingying |
Keywords: | combinatorial optimization, heuristics |
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(n2+mnlogn) time. We also extend our results to the tree‐hierarchical processing sets case and the uniform machine case.