A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty

François Clautiaux (), Boris Detienne () and Henri Lefebvre ()
Additional contact information
François Clautiaux: Université de Bordeaux,IMB UMR CNRS 5251
Boris Detienne: Université de Bordeaux,IMB UMR CNRS 5251
Henri Lefebvre: Università di Bologna

Journal of Scheduling, 2023, vol. 26, issue 2, No 4, 169-191

Abstract: Abstract Minimizing the weighted number of tardy jobs on one machine 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 the jobs to be performed, and before sequencing them on the machine. This assumption allows diverse recourse decisions to be taken in order to better adapt one’s mid-term 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 deterministic case. 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 the finite adaptability (Bertsimas and Caramanis in IEEE Trans Autom Control 55(12):2751–2766, 2010) and a convexification-based approach (Arslan and Detienne in INFORMS J Comput 34(2):857–871, 2022). We also study the additional cost of the solutions if the sequence of jobs has to be determined before the uncertainty is revealed. Computational experiments are reported to analyze the effectiveness of our approaches.

Keywords: One-machine scheduling; Robust optimization; Two-stage optimization; Mixed-integer recourse; Exact approach; Integer programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00775-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00775-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00775-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().