×

Multi-agent single machine scheduling. (English) Zbl 1144.90375

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agnetis, A., P.B. Mirchandani, D. Pacciarelli, and A. Pacifici. (2004). ”Scheduling Problems with Two Competing Agents.” Operations Research, 52(2), 229–242. · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[2] Arbib, C., S. Smriglio, and M. Servilio. (2004). ”A Competitive Scheduling Problem and its Relevance to UMTS Channel Assignment.” Networks, 44(2), 132–141. · Zbl 1055.90031 · doi:10.1002/net.20023
[3] Baker, K.R. J.C. Smith. (2003). ”A Multiple-Criterion Model for Machine Scheduling.” Journal of Scheduling, 6(1), 7–16. · Zbl 1154.90406 · doi:10.1023/A:1022231419049
[4] 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. · doi:10.1016/0167-7187(96)01014-4
[5] 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.
[6] Conway, R.W., W.L. Maxwell, and L.W. Miller. (1967). Theory of Scheduling. Reading, MA: Addison Wesley. · Zbl 1058.90500
[7] 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.
[8] 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.
[9] Lawler, E.L. (1973). ”Optimal Sequencing of a Single Machine Subject to Precedence Constraints.” Management Science, 19, 544–546. · Zbl 0254.90039 · doi:10.1287/mnsc.19.5.544
[10] Moore, J.M. (1968). ”An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs.” Management Science, 15, 102–109. · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[11] Osborne, M.J. and A. Rubinstein. (1994). A Course in Game Theory. Cambridge: MIT Press. · Zbl 1194.91003
[12] T’kindt, V. and J.C. Billaut. (2002). Multicriteria Scheduling. Berlin: Springer-Verlag.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.