| 目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法 |
| |
| 引用本文： | 李刚刚,鲁习文.目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法[J].运筹与管理,2021,30(5):129-133. |
| |
| 作者姓名： | 李刚刚 鲁习文 |
| |
| 作者单位： | 1.江西财经大学 信息管理学院,江西 南昌 330077;2.华东理工大学 理学院,上海 200237 |
| |
| 基金项目： | 国家自然科学基金资助项目(11901255);江西省教育厅科技项目(GJJ150447) |
| |
| 摘 要： | 本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。
|
| 关 键 词： | 序 柔性维修 算法 性能比 |
| 收稿时间： | 2019-01-13 |
An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan |
| |
| LI Gang-gang,LU Xi-wen.An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan[J].Operations Research and Management Science,2021,30(5):129-133. |
| |
| Authors: | LI Gang-gang LU Xi-wen |
| |
| Institution: | 1. Jiangxi University of Finance and Economics, School of Information Managenent, Nanchang 330077, China;2. East China University of Science and Technology, College of science, Shanghai 200237, China |
| |
| Abstract: | 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. |
| |
| Keywords: | scheduling flexible maintenance algorithm worst-case ratio |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
| 点击此处可从《运筹与管理》下载免费的PDF全文 |
