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

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

以钢铁企业原料码头为背景,对桥式吊机调度问题进行了分组调度以最小化被吊集装箱运输完成的总时间.在原料码头,对于给定客户需求的一组集装箱,桥式吊机需要负责从原位置取出,再决策集装箱的运输顺序以最小化集装箱的总完工时间.针对这个问题首先通过二划分的归结证明了问题是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.