工件可转包加工的排序问题研究  

A Single Machine Scheduling Problem with Subcontracting Options

作　　者：仲维亚[1] 刘晓蕾[1] 霍志明[1] 

机构地区：[1]上海大学理学院数学系,上海200444

出　　处：《运筹学学报》2012年第1期121-126,共6页Operations Research Transactions

基　　金：上海市教委重点学科(S30104)资助课题

摘　　要：研究工件可以转包加工的单台机排序问题:有n个工件,在零时刻已经到达一个单台机处,每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工.如果工件被转包加工,那么其完工时间等于在自有机器上的加工时间,而产生的加工费用与在自有机器上加工的费用不同.假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和.该问题已经被证明是NP-难的.最后给出该问题的伪多项式时间最优算法,并且提出一个完全多项式时间近似方案(FPTAS).In this paper, we study a single machine scheduling problem with sub- contracting 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.

关 键 词：排序 伪多项式时间最优算法 FPTAS 

分 类 号：O223[理学—运筹学与控制论]