Constraint Programming and Simulated Annealing Approaches for Parallel-Machine Scheduling with Conflict Constraints, Server Setups, and Flexible Maintenance

Abstract

This paper addresses a parallel-machine scheduling problem where jobs require setups performed by a single server and must respect conflict constraints that prevent certain jobs from running simultaneously. This type of problem can find applications in logistics and transport operations, particularly when scheduling vehicle fleets that share limited resources. The server is also subject to a fixed-duration maintenance activity that must be scheduled alongside the jobs. The objective is to minimize the makespan. We develop both constraint programming and simulated annealing approaches to solve this problem. Experimental results demonstrate that the constraint programming model, executed on the Minizinc solver, successfully obtains optimal solutions for small instances with 10 jobs. For larger problems with 15 jobs, simulated annealing is a good alternative since it allows to obtain solutions at 2.3\% of the optimum on average despite a fixed calculation time of 10 seconds.