Full Text:
<635>
Summary: 
<28>
CLC number:
On-line Access: 2025-04-03
Received: 2023-11-09
Revision Accepted: 2024-03-29
Crosschecked: 2025-04-07
Cited: 0
Clicked: 957
An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
| ||||||||||||||
Hao ZHOU, Liping CAO, Qi WEI, Zhenyu SHU, Yiwei JIANG. An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines[J]. Frontiers of Information Technology & Electronic Engineering, 2025, 26(3): 472-478.
@article{title="An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines",
author="Hao ZHOU, Liping CAO, Qi WEI, Zhenyu SHU, Yiwei JIANG",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="26",
number="3",
pages="472-478",
year="2025",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2300767"
}
%0 Journal Article
%T An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
%A Hao ZHOU
%A Liping CAO
%A Qi WEI
%A Zhenyu SHU
%A Yiwei JIANG
%J Frontiers of Information Technology & Electronic Engineering
%V 26
%N 3
%P 472-478
%@ 2095-9184
%D 2025
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2300767
TY - JOUR
T1 - An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
A1 - Hao ZHOU
A1 - Liping CAO
A1 - Qi WEI
A1 - Zhenyu SHU
A1 - Yiwei JIANG
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 26
IS - 3
SP - 472
EP - 478
%@ 2095-9184
Y1 - 2025
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2300767
Abstract: We study preemptive scheduling on m uniform machines with non-simultaneous available times to minimize the makespan. Each machine has a different speed and a different available time. We first provide a lower bound on the optimal makespan of the problem by converting the real machines to virtual machines that guarantee a machine with an earlier available time having a greater speed at any time. Then, we provide an algorithm with time complexity of O(nm+m2) to find an optimal schedule with, at most, (m2+3m/ 2?2 preemptions, where n is the number of jobs.
[1]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.
[2]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.
[3]Gonzalez T, Sahni S, 1978. Preemptive scheduling of uniform processor systems. J ACM, 25(1):92-101.
[4]Grigoriu L, Friesen DK, 2017. Approximation for scheduling on uniform nonsimultaneous parallel machines. J Sched, 20(6):593-600.
[5]He Y, 1998. Parametric LPT-bound on parallel machine scheduling with non-simultaneous available time. Asia-Pac J Oper Res, 15(1):29-36.
[6]He Y, 2000. Uniform machine scheduling with machine available constraints. Acta Math Appl Sin, 16(2):122-129.
[7]Horvath EC, Lam S, Sethi R, 1977. A level algorithm for preemptive scheduling. J ACM, 24(1):32-43.
[8]Huo YM, 2019. Parallel machine makespan minimization subject to machine availability and total completion time constraints. J Sched, 22(4):433-447.
[9]Hwang HC, Lim K, 2014. Exact performance of MULTIFIT for nonsimultaneous machines. Discr Appl Math, 167:172-187.
[10]Kaabi J, Harrath Y, 2019. Scheduling on uniform parallel machines with periodic unavailability constraints. Int J Prod Res, 57(1):216-227.
[11]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.
[12]Lee CY, 1991. Parallel machines scheduling with nonsimultaneous machine available time. Discr Appl Math, 30(1):53-61.
[13]Lee CY, Lei L, Pinedo M, 1997. Current trends in deterministic scheduling. Ann Oper Res, 70:1-41.
[14]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.
[15]Liu JWS, Yang AT, 1974. Optimal scheduling of independent tasks on heterogeneous computing systems. Proc ACM Annual Conf, p.38-45.
[16]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.
[17]McNaughton R, 1959. Scheduling with deadlines and loss functions. Manag Sci, 6(1):1-140.
[18]Muntz RR, Coffman EG, 1970. Preemptive scheduling of real-time tasks on multiprocessor systems. J ACM, 17(2):324-338.
[19]Santoro MC, Junqueira L, 2023. Unrelated parallel machine scheduling models with machine availability and eligibility constraints. Comput Ind Eng, 179:109219.
[20]Schmidt G, 1984. Scheduling on semi-identical processors. Z für Oper Res, 28(5):153-162.
[21]Shen LX, Wang D, Wang XY, 2013. Parallel-machine scheduling with non-simultaneous machine available time. Appl Math Model, 37(7):5227-5232.
[22]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.
[23]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.
ORCID: 
Open peer comments: Debate/Discuss/Question/Opinion
<1>