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

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.