Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions

Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions

0.00 Avg rating0 Votes
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: ,
Keywords: combinatorial optimization, heuristics
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(n2+mnlogn) time. We also extend our results to the tree‐hierarchical processing sets case and the uniform machine case.

Reviews

Required fields are marked *. Your email address will not be published.