| 已知工件总加工时间的两台同类机半在线问题 |
| |
| 引用本文： | 罗润梓,孙世杰.已知工件总加工时间的两台同类机半在线问题[J].哈尔滨工业大学学报,2008,40(5):836-840. |
| |
| 作者姓名： | 罗润梓 孙世杰 |
| |
| 作者单位： | 1. 南昌大学,数学系,南昌,330031
2. 上海大学,数学系,上海,200444 |
| |
| 摘 要： | 研究了已知总加工时间的两台同类机半在线问题.假设工件是分别独立地到达加工机器,并且工件的总加工时间是已知的,目标函数为极大化最小机器负载.将总加工时间标准化后,给出近似算法及其竞争比,并证明此竞争比是紧的.给出此问题竞争比的一个下界1.6180,并由此推出当两台机器的速度比为1.618 0时,算法是最优的,算法的竞争比与最优算法的竞争比之差小于0.089.
|
| 关 键 词： | 同类机 半在线 竞争比 |
| 文章编号： | 0367-6234(2008)05-0836-05 |
| 修稿时间： | 2005年11月21 |
Semi on-line version on two uniform machines with given total processing time of jobs |
| |
| LUO Run-zi,SUN Shi-jie.Semi on-line version on two uniform machines with given total processing time of jobs[J].Journal of Harbin Institute of Technology,2008,40(5):836-840. |
| |
| Authors: | LUO Run-zi SUN Shi-jie |
| |
| Affiliation: | 1.Dept.of Mathematics,Nanchang University,Nanchang 330031,China,2.Dept.of Mathematics,Shanghai University,Shanghai 200444,China) |
| |
| Abstract: | A semi on-line version on two uniform machines with the given total processing time is studied.We are given a sequence of independent jobs with positive processing,which must be assigned to be processed on machines.We assume that the total processing time of jobs is known in advance and our goal is to maximize the minimum workload.By normalizing the total processing time,we present an approximation algorithm and investigate its competitive ratio proved to be tight.A lower bound of 1.618 0 to this problem implies that the approximation algorithm is optimal when the speed ratio of two machines is 1.6180.And the gap between the competitive ratio of the proposed algorithm and that of the optimal value is less than 0.089. |
| |
| Keywords: | uniform machine semi on-line competitive ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
