混合亚启发式算法求解带有热量损失的单吊机调度

谢 谢, 周 莉, 郑勇跃

(1. 沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳 110044;2. 中国标准化研究院 社会信用研究室, 北京 100191;3. 辽宁省检验检测认证中心 事业发展中心, 辽宁 沈阳 110032)

本文研究了一类来自于钢铁生产企业中物流系统的吊机调度问题.每阶段板坯加工结束后,仓库作为存储板坯的缓冲区域,在这里,目标板坯(半成品或成品)需要由吊机操作拣选运输到下一阶段加工或客户端.仓库中的主要操作由吊机实施,包括将板坯运输到适合的位置,拣选客户的需求板坯,一旦板坯不能直接运输,先将压在其上方的阻碍板坯运输到其他位置等.在这些操作中,将阻碍板坯运输到其他位置的倒垛操作是非常消耗时间和能源的.倒垛操作的工作量占仓库总操作的一半以上[1].图1给出了板坯仓库的一个存储区域.钢铁企业板坯仓库中每个存储区域通常按行列堆放,大约276块板坯堆放成1～3行,1～92列.黑色和灰色分别表示需求板坯和倒垛板坯,虚线处表示该位置为空.每个区域由1台吊机操作.吊机可以由一个位置移动到另一个位置,意味着它的吊钩伴随着吊机不仅沿着平行的跨方向移动,而且还可以在跨之间的桥来回移动,两个方向可以同时进行.为了方便,本文中我们将吊钩看作吊机.板坯在每垛中按层堆放,一个堆放在另一个上面.

图1 板坯仓库的存储区域Fig.1 A storage area in slab warehouse

基于每垛存放的行列位置,图2以一垛为例,如果需求板坯在正上方,可以被直接吊走,否则需要先将阻碍板坯移动到其他地方以露出需求板坯.不同于Tang等[2-3]和Singh等[4]考虑的问题,根据存储区域的实际,本文考虑的倒垛板坯不需要再移动回原位,同时,所选取存放的位置要尽可能离倒垛板坯的原位置很近以减少倒垛时间,降低热量损失.由于原始的堆放可以保证每个板坯的位置,因此,板坯的倒垛位置充足.

图2板坯仓库的一垛板坯
Fig.2Aslabstackintheslabwarehouse

对于每个需求板坯,吊机需要尽快地将其移动到指定位置.本文研究的问题就是确定需求板坯的移动顺序、倒垛板坯的移动位置最小化总温降损失.尽管倒垛板坯可以被移动到任一空位,为了避免进一步倒垛,本文不允许将倒垛板坯移动到需求板坯的上方,吊机的工作量包括倒垛和移动操作,该过程非常繁忙,是全部操作的瓶颈.因此吊机调度可以保证每个需求板坯及时被取出并减少热量损失.

尽管已有一些相关文献研究钢铁仓库的吊机调度问题[5-9].但很少有研究考虑被吊物件热量损失的问题,求解问题的算法也仅仅是包括启发式规则和简单的邻域搜索策略,很少有尝试将贪婪算法和变深度邻域搜索策略组合对问题求解.Tang等[2]提出一个整数规划模型和两阶段启发式算法求解具有不同板坯族的问题.Tang等[3]研究了没有通用板坯的该问题并且提出遗传算法求解.Singh等[4]也提出一个改进的平行遗传算法,其中包含了一些新的遗传因子,以上研究的目标都是减少倒垛次数,在一定程度上节省了板坯操作的费用,Tang和Ren[10]也研究了板坯倒垛问题,提出了基于启发式的分部动态规划最小化吊机的总工作量.

1 问题的定义和描述

为了对问题建立数学模型,基于图1、图2,必要的符号说明如下.

B为所有倒垛板坯的集合;R为所有需求板坯的集合;ri为需求板坯i的释放时间;P为所有位置的集合;poi为板坯i的初始位置(i∈B∪R);tp,p′为从位置P到位置p′的装载移动时间;ep,p′为从位置P到位置p′的空载移动时间;pdi为需求板坯i的指定位置(i∈R);p0为吊机的初始位置.

决策变量如下:

Sj= 第j个装载移动的开始时间,j=1,2,…,(|B|+|R|);

Cj= 第j个装载移动的完成时间,j=1,2,…,(|B|+|R|);

i∈B,p∈P;

i∈B∪R,j=1,2,…,(|B|+|R|).

基于以上符号,混合整数规划模型表示如下.

这个混合整数线性规划模型是线性的,因此可以使用CPLEX软件求解.然而,随着问题规模的扩大,CPLEX求解耗费大量时间,根据一次实际计划(大约超过20个位置),该软件就停止计算了,因此有必要对该问题提出有效的启发式算法.

2 复杂性

由于本文研究的问题复杂性不可知,因此使用归结的方法的证明该问题是强NP-难的.

性质1 即使考虑一种最简单的情况:吊机的初始位置与需求板坯的目标位置相同,运输需求板坯的时间趋近于0,该情况也是强NP-难的.

证明 当这种情况发生时,只需要考虑对阻碍板坯进行倒垛.给定旅行商问题的实例,将旅行商看作单吊机,将城市看作阻碍板坯的位置.单吊机需要从它的初始位置运输通过每个倒垛板坯的位置后再回到初始位置,使得总完工时间最短,由于任意2个板坯位置预先已知,这种情况等价于已知的旅行商问题.由于旅行商问题是强NP-难的,因此,可知这种情况可解当且仅当旅行商问题可解.

