Two‐machine flow shop scheduling problem with an outsourcing option

Two‐machine flow shop scheduling problem with an outsourcing option

0.00 Avg rating0 Votes
Article ID: iaor20115031
Volume: 213
Issue: 1
Start Page Number: 66
End Page Number: 72
Publication Date: Aug 2011
Journal: European Journal of Operational Research
Authors: ,
Keywords: flow lines, job shop, subcontracting
Abstract:

We consider a two‐machine flow shop problem in which each job is processed through an in‐house system or outsourced to a subcontractor. A schedule is established for the in‐house jobs, and 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 total outsourcing costs. We show that the problem is NP‐hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial‐time algorithm to solve the special case.

Reviews

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