非同时可用同类机可中断调度问题的最优算法

周昊; 曹丽萍; 魏麒; 舒振宇; 蒋义伟

doi:10.1631/FITEE.2300767

Your Location：

Home >

Browse articles >

非同时可用同类机可中断调度问题的最优算法

常规文章 | Updated：2025-04-03

- 非同时可用同类机可中断调度问题的最优算法
  Enhanced Publication
- An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
- 信息与电子工程前沿(英文版) 2025年26卷第3期页码：472-478
- Affiliations：
  
  1.College of Basic Science, Zhejiang Shuren University, Hangzhou 310015, China
  2.School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, China
  3.College of International Economics and Trade, Ningbo University of Finance and Economics, Ningbo 315175, China
  4.School of Computer and Data Engineering, NingboTech University, Ningbo 315100, China
- Author bio：
  
  E-mail: zhouhao@zjsru.edu.cn
  ‡Corresponding author
- Funds：
  
  the Zhejiang Provincial Natural Science Foundation of China(LZ23G010001;LZ25F020012);the National Natural Science Foundation of China(62172356;61872321);the Ningbo Major Special Projects of the “Science and Technology Innovation 2025”(2024Z122)
- DOI：10.1631/FITEE.2300767
  中图分类号：
- 收稿：2023-11-09，
  
  修回：2024-03-29，
  
  纸质出版：2025-03
- Accepted：
Scan QR Code
周昊, 曹丽萍, 魏麒, 等. 非同时可用同类机可中断调度问题的最优算法[J]. 信息与电子工程前沿(英文版), 2025,26(3):472-478.

Hao ZHOU, Liping CAO, Qi WEI, et al. An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines[J]. Frontiers of Information Technology & Electronic Engineering, 2025, 26(3): 472-478.
周昊, 曹丽萍, 魏麒, 等. 非同时可用同类机可中断调度问题的最优算法[J]. 信息与电子工程前沿(英文版), 2025,26(3):472-478. DOI： 10.1631/FITEE.2300767.

Hao ZHOU, Liping CAO, Qi WEI, et al. An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines[J]. Frontiers of Information Technology & Electronic Engineering, 2025, 26(3): 472-478. DOI： 10.1631/FITEE.2300767.

摘要

研究了

台可用时间不同的同类机可中断调度问题，目标是极小化最大完工时间。每台机器都有一个不同的加工速度和可用时间。通过将真实机器转化成虚拟机器的方法给出最优调度目标值的下界。在这些虚拟机器中，可用时间越早的机器在任何时候都有更快的速度。对该问题，给出一个时间复杂度为

（

）的最优调度算法，并且该算法的中断次数不超过

（

代表工件数量）。

Abstract

关键词

Keywords

references

Błażewicz J , Dell'Olmo P , Drozdowski M , et al. , 2003 . Scheduling multiprocessor tasks on parallel processors with limited availability . Eur J Oper Res , 149 ( 2 ): 377 - 389 . https://doi.org/10.1016/S0377-2217(02)00760-9 https://doi.org/10.1016/S0377-2217(02)00760-9

Chang SY , Hwang HC , 1999 . The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines . Discr Appl Math , 92 ( 2-3 ): 135 - 147 . https://doi.org/10.1016/S0166-218X(99)00049-9 https://doi.org/10.1016/S0166-218X(99)00049-9

Gonzalez T , Sahni S , 1978 . Preemptive scheduling of uniform processor systems . J ACM , 25 ( 1 ): 92 - 101 . https://doi.org/10.1145/322047.322055 https://doi.org/10.1145/322047.322055

Grigoriu L , Friesen DK , 2017 . Approximation for scheduling on uniform nonsimultaneous parallel machines . J Sched , 20 ( 6 ): 593 - 600 . https://doi.org/10.1007/s10951-016-0501-1 https://doi.org/10.1007/s10951-016-0501-1

He Y , 1998 . Parametric LPT-bound on parallel machine scheduling with non-simultaneous available time . Asia-Pac J Oper Res , 15 ( 1 ): 29 - 36 .

He Y , 2000 . Uniform machine scheduling with machine available constraints . Acta Math Appl Sin , 16 ( 2 ): 122 - 129 . https://doi.org/10.1007/BF02677672 https://doi.org/10.1007/BF02677672

Horvath EC , Lam S , Sethi R , 1977 . A level algorithm for preemptive scheduling . J ACM , 24 ( 1 ): 32 - 43 . https://doi.org/10.1145/321992.321995 https://doi.org/10.1145/321992.321995

