有准备时间的最小带权误工工件数问题的最优解

设有工件集合N={J_1,…,J_n}要在一台机器上加工,已知J_i的准备时间、加工时间、应交工期和权分别为r_i、p_i、d_i和w_i(i=1,…,n)。问如何安排工件的加工顺序,使带权的误工工件数最小? 加工顺序确定了J_i的完工时间C_i(i=1,…,n)。当C_i≤d_i定义U_i=0,否则U_i=1本文假定r_i满足:对于我们的问题记为: (P) 当w_i≡1时,Kise等给出O(n~2)的算法求其最优解。当r_i≡0时该问题已被证明是完全的。Lawler曾用动态规划方法求其最优解。我们对r_i不为零的(P),建立了消去准则,构造了分支定界算法求其最优解,并在微机上进行了试算。