| 具有预约到达时间的平行机在线排序问题研究 |
| |
| 引用本文： | 张显东,吴克文,王锦. 具有预约到达时间的平行机在线排序问题研究[J]. 复旦学报(自然科学版), 2009, 48(6): 708-712 |
| |
| 作者姓名： | 张显东 吴克文 王锦 |
| |
| 作者单位： | 复旦大学管理学院,上海,200433;复旦大学管理学院,上海,200433;复旦大学管理学院,上海,200433 |
| |
| 基金项目： | 国家自然科学基金重点资助项目(70432001) |
| |
| 摘 要： | 以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.
|
| 关 键 词： | 在线排序 平行机排序 预约到达时间 最迟完工时间 |
On-line Scheduling of Jobs with Order Arrival Time and Hard Deadline on Two Parallel Identical Machines |
| |
| ZHANG Xian-dong,WU Ke-wen,WANG Jin. On-line Scheduling of Jobs with Order Arrival Time and Hard Deadline on Two Parallel Identical Machines[J]. Journal of Fudan University(Natural Science), 2009, 48(6): 708-712 |
| |
| Authors: | ZHANG Xian-dong WU Ke-wen WANG Jin |
| |
| Affiliation: | ZHANG Xian-dong,WU Ke-wen,WANG Jin(School of Management,Fudan University,Shanghai 200433,China) |
| |
| Abstract: | On-line scheduling of independent jobs with order arrival time and hard deadlines is an extension of traditional on-line scheduling problems.Based on real booking systems in modern service industry,on-line scheduling of independent jobs with arbitrary order arrival time,job release times and hard deadlines on two parallel identical machines is studied.The upper bound of competitive ratios of on-line algorithms for the two-machine case is analyzed.An on-line greedy algorithm with a competitive ratio of 3 is ... |
| |
| Keywords: | on-line scheduling parallel machine arbitrary release time hard deadline |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
