摘要
本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。
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.
作者
李刚刚
鲁习文
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)
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2021年第5期129-133,共5页
Operations Research and Management Science
基金
国家自然科学基金资助项目(11901255)
江西省教育厅科技项目(GJJ150447)。
关键词
序
柔性维修
算法
性能比
scheduling
flexible maintenance
algorithm
worst-case ratio
