关于带运输的单机调度在线问题的研究  

Online single machine scheduling problem with transportation

作　　者：王银玲 韩鑫[2] 邵欣欣[3] WANG Yinling;HAN Xin;SHAO Xinxin(School of Mathematical Sciences,Dalian University of Technology,Dalian 116024,Liaoning,China;School of Software Technology,Dalian University of Technology,Dalian 116024,Liaoning,China;School of Software,Dalian Neusoft University of Information,Dalian 116023,Liaoning,China)

机构地区：[1]大连理工大学数学科学学院 [2]大连理工大学软件学院 [3]大连东软信息学院软件学院

出　　处：《运筹学学报》2022年第1期125-133,共9页Operations Research Transactions

基　　金：国家自然科学基金青年基金(Nos.11701062)。

摘　　要：本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输k个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为√5+1/2的在线算法,并且证明该算法是最优在线算法。This paper studies the single machine online scheduling problem with transporters.The problem assumes that the jobs arrive online over time,and there is only a single transporter in the system,which transports up to k jobs each time.Each job needs to be processed on a single machine,and then transported to the destination by the transporter.The objective of the problem is to minimize the makespan,that is,the shortest time for all jobs to be processed and transported to the destination.For this problem,this paper studies the agreeable model,and proposes an online algorithm with the competitive ratio of √5+1/2 based on the greedy strategy,in the end,the algorithm is proved to be the optimal online algorithm.

关 键 词：运输机 单机调度 在线算法 

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