带机器准备时间的机器覆盖问题的在线、半在线算法

摘要：

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.

关键词：排序问题、在线、半在线、最坏情况界

所属期刊栏目：22

分类号：O223(运筹学)

资助基金：国家自然科学基金10271110;60674071;温州师范学院课题经费资助项目2001Z06

在线出版日期：2007-10-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：285-292