摘要
研究了m台可用时间不同的同类机可中断调度问题,目标是极小化最大完工时间。每台机器都有一个不同的加工速度和可用时间。通过将真实机器转化成虚拟机器的方法给出最优调度目标值的下界。在这些虚拟机器中,可用时间越早的机器在任何时候都有更快的速度。对该问题,给出一个时间复杂度为O(nm+m2)的最优调度算法,并且该算法的中断次数不超过 \({1\over 2}(m^{2}+3m)-2\) (n代表工件数量)。
This is a preview of subscription content, log in via an institution to check access.
References
Blazewicz 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
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
Gonzalez T, Sahni S, 1978. Preemptive scheduling of uniform processor systems. J ACM, 25(1):92–101. 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
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
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
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
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
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
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
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
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
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
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
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
McNaughton R, 1959. Scheduling with deadlines and loss functions. Manag Sci, 6(1):1–140. https://doi.org/10.1287/mnsc.6.1.1
Muntz RR, Coffman EG, 1970. Preemptive scheduling of realtime tasks on multiprocessor systems. J ACM, 17(2):324–338. 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
Schmidt G, 1984. Scheduling on semi-identical processors. Z für Oper Res, 28(5):153–162. 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
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
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.Z https://doi.org/10.1142/S0217595915500499
Author information
Authors and Affiliations
Contributions
Hao ZHOU designed the research. Liping CAO and Qi WEI designed and analyzed the algorithm. Hao ZHOU and Liping CAO drafted the paper. Zhenyu SHU helped organize the paper. Yiwei JIANG revised and finalized the paper.
Corresponding author
Ethics declarations
All the authors declare that they have no conflict of interest.
Additional information
Project supported by the Zhejiang Provincial Natural Science Foundation of China (Nos. LZ23G010001 and LZ25F020012), the National Natural Science Foundation of China (Nos. 62172356 and 61872321), and the Ningbo Major Special Projects of the “Science and Technology Innovation 2025” (No. 2024Z122)
Rights and permissions
About this article
Cite this article
Zhou, H., Cao, L., Wei, Q. et al. An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines. Front Inform Technol Electron Eng 26, 472–478 (2025). https://doi.org/10.1631/FITEE.2300767
Received:
Accepted:
Published:
Version of record:
Issue date:
DOI: https://doi.org/10.1631/FITEE.2300767