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

Multiple Crane Scheduling with No-Delay Constraints for Machine Unloading

作　　者：谢谢[1] 郑勇跃 

机构地区：[1]沈阳大学装备制造综合自动化重点实验室,辽宁沈阳110044 [2]辽宁省标准化研究院,辽宁沈阳110004

出　　处：《沈阳大学学报（自然科学版）》2017年第2期118-124,共7页Journal of Shenyang University：Natural Science

基　　金：国家自然科学基金资助项目(71672117);辽宁省自然科学基金资助项目(201602526);辽宁省高等学校杰出青年学者成长计划资助项目(LJQ2014133)

摘　　要：针对钢铁企业冷轧阶段罩式退火过程,考虑了一类带有机器卸载不延误约束的多吊机调度问题.给出了避免吊机碰撞和保证机器卸载不延误的一些可行性质.基于这些性质,提出了一个启发式算法,该算法的计算复杂性与吊机、工件和机器的数目有关.同时,给出了问题的一个下界.分别通过理论分析和计算实验,证明了启发式算法的最坏性能和平均性能.Aiming at the problem that arises in the batch annealing process in the cold roiling 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.

关 键 词：罩式退火过程 吊机调度 强NP难 启发式算法 最坏性能分析 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]