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 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 J = { J 1 , J 2 , … , J n } and two competing agents A and B. Agent A is associated with a set of n A jobs J A = { 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 n B 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 ∪ J B and n = n A + n B . The objective is to build a schedule π 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) -time (1 + 1 n A + 1) -approximation algorithm and show that this ratio of (1 + 1 n A + 1) is asymptotically tight. Finally, (1 + ϵ) -approximation algorithms are provided. [ABSTRACT FROM AUTHOR]