We consider single machine scheduling problems in the context of adversarial bilevel optimization where two agents, the leader and the follower, take decisions on the same jobset and the leader acts first with the aim of inducing the worst possible solution for the follower. Thus, the follower schedules the jobs in order to optimize a given criterion. The considered criteria are the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We focus on adversarial bilevel scheduling with job selection and data modification. In the case with job selection, the leader selects a fixed cardinality subset of the jobs that the follower schedules next. In the case with data modification, the leader can modify some of the data (processing times, due dates, weights), given a limited budget Q. Thus, the follower schedules the set of jobs with modified data. For all the considered criteria either we provide polynomial-time algorithms or show that they can be solved in the worst-case in pseudo-polynomial time.

Single machine adversarial bilevel scheduling problems / T'Kindt, Vincent; DELLA CROCE DI DOJOLA, Federico; Agnetis, Alessandro. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 315:1(2024), pp. 63-72. [10.1016/j.ejor.2023.11.018]

Single machine adversarial bilevel scheduling problems

Vincent T'kindt;Federico Della Croce;Alessandro Agnetis
2024

Abstract

We consider single machine scheduling problems in the context of adversarial bilevel optimization where two agents, the leader and the follower, take decisions on the same jobset and the leader acts first with the aim of inducing the worst possible solution for the follower. Thus, the follower schedules the jobs in order to optimize a given criterion. The considered criteria are the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We focus on adversarial bilevel scheduling with job selection and data modification. In the case with job selection, the leader selects a fixed cardinality subset of the jobs that the follower schedules next. In the case with data modification, the leader can modify some of the data (processing times, due dates, weights), given a limited budget Q. Thus, the follower schedules the set of jobs with modified data. For all the considered criteria either we provide polynomial-time algorithms or show that they can be solved in the worst-case in pseudo-polynomial time.
File in questo prodotto:
File Dimensione Formato  
TkindtDellaCroceAgnetis.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Pubblico - Tutti i diritti riservati
Dimensione 528.58 kB
Formato Adobe PDF
528.58 kB Adobe PDF Visualizza/Apri
1-s2.0-S0377221723008597-main.pdf

accesso riservato

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 648.58 kB
Formato Adobe PDF
648.58 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2990362