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

谢 谢, 郑勇跃, 张 欣, 李晓丽

(1. 沈阳大学 a. 装备制造综合自动化重点实验室, b. 后勤管理服务中心, 辽宁 沈阳 110044;2. 辽宁省检验检测认证中心 事业发展中心, 辽宁 沈阳 110032;3. 吉林省双辽市职业高级中学, 吉林 双辽 136400)

钢铁工业是经济发展的关键基础,钢铁加工是钢铁工业全过程的核心.钢铁工业的生产和运作直接决定了生产的费用、运作效率以及钢铁生产过程的质量.高温融化的钢铁、钢包及大量附属的原料和产品都经由皮带、台车和吊机运输.有效的吊机调度是确保流畅、高效生产以及稳定生产节奏的基础.吊机调度作为多个不同过程之间的运输环节,直接影响高温液态钢水运输的时间和状态的稳定.因此,从原料码头开始,高效的吊机调度,即确定吊机的操作顺序,是避免不必要的延迟的关键.原料码头中,到港轮船一侧的吊机安装在相同的轨道上,彼此之间相互干扰,但是,在两侧的吊机可以自由地相互交叉,见图1.

图1 原料码头吊机操作示意图Fig.1 Schematic diagram of crane operation of raw material terminal

原料码头的吊机调度问题不仅出现在钢铁企业内,集装箱港口码头也会遇到类似的调度问题,在集装箱港口码头使用的吊机称为龙门吊,该吊机是铁路和铁路之间以及铁路和公路之间集装箱的重要转运工具,集装箱在火车和火车以及卡车和火车之间的运输都由它们负责[1].无论是集装箱码头的龙门吊还是钢铁企业原料码头的吊机,通常安装在场地的两侧,每台吊机由两个吊钩组成,一个安装在另一个之上,吊钩之间可以独立操作,但彼此不交叉.

1 问题的定义和描述

给定M个吊机,吊机布局在集装箱位置的两侧,吊机分为两个不同的子集L={l1,…,lm}和R={r1,…,rk},L∪R=M,每个集合的吊机都从左到右排列.可行的调度至少包括以下几点:一个吊机每次只能操作一个集装箱,每个吊机至少处理一个区域,两个吊机不能同时处理一个区域,相同集合内的吊机不能交叉.不失一般性,假设每台吊机的运输能力和倒垛能力都相同.两台卡车分别位于区域的两端.

2 复杂性分析

本节证明所研究的问题是一般意义NP难的.常用的方法是对此问题构造一个实例,再通过把一个已知的二划分问题归约到这个构造的实例来实现证明.

引理1 本文所研究的问题是一般意义NP难.

证明 由二划分问题归约得到.构造的调度例子如下:两台吊机L={l1}和R={r1}.因为两个吊机不互相干扰,可以进行平等分区.对于每个整数a∈A,我们设定一个区域s∈S(S={1,…,|A|}),负载WS=a,∀a∈A.

2007年，农场的主干渠修成了水泥U型渠，干渠各出水口有了小闸门，主渠换水时方便又省劲。但田间土渠还得拦水打坝，雨靴还是父亲浇水最好的伴侣。

如果二划分问题有解,易证调度可行,且目标函数值为a/2,不超过门槛值.

如果二划分问题无解,必有函数值大于门槛值,即必存在某个吊机的工作量超过平均值,从而使得函数值大于门槛值.

以往对多吊机调度问题的研究多集中在优化吊机之间的避让,有效地协调多吊机之间的操作,减少集装箱及吊机之间的等待时间,而精细化的吊机之间的操作以减少避让,增加了算法的运行时间,此外,吊机在原料码头对集装箱这类大型物件实际的操作过程中,对每台吊机操作的细节很难具体地实施,本文从平衡集装箱任务量的角度,将一侧相邻两吊机间的操作看作平行机操作,定义为挪动吊机;另一侧的一台吊机定义为运输吊机;即每三台吊机作为一组.这样避免了吊机之间为保证安全距离而带来的不必要的等待.分组决策的吊机调度可以有效地利用吊机,将传统的生产与物流运输集成决策的的思想引入调度过程,可以提高生产率.

3 问题的性质及启发式算法

3.1 问题的性质

性质1 在已有吊机分组下存在一个最优调度满足:任意一个吊机、集装箱都没有空闲.

性质2 在已有吊机分组下存在一个最优调度满足:集装箱被吊机运输的出发时间或者是在集装箱区域内挪动完成时间,或者是在吊机的可利用的时间.

性质3 在已有吊机分组下存在一个最优调度满足:①分配给同一个挪动吊机的集装箱按照挪动时间非降(SPT规则)排序;②分配给运输吊机的集装箱按照挪动完成的时间非降排序.

