Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization

Arthur Kramer*, Manuel Iori*, and Philippe Lacomme**

*DISMI, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy.

**ISIMA, University of Clermont-Auvergne, 63178 Aubičre, France.


This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature.

Key words

Scheduling, mathematical formulations, parallel machines, family setup times, weighted completion times.


To download the instances click here.

To download the detailed results click here.