A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop
提出一种移动瓶颈启发式算法，将作业车间分解为多个单机子问题依次求解，在66个十机十工件实例上接近最优解，优于带回溯的经典调度规则。
We present a shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. The method decomposes the job shop into a number of single-machine subproblems that are solved one after another. Each machine is scheduled according to the solution of its corresponding subproblem. The order in which the single machine subproblems are solved has a significant impact on the quality of the overall solution and on the time required to obtain this solution. We therefore test a number of different orders for solving the subproblems. Computational results on 66 instances with ten jobs and ten machines show that our heuristic yields solutions that are close to optimal, and it clearly outperforms a well-known dispatching rule enhanced with backtracking mechanisms. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 1–17, 1999