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.
- equal processing time jobs
- inclusive processing sets
- parallel machines
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research