贪婪算法与最坏性能比分析

• 作者: 时凌
• 来源期刊: 中南民族大学学报(自然科学版)
• 学科: 数学
• 关键词: 自由作业 准备时间 延长时间 最坏性能比 贪婪算法
• 年，卷（期）: 2002,（4）
• 所属期刊栏目: 数学与技术经济科学
• 页码范围: 82-84,87
• 页数: 4页
• 分类号: O223
• 字数: 3784字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-4321.2002.04.025

摘要

研究了具有准备时间和延迟时间的自由作业问题.通过引入虚拟工作,证明该问题是强NP-困难的,提出了解决这个问题的一种方法贪婪算法,并证明了在只有2台机器的情况下,具有准备时间和延迟时间的自由作业问题使用贪婪算法,其最坏性能比是3/2.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	时凌	湖北民族学院数学系	24	20	3.0	3.0