{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T11:53:16Z","timestamp":1785412396681,"version":"3.56.0"},"reference-count":35,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T00:00:00Z","timestamp":1782950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100031512","name":"Guangdong Police College","doi-asserted-by":"crossref","award":["2026FY02"],"award-info":[{"award-number":["2026FY02"]}],"id":[{"id":"10.13039\/100031512","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100031512","name":"Guangdong Police College","doi-asserted-by":"crossref","award":["2026JY01"],"award-info":[{"award-number":["2026JY01"]}],"id":[{"id":"10.13039\/100031512","id-type":"DOI","asserted-by":"crossref"}]},{"award":["2026FY02"],"award-info":[{"award-number":["2026FY02"]}],"id":[{"id":"https:\/\/ror.org\/05krxyw16","id-type":"ROR","asserted-by":"publisher"}]},{"award":["2026JY01"],"award-info":[{"award-number":["2026JY01"]}],"id":[{"id":"https:\/\/ror.org\/05krxyw16","id-type":"ROR","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Approximation jobs are widely deployed on Amazon EC2, which compute partial task segments to obtain useful results. For such jobs, maximizing total profit is the primary goal, where profit equals the sum of job utilities minus the total machine costs. Unfortunately, maximizing the total profit of approximation jobs is an NP-hard problem. This problem is further complicated by online job arrivals and heterogeneous resource demands across different tasks. This work builds an optimization framework that clearly characterizes job utility and machine costs to resolve this problem. Within this framework, we propose an efficient dual algorithm for job scheduling. The proposed method leverages the dual-fitting approach to measure algorithm performance by analyzing the primal and dual objective growth at each step. This work proves that our algorithm achieves a constant competitive ratio. The results from the trace-driven simulations demonstrate that our algorithms consistently outperform these baselines across various metrics.<\/jats:p>","DOI":"10.3390\/a19070539","type":"journal-article","created":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T14:51:25Z","timestamp":1783003885000},"page":"539","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Novel Model for Online Scheduling of Approximation Jobs"],"prefix":"10.3390","volume":"19","author":[{"given":"Qi","family":"Li","sequence":"first","affiliation":[{"name":"Department of Network Information Security, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaolei","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Network Information Security, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuo","family":"Wen","sequence":"additional","affiliation":[{"name":"Department of Network Information Security, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Du","sequence":"additional","affiliation":[{"name":"Department of Network Information Security, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Mao","sequence":"additional","affiliation":[{"name":"Department of Network Information Security, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Cai","sequence":"additional","affiliation":[{"name":"Computer Science and Electronic Engineering, Hunan University, Changsha 410012, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,7,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Li, Q., Wen, S., Wang, X., Du, W., Cai, L., and Xu, H. (2025). Online Job Scheduling for Profit Maximization in a Heterogeneous Cluster. 23rd IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE.","DOI":"10.1109\/ISPA67752.2025.00218"},{"key":"ref_2","unstructured":"(2026, June 22). Amazon Mechanical Turk (MTurk). Available online: http:\/\/www.mturk.com."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1109\/TNET.2024.3495522","article-title":"Smoothed Online Decision Making in Communication: Algorithms and Applications","volume":"33","author":"Liu","year":"2024","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2243","DOI":"10.1109\/TNET.2020.3006906","article-title":"Online Resource Allocation with Machine Variability: A Bandit Perspective","volume":"28","author":"Xu","year":"2020","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1109\/TASE.2024.3368617","article-title":"Scheduling Unrelated Parallel Batch Processing Machines Under Time-of-Use Electricity Prices","volume":"22","author":"Tian","year":"2024","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Albahar, H., Dongare, S., Du, Y., Zhao, N., Paul, A.K., and Butt, A.R. (2022). SCHEDTUNE: A Heterogeneity-Aware GPU Scheduler for Deep Learning. 2022 IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid), Taormina, Italy, 16\u201319 May 2022, IEEE.","DOI":"10.1109\/CCGrid54584.2022.00079"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"20883","DOI":"10.1109\/JIOT.2026.3665092","article-title":"Carbon-Aware Dynamic Task Scheduling in Hierarchical Cloud\u2013Edge Systems for IoT Devices","volume":"13","author":"Gao","year":"2026","journal-title":"IEEE Internet Things J."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"10340","DOI":"10.1109\/TNET.2016.2619743","article-title":"Online Auctions in IaaS Clouds: Welfare and Profit Maximization with Server Costs","volume":"25","author":"Zhang","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1109\/TSC.2025.3528346","article-title":"TF-DDRL: A Transformer-enhanced Distributed DRL Technique for Scheduling IoT Applications in Edge and Cloud Computing Environments","volume":"18","author":"Wang","year":"2025","journal-title":"IEEE Trans. Serv. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"14559","DOI":"10.1109\/JIOT.2025.3526662","article-title":"Faster and Stronger: Unleashing Data Processing Potential through Hardware Heterogeneity","volume":"12","author":"Wang","year":"2025","journal-title":"IEEE Internet Things J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/BF02099703","article-title":"An algorithm for large scale 0-1 integer programming with application to airline crew scheduling","volume":"57","author":"Wedelin","year":"1995","journal-title":"Ann. Oper. Res."},{"key":"ref_12","unstructured":"Elnikety, S., Larus, J., Yan, C., He, Y., and Larus, J. (2012, January 14\u201317). Scheduling interactive services with partial execution. Proceedings of the ACM Symposium on Cloud Computing (SoCC), San Jose, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"6209","DOI":"10.1109\/TMC.2025.3540017","article-title":"Profit Maximization of Delay-Sensitive, Differential Accuracy Inference Services in Mobile Edge Computing","volume":"24","author":"Zhang","year":"2025","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2267","DOI":"10.1109\/TSC.2025.3570845","article-title":"Online Workload Scheduling for Social Welfare Maximization in the Computing Continuum","volume":"18","author":"Zhao","year":"2025","journal-title":"IEEE Trans. Serv. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/TCC.2025.3548604","article-title":"Deadline-Aware Online Job Scheduling for Distributed Training in Heterogeneous Clusters","volume":"13","author":"Zhang","year":"2025","journal-title":"IEEE Trans. Cloud Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"125232","DOI":"10.1016\/j.apenergy.2024.125232","article-title":"Optimal charging for large-scale heterogeneous electric vehicles: A novel paradigm based on learning and backward clustering","volume":"382","author":"Xu","year":"2025","journal-title":"Appl. Energy"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Bao, Y., Peng, Y., Wu, C., and Li, Z. (2018). Online job scheduling in distributed machine learning clusters. IEEE INFOCOM, IEEE.","DOI":"10.1109\/INFOCOM.2018.8486422"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"You, W., Jiao, L., Li, J., and Zhou, R. (2020). Scheduling DDoS Cloud Scrubbing in ISP Networks via Randomized Online Auctions. Proceedings of IEEE INFOCOM, IEEE.","DOI":"10.1109\/INFOCOM41043.2020.9155493"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"9341","DOI":"10.1109\/JIOT.2020.2984332","article-title":"CEFL: Online Admission Control, Data Scheduling, and Accuracy Tuning for Cost-Efficient Federated Learning Across Edge Nodes","volume":"7","author":"Zhou","year":"2020","journal-title":"IEEE Internet Things J."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.jclepro.2013.12.024","article-title":"Optimizing the production scheduling of a single machine to minimize total energy consumption costs","volume":"67","author":"Shrouf","year":"2014","journal-title":"J. Clean. Prod."},{"key":"ref_21","unstructured":"Gan, K., Keyvanshokooh, E., Liu, X., and Murphy, S. (2024). Contextual Bandits with Budgeted Information Reveal. Proceedings of AISTATS, PMLR."},{"key":"ref_22","unstructured":"Gupta, A., Krishnaswamy, R., and Pruhs, K. (2002). Online primal-dual for nonlinear optimization with applications to speed scaling. Proceedings of WAOA, Springer."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., and Huang, Z. (2014, January 5\u20137). Primal dual gives optimal energy efficient online algorithms. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.83"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"8063","DOI":"10.1109\/TVT.2024.3524747","article-title":"Online Queue-Aware Service Migration and Resource Allocation in Mobile Edge Computing","volume":"74","author":"Du","year":"2025","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"3731","DOI":"10.1109\/TVT.2021.3063380","article-title":"Incentive Mechanisms for Large-Scale Crowdsourcing Task Diffusion Based on Social Influence","volume":"70","author":"Xu","year":"2021","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Doostmohammadian, M., Aghasi, A., Rikos, A.I., Grammenos, A., Kalyvianaki, E., Hadjicostis, C.N., Johansson, K.H., and Charalambous, T. (2022). Distributed CPU scheduling subject to nonlinear constraints. IEEE Conference on Control Technology and Applications, IEEE.","DOI":"10.1109\/CCTA49430.2022.9966048"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"113018","DOI":"10.1016\/j.engappai.2025.113018","article-title":"Machine learning and CPU (central processing unit) scheduling co-optimization over a network of computing centres","volume":"163","author":"Doostmohammadian","year":"2026","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Zheng, Z., and Shroff, N. (2016). Online multi-resource allocation for deadline sensitive jobs with partial values in the cloud. Proceedings of IEEE INFOCOM, IEEE.","DOI":"10.1109\/INFOCOM.2016.7524430"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Zheng, Z.Z., and Shroff, N.B. (2014). Online Welfare Maximization for Electric Vehicle Charging with Electricity Cost. ACM e-Energy, Association for Computing Machinery.","DOI":"10.1145\/2602044.2602053"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2514","DOI":"10.1109\/TPDS.2018.2829860","article-title":"Minimize the Make-span of Batched Requests for FPGA Pooling in Cloud Computing","volume":"29","author":"Zhao","year":"2018","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_31","first-page":"1","article-title":"Flow-Time Minimization for Timely Data Stream Processing in UAV-Aided Mobile Edge Computing","volume":"20","author":"Xu","year":"2024","journal-title":"ACM Trans. Sens. Netw."},{"key":"ref_32","unstructured":"Ma, G., Li, H., Wang, X., Chen, X., Bian, Y., Hu, M., Wang, X., and Zhang, J. (2022). Mobility-aware Task Splitting and Resource Allocation for Vehicular MEC. ACM MobiCom, Association for Computing Machinery."},{"key":"ref_33","unstructured":"Mount, D.M. (2025). CMSC 451: Greedy Algorithms for Scheduling, University of Maryland. University of Maryland Technical Report."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Boyd, S., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_35","unstructured":"Reiss, C., Wilkes, J., and Hellerstein, J.L. (2026, June 01). Google Cluster-Usage Traces. Available online: https:\/\/github.com\/google\/cluster-data."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/539\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T04:11:34Z","timestamp":1783570294000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,2]]},"references-count":35,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2026,7]]}},"alternative-id":["a19070539"],"URL":"https:\/\/doi.org\/10.3390\/a19070539","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,2]]}}}