| 有使用限制的二台机器流水作业问题 |
| |
| 引用本文： | 杨名,鲁习文.有使用限制的二台机器流水作业问题[J].运筹学学报,2011,15(3):62-69. |
| |
| 作者姓名： | 杨名 鲁习文 |
| |
| 作者单位： | 华东理工大学理学院数学系,上海,200237 |
| |
| 基金项目： | 上海自然科学基金(09ZR1407200); 国家自然科学基金(11071072) |
| |
| 摘 要： | 本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间，工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形，并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题，给出了一个竞争比为3/2的半在线算法。
|
| 关 键 词： | 竞争比排序 流水作业 使用限制 近似算法 竞争比 |
| 收稿时间： | 2011-05-19 |
| 修稿时间： | 2011-07-12 |
Two-Machine Flow Shop Problems with Availability Constraints |
| |
| YANG Ming,LU Xiwen.Two-Machine Flow Shop Problems with Availability Constraints[J].OR Transactions,2011,15(3):62-69. |
| |
| Authors: | YANG Ming LU Xiwen |
| |
| Institution: | YANG Ming LU Xiwen Department of Mathematics,East China University of Science and Technology,Shanghai 200237,China. |
| |
| Abstract: | This paper investigates the problems for two-machine flow shop scheduling with availability constraints.A resumable scenario is assumed,i.e.,if a job cannot be finished before the interval it is continued after the machine becomes available again.The objective is to minimize the makespan.This paper first considers an approximate case of the problem with several availability constraints on both machines,presents an algorithm with performance ratio of |,then gives an algorithm with competitive ratio of 3/2 fo... |
| |
| Keywords: | scheduling flow shop availability constraint approximation algorithm competitive ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
