A Mechanism Design Approach for Dynamic Task Online Scheduling

Xiao-Peng Lin; Hua-Ching Chen; Hsuan-Ming Feng

doi:10.46604/ijeti.2026.16741

Authors

Xiao-Peng Lin School of Information Engineering, Xiamen Ocean Vocational College, Xiamen, Fujian 361000, China
Hua-Ching Chen School of Information Engineering, Xiamen Ocean Vocational College, Xiamen, Fujian 361000, China
Hsuan-Ming Feng Department of Computer Science and Information Engineering, National Quemoy University, Taiwan, R.O.C.

DOI:

https://doi.org/10.46604/ijeti.2026.16741

Keywords:

game theory, grid computing, mechanism design, online task scheduling

Abstract

In game-theoretic grid computing, selfish users may misreport task information to obtain individual advantages, leading to prolonged scheduling negotiations and degraded system performance. This study aims to develop the resource allocation mechanism for dynamic tasks (RAMDT), an online scheduling mechanism based on the direct revelation principle. RAMDT incentivizes users to truthfully disclose their private task attributes—value, length, arrival time, and deadline—at the initial bidding stage, thereby accelerating equilibrium convergence, reducing bidding rounds, and minimizing resource waste. Theoretical analysis demonstrates that RAMDT satisfies individual rationality and incentive compatibility, ensuring truthful reporting is a weakly dominant strategy for rational users. Simulation results show that compared with random-bidding protocols, RAMDT reduces the number of rounds for resource equilibrium from exponential to linear in the number of users, and achieves a higher task completion rate than the first-come, first-served (FCFS) scheme. Overall, RAMDT aligns self-interested user behavior with system-wide scheduling efficiency.

References

A. J. Jadhav and G. A. Patil, “Optimizing Computational Resources for Improved Accuracy in Grid Computing Environments,” International Journal of Advance Computational Engineering and Networking (IJACEN), vol. 12, no. 9, pp. 93–98, 2024.

R. Wolski, J. S. Plank, J. Brevik, and T. Bryan, “Analyzing Market-Based Resource Allocation Strategies for the Computational Grid,” International Journal of High Performance Computing Applications, vol. 15, no. 3, pp. 258–281, 2001.

R. Buyya, D. Abramson, and S. Venugopal, “The Grid Economy,” Proceedings of the IEEE, vol. 93, no. 3, pp. 698–714, 2005.

I. Foster and C. Kesselman, Eds., The Grid 2: Blueprint for a New Computing Infrastructure, 2nd ed., San Francisco, CA, USA: Morgan Kaufmann, 2004.

X. P. Lin, X. C. Li, and D. H. Guo, “Principles and Key Technologies of Grid Computing,” Communications Technology, vol. 42, no. 2, pp. 218–220, 2009 (in Chinese).

Z. T. Jiang, K. Li, Y. Wang, M. L. Liu, and H. Q. Li, “A Task Allocation Schema Based on Response Time Optimization in Cloud Computing,” Cluster Computing, vol. 27, no. 3, pp. 3893–3910, 2024.

S. Feng, J. Kim, Y. Yang, J. Boudreau, T. Chowdhury, A. Hoisie, et al., “Alternative Mixed Integer Linear Programming Optimization for Joint Job Scheduling and Data Allocation in Grid Computing,” Future Generation Computer Systems, vol. 175, article no. 108075, 2026.

S. Chen, L. Jiao, F. Liu, and L. Wang, “EdgeDR: An Online Mechanism Design for Demand Response in Edge Clouds,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 2, pp. 343–358, 2022.

A. B. MacKenzie and L. A. DaSilva, Game Theory for Wireless Engineers. San Rafael, CA, USA: Morgan & Claypool Publishers, 2006.

Y. K. Kwok, K. Hwang, and S. S. Song, “Selfish Grids: Game-Theoretic Modeling and NAS/PSA Benchmark Evaluation,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, pp. 621–636, 2007.

E. N. Alkhanak, S. P. Lee, R. Rezaei, and R. M. Parizi, “Cost Optimization Approaches for Scientific Workflow Scheduling in Cloud and Grid Computing: A Review, Classifications, and Open Issues,” Journal of Systems and Software, vol. 113, pp. 1–26, 2016.

M. B. Qureshi, M. M. Dehnavi, N. Min-Allah, M. S. Qureshi, H. Hussain, I. Rentifis, et al., “Survey on Grid Resource Allocation Mechanisms,” Journal of Grid Computing, vol. 12, no. 2, pp. 399–441, 2014.

M. G. Buscemi, U. Montanari, and S. Taneja, “A Game-Theoretic Analysis of Grid Job Scheduling,” Journal of Grid Computing, vol. 10, no. 3, pp. 501–509, 2012.

F. Xhafa and J. Kolodziej, “Game-Theoretic, Market and Meta-Heuristics Approaches for Modelling Scheduling and Resource Allocation in Grid Systems,” Proceedings of the 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), IEEE, pp. 235–242, 2010.

N. Sharghivand, F. Derakhshan, and N. Siasi, “A Comprehensive Survey on Auction Mechanism Design for Cloud/Edge Resource Management and Pricing,” IEEE Access, vol. 9, pp. 126502–126529, 2021.

H. Prasad, A. Anand, S. S. Sudha, S. Choudhury, M. K. Gourisaria, and A. Bandyopadhyay, “Game Theory-Based Auction Approach for Resource Allocation in Grid Computing Using Microgrids,” Proceedings of the 2024 Global Conference on Communications and Information Technologies (GCCIT 2024), IEEE, pp. 1–6, 2024.

A. Salehan, H. Deldari, and S. Abrishami, “An Online Valuation-Based Sealed Winner-Bid Auction Game for Resource Allocation and Pricing in Clouds,” The Journal of Supercomputing, vol. 73, no. 11, pp. 4868–4905, 2017.

J. Tadrous, A. Eryilmaz, and A. Sabharwal, “Action-Based Scheduling: Leveraging App Interactivity for Scheduler Efficiency,” IEEE/ACM Transactions on Networking, vol. 27, no. 1, pp. 112–125, 2019.

T. Börgers, D. Krähmer, and R. Strausz, An Introduction to the Theory of Mechanism Design. Oxford, U.K.: Oxford University Press, 2015.