Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs

This article studies a multi-agent scheduling problem on a set of m machines in a no-wait flow shop system, where each agent's objective function is to maximize its own weighted number of just-in-time jobs. Two variants of the problem are investigated. One is the constrained optimization problem and the other is the Pareto optimization problem. When the number of agents is arbitrary, both problems are proved to be strongly NP-hard. When the number of agents is fixed, pseudo-polynomial time algorithms are first designed to solve them, respectively, then an (1,1- epsilon, ... , 1 - epsilon)-approximation algorithm is provided for the former problem, and an (1 - epsilon)-approximate Pareto-optimal frontier is constructed for the latter problem.