带有装卸服务器的三台平行机排序问题的LS算法

• 作者: 胡觉亮 蒋义伟 马春磊
• 来源期刊: 浙江理工大学学报（自然科学版）
• 学科: 数学
• 关键词: 平行机排序 服务器 最坏情况界 makespan LS算法
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 数学及应用
• 页码范围: 122-126
• 页数: 5页
• 分类号: O233
• 字数: 3171字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-3851(n).2019.01.018

摘要

针对一个装载服务器和一个卸载服务器的情形, 研究三台平行机上的排序问题.每个工件在加工前需要由装载服务器安装到机器上, 加工结束后由卸载服务器进行卸载.装载和卸载时间均为单位时间, 目标是极小化最大完工时间.该问题是NP-难问题, 因此采用经典的List scheduling (LS) 算法进行求解.通过引入块的概念对LS排序的结构进行分析, 进而证明了LS算法的最坏情况界至多为17/9.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡觉亮	浙江理工大学理学院	81	456	12.0	17.0
2	蒋义伟	浙江理工大学理学院	19	25	3.0	4.0
3	马春磊	浙江理工大学理学院	3	0	0.0	0.0