Multi-agent scheduling on a single machine with max-form criteria

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 t...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2008-07, Vol.188 (2), p.603-609
Main Authors: Cheng, T.C.E., Ng, C.T., Yuan, J.J.
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Fixed jobs
Multi-agent
Operational research. Management science
Production scheduling
Scheduling
Stochastic models
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2007.04.040