原料码头桥式吊机调度的分组与算法  

Heuristic Algorithm for Solving Bridge Crane Scheduling by Using Crane in Group Arising in Raw Material Terminal

作　　者：谢谢[1] 郑勇跃 张欣[2] 李晓丽 XIE Xie;ZHENG Yongyue;ZHANG Xin;LI Xiaoli(Key Laboratory of Manufacturing Industrial and Integrated Automation,Shenyang University,Shenyang 110044,China;Logistics Management Service Centre,Shenyang University,Shenyang 110044,China;Center of Career Development,Liaoning Inspection,Examination&Certification Centre,Shenyang 110032,China;Vocational High School,Shuangliao 136400,China)

机构地区：[1]沈阳大学装备制造综合自动化重点实验室,辽宁沈阳110044 [2]沈阳大学后勤管理服务中心,辽宁沈阳110044 [3]辽宁省检验检测认证中心事业发展中心,辽宁沈阳110032 [4]吉林省双辽市职业高级中学,吉林双辽136400

出　　处：《沈阳大学学报（自然科学版）》2021年第5期391-395,共5页Journal of Shenyang University：Natural Science

基　　金：国家自然科学基金资助项目(71672117);辽宁省自然科学基金资助项目(2020-BS-263).

摘　　要：以钢铁企业原料码头为背景,对桥式吊机调度问题进行了分组调度以最小化被吊集装箱运输完成的总时间.在原料码头,对于给定客户需求的一组集装箱,桥式吊机需要负责从原位置取出,再决策集装箱的运输顺序以最小化集装箱的总完工时间.针对这个问题首先通过二划分的归结证明了问题是NP难的.进一步分析了问题的最优性质,根据问题的性质设计了一个基于吊机分组的启发式算法.为评价启发式算法的性能,提出了有效的下界,通过计算实验验证了该启发式算法的有效性.Taking the raw material terminal of iron and steel enterprises as the background,the bridge crane scheduling problem was grouped and scheduled to minimize the total time for the completion of the transportation of the hoisted container.At the raw material terminal,for a set of containers for a given customer demand,the bridge crane needs to be responsible for taking out from the original location,and then decide the transportation order of the containers to minimize the total completion time of the containers.To solve this problem,it was proved that the problem is NP-hard by the resolution of two partitions.The optimal nature of the problem was further analyzed,and a heuristic algorithm based on crane grouping was designed according to the nature of the problem.In order to evaluate the performance of the heuristic algorithm,an effective lower bound was proposed,and the effectiveness of the heuristic algorithm was verified through computational experiments.

关 键 词：钢铁企业 吊机调度 NP难 启发式算法 分组 

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