.png){kind=icon}
.png){kind=icon}
Return
Parallel-batching scheduling with two agents, release dates and equal processing times
.png){kind=icon}
PRE
AI
DOI：10.1080/00207543.2025.2525534.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper investigates a two-agent scheduling problem with release dates and equal processing times on an unbounded parallel-batching machine. Each agent's scheduling criterion is regular and takes either the max-form or the sum-form. We address three variants of the problem. The first variant is the restricted version, which aims to determine a feasible schedule that minimises one agent's criterion while keeping the other agent's objective value not exceeding a specified upper bound. The second variant is the linear-combination version, which seeks to find a feasible schedule that minimises a linear combination of the criteria of both agents. The third variant is the Pareto version, which wants to identify all Pareto-optimal points and generate the corresponding Pareto-optimal schedules. When one agent's criterion is of the max-form, we present polynomial-time algorithms for all three variants. However, when both agents' criteria are of the sum-form, several variants of the problem are shown to beNP-hard. In the Pareto version under this scenario, we design a pseudo-polynomial-time algorithm and a(1,1+ϵ)-approximate Pareto-optimal frontier. For the restricted version, we provide a fully polynomial-time approximation scheme (FPTAS) as well as a super-dual FPTAS.
Keywords:
Two-agent scheduling
parallel-batching
release date
equal processing times
approximation scheme
Journal
IF:
7.3
Papers:
1.1W
Citations:
3.7W