.png){kind=icon}
.png){kind=icon}
Return
Single machine adversarial bilevel scheduling problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2023.11.018.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Scheduling
Single machine
Bilevel optimization
Complexity results
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
View more organizations