具有优先权和准备时间的自由作业时间表问题  

Open-shop Scheduling Problem with Release Times and Job Priorities

作　　者：时凌[1] 

机构地区：[1]湖北民族学院数学系,湖北恩施445000

出　　处：《数学的实践与认识》2004年第7期97-101,共5页Mathematics in Practice and Theory

摘　　要：研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 2 -2 /( m +1 ) ,其中 m是机器台数 .对于只有两台机器的情况 ,即当 m =2 时 ,证明该算法的最坏性能比是 4/3 ,并通过实例证明上界是紧的 .The paper presents open-shop scheduling problem with release times and job priorities, we give a simple heuristic and prove that its worst-case performance is 4/3, the bound is tight.

关 键 词：优先权 准备时间 自由作业问题 稠密时间表 启发式算法 最坏性能比 

分 类 号：F224[经济管理—国民经济]