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

• 作者: 蔡圣义
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 排序问题 在线 半在线 最坏情况界
• 年，卷（期）: 2007,（3）
• 页码范围: 285-292
• 页数: 8页
• 分类号: O223
• 字数: 6454字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2007.03.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蔡圣义	温州大学数学与信息科学学院	2	2	1.0	1.0