一个带退化工件的单机准时生产制问题

• 作者: 刘静 闵啸
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 单机排序 共同交货期 退化工件 准时 多项式时间算法
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 34-37,45
• 页数: 5页
• 分类号: O223
• 字数: 4812字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2010.01.008

摘要

研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(n log n)时间的最优算法.