带有拒绝工件和机器维修区间的单机排序问题

• 作者: 张敏娇 罗成新
• 来源期刊: 重庆师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 单机排序 维修区间 拒绝工件 NP-难 近似算法
• 年，卷（期）: 2012,（6）
• 所属期刊栏目: 运筹学与控制论
• 页码范围: 15-19
• 分类号: O221.7
• 字数: 3961字
• 语种: 中文

摘要

考虑带有拒绝工件和机器维修区间的单机排序问题.目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和.这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解.为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS).该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O( n2/ε2),其中n为输入工件的个数,ε＞0为任意小的实数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗成新	沈阳师范大学数学与系统科学学院	38	45	4.0	5.0
2	张敏娇	沈阳师范大学数学与系统科学学院	2	7	1.0	2.0