Full Text:  <346>

CLC number: 

On-line Access: 2024-08-27

Received: 2023-10-17

Revision Accepted: 2024-05-08

Crosschecked: 0000-00-00

Cited: 0

Clicked: 629

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

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

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

Reference

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE