|
|
Frontiers of Information Technology & Electronic Engineering
ISSN 2095-9184 (print), ISSN 2095-9230 (online)
2025 Vol.26 No.3 P.472-478
An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines
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.
Key words:
1浙江树人学院基础学院，中国杭州市，310015
2浙江工商大学管理工程与电子商务学院，中国杭州市，310018
3宁波财经学院国际经济贸易学院，中国宁波市，315175
4浙大宁波理工学院计算机与数据工程学院，中国宁波市，315100
摘要：研究了m台可用时间不同的同类机可中断调度问题，目标是极小化最大完工时间。每台机器都有一个不同的加工速度和可用时间。通过将真实机器转化成虚拟机器的方法给出最优调度目标值的下界。在这些虚拟机器中，可用时间越早的机器在任何时候都有更快的速度。对该问题，给出一个时间复杂度为O(nm+m2)的最优调度算法，并且该算法的中断次数不超过（n代表工件数量）。
关键词组：
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/FITEE.2300767
CLC number:
Download Full Text:
Downloaded:
636
Download summary:
<Click Here>Downloaded:
30Clicked:
959
Cited:
0
On-line Access:
2025-04-03
Received:
2023-11-09
Revision Accepted:
2024-03-29
Crosschecked:
2025-04-07