An improved algorithm for a two-stage production scheduling problem with an outsourcing option

被引:4
作者
Jiang, Xiaojuan [1 ]
Zhang, An [2 ]
Chen, Yong [2 ]
Chen, Guangting [3 ]
Lee, Kangbok [1 ]
机构
[1] Pohang Univ Sci & Technol, Dept Ind & Management Engn, Pohang 37673, South Korea
[2] Hangzhou Dianzi Univ, Dept Math, Hangzhou 310018, Peoples R China
[3] Taizhou Univ, Taizhou 317000, Peoples R China
基金
新加坡国家研究基金会; 中国国家自然科学基金;
关键词
Scheduling; Flow shop; Outsourcing; Approximation algorithm; Worst-case analysis; OPTIMIZATION; MANUFACTURER; DECISIONS;
D O I
10.1016/j.tcs.2021.05.022
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页码:59 / 69
页数:11
相关论文
共 21 条
[1]   A Brownian approximation of a production-inventory system with a manufacturer that subcontracts [J].
Bradley, JR .
OPERATIONS RESEARCH, 2004, 52 (05) :765-784
[2]   Competition and outsourcing with scale economies [J].
Cachon, GP ;
Harker, PT .
MANAGEMENT SCIENCE, 2002, 48 (10) :1314-1333
[3]   Optimization of processing and delivery decisions involving third-party machines [J].
Cai, Xiaoqiang ;
Lee, Chung-Yee ;
Vairaktarakis, George L. .
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 2005, 63 (5-7) :E2269-E2278
[4]   The relevance of outsourcing and leagile strategies in performance optimization of an integrated process planning and scheduling model [J].
Chan, F. T. S. ;
Kumar, V. ;
Tiwari, M. K. .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2009, 47 (01) :119-142
[5]   Scheduling with subcontracting options [J].
Chen, Zhi-Long ;
Li, Chung-Lun .
IIE TRANSACTIONS, 2008, 40 (12) :1171-1184
[6]   Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty [J].
Choi, Byung-Cheon ;
Chung, Kwanghun .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 252 (02) :367-375
[7]   Two-machine flow shop scheduling problem with an outsourcing option [J].
Choi, Byung-Cheon ;
Chung, Jibok .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 213 (01) :66-72
[8]   Outsourcing and scheduling for two-machine ordered flow shop scheduling problems [J].
Chung, Dae-Young ;
Choi, Byung-Cheon .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 226 (01) :46-52
[9]   The Longest Processing Time rule for identical parallel machines revisited [J].
Della Croce, Federico ;
Scatamacchia, Rosario .
JOURNAL OF SCHEDULING, 2020, 23 (02) :163-176
[10]   TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION [J].
Gao, Qiang ;
Lu, Xiwen .
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2014, 31 (01)