自由作业问题的一种启发式算法及最坏性能比分析
时凌
湖北民族学院,理学院,湖北,恩施,445000
摘要：研究具有准备时间的自由作业问题,给出一种简单的启发式算法,证明在此启发式算法下,最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.从而证明了对该问题的猜想:即在贪婪算法的情况下其最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的.特别当m=2时,具有准备时间的自由作业问题,利用该启发式算法得到的最坏性能比是3/2,其上界也是紧的.
关键词：自由作业问题准备时间最坏性能比分析启发式算法
分类号：O223(运筹学)
资助基金：湖北省教育厅指导性项目(2001C04)
论文发表日期：2002-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：4( 62-65 )
英文信息