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

ABSTRACT

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 -hard. When the number of agents is fixed, pseudo-polynomial time algorithms are first designed to solve them, respectively, then an -approximation algorithm is provided for the former problem, and an -approximate Pareto-optimal frontier is constructed for the latter problem.

KEYWORDS:

• Multi-agent scheduling
• just-in-time jobs
• no-wait flow shop
• approximate pareto-optimal frontier

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [Grant Nos. 11401605, 11501279 and 11701595]; and the Young Backbone Teachers of Henan Colleges [2015GGJS-193].