| 两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题 |
| |
| 引用本文： | 豆俊梅,谷存昌,慕运动.两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题[J].河南科学,2012(10):1414-1418. |
| |
| 作者姓名： | 豆俊梅 谷存昌 慕运动 |
| |
| 作者单位： | 河南工业大学理学院,郑州450001 |
| |
| 基金项目： | 河南省基础与前沿技术研究计划资助项目（082300410070）; 河南省教育厅自然科学研究项目（2011B110007,2011B110008）; 河南工业大学校级科研基金项目（09XJC008;10XZR010） |
| |
| 摘 要： | 研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.
|
| 关 键 词： | 平行机 在线算法 链约束 完工时间平方和 竞争比分析 |
The On-line Scheduling Problem of Unit-length Jobs with Chains Precedence Constraints on Two Parallel Machines to Minimize the Square Sum of the Machine Makespans |
| |
| Dou Junmei,Gu Cunchang,Mu Yundong.The On-line Scheduling Problem of Unit-length Jobs with Chains Precedence Constraints on Two Parallel Machines to Minimize the Square Sum of the Machine Makespans[J].Henan Science,2012(10):1414-1418. |
| |
| Authors: | Dou Junmei Gu Cunchang Mu Yundong |
| |
| Institution: | (College of Science,Henan University of Technology,Zhengzhou 450001,China) |
| |
| Abstract: | In this paper,we study the on-line scheduling problem of unit-length jobs with chains precedence constraints on two parallel processors.The jobs are released at integer times.The objective is to minimize the square sum of the machine makespans.By adversary argument,we prove that the competitive ratio in an arbitrary algorithm is not less than 54,and asymptotically tends to 2 in dense algorithms.Then we give a best possible dense algorithm of the competitive ratio 2. |
| |
| Keywords: | parallel machines on-line algorithm chains precedence constraints the square sum of the machine makespans competitive ratio analysis |
| 本文献已被 维普 等数据库收录！ |
