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 | 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
non disponibili
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.
https://hdl.handle.net/11583/2990362