{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:25:52Z","timestamp":1760059552514,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T00:00:00Z","timestamp":1750377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72201009"],"award-info":[{"award-number":["72201009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Energy-aware scheduling plays a critical role in modern computing and manufacturing systems, where energy consumption often increases with job execution order or resource usage intensity. This study investigates a scheduling problem in which a sequence of heterogeneous jobs\u2014classified as either heavy or light\u2014must be assigned to multiple identical machines with monotonically increasing slot costs. While the machines are structurally symmetric, the fixed job order and cost asymmetry introduce significant challenges for optimal job allocation. We formulate the problem as an integer linear program and simplify the objective by isolating the cumulative cost of heavy jobs, thereby reducing the search for optimality to a position-based assignment problem. To address this challenge, we propose a structured assignment model termed monotonic machine assignment, which enforces index-based job distribution rules and restores a form of functional symmetry across machines. We prove that any feasible assignment can be transformed into a monotonic one without increasing the total energy cost, ensuring that the global optimum lies within this reduced search space. Building on this framework, we first present a general dynamic programming algorithm with complexity O(n2m2). More importantly, by introducing a structural correction scheme based on misaligned assignments, we design an iterative refinement algorithm that achieves global optimality in only O(nm2) time, offering significant scalability for large instances. Our results contribute both structural insight and practical methods for optimal, position-sensitive, energy-aware scheduling, with potential applications in embedded systems, pipelined computation, and real-time operations.<\/jats:p>","DOI":"10.3390\/sym17070980","type":"journal-article","created":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T11:23:24Z","timestamp":1750418604000},"page":"980","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Energy-Aware Scheduling of Heterogeneous Jobs with Monotonically Increasing Slot Costs"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1365-2668","authenticated-orcid":false,"given":"Lin","family":"Zhao","sequence":"first","affiliation":[{"name":"School of Economics, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Fu","sequence":"additional","affiliation":[{"name":"Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mu","family":"Su","sequence":"additional","affiliation":[{"name":"Chinese Academy of Sciences and Technology for Development, Beijing 100038, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2755977","article-title":"The impact of information technology on energy consumption and carbon emissions","volume":"2015","author":"Gelenbe","year":"2015","journal-title":"Ubiquity"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Freitag, C., Berners-Lee, M., Widdicks, K., Knowles, B., Blair, G., and Friday, A. (2021). The climate impact of ICT: A review of estimates, trends and regulations. arXiv.","DOI":"10.1016\/j.patter.2021.100340"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2258","DOI":"10.22214\/ijraset.2020.5369","article-title":"Task scheduling in cloud computing: A survey","volume":"8","author":"Venu","year":"2020","journal-title":"Int. J. Res. Appl. Sci. Eng. Technol. (IJRASET)"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ding, L., Guan, Z., Luo, D., Rauf, M., and Fang, W. (2024). An adaptive search algorithm for multiplicity dynamic flexible job shop scheduling with new order arrivals. Symmetry, 16.","DOI":"10.3390\/sym16060641"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Mei, X., Wang, Q., Chu, X., Liu, H., Leung, Y.W., and Li, Z. (2021). Energy-aware task scheduling with deadline constraint in DVFS-enabled heterogeneous clusters. arXiv.","DOI":"10.1109\/TPDS.2022.3181096"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"107312","DOI":"10.1016\/j.asoc.2021.107312","article-title":"Optimal production and maintenance scheduling for a degrading multi-failure modes single-machine production environment","volume":"106","author":"Sharifi","year":"2021","journal-title":"Appl. Soft Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"e70028","DOI":"10.1049\/cim2.70028","article-title":"A novel DQN-based hybrid algorithm for integrated scheduling and machine maintenance in dynamic flexible job shops","volume":"7","author":"Chen","year":"2025","journal-title":"IET Collab. Intell. Manuf."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kocot, B., Czarnul, P., and Proficz, J. (2023). Energy-aware scheduling for high-performance computing systems: A survey. Energies, 16.","DOI":"10.3390\/en16020890"},{"key":"ref_9","unstructured":"Yao, F., Demers, A., and Shenker, S. (1995, January 23\u201325). A scheduling model for reduced CPU energy. Proceedings of the IEEE 36th Annual Foundations of Computer Science, Milwaukee, WI, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Ben Alla, S., Ben Alla, H., Touhafi, A., and Ezzati, A. (2019). An efficient energy-aware tasks scheduling with deadline-constrained in cloud computing. Computers, 8.","DOI":"10.3390\/computers8020046"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TSUSC.2024.3360975","article-title":"Battery-aware workflow scheduling for portable heterogeneous computing","volume":"9","author":"Jiang","year":"2024","journal-title":"IEEE Trans. Sustain. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","article-title":"Energy-efficient algorithms","volume":"53","author":"Albers","year":"2010","journal-title":"Commun. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/0305-0548(94)90080-9","article-title":"Scheduling jobs under simple linear deterioration","volume":"21","author":"Mosheiov","year":"1994","journal-title":"Comput. Oper. Res."},{"key":"ref_14","unstructured":"Boddy, M., and Dean, T.L. (1989). Solving Time-Dependent Planning Problems, Brown University, Department of Computer Science."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0020-0190(93)90175-9","article-title":"Complexity of scheduling tasks with time-dependent execution times","volume":"48","author":"Ho","year":"1993","journal-title":"Inf. Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/0377-2217(95)00382-7","article-title":"Scheduling projects to maximize net present value\u2014The case of time-dependent, contingent cash flows","volume":"96","author":"Etgar","year":"1997","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0020-0190(01)00244-7","article-title":"Three scheduling problems with deteriorating jobs to minimize the total completion time","volume":"81","author":"Ng","year":"2002","journal-title":"Inf. Process. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wang, Z., Goudarzi, M., Gong, M., and Buyya, R. (2023). Deep reinforcement learning-based scheduling for optimizing system load and response time in edge and fog computing environments. arXiv.","DOI":"10.1016\/j.future.2023.10.012"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.future.2023.10.002","article-title":"Energy efficient task scheduling based on deep reinforcement learning in cloud environment: A specialized review","volume":"151","author":"Hou","year":"2024","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s11227-024-06907-y","article-title":"Intelligent energy pairing scheduler (InEPS) for heterogeneous HPC clusters","volume":"81","author":"Stafford","year":"2025","journal-title":"J. Supercomput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"104898","DOI":"10.1016\/j.robot.2024.104898","article-title":"Energy-aware multi-robot task scheduling using meta-heuristic optimization methods for ambiently-powered robot swarms","volume":"186","author":"Mokhtari","year":"2025","journal-title":"Robot. Auton. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mahmood, A., Khan, S.A., Albalooshi, F., and Awwad, N. (2017). Energy-aware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm. Electronics, 6.","DOI":"10.3390\/electronics6020040"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1109\/JSYST.2014.2322503","article-title":"Design techniques and applications of cyberphysical systems: A survey","volume":"9","author":"Khaitan","year":"2015","journal-title":"IEEE Syst. J."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Esmaili, A., and Pedram, M. (2020, January 25\u201326). Energy-aware scheduling of jobs in heterogeneous cluster systems using deep reinforcement learning. Proceedings of the 2020 21st International Symposium on Quality Electronic Design (ISQED), Santa Clara, CA, USA.","DOI":"10.1109\/ISQED48828.2020.9137025"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"102524","DOI":"10.1016\/j.sysarc.2022.102524","article-title":"A survey of energy-aware scheduling in mixed-criticality systems","volume":"127","author":"Zhang","year":"2022","journal-title":"J. Syst. Archit."},{"key":"ref_26","unstructured":"Kulkarni, J., and Munagala, K. (2012, January 13\u201314). Algorithms for cost-aware scheduling. Proceedings of the International Workshop on Approximation and Online Algorithms, Ljubljana, Slovenia."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3136754","article-title":"Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints","volume":"65","author":"Im","year":"2017","journal-title":"J. ACM"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Chen, L., Megow, N., Rischke, R., Stougie, L., and Verschae, J. (2015, January 24\u201328). Optimal algorithms and a PTAS for cost-aware scheduling. Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Milan, Italy.","DOI":"10.1007\/978-3-662-48054-0_18"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., and Stougie, L. (2010, January 9\u201311). Universal sequencing on a single machine. Proceedings of the Integer Programming and Combinatorial Optimization, Lausanne, Switzerland.","DOI":"10.1007\/978-3-642-13036-6_18"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0166-218X(95)00031-L","article-title":"Three-dimensional axial assignment problems with decomposable cost coefficients","volume":"65","author":"Burkard","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_31","unstructured":"Smolka, G. (November, January 29). Solving various weighted matching problems with constraints. Proceedings of the Principles and Practice of Constraint Programming-CP97, Linz, Austria."},{"key":"ref_32","unstructured":"Chuzhoy, J., Guha, S., Khanna, S., and Naor, J.S. (2004, January 17\u201319). Machine minimization for scheduling jobs with interval constraints. Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, Rome, Italy."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Im, S., Li, S., Moseley, B., and Torng, E. (2015, January 4\u20136). A dynamic programming framework for non-preemptive scheduling problems on multiple machines. Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, San Diego, CA, USA.","DOI":"10.1137\/1.9781611973730.72"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1684","DOI":"10.1137\/130911317","article-title":"The geometry of scheduling","volume":"43","author":"Bansal","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1109\/TC.2022.3191733","article-title":"Adaptive cloud bundle provisioning and multi-workflow scheduling via coalition reinforcement learning","volume":"72","author":"Wang","year":"2022","journal-title":"IEEE Trans. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Chandrasiri, S., and Meedeniya, D. (2025). Energy-efficient dynamic workflow scheduling in cloud environments using deep learning. Sensors, 25.","DOI":"10.3390\/s25051428"},{"key":"ref_37","first-page":"100517","article-title":"Energy and performance-efficient task scheduling in heterogeneous virtualized cloud computing","volume":"30","author":"Hussain","year":"2021","journal-title":"Sustain. Comput. Inform. Syst."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"4261","DOI":"10.1007\/s11227-021-04016-8","article-title":"An energy-aware scheduling of dynamic workflows using big data similarity statistical analysis in cloud computing","volume":"78","author":"Grami","year":"2022","journal-title":"J. Supercomput."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Br\u00e4nnvall, R., Stark, T., Gustafsson, J., Eriksson, M., and Summers, J. (2023, January 20\u201323). Cost optimization for the edge-cloud continuum by energy-aware workload placement. Proceedings of the Companion Proceedings of the 14th ACM International Conference on Future Energy Systems, New York, NY, USA. e-Energy \u201923 Companion.","DOI":"10.1145\/3599733.3600253"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/7\/980\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:56:00Z","timestamp":1760032560000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/7\/980"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,20]]},"references-count":39,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,7]]}},"alternative-id":["sym17070980"],"URL":"https:\/\/doi.org\/10.3390\/sym17070980","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2025,6,20]]}}}