目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法  

An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan

作　　者：李刚刚 鲁习文[2] LI Gang-gang;LU Xi-wen(Jiangxi University of Finance and Economics,School of Information Managenent,Nanchang 330077,China;East China University of Science and Technology,College of science,Shanghai 200237,China)

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

出　　处：《运筹与管理》2021年第5期129-133,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(11901255);江西省教育厅科技项目(GJJ150447)。

摘　　要：本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。This paper considers a two-machine scheduling problem with flexible maintenance with the objective to minimize makespan.In the scheduling model,the first machine needs maintenance during a fixed period,while the other one is available all the time.Preemption is not allowed.We provide an approximation algorithm with worst-case ratio ofand show that the worst-case ratio is tight.

关 键 词：序 柔性维修 算法 性能比 

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