This archive is distributed in association with the INFORMS Journal on Computing under the MIT License.
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper A flow-based formulation for parallel machine scheduling using decision diagrams by Daniel Kowalczyk, Roel Leus, Christopher Hojny and Stefan Røpke.
Important: This code is being developed on an on-going basis at https://gitlab.kuleuven.be/u0056096/parallel-machine-bdd . Please go there if you would like to get a more recent version or would like support
To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.
Below is the BibTex for citing this snapshot of the repository.
@article{Kowalczyk2023,
author = {Daniel Kowalczyk, Roel Leus, Christopher Hojny, and Stefan R\o{}pke},
publisher = {INFORMS Journal on Computing},
title = {{A flow-based formulation for parallel machine scheduling
using decision diagrams}},
year = {2023},
doi = {10.1287/ijoc.2022.0301},
url = {https://github.com/INFORMSJoC/2022.0301},
}
We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition in order to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves three instances from the literature for the first time. We compare the new formulation with the time-indexed and arc-time-indexed formulation by means of a series of computational experiments.
In the original repository, the code was built using the CMake build system. You can find the full description of the build process in the Gitlab repository of the authors.
Computation time (in seconds) and number of instances solved at the
root for the LP relaxation of TIF and ATIF
Computation time (in seconds) and number of instances solved at the
root for the LP relaxation of BDDFr and BDDF
Size of the graph for TIF, ATIF, BDDFr , and BDDF
Average and maxium gap from the starting solution for the formulations TIF,
ATIF, BDDFr , and BDDF
Performance profiles over all the instances solved to optimality by both
algorithms. BDDF is the algorithm devised in this paper, while ATIF is the
algorithm devised in this paper by
Oliveira, D. and Pessoa, A.
For a more detailed comparison, we also show the performance profiles for each pair of number of jobs and number of machines. For the sake of brevity, we refer to the paper for the description of the results.
Summary of the results of BDDF with different initial solutions:
This code is being developed on an on-going basis at the author's Gitlab site.
For support in using this software, submit an issue.