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 -> M-2, M-2, p(ij)(A)=p, no- wait | CmaxA: CmaxB <= Q: Given a set of n jobs J={J(1),J(2), . . . ,J(n)} and two competing agents A and B. Agent A is associated with a set of nA jobs JA={J(1)A,J(2)A, . . . ,J(n)(A)A} to be processed on the machine M-1 first and then on the machine M-2 with no-wait constraint, and agent B is associated with a set of n(B) jobs J(B)={J(1)B,J(2)B, . . . ,J(nB)(B)} to be processed on the machine M-2 only, where the processing times for the jobs of agent A are all the same (i.e., p(ij)A=p), J=J(A)boolean OR J(B) and 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(nlog n)-time (1+1/n(A)+1)-approximation algorithm and show that this ratio of (1+1/n(A)+1) is asymptotically tight. Finally, (1+epsilon)-approximation algorithms are provided.