×

A market-based multi-agent system model for decentralized multi-project scheduling. (English) Zbl 1144.90377

Summary: We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

PSPLIB; MPSPLib
PDFBibTeX XMLCite
Full Text: DOI

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. and F. Rossi. (2000). ”Optimal Resource Assignment Through Negotiation in a Multi-agent Manufacturing System.” IIE Transactions, 32, 963–974.
[3] Brucker, P., A. Drexl, R. Moehring, K. Neumann, and E. Pesch. (1999). ”Resource-Constrained Project Scheduling: Notation, Classification, Models and Methods.” European Journal of Operational Research, 112, 3–41. · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5
[4] Jennings, N.R. and M. Wooldridge. (1995). ”Applying Agent Technology.” Applied Artificial Intelligence, 9, 357–369. · Zbl 05386872 · doi:10.1080/08839519508945480
[5] Klemperer, P. (1999). ”Auction Theory: A Guide to the Literature.” Journal of Economic Surveys, 13, 227–286. · doi:10.1111/1467-6419.00083
[6] Knotts, G., M. Dror, and B.C. Hartman. (2000). ”Agent-Based Project Scheduling.” IIE Transactions, 32, 387–401.
[7] Kolisch, R. (1996). ”Serial and Parallel Resource-Constrained Project Scheduling Methods Revisited: Theory and Computation.” European Journal of Operational Research, 90, 320–333. · Zbl 0916.90151 · doi:10.1016/0377-2217(95)00357-6
[8] Kolisch R. and A. Sprecher. (1996). ”PSPLIB-A Project Scheduling Library.” European Journal of Operational Research, 96, 205–216. · Zbl 0947.90587
[9] Kubiak, W., J. Bla\.zewicz, P. Formanowicz, J. Breit, and G. Schmidt. (2002). ”Two-Machine Flow Shops with Limited Machine Availability.” European Journal of Operational Research, 136, 528–540. · Zbl 1007.90026
[10] Lova, A. and P. Tormos. (2001). ”Analysis of Scheduling Schemes and Heuristic Rules Performance in Resource-Constrained Multiproject Scheduling.” Annals of Operations Research 102, 263–286. · Zbl 0990.90511 · doi:10.1023/A:1010966401888
[11] Lee, Y.-H., S.R. Kumara, and K. Chatterjee. (2003). ”Multiagent Based Dynamic Resource Scheduling for Distributed Multiple Projects Using a Market Mechanism.” Journal of Intelligent Manufacturing, 14, 471–484. · doi:10.1023/A:1025753309346
[12] McAfee, R.P. and J. McMillan. (1987). ”Auctions and Bidding.” Journal of Economic Literature, 25, 699–738. · Zbl 0624.90003
[13] Parkes, D.C. (1999). ”iBundle: An Efficient Ascending Price Bundle Auction.” In Proc. of first ACM Conference on Electronic Commerce, pp. 148–157.
[14] Rothkopf, M.H., A. Pereč, and R.M. Harstad. (1998). ”Computationally Manageable Combinatorial Auctions.” Management Science, 44, 1131–1147. · Zbl 0989.90094 · doi:10.1287/mnsc.44.8.1131
[15] Sandholm, T. (2000). ”Approaches to Winner Determination in Combinatorial Auctions.” Elsevier Decision Support System, 28, 165–176. · Zbl 01938590 · doi:10.1016/S0167-9236(99)00066-4
[16] Sandholm, T. and S. Suri. (2000). ”Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations.” In Proc. of National Conference on Artificial Intelligence, pp. 90–97.
[17] Sandholm, T., S. Suri, A. Gilpin, and D. Levine. (2002). ”Winner Determination in Combinatorial Auction Generalizations.” In Proc. of the First International Conference on Autonomous Agents and Multi-Agent Systems. · Zbl 1232.91329
[18] Wellman, M.P., W.E. Walsh, P.R. Wurman, and J.K. MacKie-Mason. (2001). ”Auction Protocols for Decentralized Scheduling.” Games and Economic Behavior, 35, 271–303. · Zbl 0996.90047 · doi:10.1006/game.2000.0822
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.