English

运筹学学报 >

2016 , Vol. 20 >Issue 4: 109 - 114

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.04.013

运筹学

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

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

收稿日期: 2016-02-01

  网络出版日期: 2016-12-15

基金资助

国家自然科学基金(Nos. 11571252, 11401149), 浙江省自然科学基金(No. LY16A010015), 数学天元基金(No. 11526184)

收起

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

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

Received date: 2016-02-01

  Online published: 2016-12-15

Fold

摘要

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

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

本文引用格式

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

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

参考文献

[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.
Options
文章导航

/

〈 〉