Two-agent scheduling with time-dependent and position-dependent in a flow-shop system

In this paper, we consider the two-agent scheduling with time-dependent and position-dependent processing time in a two-machine flow-shop system. The objective is to minimize the makespan of agent A under the constraint that the objective of agent B cannot exceed a given upper bound. In the time-dependent processing time model, the constraint is the makespan of agent B. We first show that the problem is NP-hard in the ordinary sense. Then we prove that there exists an optimal schedule which is a permutation schedule, and there exists an optimal schedule in which the adapted version of Johnson’s rule do not hold for neither agent A nor agent B. Furthermore, we show that three special cases are polynomially solvable. In the position-dependent processing time model, if the constraint is the makespan of agent B, we show that the problem is NP-hard in the ordinary sense. If the constraint is the total completion times of agent B and jobs have different release dates, the problem is strongly NP-hard.