Job shop scheduling with the option of jobs outsourcing

Incorporating outsourcing in scheduling is addressed by several researchers recently. However, this scope is not investigated thoroughly, particularly in the job shop environment. In this paper, a new job shop scheduling problem is studied with the option of jobs outsourcing. The problem objective is to minimise a weighted sum of makespan and total outsourcing cost. With the aim of solving this problem optimally, two solution approaches of combinatorial optimisation problems, i.e. mathematical programming and constraint programming are examined. Furthermore, two problem relaxation approaches are developed to obtain strong lower bounds for some large scale problems for which the optimality is not proven by the applied solution techniques. Using extensive numerical experiments, the performance of the solution approaches is evaluated. Moreover, the effect the objectives's weights in the objective function on the performance of the solution approaches is also investigated. It is concluded that constraint programming outperforms mathematical programming significantly in proving solution optimality, as it can solve small and medium size problems optimally. Moreover, by solving the relaxed problems, one can obtain good lower bounds for optimal solutions even in some large scale problems.