有宽容交货期的加权超前延误工件数问题

• 来源期刊: 深圳大学学报（理工版）
• 学科: 数学
• 关键词: 共同宽容交货期 加权工件 多项式算法 动态规划算法 近似算法 背包问题 超前延误工件
• 年，卷（期）: 2006,（3）
• 所属期刊栏目: 应用数学
• 页码范围: 278-282
• 页数: 5页
• 分类号: O223
• 字数: 3566字
• 语种: 中文

摘要

研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个伪多项式时间动态规划算法,证明其是一般意义下的NP-hard问题.