# Single and Parallel Machine Scheduling with Variable Release Dates

arXiv: https://arxiv.org/abs/2103.01785 · HTML: https://mlsanity.com/paper/2103.01785/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 54 references that are in the map.
- First posted on arXiv 2 Mar 2021.

## Builds on (most cited first, 3 of 3)

- [Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines](https://mlsanity.com/paper/1808.10661/) (2018)
- [A new CP-approach for a parallel machine scheduling problem with time constraints on machine qualifications](https://mlsanity.com/paper/1910.07203/) (2019)
- [Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time](https://mlsanity.com/paper/2005.10097/) (2020)

## Abstract (arXiv)

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.