论文部分内容阅读
本文考虑的是有调整时间的多工件组成的产品加工问题：每一产品由若干个工件组成，任一产品的完工时间定义为其所含全部工件完工时的时间，加工一批同类工件前可能需要不同的调整时间.我们主要研究了单机加工条件下，每一产品由m个不同类的普通工件和一个特殊工件组成，仅此m+1个工件均完工时，产品才算完工，而机器每加工一批普通工件前需一固定调整时间.当目标函数是最小化加权完工时间之和时，本文对两种不同加工情况下的三个问题证明了其最优序的结构特点并分别构造了相应有效的动态规划算法.接着对逐个完工条件下的一般加权完工时间之和问题，对各工件权相同和不同两种情况分别给出了近似算法并估计了各自的性能比.