基于动态规划的分批排序算法

• 作者: 钟雪灵
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 分批排序 截止期限 提前完工时间 动态规划
• 年，卷（期）: 2010,（7）
• 所属期刊栏目: 工程与应用
• 页码范围: 229-231,235
• 页数: 4页
• 分类号: TP301
• 字数: 2873字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.07.070

摘要

研究了在给定截止期限(deadline)下的单机分批(batch)排序问题,目标函数是最大提前完工时间.由于工件不能延迟,因此先讨论了问题可行解的存在.当问题有可行解时,证明了工件按最早截止期限(Earliest Deadline,ED)规则的排序是一个最优排序,接着给出一个时间复杂度为O(n~3)的动态规划算法来获得最优分批.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钟雪灵	暨南大学管理学院	28	93	6.0	9.0