An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines

Hao ZHOU; Liping CAO; Qi WEI; Zhenyu SHU; Yiwei JIANG

doi:10.1631/FITEE.2300767

Your Location：

Home >

Browse articles >

An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines

Regular Papers | Updated：2025-04-03

- An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
  Enhanced Publication
- 非同时可用同类机可中断调度问题的最优算法
- Frontiers of Information Technology & Electronic Engineering Vol. 26, Issue 3, Pages: 472-478(2025)
- 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：
- DOI：10.1631/FITEE.2300767
  CLC：
- Received：09 November 2023，
  
  Revised：29 March 2024，
  
  Published：2025-03
- Accepted：
Scan QR Code
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：

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

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