罩式退火过程中的多吊机调度问题

Multi-Crane Scheduling in Batch Annealing Process

研究了钢铁企业罩式退火中的多吊机调度问题,目标函数是最小化最后一个板卷的退火完工时间.通过考虑机器和吊机位置,建立了混合整数规划模型,并提出了一种整合的方法以降低问题的难度同时保持问题的本质.然而,即使是整合后的问题也是强NP难的.进一步提出了包括分配和调度的两阶段启发式算法.在分配阶段,利用动态规划先将每个吊机分配给唯一的子区块,再进行机器的分配.调度阶段采用最早需要操作阶段优先的策略.最后,算法的有效性通过绝对性能分析的角度给出了估测.

A multi-crane scheduling problem was addressed,which is motivated by batch annealing process（BAP） in the iron and steel factory.The objective is to minimize the last coil annealing completion time（makespan）.A mixed-integer linear programming（MILP） model is formulated by considering both positions of bases and cranes.Afterwards,an aggregate approach is proposed to reduce problem difficulty but keep the essential features of practical problem.However,the aggregated problem is still proofed strongly NP-hard.A two-phase heuristic algorithm is proposed,which consists of assignment and scheduling.The assignment phase based on a dynamic programming is to assign each crane to its exclusive sub-region,followed by a resource assignment to each sub-region.Scheduling phase adopts an earliest requirement performed stage first strategy.Finally,from an absolute performance point of view,the quality of the proposed heuristic is measured.