基于退化效应的两台机器流水作业可拒绝排序

• 作者: 孟凡晓 苗翠霞
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 排序 流水作业 退化效应 可拒绝 NP-难
• 年，卷（期）: 2017,（2）
• 页码范围: 66-72
• 页数: 7页
• 分类号: O223
• 字数: 3672字
• 语种: 中文
• DOI: 10.15960/j.cnki.issn.1007-6093.2017.02.008

摘要

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	苗翠霞	曲阜师范大学数学科学学院	16	45	2.0	6.0
2	孟凡晓	曲阜师范大学数学科学学院	1	2	1.0	1.0