Treffer: Parallel-batching scheduling with two agents, release dates and equal processing times.

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 be $ \mathcal {NP} $ NP -hard. In the Pareto version under this scenario, we design a pseudo-polynomial-time algorithm and a $ (1, 1+\epsilon) $ (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. [ABSTRACT FROM AUTHOR]

Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Volltext ist im Gastzugang nicht verfügbar. Login für vollen Zugriff.