Article ID: | iaor2013408 |
Volume: | 226 |
Issue: | 1 |
Start Page Number: | 46 |
End Page Number: | 52 |
Publication Date: | Apr 2013 |
Journal: | European Journal of Operational Research |
Authors: | Choi Byung-Cheon, Chung Dae-Young |
Keywords: | flowshop, NP-hard, outsourcing |
This paper considers a two‐machine ordered flow shop problem, where each job is processed through the in‐house system or outsourced to a subcontractor. For in‐house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP‐hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job