| Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system |
| |
| 引用本文： | TAN Zhiyi1,2 & HE Yong1 1. Department of Mathematics,Zhejiang University,Hangzhou 310027,China (email: tanzy@math.zju. edu.cn, heyong@math.zju.edu.cn), 2. State Key Laboratory of CAD & CG,Zhejiang University,Hangzhou 310027,China. Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system[J]. 中国科学F辑(英文版), 2004, 47(2): 161-169. DOI: 10.1360/01yf0571 |
| |
| 作者姓名： | TAN Zhiyi1 2 & HE Yong1 1. Department of Mathematics Zhejiang University Hangzhou 310027 China (email: tanzy@math.zju. edu.cn heyong@math.zju.edu.cn) 2. State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027 China |
| |
| 基金项目： | 国家自然科学基金，中国博士后科学基金 |
| |
| 摘 要： | Consider a resource allocation problem on the following system. A system consists of m identical parallel machines and is alive only when all the machines are alive. To keep a machine alive, it requires resources (material, fuel, etc.). Resources with various sizes arrive one by one and the goal is to keep the system alive as long as possible. The problem has applications in many areas such as sequencing of maintenance actions for modular gas turbine aircraft engines[1]. Using scheduling term…
|
Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system |
| |
| Zhiyi Tan,Yong He. Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system[J]. Science in China(Information Sciences), 2004, 47(2): 161-169. DOI: 10.1360/01yf0571 |
| |
| Authors: | Zhiyi Tan Yong He |
| |
| Affiliation: | 1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China;State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China
2. Department of Mathematics, Zhejiang University, Hangzhou 310027, China |
| |
| Abstract: | Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002. |
| |
| Keywords: | scheduling design and analysis of algorithm worst-case ratio. |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
|
