| 带机器准备时间的机器覆盖问题的在线、半在线算法 |
| |
| 引用本文： | 蔡圣义. 带机器准备时间的机器覆盖问题的在线、半在线算法[J]. 高校应用数学学报(A辑), 2007, 22(3): 285-292 |
| |
| 作者姓名： | 蔡圣义 |
| |
| 作者单位： | 温州大学,数学与信息科学学院,浙江温州,325035 |
| |
| 基金项目： | 国家自然科学基金 , 温州师范学院课题经费资助项目 |
| |
| 摘 要： | 研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.
|
| 关 键 词： | 排序问题 在线 半在线 最坏情况界 |
| 文章编号： | 1000-4424（2007）03-0285-08 |
| 收稿时间： | 2005-04-29 |
| 修稿时间： | 2005-04-29 |
Online, semi-online algorithms for machine covering with non-simultaneous machine available time |
| |
| CAI Sheng-yi. Online, semi-online algorithms for machine covering with non-simultaneous machine available time[J]. Applied Mathematics A Journal of Chinese Universities, 2007, 22(3): 285-292 |
| |
| Authors: | CAI Sheng-yi |
| |
| Affiliation: | School of Mathematics 83 Information Science, Wenzhou University, 325035, China |
| |
| Abstract: | The paper considers the parallel machine scheduling problem with non-simultaneous machine available time and the object is to maximize the earliest machine completion time.In on- line version,the worst-case ratio of LS being 1/m is proved,so LS is the optimal algorithm for this problem.Three different semi-online conditions-the largest processing time known in advance,the total processing time known in advance and the jobs ordered in non-increasing processing time are investigated.For each problem the optimal algorithm (worst-case ratio 2/3,2/3,3/4) for two machine case is presented. |
| |
| Keywords: | scheduling online semi-online worst-case ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
