可转包两台流水作业机排序的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2016.04.013

运筹学学报

可转包两台流水作业机排序的近似算法

陈光亭¹陈蕾¹张安^1,* 陈永¹

1. 杭州电子科技大学理学院, 杭州 310018

收稿日期:2016-02-01 出版日期:2016-12-15 发布日期:2016-12-15
通讯作者: 张安 anzhang@hdu.edu.cn
基金资助:
国家自然科学基金(Nos. 11571252, 11401149), 浙江省自然科学基金(No. LY16A010015), 数学天元基金(No. 11526184)

Approximation algorithms for two-machine flow shop scheduling with an outsourcing option

CHEN Guangting¹CHEN Lei¹ZHANG An^1,* CHEN Yong¹

2. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China

Received:2016-02-01 Online:2016-12-15 Published:2016-12-15

摘要/Abstract

摘要：

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.

关键词: 可转包, 流水作业, 近似算法, 最坏情况分析

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.

Key words: outsourcing option, flow shop, approximation algorithm, worst case analysis

陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.013.

CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong.

Approximation algorithms for two-machine flow shop scheduling with an outsourcing option

[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.013.

参考文献

[1] Qi X. Outsourcing and production scheduling for a two-stage flow shop [J]. International Journal of Production Economics, 2011, 129: 43-50.

[2] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option [J]. European Journal of Operational Research, 2011, 213: 66-72.

[3] Chung D Y, Choi B C. Outsourcing and scheduling for two-machine ordered flow shop scheduling problems [J]. European Journal of Operational Research, 2013, 226: 46-52.

[4] Lee K, Choi B C. Two-stage production scheduling with an outsourcing option [J]. European Journal of Operational Research, 2011, 213: 489-497.

[5] 陈荣军, 唐国春. 可转包的两机自由作业排序问题 [J]. 数学进展, 2014, 43: 887-894.

[6] Guo X P, Lei D M. Bi-objective job shop scheduling with outsourcing options [J]. International Journal of Production Research, 2014, 52: 3832-3841.

[7] Lei D M, Guo X P. A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options [J]. International Journal of Production Research, 2016, 54: 4793-4804.

[8] Chen Z L, Li C L. Scheduling with subcontracting options [J]. IIE Transactions, 2008, 40: 1171-1182.

[9] Mokhtari H, Abadi I N K. Scheduling with an outsourcing option on both manufacturer and subcontractors [J]. Computers \& Operations Research, 2013, 40: 1234-1242.

[10] Qi X. Coordinated logistics scheduling for in-house production and outsourcing [J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(1): 188-192.

[11] Zhong W Y, Huo Z M. Single machine scheduling problems with subcontracting options [J]. Journal of Combinatorial Optimization, 2013, 26: 489-498.

[12] 仲维亚, 刘晓蕾, 霍志明. 工件可转包加工的排序问题研究 [J]. 运筹学学报, 2012, 16: 121-126.

[13] Johnson S M. Optimal two and three-stage production schedules with set-up times included [J]. Naval Research Logistics Quarterly, 1954, 1, 61-68.

[14] Smith M L, Panwalkar S S, Dudek R A. Flow shop sequencing problem with ordered processing time matrices [J]. Management Science, 1975, 21, 544-549.

[15] Panwalkar S S, Khan A W. An ordered flow shop sequencing problem with mean completion time criterion [J]. International Journal of Production Research, 1976, 14, 631-635.

可转包两台流水作业机排序的近似算法

Approximation algorithms for two-machine flow shop scheduling with an outsourcing option

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[2]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[3]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[4]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[5]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[6]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[7]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[8]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[9]	苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2): 66-72.
[10]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[11]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[12]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[13]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.
[14]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[15]	井彩霞, 赵聪俐, 袁二明. 重入排序问题综述[J]. 运筹学学报, 2015, 19(2): 37-44.