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

LS algorithm for scheduling three parallel machines with loading and unloading server

作　　者：马春磊 胡觉亮[1] 蒋义伟[1] MA Chunlei;HU Jueliang;JIANG Yiwei(School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China)

机构地区：[1]浙江理工大学理学院

出　　处：《浙江理工大学学报（自然科学版）》2019年第1期122-126,共5页Journal of Zhejiang Sci-Tech University(Natural Sciences)

基　　金：国家自然科学基金项目(11471286,11571013)

摘　　要：针对一个装载服务器和一个卸载服务器的情形,研究三台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP-难问题,因此采用经典的List scheduling(LS)算法进行求解。通过引入块的概念对LS排序的结构进行分析,进而证明了LS算法的最坏情况界至多为17/9。In this paper, the scheduling problem for three parallel machines was studied for the case of one loading server and one unloading server. Before processing, each job needs to be installed on the machine by the loading server. After the processing ends, the unloading server unloads. The loading and unloading time is the unit time. Our goal is to minimize the makespan. Since the problem is NP-hard problem, the classical List scheduling (LS) algorithm is applied to solve it. The structure of LS scheduling is analyzed by introducing the concept of block, Finally, it is shown that the worst-case ratio of LS algorithm is at most 17/9.

关 键 词：平行机排序 服务器 最坏情况界 MAKESPAN LS算法 

分 类 号：O233[理学—运筹学与控制论]