Skip to main content
SpringerLink
Log in

Multi-agent single machine scheduling

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agnetis, A., P.B. Mirchandani, D. Pacciarelli, and A. Pacifici. (2004). “Scheduling Problems with Two Competing Agents.” Operations Research, 52(2), 229–242.

    Article  Google Scholar 

  • Arbib, C., S. Smriglio, and M. Servilio. (2004). “A Competitive Scheduling Problem and its Relevance to UMTS Channel Assignment.” Networks, 44(2), 132–141.

    Article  Google Scholar 

  • Baker, K.R. J.C. Smith. (2003). “A Multiple-Criterion Model for Machine Scheduling.” Journal of Scheduling, 6(1), 7–16.

    Article  Google Scholar 

  • Brewer, P.J. and C.R. Plott (1996). “A Binary Conflict Ascending Price (BICAP) Mechanism for the Decentralized Allocation of the Right to Use Railroad Tracks.” International Journal of Industrial Organization, 14, 857–886.

    Article  Google Scholar 

  • Chen, Y., Y. Peng, T. Finin, Y. Labrou, S. Cost, B. Chu, J. Yao’, R. Sun, and B. Wilhelm. (1999). “A Negotiation-Based Multi-Agent System for Supply Chain Management.” In Proc. of the Agents’99 Workshop “Agent-Based Decision-Support for Managing the Internet-Enabled Supply-Chain,” Seattle, WA, pp. 15–20.

  • Conway, R.W., W.L. Maxwell, and L.W. Miller. (1967). Theory of Scheduling. Reading, MA: Addison Wesley.

    Google Scholar 

  • Huang, X. and J.C. Hallam. (1995). “Spring-Based Negotiation for Conflict Resolution in AGV Scheduling.” In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics.

  • Kim, K., B.C. Poulon, C.J. Petrie, and V.R. Lesser. (2000). “Compensatory Negotiation for Agent-Based Project Schedule Coordination.” CIFE Working Paper #55. Stanford University.

  • Lawler, E.L. (1973). “Optimal Sequencing of a Single Machine Subject to Precedence Constraints.” Management Science, 19, 544–546.

    Google Scholar 

  • Moore, J.M. (1968). “An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs.” Management Science, 15, 102–109.

    Article  Google Scholar 

  • Osborne, M.J. and A. Rubinstein. (1994). A Course in Game Theory. Cambridge: MIT Press.

    Google Scholar 

  • T’kindt, V. and J.C. Billaut. (2002). Multicriteria Scheduling. Berlin: Springer-Verlag.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria dell’Informazione, Università di Siena, Via Roma, 56 – 53100, Siena, Italy

    Alessandro Agnetis

  2. Dipartimento di Informatica e Automazione, Università Roma Tre, Roma, Italy

    Dario Pacciarelli

  3. Dipartimento di Ingegneria dell’Impresa and Centro Vito Volterra, Università di Roma “Tor Vergata”, Roma, Italy

    Andrea Pacifici

Authors
  1. Alessandro Agnetis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dario Pacciarelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrea Pacifici
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alessandro Agnetis.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Agnetis, A., Pacciarelli, D. & Pacifici, A. Multi-agent single machine scheduling. Ann Oper Res 150, 3–15 (2007). https://doi.org/10.1007/s10479-006-0164-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-006-0164-y

Keywords

Search

Navigation