带有机器卸载不延误约束的多吊机调度问题

摘要

Aiming at the problem that arises in the batch annealing process in the cold rolling stage of steel production, a multiple crane scheduling problem with no-delay constraints for machine unloading is studied.Some feasible properties are identified to avoid crane collisions and guarantee machine unloading no-delay constraints.Based on these necessary conditions, a heuristic algorithm with running time in connection with the number of cranes, coils and machines is presented.A lower bound to the problem is also developed.Through the theoretically analysis and computational experiments, the worst case bound and the average performance of the heuristic algorithm are proved.%针对钢铁企业冷轧阶段罩式退火过程,考虑了一类带有机器卸载不延误约束的多吊机调度问题.给出了避免吊机碰撞和保证机器卸载不延误的一些可行性质.基于这些性质,提出了一个启发式算法,该算法的计算复杂性与吊机、工件和机器的数目有关.同时,给出了问题的一个下界.分别通过理论分析和计算实验,证明了启发式算法的最坏性能和平均性能.