考虑工件可以转包的两机流水作业排序问题, 假设转包费用有一个上限, 极小化未转包工件最大完工时间或未转包工件总完工时间与转包费用之和, 分析问题的 复杂性并设计拟多项式时间算法.

In this paper, two-machine flow shop scheduling model with outsourcing is considered. In the model, the outsourcing cost has an upper bound which is not permitted to exceed. Two kind of objectives are studied, i.e., minimizing the makespan of the jobs in-house, and minimizing the sum of total weighted completion times and the transportation cost of in-house jobs. For the model with different objectives, we analyze the complexity and design pseudo-polynomial algorithms.