| 带机器准备时间的已知工件总加工时间半在线问题 |
| |
| 引用本文： | 罗润梓,孙世杰,何龙敏.带机器准备时间的已知工件总加工时间半在线问题[J].南昌大学学报(理科版),2010,34(1):1. |
| |
| 作者姓名： | 罗润梓 孙世杰 何龙敏 |
| |
| 作者单位： | 南昌大学数学系； 上海大学数学系； |
| |
| 基金项目： | 江西省自然科学基金资助项目(2007GZS2126) |
| |
| 摘 要： | 考虑带机器准备时间的已知工件总加工时间半在线问题。首先考虑P2,ri|sum|Cmin问题,给出Prsum算法并证明此算法的竞争比为23,且是最优算法;然后考虑Q2,ri|sum|Cmax问题,给出Qrsum算法并证明此算法的竞争比为2,同时给出此问题的一个下界1+3～(1/2)/2。显然Qrsum算法的竞争比与最
|
| 关 键 词： | 排序 竞争比 半在线 |
Semi-online Scheduling Problem with Non-simultaneous Machnie Avaliable Line and Known the Total Size |
| |
| LUO Run-zi,SUN Shi-jie,HE Long-min.Semi-online Scheduling Problem with Non-simultaneous Machnie Avaliable Line and Known the Total Size[J].Journal of Nanchang University(Natural Science),2010,34(1):1. |
| |
| Authors: | LUO Run-zi SUN Shi-jie HE Long-min |
| |
| Institution: | 1.Department of Mathematics/a>;Nanchang University/a>;Nanchang 330031/a>;China/a>;2.Department of Mathematics/a>;Shanghai University/a>;Shanghai 200444/a>;China |
| |
| Abstract: | In this paper,it investigate a semi-online version on two machines with non-simultaneous machine available time where the total processing time of jobs is known in advance.It first consider P2,ri|sum|Cmin problem,we give a Prsum algorithm and prove its competitive ratio is 3/2 which is optimal.Then it consider Q2,ri|sum|Cmax problem,it propose a Qrsum algorithm and prove its competitive ratio is 2~(1/2).It also claim that the lower bound of this problem is 1+3~(1/2)/2.It is obvious that the gap between the ... |
| |
| Keywords: | competitive ratio semi-online scheduling |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《南昌大学学报(理科版)》浏览原始摘要信息 |
| 点击此处可从《南昌大学学报(理科版)》下载免费的PDF全文 |
