Full Text:   <537>

Summary:  <3>

CLC number: 

On-line Access: 2024-08-27

Received: 2023-10-17

Revision Accepted: 2024-05-08

Crosschecked: 0000-00-00

Cited: 0

Clicked: 886

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE C 1998 Vol.-1 No.-1 P.

http://doi.org/10.1631/FITEE.2300767


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


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.

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

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

关键词:最优算法;可中断调度;同类机;非同时可用时间

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

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 - 2025 Journal of Zhejiang University-SCIENCE