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

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

研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是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.