A Parallel Machine Scheduling Problem with Release Dates, Equal Processing Times, and Eligibility Constraints

Abstract

We consider a problem of scheduling independent jobs on parallel machines to minimize the total completion time. Each job has a given release date and a set of eligible machines, and all jobs have equal processing times. For the problem with a fixed number of machines, we show its computational complexity of the problem by providing a polynomial time dynamic programming algorithm. For the problem with an arbitrary number of machines, we propose approximation algorithms and they are evaluated by worst-case analysis and numerical experiments.