工件和工具混合搬运的多吊机调度问题

谢　谢, 郑勇跃, 李彦平

(1. 沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳　110044;2. 辽宁省标准化研究院, 辽宁 沈阳　110004)



工件和工具混合搬运的多吊机调度问题

谢谢1, 郑勇跃2, 李彦平1

(1. 沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳110044;2. 辽宁省标准化研究院, 辽宁 沈阳110004)

从钢铁企业罩式退火过程提炼出一类工件和工具混合搬运的多吊机调度问题以最小化最大完工时间.由于该问题是强NP-难的,提出一个基于工具分配的启发式算法并证明了算法的绝对性能比为2,渐近性能比为3.算法的性能通过数值计算实验给出了估测,结果表明,所提出的启发式算法对大规模问题也可以产生高质量的解.

调度;罩式退火过程;绝对最坏性能;渐近最坏性能

钢铁企业的罩式退火是根据材料和工件尺寸采用不同的保温时间,然后进行缓慢冷却,目的是使金属内部组织达到或接近平衡状态,获得良好的工艺性能和使用性能,或者为进一步淬火作组织准备.罩式退火车间通常由若干矩形的区组成,在每一区内,炉台按照它们的坐标排列.在区的上方,由两个或多个吊机(如图1)将排在一起的这几个板卷按照一定的顺序堆放到适合的炉台上,依次经过:0—装板卷和对流板;1—装内罩;2—自然充气;3—装加热罩;4—加热;5—卸加热罩;6—自然冷却;7—装冷却罩;8—冷却;9—卸冷却罩;10—卸内罩;11—卸板卷和对流板这12个阶段完成对板卷的罩式退火过程.除第2、4、6和第8阶段外,其余都需要吊机的装载或卸载操作.当加热罩或冷却罩被吊机移动时(第3,5,7,9阶段),这两种罩不能加工工件.因此,加热罩或冷却罩的装载和卸载,必须同时考虑吊机和罩的使用.每个移动的操作都由上方的吊机执行.

本文将板卷看做工件、加热罩和冷却罩看做工具,提出并分析将工件和工具混合搬运的多吊机调度问题,同时考虑分配和调度有限的加热罩、冷却罩以最小化一个区内工件的最大完工时间(也就是说,极小化一个区内最后工件退火完成的时间).

图1　罩式退火车间图例Fig.1　Sample of a block in batch annealing process workshop

近年来,关于吊机调度问题的研究主要集中在电镀生产线以及港口码头的岸吊调度中,尽管已经有相关文献进行过研究,但很难直接应用于钢铁企业吊机的实际作业过程.Philips和Unger[1]首次提出电镀生产线中的吊机调度问题,他们给出了一个混合整数规划模型以确定单吊机生产线的最优周期.然而,在此之后的近30年,人们一直都在关注单吊机调度,忽略了多吊机

