JZUS - Journal of Zhejiang University SCIENCE

Frontiers of Information Technology & Electronic Engineering

Accepted manuscript available online (unedited version)

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

Author(s): Hao ZHOU, Liping CAO, Qi WEI, Zhenyu SHU, Yiwei JIANG
Affiliation(s): College of Basic Science, Zhejiang Shuren University, Hangzhou 310015, China; more
Corresponding email(s): zhouhao@zjsru.edu.cn, ywjiang@zjgsu.edu.cn
Key Words:

Share this article to： More <<< Previous Paper \|

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,in press.https://doi.org/10.1631/FITEE.2300767

@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",
year="in press",
publisher="Zhejiang University Press & Springer",
doi="https://doi.org/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
%P 472-478
%@ 2095-9184
%D in press
%I Zhejiang University Press & Springer
doi="https://doi.org/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
SP - 472
EP - 478
%@ 2095-9184
Y1 - in press
PB - Zhejiang University Press & Springer
ER -
doi="https://doi.org/10.1631/FITEE.2300767"

Abstract
Chinese Summary
Academic Network
Reviewer Comment

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+m²) to find an optimal schedule with, at most, (m²+3m/ 2−2 preemptions, where n is the number of jobs.

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

周昊¹，曹丽萍²，魏麒³，舒振宇⁴，蒋义伟²
¹浙江树人学院基础学院，中国杭州市，310015
²浙江工商大学管理工程与电子商务学院，中国杭州市，310018
³宁波财经学院国际经济贸易学院，中国宁波市，315175
⁴浙大宁波理工学院计算机与数据工程学院，中国宁波市，315100
摘要：研究了m台可用时间不同的同类机可中断调度问题，目标是极小化最大完工时间。每台机器都有一个不同的加工速度和可用时间。通过将真实机器转化成虚拟机器的方法给出最优调度目标值的下界。在这些虚拟机器中，可用时间越早的机器在任何时候都有更快的速度。对该问题，给出一个时间复杂度为O(nm+m²)的最优调度算法，并且该算法的中断次数不超过（n代表工件数量）。

关键词组：最优算法；可中断调度；同类机；非同时可用时间

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

- Go to

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

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference