自由作业问题的一种启发式算法及最坏性能比分析

• 作者: 时凌
• 来源期刊: 湖北民族学院学报(自然科学版)
• 学科: 数学
• 关键词: 自由作业问题 准备时间 最坏性能比分析 启发式算法
• 年，卷（期）: 2002,（4）
• 页码范围: 62-65
• 页数: 4页
• 分类号: O223
• 字数: 3147字
• 语种: 中文
• DOI: 10.3969/j.issn.1008-8423.2002.04.017

摘要

研究具有准备时间的自由作业问题,给出一种简单的启发式算法,证明在此启发式算法下,最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.从而证明了对该问题的猜想:即在贪婪算法的情况下其最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.特别当m=2时,具有准备时间的自由作业问题,利用该启发式算法得到的最坏性能比是3/2,其上界也是紧的.

作者信息

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