Optimization of processing and delivery decisions involving third-party machines

We are concerned with a problem where a manufacturer has to complete a number of orders received from the customers. Due to the capacity limit, the manufacturer has to subcontract a certain set of jobs to a third party for processing. We investigate the model that involves two machines, with one being a machine owned by the manufacturer and the other by the third party. The available time slot (i.e., the shift) on the third-party machine each day is extendable, at an extra cost. Transportation time to have a job processed by the third-party machine is also considered. The objective is to minimize the total cost, including the lateness cost, the cost to use the third-party machine, and the overtime cost. This is shown to be an integer nonlinear optimization problem, which is NP-hard. Properties on this model are obtained. Algorithms to find optimal solutions are developed. (C) 2005 Elsevier Ltd. All rights reserved.