目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法  

An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time

作　　者：李刚刚 鲁习文[2] LI Ganggang;LU Xiwen(School of Information Technology§Jiangxi University of Finance and Economics,Nanchang 330013,China;School of Science,East China University of Science and Technology,Shanghai 200237,China)

机构地区：[1]江西财经大学信息管理学院,南昌330013 [2]华东理工大学理学院,上海200237

出　　处：《运筹学学报》2019年第4期95-104,共10页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11626120,11901255);江西省教育厅科技项目(No.GJJ150447)

摘　　要：单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O(n^3)的近似算法,将性能比从3/2改进到5/4.The single-machine scheduling problem with a period of maintenance to minimize total delivery time has been studied.In this paper,we revisit the problem and propose an algorithm with time complexity of O(n^3)to improve the worst-case ratio from3/2 to 5/4.

关 键 词：排序 运输时间 维修 算法 性能比 

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