离散加工时间的可控排序问题(英文)  

Scheduling Problems with Discretely Compressible Processing Times

作　　者：张树霞[1] 曹志刚[2] 张玉忠[2] 

机构地区：[1]华东师范大学数学系 [2]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《运筹学学报》2007年第2期59-64,共6页Operations Research Transactions

基　　金：Project supported by the National Natural Science Foundation(No.10671108) of China.

摘　　要：本文主要研究了离散加工时间的可控排序问题,目标函数是总压缩费用约束下极小化最大完工时间,对单机工件有不同到达时间以及同型机工件到达时间都相同这两个问题,我们设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法．In this paper, we consider the single machine scheduling problem with discretely compressible processing times, the objective is to minimize makespan with the constraint of total compression cost. Jobs may have different release times. We also consider the identical-parallel-machine version with simultaneous release times. We design for the first time pseudo-polynomial time algorithms by approach of dynamic programming and FPTASs.

关 键 词：运筹学 排序 动态规划 离散可控 FPTAS算法 

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