# Constraint Programming and Constructive Heuristics for Parallel Machine Scheduling with Sequence-Dependent Setups and Common Servers

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2023.

## Built on by (most cited first, 3 of 3)

- [Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks](https://mlsanity.com/paper/2508.20056/) (2025)
- [Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach](https://mlsanity.com/paper/2601.06542/) (2026)
- [Integrated packing, placement, scheduling, and routing of personalized production: a pharmaceutical Industry 4.0 use-case with a planar transport system](https://mlsanity.com/paper/2604.21029/) (2026)

## Abstract (arXiv)

This paper examines scheduling problem denoted as P|seq, ser|Cmax in Graham's notation; in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by one of the available servers (ser). The goal is to minimize the makespan (Cmax). We propose a Constraint Programming (CP) model for finding the optimal solution and constructive heuristics suitable for large problem instances. These heuristics are also used to provide a feasible starting solution to the proposed CP model, significantly improving its efficiency. This combined approach constructs solutions for benchmark instances of up to 20 machines and 500 tasks in 10 seconds, with makespans 3-11.5% greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.