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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

137 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)603-609
Number of pages7
JournalEuropean Journal of Operational Research
Volume188
Issue number2
DOIs
Publication statusPublished - 16 Jul 2008

Keywords

  • Fixed jobs
  • Multi-agent
  • Scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this