证明 ①通过相邻的集装箱交换得证;②按照集装箱被挪动完成的时间进行重新排序,满足c1≤c2≤…≤cn.不失一般性,假设集装箱k,k+1∈S并且满足ck≤ck+1.根据问题描述可知,sk+1≥sk+T.现将集装箱k+1安排在集装箱k后运输,其余集装箱保持不变.显然,目标函数值至少减少T.因此,分配给运输吊机的集装箱按照挪动完成的时间非降排序.

由以上性质可知,当运输吊机可利用时,它或者立刻开始运输集装箱,或者等待集装箱倒垛完成.因此,每一个运输集装箱的出发时间需要决策、运输集装箱的顺序也是需要决策的.

3.2 启发式算法

第1步 吊机分组.左侧吊机按照一台运输吊机和两台倒垛吊机的模式划分.右侧吊机按照两台倒垛吊机和一台运输吊机的模式划分.即将左侧第一台吊机作为运输吊机、与右侧作为倒垛吊机的第一、二台吊机分为一组.左侧第二、三台倒垛吊机与右侧第三台运输吊机分为一组.以此类推.左右两侧最后剩余的吊机作为一组.如果左右各剩余一台吊机即一台作为倒垛吊机一台作为运输吊机.同一侧剩余吊机仅作为运输吊机使用,将分成的组数使用|G|表示.

第2步 在每组中,按照SPT规则首先对分配给同一吊机的倒垛集装箱进行排序,满足p1≤p2≤…≤pn,计算挪动完成时间并按照非降的顺序c1≤c2≤…≤cn排列.

第3步 计算每一组内集装箱运输的开始时间sj,进一步计算出集装箱j到达卡车的时间Cj=sj+tj.

定理1 在吊机分组确定时,已知集装箱在吊机上的倒垛顺序与运输顺序,启发式算法能够在O(n4)时间内产生最优调度.其中运输的出发时间sj计算次数至多为O(n2).

4 结 果

为了评估启发式算法的性能,在本节中进行数值计算实验.启发式算法使用VC++6.0编程,在Pentium-Ⅳ的PC机上运行,操作系统是Windows XP,CPU是2.40 GHz,内存为1 GB.

依据钢铁企业码头的实际情况,随机产生的实例参数如下.

集装箱数量n:10, 20, 30, 50, 80, 100;

左右两侧吊机的数目L和R:从[1, 10]的均匀分布中产生;

集装箱原地挪动时间pj:从[1, 10]的均匀分布中产生;

集装箱的运输开始时间和运输时间sj和tj:从[1, 10]和[1, 20]的均匀分布中产生.

实验结果如表1所示.在表1中误差比r的平均值和最大值分别定义为avg(r)和max(r),其中r的平均值表示启发式算法对这12组实例的平均运行情况,而最大值则表示其最坏运行情况.使用Avg.CPU表示每一组的平均计算时间.

表1 启发式实验结果Table 1 Results of heuristic experiment

从计算结果可以看出以下几点.

1) 当L=3,R=5或L=5,R=3时,随着问题规模的增大算法的平均误差比avg(r)和最大误差比max(r)减小,而当L=5,R=3时,算法的avg(r)和max(r)比L=3,R=5时更小,可能由于算法在L=5,R=3时吊机的分组多余了2台运输吊机,减少了倒垛后集装箱的等待时间.

2) 类似地,当L=4,R=7或L=7,R=4时,随着问题规模的增大算法的平均误差比avg(r)和最大误差比max(r)减小,然而比起情况1)时,算法的avg(r)和max(r)有所增大,由于左右两侧吊机的数目较大,剩余未被分组的吊机经常处于空闲状态或使得集装箱发生不必要的等待.

3) 随着吊机数目的增加,吊机的分组也越来越多,当L=6,R=8或L=8,R=6时,可分为完整的4组时,比起情况1)中的不完整的4组,算法的avg(r)和max(r)减小,说明吊机分组操作集装箱比起不分组的调度更有效率.而实际港口码头集装箱数目需要调度的数目不会超过100,对于小规模实例,算法可以迅速获得问题的解.对于较大规模的问题,算法的计算时间也不超过1s.因此计算的实验结果表明:本文提出的启发式算法可以在很短时间内求出问题的近优解.

5 结 论

本文针对原料码头的集装箱调度问题提出了一个吊机分组的启发式算法,首先通过二划分的归结证明了问题是NP难的.进一步分析了问题的最优性质,基于最优性质提出了基于吊机分组的启发式算法.为评价启发式算法的性能,提出了有效的下界,通过实验结果验证启发式算法的有效性.有关吊机的分组决策再调度未来将进一步考虑其他的目标函数,如最大拖期和最大延迟等.