【摘要】 研究了具有优先权的自由作业时间表问题,在工件具有准备时间的条件下,给出一种新的启发式算法,其最坏性能比不超过2,猜想该算法的紧界是2-2/(m+1),其中m是机器的台数.证明在3台机器的情况下,该算法的最坏性能比为3/2,且上界是紧的.更多还原

【Abstract】 This paper considers the open shop scheduling problems with job priorities and release times.For arbitrary number of machines,a simply algorithm can produce a schedule whose make span is at most 2 times of the optimal one in the worst-case in general.However,we conjecture the tight bound is 2-2/(m+1) (m is the number of machines).The worst-case ratio is proved to be 3/2 for m=3,and the bound is tight.更多还原