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: Optimal algorithm; Preemptive scheduling; Uniform machine; Non-simultaneous available times

Share this article to： More <<< Previous Paper \|Next 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
%@ 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 -
EP -
%@ 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 that a machine with an earlier available time has a greater speed at any time. Then, we provide an O(nm+m²)-time algorithm to find an optimal schedule with, at most, 0.5(m²+3m)−2 preemptions.

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

Reference

Open peer comments: Debate/Discuss/Question/Opinion

<1>

- Go to

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

Reference