Article ID Journal Published Year Pages File Type
478325 European Journal of Operational Research 2013 7 Pages PDF
Abstract

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 j has a processing time requirement pj, and machine i a characteristic qi. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, pj/qi. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{pj, qi} (min{pj, qi}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.

► We consider a two-machine ordered flow shop problem with an outsourcing option. ► An approximation algorithm with the tight worst-case performance bound is presented. ► The special case with pj/qipj/qi is NP-hard. ► The special case with max{pj,qi}{pj,qi} is NP-hard. ► The special case with min{pj,qi}{pj,qi} is polynomially solvable.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,