Back to Search
Start Over
Two-agent scheduling in a two-machine open shop.
- Source :
-
Annals of Operations Research . Feb2024, Vol. 333 Issue 1, p275-301. 27p. - Publication Year :
- 2024
-
Abstract
- This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02545330
- Volume :
- 333
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Annals of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 175254717
- Full Text :
- https://doi.org/10.1007/s10479-023-05780-x