-
题名离散加工时间的可控排序问题(英文)
被引量：4
- 1
-
-
作者
张树霞
曹志刚
张玉忠
-
机构
华东师范大学数学系
曲阜师范大学运筹与管理学院
-
出处
《运筹学学报》
CSCD
北大核心
2007年第2期59-64,共6页
-
基金
Project supported by the National Natural Science Foundation(No.10671108) of China.
-
文摘
本文主要研究了离散加工时间的可控排序问题,目标函数是总压缩费用约束下极小化最大完工时间,对单机工件有不同到达时间以及同型机工件到达时间都相同这两个问题,我们设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法．
-
关键词
运筹学
排序
动态规划
离散可控
fptas算法
-
Keywords
Operations research, scheduling, dynamic programming, discretely compressible processing times, fptas
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名时间一致时极小化工件配送时间的近似算法
- 2
-
-
作者
唐庆晨
-
机构
济宁学院数学系
-
出处
《济宁学院学报》
2008年第6期31-34,共4页
-
文摘
本文主要研究了平行机上时间一致时极小化工件配送时间的分批排序问题,该问题是传统的分批排序与当代的物流相结合而产生的一类新的问题.一般情况下当工件有不同的到达时间时该问题是强NP—难的,但对工件有有限个到达时间及机器台数有限时,若所有的输入数据均为整数,本文给出了问题的伪多项式时间算法,从而说明了在这种情况下问题不是强NP—难的.当输入数据是有理数时,本文给出了问题的FPTAS算法.并给出了时间一致时一般情形的PTAS算法.
-
关键词
配送时间
近似算法
fptas算法
PTAS算法
平行机
-
Keywords
delivery time
approximation algorithm
fptas algorithm
PTAS algorithm
parallel machines
-
分类号
O223
[理学—运筹学与控制论]
-
