论文部分内容阅读
研究钢管加工流程中一类新型两台机器流水车间调度问题,工件在第一台机器上加工后被分解成多个子工件.对于最小化最大完成时间的情况,给出一个多项式时间的最优算法;对于最小化最大完成时间与惩罚费用之和的情况,给出一个拟多项式时间的动态规划算法;对于考虑生产前运输的最小化最大完成时间的情况,分析了问题的复杂性.证明了第一种情况的最优算法可作为后两种情况的2-近似算法.数值实验表明了算法的有效性.
In this paper, a new type of two-machine flowshop scheduling problem in steel pipe processing is studied, and the work piece is decomposed into many sub-workpieces after the first machine is machined.To minimize the maximum completion time, an optimal polynomial time algorithm ; For the case of minimizing the sum of the maximum completion time and the penalty cost, a dynamic programming algorithm for the quasi-polynomial time is given, and the complexity of the problem is analyzed for considering the minimization maximum completion time of the pre-production transportation. The optimal algorithm of a situation can be used as the 2-approximation algorithm of the latter two cases. Numerical experiments show the effectiveness of the algorithm.