Outsourcing and scheduling for two‐machine ordered flow shop scheduling problems

Outsourcing and scheduling for two‐machine ordered flow shop scheduling problems

0.00 Avg rating0 Votes
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: ,
Keywords: flowshop, NP-hard, outsourcing
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 p j , and machine i a characteristic q i . 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, p j /q i . 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{p j , q i } (min{p j , q i }). We show that the first and the second cases are NP‐hard and the third case is polynomially solvable.

Reviews

Required fields are marked *. Your email address will not be published.