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

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

Abstract

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

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[6]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[7]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[8]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[9]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[10]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[11]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[12]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.
[13]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.
[14]	JING Caixia, ZHAO Congli, YUAN Erming. A review of re-entrant scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 37-44.
[15]	WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing. Approximation algorithms for the priority facility location problem with submodular penalties [J]. Operations Research Transactions, 2015, 19(2): 1-14.