Multi-agent scheduling on a single machine with max-form criteria |
| |
Authors: | T.C.E. Cheng C.T. Ng J.J. Yuan |
| |
Affiliation: | 1. Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People’s Republic of China;2. Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People’s Republic of China |
| |
Abstract: | We consider multi-agent scheduling on a single machine, where the objective functions of the agents are of the max-form. For the feasibility model, we show that the problem can be solved in polynomial time even when the jobs are subject to precedence restrictions. For the minimality model, we show that the problem is strongly NP-hard in general, but can be solved in pseudo-polynomial-time when the number of agents is a given constant. We then identify some special cases of the minimality model that can be solved in polynomial-time. |
| |
Keywords: | Scheduling Multi-agent Fixed jobs |
本文献已被 ScienceDirect 等数据库收录! |
|