Single and Parallel Machine Scheduling with Variable Release Dates
This addresses a practical scheduling extension for operations research, but it is incremental as it builds on the standard flowtime minimization problem.
The paper tackles the problem of scheduling jobs on single and parallel machines where release dates are variable but constrained by a global deadline, showing it is NP-complete even for a single machine and empirically evaluating genetic algorithms, tree search, and constraint programming.
In this paper we study a simple extension of the total weighted flowtime minimization problem for single and identical parallel machines. While the standard problem simply defines a set of jobs with their processing times and weights and assumes that all jobs have release date 0 and have no deadline, we assume that the release date of each job is a decision variable that is only constrained by a single global latest arrival deadline. To our knowledge, this simple yet practically highly relevant extension has never been studied. Our main contribution is that we show the NP- completeness of the problem even for the single machine case and provide an exhaustive empirical study of different typical approaches including genetic algorithms, tree search, and constraint programming.