预先知道工件最大加工时间的带机器费用的排序

• 作 者: 蔡圣义
• 机 构: 温州师范学院数学系
• 出 处: 温州师范学院学报
• 发表日期: 2001年6期
• 关键词: 工件最大加工时间 半在线排序问题 机器费用 算法设计 竞争比 半在线算法 semionlineschedulingmachine costanalysis of

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在