×

Randomized mechanism design for decentralized network scheduling. (English) Zbl 1455.90081

Summary: In the network scheduling, jobs (tasks) must be scheduled on uniform machines (processors) connected by a complete graph so as to minimize the total weighted completion time. This setting can be applied in distributed multi-processor computing environments and also in operations research. In this paper, we study the design of randomized decentralized mechanism in the setting where a set of non-preemptive jobs select randomly a machine from a set of uniform machines to be processed on, and each machine can process at most one job at a time. We introduce a new concept of myopic Bayes-Nash incentive compatibility which weakens the classical Bayes-Nash incentive compatibility and derive a randomized decentralized mechanism under the assumption that each job is a rational and selfish agent. We show that our mechanism can induce jobs to report truthfully their private information referred to myopic Bayes-Nash implementability by using a graph theoretic interpretation of the incentive compatibility constraints. Furthermore, we prove that the performance of this mechanism is asymptotically optimal.

MSC:

90B36 Stochastic scheduling theory in operations research
90B10 Deterministic network models in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben, D.; Wein, L., An inverse optimization based auction mechanism to support a multiattribute RFQ process, Manage. Sci., 49, 1529-1545 (2003) · Zbl 1232.91274
[2] Bianco, L.; Ricciarddli, S., Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Res. Logist. Quart., 29, 151-167 (1982) · Zbl 0539.90044
[3] Cao, J.; Chen, J.; Zhao, Q., An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm, Cybernet. Inform. Technol., 14, 25-39 (2014)
[4] Chen, J.; Zhang, H.; Hu, G.; Huang, X.; Zhang, X., Delay optimization via packet scheduling for multi-path routing in wireless networks, Wireless Pers. Commun., 82, 4, 2637-2654 (2015)
[5] Chou, C.; Liu, H.; Queyranne, M.; Simchi-levi, D., On the asymptotic optimality of a simple on-line algotithm for the stochastic single mchine weighted completion time problem and its extensions, Oper. Res., 54, 464-474 (2006) · Zbl 1167.90521
[6] Chou, C.; Queyranne, M.; Simchi-levi, D., The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Math. Program., 106, 137-157 (2006) · Zbl 1134.90382
[7] Correa, J. R.; Wangner, M. R., LP-Based on-line scheduling: From single to parallel machines, Math. Program., 119, 109-136 (2009) · Zbl 1162.90009
[8] Demeange, G.; Gale, D.; Sotomayor, M., Multiple item auctions, J. Polit. Econ., 94, 863-872 (1986)
[9] Duives, J.; Heydenreich, B.; Mishra, D.; Müller, R.; Uetz, M., Optimal mechanisms for single machine scheduling, J. Sched., 18, 45-59 (2015) · Zbl 1310.90052
[10] Edmonds, J., Submodular functions, matroids and certain polyhedra, Proceedings International Conference on Cumbinatorics (Calgary Canada), 1970, pp. 69-87. · Zbl 0268.05019
[11] Gallien, J.; Vein, L., A smart market for industrial procurement with capacity constraints, Manage. Sci., 51, 76-91 (2005) · Zbl 1232.91300
[12] Gazmuri, G., Probabilistic analysis of a machine scheduling problem, Math. Oper. Res., 10, 328-339 (1985) · Zbl 0565.90028
[13] Goemans, M.X., A supermodular relaxation for scheduling with release dates, in Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, W.H. Cunningham, S.T. McCormick, and M. Queyranne, eds., Vol. 1084, Springer, Berlin, 1996, pp. 288-300. · Zbl 1414.90149
[14] Heydenreich, B.; Müller, R.; Uetz, M., Games and mechanism design in machine scheduling-an introduction, Prod. Oper. Manag., 16, 437-454 (2007)
[15] Heydenreich, B.; Müller, R.; Uetz, M., Mechanism design for decentralized online machine scheduling, Oper. Res., 58, 445-457 (2010) · Zbl 1233.90157
[16] Huang, Y.; Bessis, N.; Norrington, P.; Kuonen, P.; Hirsbrunner, B., Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm, Future Gener. Comput. Syst., 29, 402-415 (2013)
[17] Ishii, R.P., Mello, R.F.D., and Yang, L.T., A complex network-based approach for job scheduling in grid environments, in High Performance Computing and Communications. Lecture Notes in Computer Science, R. Perrott, B.M. Chapman, J. Subhlok, R.F. de Mello, and L.T. Yang, eds., Vol. 4782, Springer, Berlin, 2007, pp. 204-215.
[18] Liao, S.; Van Delft, C.; Vial, J. P., Distributionally robust workforce scheduling in call centres with uncertain arrival rates, Optim. Methods Softw., 28, 3, 501-522 (2013) · Zbl 1266.90122
[19] Liu, P.; Lu, X., Online scheduling of two uniform machines to minimize total completion times, J. Ind. Manag. Optim., 5, 95-102 (2009) · Zbl 1158.90351
[20] Malakhov, A.; Vohra, R., An optimal auction for capacity constrained bidders: A network perspective, Econom. Theory, 39, 113-128 (2007) · Zbl 1156.91356
[21] Megow, N.; Uetz, M.; Vredeveld, T., Models and algorithms for stochastic on-line scheduling, Math. Oper. Res., 31, 513-525 (2006) · Zbl 1278.90182
[22] Mitra, M., Mechanism design in queueing problems, Econom. Theory, 17, 277-305 (2001) · Zbl 0989.90035
[23] Möhring, R. H.; Schulz, A. S.; Uetz, M., Approximation in stochastic scheduling: The power of LP-based priority policies, J. ACM, 46, 924-942 (1999) · Zbl 1176.90262
[24] Müller, R.; Perea, A.; Wolf, S., Weak monotonicity and Bayes-Nash incentive compatibility, Games Econom. Behav., 61, 344-358 (2007) · Zbl 1271.91072
[25] Nisan, N. and Ronen, A., Computationally feasible VCG mechanisms, J. Artificial Intelligence Res. 29 (2007), pp. 19-47. · Zbl 1165.91387
[26] Raj, S., Telatar, E., and Tse, D., Jop scheduling and multiple access, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 66 (2003), pp. 127-137. · Zbl 1064.94535
[27] Schulz, A.S., Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, in International Conference on Integer Programming and Combinatorial Optimization (Vancouver, B.C., Canada), W.H. Cunningham, S.T. McCormick, and M. Queyranne, eds., vol. 1084, Lecture Notes in Computer Science, Springer-Verlag, New York, 1996, pp. 301-315. · Zbl 1414.90167
[28] Wellman, M. P.; Walsh, W. E.; Wurman, P. R.; Mackie Mason, J. K., Auction protocols for decentralized scheduling, Games Econom. Behav., 35, 271-303 (2001) · Zbl 0996.90047
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.