一类新型批处理机调度问题的理论分析

钢卷在冷轧生产中,为了改进其性能,需要在罩式炉进行退火,退火过程由加热、保温和降温三段组成,而这三段处理时间由于工艺上的要求不能归结为一个时间,这与传统批处理机调度有明显的差别.对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型,开发了基于动态规划的启发式算法.通过理论分析,获得该算法的误差性能比为3.对于三段中的某一段板卷的处理时间相同的情况,证明了启发式算法的误差性能比是2,而且证明是紧界.对于三段中的某二段板卷的处理时间相同的情况,证明了启发式算法是最优算法.对启发式算法扩展到带有任意段的加工时间的一般情况进行了性能分析.

Theoretical analysis of scheduling of a new batching machine

The processing time of the steel coils,which are to be processed in the bell type annealing furnace to improve quality,is composed of three operations steps,that is,heating,keeping and lowering temperature.The three-step processing of the jobs cannot be regarded as a whole process or three independent processes for technical reasons,and is different from the classical batching machine.An integer nonlinear programming is proposed and a heuristic algorithm based on dynamic programming is applied to the total weighted completion time for the new batching machine.The worst case performance of the heuristic algorithm is proved to be at most 3.If any two steps’ processing times are the same,the heuristic algorithm can obtain the optimal solution.If any one step’s processing time of all the jobs is the same,the worst performance of the heuristic algorithm is proved to be at most 2 and the bound is tight.We also analyze the worst case of the heuristic algorithm for the general case where jobs processing are composed of any step-processing.