论文部分内容阅读
该文考虑下述订单问题:m份订单中共有n个工件需要在同一台机器上加工,这n个工件分属k种不同的类,当机器从加工某一类中的工件转向加工不同于它的第j类工件时,需要一个安装时间Sj,机器加工第一个工件前也有相应于该工件所属类的安装时间.目标是寻找一个使得m份订单的完工时间之和最小的加工顺序.文中根据安装时间、订单完工的定义的不同,分了三种情形,并分别给出了多项式时间算法、分枝定界算法和启发式算法.