| 预先知道工件最大加工时间的带机器费用的排序 |
| |
| 引用本文： | 蔡圣义.预先知道工件最大加工时间的带机器费用的排序[J].温州大学学报(自然科学版),2001,22(6):4-7. |
| |
| 作者姓名： | 蔡圣义 |
| |
| 作者单位： | 温州师范学院数学系 浙江温州325003 |
| |
| 摘 要： | 对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。
|
| 关 键 词： | 工件最大加工时间 半在线排序问题 机器费用 算法设计 竞争比 半在线算法 |
Semi-online Scheduling with Machine Cost |
| |
| CAI Sheng,yi.Semi-online Scheduling with Machine Cost[J].Journal of Wenzhou University Natural Science,2001,22(6):4-7. |
| |
| Authors: | CAI Sheng yi |
| |
| Institution: | Department of Mathematics |
| |
| Abstract: | |
| |
| Keywords: | semi online scheduling machine cost analysis of algorithm competitive ratio |
| 本文献已被 CNKI 维普 等数据库收录！ |
