Decision-Diagrams-for-Single-Machine-Scheduling

Author: Mathijs de Weerdt, Robert Baart, Lei He, Delft University of Technology

Single-machine scheduling where jobs have a penalty for being late or for being rejected altogether is an important (sub)problem in manufacturing, logistics, and satellite scheduling. It is known to be NP-hard in the strong sense, and there is no polynomial-time algorithm that can guarantee a constant-factor approximation (unless P=NP). We provide an exact algorithm that is fixed-parameter tractable (FPT) in the slack and the maximum number of time windows overlapping at any point in time, i.e., the width. This algorithm has a runtime exponential in these parameters, but quadratic in the number of jobs, even when modeling sequence-dependent setup times. Moreover, we give a fully-polynomial time approximation scheme (FPTAS) that is FPT with only this width as a parameter, having a runtime bound that is cubic. Finally, we propose a neighbourhood heuristic similar to the Balas-Simonetti neighbourhood. All algorithms use an efficient representation of the state space inspired by decision diagrams, where partial solutions that are provably dominated are excluded from further consideration.

Introduction

The repository contains the order acceptance and scheduling (OAS) datasets provided by Oğuz et al. (2010) and two new datasets with bounded width and correlated processing time and value, which are generated by us. It also contains the source code for the exact method (EM.py), the FPTAS (FPTAS.py) and the Balas-Simonetti neighbourhood method (Balas.py). Finally, the optimal solutions for some instances are also provided.

If you use these code or data, please cite the following paper: Mathijs de Weerdt, Robert Baart, Lei He (2021), Single-machine scheduling with release times, deadlines, setup times, and rejection, In European Journal of Operational Research Volume 291 p.629-639.

All results from the paper are generated with the Solver(). EM.py also includes a more direct Dynamic Programming implementation. The variant without making the triangle inequality assumption on sequence-dependent setup times is the correct one for all instances. Unfortunately, the paper includes the triangle inequality in Equation 2. The line with X_k should be without the "+ s_kj" to remove the triangle inequality assumption.

References

Oğuz, C., Salman, F. S., & Yalçın, Z. B. (2010). Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics, 125(1), 200–211.

Instructions

First extract the Dataset_OAS to run the provided example instances. Please use Python >= 3.6. The last lines in the EM.py file can be used to define which experiments are run.