Huo YM , 2019 . Parallel machine makespan minimization subject to machine availability and total completion time constraints . J Sched , 22 ( 4 ): 433 - 447 . https://doi.org/10.1007/s10951-017-0551-z https://doi.org/10.1007/s10951-017-0551-z

Hwang HC , Lim K , 2014 . Exact performance of MULTIFIT for nonsimultaneous machines . Discr Appl Math , 167 : 172 - 187 . https://doi.org/10.1016/j.dam.2013.10.022 https://doi.org/10.1016/j.dam.2013.10.022

Kaabi J , Harrath Y , 2019 . Scheduling on uniform parallel machines with periodic unavailability constraints . Int J Prod Res , 57 ( 1 ): 216 - 227 . https://doi.org/10.1080/00207543.2018.1471242 https://doi.org/10.1080/00207543.2018.1471242

Kurt A , Çetinkaya FC , 2024 . Unrelated parallel machine scheduling under machine availability and eligibility constraints to minimize the makespan of non-resumable jobs . Int J Ind Eng Manag , 15 ( 1 ): 18 - 33 . https://doi.org/10.24867/IJIEM-2024-1-345 https://doi.org/10.24867/IJIEM-2024-1-345

Lee CY , 1991 . Parallel machines scheduling with nonsimultaneous machine available time . Discr Appl Math , 30 ( 1 ): 53 - 61 . https://doi.org/10.1016/0166-218X(91)90013-M https://doi.org/10.1016/0166-218X(91)90013-M

Lee CY , Lei L , Pinedo M , 1997 . Current trends in deterministic scheduling . Ann Oper Res , 70 : 1 - 41 . https://doi.org/10.1023/A:1018909801944 https://doi.org/10.1023/A:1018909801944

Lee CY , He Y , Tang GC , 2000 . A note on "parallel machine scheduling with non-simultaneous machine available time." Discr Appl Math , 100 ( 1-2 ): 133 - 135 . https://doi.org/10.1016/S0166-218X(99)00201-2 https://doi.org/10.1016/S0166-218X(99)00201-2

Liu JWS , Yang AT , 1974 . Optimal scheduling of independent tasks on heterogeneous computing systems . Proc ACM Annual Conf , p. 38 - 45 . https://doi.org/10.1145/800182.810377 https://doi.org/10.1145/800182.810377

Mahjoub A , Kaabi J , Harrath Y , 2021 . Absolute bounds of list algorithms for parallel machines scheduling with unavailability periods . Int Trans Oper Res , 28 ( 3 ): 1594 - 1610 . https://doi.org/10.1111/itor.12589 https://doi.org/10.1111/itor.12589

McNaughton R , 1959 . Scheduling with deadlines and loss functions . Manag Sci , 6 ( 1 ): 1 - 140 . https://doi.org/10.1287/mnsc.6.1.1 https://doi.org/10.1287/mnsc.6.1.1

Muntz RR , Coffman EG , 1970 . Preemptive scheduling of real-time tasks on multiprocessor systems . J ACM , 17 ( 2 ): 324 - 338 . https://doi.org/10.1145/321574.321586 https://doi.org/10.1145/321574.321586

Santoro MC , Junqueira L , 2023 . Unrelated parallel machine scheduling models with machine availability and eligibility constraints . Comput Ind Eng , 179 : 109219 . https://doi.org/10.1016/j.cie.2023.109219 https://doi.org/10.1016/j.cie.2023.109219

Schmidt G , 1984 . Scheduling on semi-identical processors . Z für Oper Res , 28 ( 5 ): 153 - 162 . https://doi.org/10.1007/BF01920917 https://doi.org/10.1007/BF01920917

Shen LX , Wang D , Wang XY , 2013 . Parallel-machine scheduling with non-simultaneous machine available time . Appl Math Model , 37 ( 7 ): 5227 - 5232 . https://doi.org/10.1016/j.apm.2012.09.053 https://doi.org/10.1016/j.apm.2012.09.053

Wang XY , Zhou ZL , Ji P , et al. , 2014 . Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times . Comput Ind Eng , 74 : 88 - 91 . https://doi.org/10.1016/j.cie.2014.05.003 https://doi.org/10.1016/j.cie.2014.05.003

Wang XY , Hu XP , Liu WG , 2015 . Scheduling with deteriorating jobs and non-simultaneous machine available times . Asia-Pac J Oper Res , 32 ( 6 ): 1550049 . https://doi.org/10.1142/S0217595915500499 https://doi.org/10.1142/S0217595915500499

浏览量

121

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据