3 启发式算法及最坏性能分析

在本节中,提出了一个混合亚启发式算法求解该问题.该算法在搜索不同的邻域空间与当前解的有效性上保持了一种平衡.分散搜索作为一种搜索机制结合了变深度邻域搜索的特点对解进一步搜索.第一步,首先使用贪婪启发式算法构成参考集,再根据解的组合机制产生新的解.之后通过使用变深度邻域搜索策略改进当前解,如果改进的解好于当前参考集的最坏解,则替换当前参考集里的解.

3.1 参考集的建立

第1步 计算吊机对阻碍板坯从各自的位置到倒垛空位的距离,逐一按照非减的顺序排序;

第2步 逐一计算吊机当前位置到需求板坯的最近距离.

3.2 解的组合机制

3.3 解的改进

3.3.1 邻域

(1) 转换移动(Nshift).解的邻域转换定义为通过改变解内任意板坯的分配来获得.

(2) 交互式移动(Nswap).解的邻域可以定义为通过交换解内两个板坯的分配来获得.

3.3.2 变深度搜索策略

(1) 通过搜索初始解的邻域Nswap获得.一旦找到局部最优解η(假设η是第一层的节点数)作为产生搜索树的第一层,搜索树的下一层按照如下方式建立:假设n1表示层d的节点数目;令d表示层数,M(d)为层d中解的候选列表;假设n1为候选解集M(d)的移动数目,n2为通过局部搜索产生的移动中最好的移动数目.

(2) 探索n1个解的节点邻域Nswap中,n2为发现的最好解的数目.因此,在d+1层产生的解为N=n1×n2个.如果根节点处的解不能改进,则用该处的解作为最好的解.一旦全局解不能进一步改进,则搜索停止.

4 计算结果

为了估测所提出启发式算法的性能,计算实验基于实际生产数据.所有的算法使用VC++ 6.0编程并且运行在P4-3.00 GHz CPU以及内存为1G RAM的电脑上.MILP模型使用软件CPLEX 11.0版本求解.

问题的实例使用如下数值:存储区域的全部位置|P|,区域的空间利用率U,所有需求板坯的数目|R|以及倒垛板坯的数目|B|.目标位置都在存储区域一行的一侧,举例说明,目标位置的选取从1到|R|,具体的位置从可能的位置中选取.如图1所示,同一垛中相邻两板坯的位置为1,相邻两垛中的距离为2,吊机沿两个方向的装载移动和空载移动的速度分别为v1=1 m/s,v2=2 m/s,λ1=2 m/s,λ2=4 m/s.上提下放的速度为μ=2.5 m/s.

表1 2种所提出算法的性能比较Table 1 The performance for two proposed methods

注: {·} 括号里的数字表示在时间限制内MILP模型不能最优求解的实例数目.

对于每个实例,仓库的存储基于空间利用率以及N个可利用的位置.初始位置的选择考虑板坯的可行性,|R|个需求板坯存储在所有可行位置.尝试使用MILP模型求解小规模问题R,B,P分别为2,3,12.对于以上参数的各种组合,10个实例一组,分别使用MILP模型和混合亚启发式算法求解问题.设置10h为使用MILP模型求解问题的时间限制,如果在这个时间内不能获得最优解,则记录下最好的可行解.由于MILP模型不能对每个实例求出最优解,使用下界LB,作为比较不同解质量的标准(Cmax-LB)/LB×100%.我们也将混合亚启发式算法与下界进行比较从而对所提出的算法进行估测.算法的平均相对偏差(ARD)和计算时间如表1.

随着空间利用率的增加,MILP求解的时间大大增加了.当总的需求板坯数目和阻碍板坯数目达到8,空间利用率达到70%,时,使用MILP模型就不能在10h内求得问题的最优解.对于一些小规模的例子,MILP模型可以求出问题的最优解.随着问题规模的扩大,MILP模型和下界之间的偏差变大,表明下界LB的质量看起来随着问题规模增大而恶化.这是因为,由于下界使用最短的移动时间估测实际的移动时间,然而,随着问题规模的增大两个位置之间的平均移动距离也增加了.

混合亚启发式算法对任意测试的实例几乎都快速求解,解的质量距离最优解也不远.与MILP模型相比随着问题规模的增大,性能更加稳定.虽然随着问题规模的增加计算时间也增加了,求解70%空间利用率的实例时间长于低空间利用率如50%和高空间利用率90%,不同于MILP模型,求解的最长时间是空间利用率为90%的实例.或许是因为高空间利用率,对于阻碍板坯有非常少的空位,低空间利用率,则阻碍板坯较少可以帮助减少搜索时间.

5 结 论

本文研究了钢铁企业板坯仓库的单吊机倒垛问题,目标函数为最小化被吊板坯总热量损失.针对这个问题,建立了混合整数规划模型,该模型用于最优求解小规模的问题,针对中大规模问题,进一步提出一个混合亚启发式算法,通过变深度邻域搜索策略改进初始解的性能.计算实验表明,所提出的方法可以有效的求解该问题.未来的研究将进一步扩展问题的模型和算法用于求解其他目标函数,如最小化总倒垛和总拣选的费用等.