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

¹ School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, P.R. China
² Institute of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P.R. China

^* Corresponding author: miaocuixia@126.com

Received: 4 August 2024
Accepted: 10 September 2025

Abstract

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.