Algorithms for a two-machine no-wait flow shop scheduling problem with two competing agents

Qi-Xia Yang, Long-Cheng Liu (), Min Huang and Tian-Run Wang
Additional contact information
Qi-Xia Yang: Xiamen University
Long-Cheng Liu: Xiamen University
Min Huang: Xiamen University
Tian-Run Wang: Xiamen University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 1, No 6, 17 pages

Abstract: Abstract In this paper, we consider the following two-machine no-wait flow shop scheduling problem with two competing agents $$F2~|~M_1\rightarrow M_2,~ M_2,~ p_{ij}^{A} = p,~ no\text{- }wait~|~C_{\max }^A:~ C_{\max }^B~\le Q $$ F 2 | M 1 → M 2 , M 2 , p ij A = p , n o - w a i t | C max A : C max B ≤ Q : Given a set of n jobs $$\mathcal {J} = \{ J_1, J_2, \ldots , J_n\}$$ J = { J 1 , J 2 , … , J n } and two competing agents A and B. Agent A is associated with a set of $$n_A$$ n A jobs $$\mathcal {J}^A = \{J_1^A, J_2^A, \ldots , J_{n_A}^A\}$$ J A = { J 1 A , J 2 A , … , J n A A } to be processed on the machine $$M_1$$ M 1 first and then on the machine $$M_2$$ M 2 with no-wait constraint, and agent B is associated with a set of $$n_B$$ n B jobs $$\mathcal {J}^B = \{J_1^B, J_2^B, \ldots , J_{n_B}^B\}$$ J B = { J 1 B , J 2 B , … , J n B B } to be processed on the machine $$M_2$$ M 2 only, where the processing times for the jobs of agent A are all the same (i.e., $$p_{ij}^A = p$$ p ij A = p ), $$\mathcal {J} = \mathcal {J}^A \cup \mathcal {J}^B$$ J = J A ∪ J B and $$n = n_A + n_B$$ n = n A + n B . The objective is to build a schedule $$\pi $$ π of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an $$O(n \log n)$$ O ( n log n ) -time $$(1 + \frac{1}{n_A +1})$$ ( 1 + 1 n A + 1 ) -approximation algorithm and show that this ratio of $$(1 + \frac{1}{n_A +1})$$ ( 1 + 1 n A + 1 ) is asymptotically tight. Finally, $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithms are provided.

Keywords: Scheduling with two agents; No-wait flow shop; Optimal algorithm; Approximation algorithm; Makespan (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01198-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:1:d:10.1007_s10878-024-01198-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01198-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().