同时加工排序问题的分支定界法和启发式算法

摘要

同时加工机器或者称为批加工机器是可以同时加工多个工件的机器.本文研究使带权总完工时间为最小的同时加工排序问题1|B|∑wjCj.这个问题的计算复杂性还没有解决.我们给出这个问题的精确解法一分支定界法和几个启发式算法,并且用较多实例对启发式算法的性能进行了比较.%A batch machine or batching processing machine is one that can process several jobs simultaneously. We study the problem 1|B| ∑wjCj of minimizing the total weighted completion time on a batch machine. The computational complexity of this problem is open. We provide an exact solution procedure-a branch and bound approach and heuristic algorithms for it, and compare the heuristics with considerable instances.