Single machine scheduling with outsourcing allowed

This paper considers a single-machine scheduling problem with outsourcing allowed, where each job can be either processed on an in-house single-machine or outsourced. Outsourcing is commonly required as a way to improve productivity effectively and efficiently in various companies, especially, including electronics industries and motor industries. The objective is to minimize the weighted sum of the outsourcing cost and the scheduling measure represented by the sum of completion times, subject to outsourcing budget. In the problem analysis, it is proved that the proposed problem is NP-hard in the ordinary sense, and some solution properties are characterized. Therewith, two associated heuristic algorithms and the branch-and-bound algorithm are derived.