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

Open-shop Scheduling Problem with Release Times and Job Priorities

研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 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.