Abstract:Flow shop scheduling where each job can be either processed in-house shop or outsourced to a subcontractor is studied. The jobs in-house are processed in serial batches, i.e., the jobs are processed in batches on the machine in a serial manner and the processing time of a batch is the sum of the processing times of all jobs in the batch. And all the jobs are shipped to customers in batches after processing. Each of the outsourced jobs requires paying an outsourcing cost. The objective is to minimize the sum of the performance measure (the total completion time or the makespan) and transportation cost for in-house jobs, subject to a limit on total outsourcing cost. The transportation cost is proportional to the batch number of jobs. Two special cases where job’s processing time depends solely on job itself or on the machine are considered. In the first case, two approximation algorithms are designed respectively for different performance measures after the NP hardness of the problem and the structure of the optimal solution are analyzed. On the basis of analyzing the solution structure, two polynomial algorithms are proposed in the second case.