Abstract: In this paper, we study a single machine scheduling problem with subcontracting options as follows: there are n jobs which are available at time zero. Each job can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted to the subcontractor, its delivery lead time is the same as the in-house processing time, but the processing cost is different from the in-house processing cost. The delivery lead time and processing cost of a subcontracted job is independent of the total workload of the subcontractor. The objective is to minimize the weighted sum of the maximal completion time (which is defined as the larger one of the maximal completion time of the in-house jobs and the maximal delivery lead time of the out-house jobs) and the total processing cost. This problem has been proved to be NP-hard. We first give a pseudo-polynomial time algorithm for this problem, then give an FPTAS.

Key words: scheduling, pseudo-polynomial time algorithm, FPTAS