| 可转包两台流水作业机排序的近似算法 |
| |
| 引用本文： | 陈光亭,陈蕾,张安,陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114. DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.013 |
| |
| 作者姓名： | 陈光亭 陈蕾 张安 陈永 |
| |
| 作者单位： | 1. 杭州电子科技大学理学院, 杭州 310018 |
| |
| 基金项目： | 国家自然科学基金(Nos. 11571252, 11401149), 浙江省自然科学基金(No. LY16A010015), 数学天元基金(No. 11526184) |
| |
| 摘 要： | 研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为frac{3}{2}的改进算法, 以上算法界均为紧界.
|
| 关 键 词： | 可转包 流水作业 近似算法 最坏情况分析 |
| 收稿时间： | 2016-02-01 |
Approximation algorithms for two-machine flow shop scheduling with an outsourcing option |
| |
| CHEN Guangting,CHEN Lei,ZHANG An,CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option[J]. OR Transactions, 2016, 20(4): 109-114. DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.013 |
| |
| Authors: | CHEN Guangting CHEN Lei ZHANG An CHEN Yong |
| |
| Affiliation: | 2. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China |
| |
| Abstract: | The paper investigates flow shop scheduling with an outsourcing option. The objective is to minimize the sum of the in-house cost and the outsourcing cost, where the in-house cost is measured by the maximum completion time of jobs. We design approximation algorithms to solve the problem. For two-machine flow shop, we provide an algorithm with a worst case ratio of 2. For two-machine ordered flow shop, we give an improved algorithm with worst case ratio frac{3}{2}. Both ratios are tight. |
| |
| Keywords: | outsourcing option flow shop approximation algorithm worst case analysis |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
