Randomized mechanism design for decentralized network scheduling

References

• D. Ben and L. Wein, An inverse optimization based auction mechanism to support a multiattribute RFQ process, Manage. Sci. 49 (2003), pp. 1529–1545. doi: 10.1287/mnsc.49.11.1529.20588
   Web of Science ®Google Scholar
• L. Bianco and S. Ricciarddli, Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Res. Logist. Quart. 29 (1982), pp. 151–167. doi: 10.1002/nav.3800290114
   Google Scholar
• J. Cao, J. Chen, and Q. Zhao, An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm, Cybernet. Inform. Technol. 14 (2014), pp. 25–39.
   Google Scholar
• J. Chen, H. Zhang, G. Hu, X. Huang, and X. Zhang, Delay optimization via packet scheduling for multi-path routing in wireless networks, Wireless Pers. Commun. 82(4) (2015), pp. 2637–2654. doi: 10.1007/s11277-015-2370-x
   Web of Science ®Google Scholar
• C. Chou, H. Liu, M. Queyranne, and D. Simchi-levi, 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 (2006), pp. 464–474. doi: 10.1287/opre.1060.0270
   Web of Science ®Google Scholar
• C. Chou, M. Queyranne, and D. Simchi-levi, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Math. Program. 106 (2006), pp. 137–157. doi: 10.1007/s10107-005-0588-1
   Web of Science ®Google Scholar
• J.R. Correa and M.R. Wangner, LP-Based on-line scheduling: From single to parallel machines, Math. Program. 119 (2009), pp. 109–136. doi: 10.1007/s10107-007-0204-7
   Web of Science ®Google Scholar
• G. Demeange, D. Gale, and M. Sotomayor, Multiple item auctions, J. Polit. Econ. 94 (1986), pp. 863–872. doi: 10.1086/261411
   Google Scholar
• J. Duives, B. Heydenreich, D. Mishra, R. Müller, and M. Uetz, Optimal mechanisms for single machine scheduling, J. Sched. 18 (2015), pp. 45–59. doi: 10.1007/s10951-014-0378-9
   Google Scholar
• J. Edmonds, Submodular functions, matroids and certain polyhedra, Proceedings International Conference on Cumbinatorics (Calgary Canada), 1970, pp. 69–87.
   Google Scholar
• J. Gallien and L. Vein, A smart market for industrial procurement with capacity constraints, Manage. Sci. 51 (2005), pp. 76–91. doi: 10.1287/mnsc.1040.0230
   Web of Science ®Google Scholar
• G. Gazmuri, Probabilistic analysis of a machine scheduling problem, Math. Oper. Res. 10 (1985), pp. 328–339. doi: 10.1287/moor.10.2.328
   Web of Science ®Google Scholar
• M.X. Goemans, 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.
   Google Scholar
• B. Heydenreich, R. Müller, and M. Uetz, Games and mechanism design in machine scheduling–an introduction, Prod. Oper. Manag. 16 (2007), pp. 437–454. doi: 10.1111/j.1937-5956.2007.tb00271.x
   Web of Science ®Google Scholar
• B. Heydenreich, R. Müller, and M. Uetz, Mechanism design for decentralized online machine scheduling, Oper. Res. 58 (2010), pp. 445–457. doi: 10.1287/opre.1090.0732
   Web of Science ®Google Scholar
• Y. Huang, N. Bessis, P. Norrington, P. Kuonen, and B. Hirsbrunner, Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm, Future Gener. Comput. Syst. 29 (2013), pp. 402–415. doi: 10.1016/j.future.2011.05.006
   Web of Science ®Google Scholar
• R.P. Ishii, R.F.D. Mello, and L.T. Yang, 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.
   Google Scholar
• S. Liao, C. Van Delft, and J.P. Vial, Distributionally robust workforce scheduling in call centres with uncertain arrival rates, Optim. Methods Softw. 28(3) (2013), pp. 501–522. doi: 10.1080/10556788.2012.694166
   Web of Science ®Google Scholar
• P. Liu and X. Lu, Online scheduling of two uniform machines to minimize total completion times, J. Ind. Manag. Optim. 5 (2009), pp. 95–102. doi: 10.3934/jimo.2009.5.95
   Google Scholar
• A. Malakhov and R. Vohra, An optimal auction for capacity constrained bidders: A network perspective, Econom. Theory 39 (2007), pp. 113–128. doi: 10.1007/s00199-007-0312-x
   Web of Science ®Google Scholar
• N. Megow, M. Uetz, and T. Vredeveld, Models and algorithms for stochastic on-line scheduling, Math. Oper. Res. 31 (2006), pp. 513–525. doi: 10.1287/moor.1060.0201
   Web of Science ®Google Scholar
• M. Mitra, Mechanism design in queueing problems, Econom. Theory 17 (2001), pp. 277–305. doi: 10.1007/PL00004107
   Web of Science ®Google Scholar
• R.H. Möhring, A.S. Schulz, and M. Uetz, Approximation in stochastic scheduling: The power of LP-based priority policies, J. ACM 46 (1999), pp. 924–942. doi: 10.1145/331524.331530
   Web of Science ®Google Scholar
• R. Müller, A. Perea, and S. Wolf, Weak monotonicity and Bayes–Nash incentive compatibility, Games Econom. Behav. 61 (2007), pp. 344–358. doi: 10.1016/j.geb.2007.01.008
   Web of Science ®Google Scholar
• N. Nisan and A. Ronen, Computationally feasible VCG mechanisms, J. Artificial Intelligence Res. 29 (2007), pp. 19–47.
   Google Scholar
• S. Raj, E. Telatar, and D. Tse, Jop scheduling and multiple access, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 66 (2003), pp. 127–137.
   Google Scholar
• A.S. Schulz, 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.
   Google Scholar
• M.P. Wellman, W.E. Walsh, P.R. Wurman, and J.K. Mackie Mason, Auction protocols for decentralized scheduling, Games Econom. Behav. 35 (2001), pp. 271–303. doi: 10.1006/game.2000.0822
   Web of Science ®Google Scholar