Single Machine Scheduling Problem with Batch Outsourcing

Outsourcing as a useful strategy in the industry can be integrated into scheduling problems. Moreover, batch outsourcing is a practical assumption owing to the logistics issues for transferring the parts between the manufacturer and the subcontractors. However, this assumption is rarely addressed in the scheduling literature. In this paper, a novel single machine scheduling problem with the option of batch outsourcing is studied. The objective is to minimize the sum of the total completion time of the jobs and the total outsourcing cost. To solve the problem, first, two mixed-integer linear programming (MILP) models, named MP۱ and MP۲, are developed, which respectively use a straightforward and an innovative approach to model the outsourcing batches. Next, an optimal property for the outsourcing batches is proven. This property is used to establish a valid inequality for model MP۲, which is added to it to obtain a third MILP model, MP۳. Extensive computational experiments showed that MP۲ outperforms MP۱ significantly. Moreover, including the derived valid inequality in MP۳ enhances its performance considerably in comparing to MP۲. Furthermore, it is observed that MP۳ is capable of solving many practical-size problem instances optimally or with a low maximum optimality gap.

کلیدواژه ها:

Single machine scheduling problem ، Outsourcing ، Subcontracting ، Batch outsourcing ، Total completion time ، mathematical programming