一类带外包选择的单机排序问题

Single Machine Scheduling with Subcontracting Options

研究了一类带外包选择的单机排序问题.假设仅有一台本地机器和一个外包承包商,每个工件既可以在本地机器上加工又可以外包商处加工.本地加工的费用为总误工工件数,外包加工的费用与外包工件有关.对于极小化总加工费用这一NP难问题,给出伪多项式时间动态规划算法.如果外包费用正比于外包工件的加工时间,设计出近似算法并给出最坏情况分析.

This paper studies single-machine scheduling with subcontracting options. There is a single machine in-house and only one subcontractor. Each job can either be scheduled in-house or be subcontracted. The production cost on the in-house machine is measured by the number of tardy jobs, while the outsourcing cost is determined by the subcontracted jobs. The problem of minimizing the total cost is NP-hard. It gives a pseudo-polynomial time algorithm based on the dynamic programming method. Moreover, if the outsoureing cost is proportional to the total processing time of subcontracted jobs, then an approximation algorithm with worst case analysis is designed.