We address an analytical scheduling model with subcontracting and delivery. Each job can be scheduled either on a single machine at a manufacturer or outsourced to a subcontractor. For a given set of jobs, the decisions we need to make include the selection of the subset of jobs to be outsourced and the schedule of all the jobs. The objective function in our scheduling model is to minimize the weighted sum of the number of tardy jobs and the total cost. We show our scheduling problem is binary NP-hard, and present a dynamic programming algorithm for it.

scheduling, subcontracting, NP-hard, dynamic programming.