Open Research Index

Solution of a bilevel optimistic scheduling problem on parallel machines

Quentin Schau, Olivier Ploton, Vincent T'kindt, Han Hoogeveen, Federico Della Croce, Jippe Hoogeveen

arXivarxiv/2603.05107Mar 5, 2026math.OCscore 0

We consider the uniform parallel machines scheduling problem in the context of optimistic bilevel optimization, where two speed options are considered. In this scenario, the leader aims to minimize the weighted number of tardy jobs, while the follower seeks to minimize the total completion time on a set of uniform machines. This problem has practical applications in Industry 4.0. We show that this problem is NP-hard in the strong sense by providing a reduction from the Numerical 3-Dimensional Matching problem and we provide a moderately exponential-time dynamic programming algorithm. The…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2603.05107
curl -X POST /api/v1/records/arxiv/2603.05107/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.05107/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'