带有装卸服务器的两台平行机调度问题的LS和LPT算法  

LS and LPT Algorithms for Two-Machine Scheduling with a Loading Server and an Unloading Server

作　　者：蒋义伟 周萍[2] 马春磊 JIANG Yiwei;ZHOU Ping;MA Chunlei(School of Management and E-Business,Zhejiang Gongshang University,Hangzhou 310018;College of Humanities,Zhejiang Business College,Hangzhou 310053;School of Sciences,Zhejiang Sci-Tech University,Hangzhou 310018)

机构地区：[1]浙江工商大学管理工程与电子商务学院,杭州310018 [2]浙江商业职业技术学院人文学院,杭州310053 [3]浙江理工大学理学院,杭州310018

出　　处：《系统科学与数学》2019年第8期1276-1286,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金项目(11571013)资助课题

摘　　要：研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.In this paper.we consider two-machine scheduling with a loading server and an unloading server.Each job has to be laded by the loading server before being processed on one of the two machines and unloaded immediately by the unloading server after its processing.The loading and unloading times are both equal to one time unit.Our goal is to find a schedule that minimizes the makespan.Since the problem is NP-hard,we analyze the classical List Scheduling(LS) and Largest Processing Time(LPT) algorithms for the problem.We show that the worst-case ratios of LS and LPT are 11/7 and 7/6,respectively.It is an improvement of the previous results.

关 键 词：调度 服务器 MAKESPAN 算法 最坏情况界 

分 类 号：O1[理学—数学]