间的同时调度.一个重要的原因是:多吊机调度问题比单吊机调度问题更为复杂,因此研究相对较少.在实际中,由于一跨上存在至少两吊机,所以需要考虑到吊机分配的决策以避免吊机之间的交叉和碰撞.对于两台吊机的问题,Lei和Wang[2]使用一种zoned方法提出了一种启发式算法.考虑了工件必须沿着从装载站到卸载站一个方向依次经过处理槽的两台吊机的调度问题.他们把这条生产线划分为两个互不重叠的区域,每个区域内部处理槽中工件的移动分配给一个吊机,通过交替解决两个吊机的问题来确定最优排序.Leung等[3]提出了多吊机的最小化周期调度的混合整数规划模型,并对该问题提出了一个有效不等式,给出了一些初步的计算结果.当吊机数目预先确定,假设吊机间不碰撞,Kats和Levner[4]给出了计算时间为O(n2logn)的算法以最小化多吊机排序问题的周期时间.此外,Daganzo[5]首次提出岸吊调度,分析了吊机分配策略对于最大化终端输出和预期车辆延迟的影响,并没有考虑到吊机间的相互干涉.Guan等人[6]针对问题的中小规模,分别提出拉格朗日松弛方法和带有不交叉约束的时间空间网络流模型;对(Guan,2013 #417)大规模问题,提出两个有效的启发式算法.Tang等人[7]考虑了两类设备的协调以减少连续作业任务间的空闲时间.分析了问题的最优性质、建立混合整数规划模型、提出有效不等式及两个下界,进一步提出一个改进的粒子群算法.Kaveshgar和Huynh[8]考虑了集装箱、场地区域、吊机干涉、安全边界间的优先关系,建立一个混合整数规划模型,并设计了结合贪婪算法的遗传算法.有关罩式退火过程的多吊机调度问题,谢和李[9]提出了一类两阶段的启发式算法,分别将吊机和工具进行先分配后调度,并没有将多吊机对工件和工具的搬运混合考虑.

结合上述文献,很少有学者将吊机搬运过程的多类物件混合调度,本文主要研究钢铁企业罩式退火过程将板卷(工件)、加热罩和冷却罩(工具)混合考虑的吊机调度问题,提出了基于工具分配的启发式算法,并进一步分析了算法的绝对最坏性能和渐近最坏性能.

1　问题参数及描述

2　基于工具分配的启发式算法及其分析

启发式算法的过程将使用下面的工具分配问题的模型:

(1)

(2)

(3)

(4)

(5)

(6)

给定分配问题的可行解,令

由上面可知,每一个工件工具之间的分配问题的可行解给出了工具f(c)加工工件的顺序.吊机调度问题在这个结果的基础上,一旦吊机空闲,选择距离当前需要操作的最近的工件.

令

对任意的工件工具分配的距离向量d,令

根据等待时间,有

和

因此,问题的最优目标函数为

根据分配问题的最优性,有

和

引理1给定工件的距离向量d=(d1,d2,…,dn),启发式得到的解满足下面的条件:

定理1表明当工件工具的分配给定,这个算法的绝对最坏性能比为3.

定理1ZH/Z*≤3.

下面的定理表明问题的渐近最坏性能比是2.

由于M(d0)≤M(d*),因此,

3　数值实验与计算结果

在这部分中,我们对基于工具分配的启发式算法进行实验以检验其有效性.这个算法由C语言编程,在Pentium-Ⅳ的PC机上运行,操作系统是Windows XP,CPU是2.40 GHz.根据罩式退火过程的实际生产,测试问题所用到的参数利用以下方式随机产生.

工件的数目(n):15,25,55,85,100,200;

加热罩的数目(|F|)和冷却罩的数目(|C|):在[10,200]之间离散平均分布随机生成;

装载移动速度(v),空移动速度(λ),提起和下放的时间(μ):在[1,5]之间离散平均分布随机生成,此计算实例中,取v=1,λ=2,μ=1;

计算结果表明算法最多在15 s的CPU时间内求得问题的近优解.从表中可以看出算法的偏差随着工件数量的增多,即问题规模的增大,偏差逐渐减小,但最大的偏差也不超过2,尤其是当问题规模增加到n=100时,偏差明显减小,当n=200时偏差值已小于1.进一步验证了算法的绝对最坏性能比和渐近最坏性能比.此外,随着加热时间和冷却时间的增加,吊机调度对偏差的影响也逐渐减小.当工件的数目n越接近|F|和|C|时,算法的性能越好.这可以解释当需要加工的工件增多时,机器就变成了瓶颈设备.计算实验表明吊机与工具的分配并协调调度有利于平衡最大完工时间和设备的利用率.

表1　基于工具分配的启发式算法性能计算实验结果

4　结　　论

本文研究了罩式退火过程中多吊机混合搬运工件与工具的调度问题以最小化最大完工时间.针对这个强NP-难问题,提出一个基于工具分配的启发式算法,并对该算法的最坏性能和渐进最坏性能进行了分析.根据问题的实际参数测试算法的计算性能表明,本文的研究适合解决混合搬运各种吊件进行多阶段生产的、避免碰撞的多吊机调度问题.除了罩式退火过程可以应用这个研究解决外,本章的研究在考虑具体的实施细节时,可以扩展到钢铁企业炼钢连铸、连铸精炼中的部分生产过程.

[1] PHILLIPS L W,UNGER P S. Mathematical programming solution of a hoist scheduling problem[J]. IIE Transactions, 1976,8(2):219-225.

[2] LEI L,WANG T J. The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time window constraints[J]. Management Science, 1991,37(12):1629-1639.

[3] LEUNG J M Y,ZHANG G Q,YANG X G,et al. Optimal cyclic multi-hoist scheduling:a mixed integer programming approach[J]. Operations Research, 2004,52(6):965-976.

[4] KATS V,LEVNER E. Cyclic scheduling in a robotic production line[J]. Journal of Scheduling, 2002,5(1):23-41.

[5] DAGANZO C F. The crane scheduling problem[J]. Transportation Research Part B Methodological, 1989,23(3):159-175.

[6] GUAN Y P,YANG K H,ZHOU Z L. The crane scheduling problem:models and solution approaches[J]. Annals of Operations Research, 2013,203(1):119-139.

[7] TANG L X,ZHAO J,LIU J Y. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research, 2014,236(3):978-990.

[8] KAVESHGAR N,HUYNH N. Integrated quay crane and yard truck scheduling for unloading inbound containers [J]. International Journal of Production Economics, 2015,159(3):168-177.

[9] 谢谢,李彦平. 罩式退火过程中的多吊机调度问题[J]. 沈阳大学校报(自然科学版), 2012,24(1):12-19.

(XIE X,LI Y P. Multi-crane scheduling in batch annealing process[J]. Journal of Shenyang University( Natural Science), 2012,24(1):12-19.)

【责任编辑: 李艳】

Job and Tool Mixed Transportation Based Multi-Crane Scheduling Problem

XieXie1,ZhengYongyue2,LiYanping1

(1. Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University, Shenyang 110044, China; 2. Liaoning Institute of Standardization, Shenyang 110044, China)

A job and tool mixed transportation based multi-crane scheduling problem is studied for solving batch annealing processing in the iron and steel enterprises. The objective is to minimize the makespan. For the demonstrated NP-hard problem, a tool assigned based heuristic algorithm is proposed. The heuristic is analyzed from an absolute worst-case performance ratio of 3 and an asymptotic worst-case performance ratio is 2 respectively. The average performance of the solution approach is computationally evaluated. The results show that the proposed heuristic algorithm is capable of generating good quality solutions for large-scale problem.

scheduling; batch annealing process; absolute worst-case performance; asymptotic worst-case performance

2015-11-19

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

谢谢(1981-),女,辽宁沈阳人,沈阳大学副教授,博士; 李彦平(1958-),男,辽宁沈阳人,沈阳大学教授,博士.

2095-5456(2016)04-0291-06

TP 301.6

A