Abstract: Scheduling with outsourcing is studied in this paper. It is assumed that both manufacturer and subcontractor have a single machine to process n jobs. The manufacturer needs to determine simultaneously a set of outsourced jobs and the schedule of the jobs in-house such that two criterias, i.e., outsourcing cost and production cost, are minimized.The production cost is measured by the number of tardy jobs or the total tardiness of jobs in-house, and the outsourcing cost is proportional to the total processing time of jobs outsourced. Two kinds of problems with different criterias are considered. We analyze the computational complexity and provide pseudo-polynomial time optimization algorithms for the NP-hard version of the problems. 

Key words: scheduling, outsourcing, bicriteria