Full Text:
<316>
CLC number:
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 0000-00-00
Cited: 0
Clicked: 562
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, 1998, -1(-1): .
@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="-1",
number="-1",
pages="",
year="1998",
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 Journal of Zhejiang University SCIENCE C
%V -1
%N -1
%P
%@ 2095-9184
%D 1998
%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 - Journal of Zhejiang University Science C
VL - -1
IS - -1
SP -
EP -
%@ 2095-9184
Y1 - 1998
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 that a machine with an earlier available time has a greater speed at any time. Then, we provide an O(nm+m2)-time algorithm to find an optimal schedule with, at most, 0.5(m2+3m)−2 preemptions.
Open peer comments: Debate/Discuss/Question/Opinion
<1>