Jointly with François Clautiaux, Boris Detienne

Year: 2022

Abstract: Minimizing the weighted number of tardy jobs is a classical and intensively studied scheduling problem. In this paper, we develop a two-stage robust approach, where exact weights are known after accepting to perform the jobs, and before sequencing them on the machine. This assumption allows diverse recourse decisions to be taken in order to better adapt one's tactical plan. The contribution of this paper is twofold: first, we introduce a new scheduling problem and model it as a min-max-min optimization problem with mixed-integer recourse by extending existing models proposed for the classical problem where all the costs are assumed to be known. Second, we take advantage of the special structure of the problem to propose two solution approaches based on results from the recent robust optimization literature, namely finite adaptability (Bertsimas and Caramanis, 2010) and a convexification-based approach (Arslan and Detienne, 2020). We also study the cost of finding anchored solutions, where the sequence of jobs has to be decided before the uncertainty is revealed. Computational experiments to analyze the effectiveness of our approaches are reported.

Cite as:

@article{Clautiaux2023,
  title = {A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty},
  volume = {26},
  ISSN = {1099-1425},
  DOI = {10.1007/s10951-022-00775-1},
  number = {2},
  journal = {Journal of Scheduling},
  publisher = {Springer Science and Business Media LLC},
  author = {Clautiaux,  Fran\c{c}ois and Detienne,  Boris and Lefebvre,  Henri},
  year = {2023},
  X_month = feb,
  pages = {169--191}
}

Open Access

HAL science ouverte

Open Data

We have public instances (instances.zip) and open raw experimental results (results.csv).
The columns in results.csv are explained in the public rmarkdown (see open methodology) while the instances are given in the following format:

• One line with the number of jobs: \( |\mathcal J| \) ;
• One line per job \(j\in\mathcal J\), with: \(w_j, r_j, d_j, p_j, \tau_j, \delta_j, f_j\).

The input data is separated by tabs or space.
instances.zip results.csv

Open Methodology

You can find our R reports here.

Open Source

Unfortunately, we are not able to provide an open source implementation of our appoach. However, it can be implemented using the now open-source library BaPCod or use the idol C++ framework. At the time we published the paper, BaPCode was not open source and we were not allowed to share it.

Open Educational Resources

-