轧钢切断阶段动态HFS调度模型和LR算法研究

轩 华， 曹 颖

(郑州大学 管理工程系 河南 郑州 450001)

0 引言

钢管是轧钢生产的一项重要产品，大量用作输送流体的管道，如输送石油、天然气、煤气、水及某些固体物料的管道等.迄今为止，针对钢铁业中的炼钢过程或热轧调度的研究比较多[1-2],而针对钢管生产研究的文献还比较少.文献[3]利用了遗传算法得到钢管生产批量计划的近似最优解，模型考虑了两个目标：最小化剩余物和最小化所有的over-grade.文献[4]从整个生产工艺的角度，对钢管合同计划进行了建模和求解，目标是最小化带权重的合同完成时间和.

钢管的制造方法主要有热轧、焊接和冷加工等，其中热轧工艺是无缝钢管的主要制造方法，占无缝管产量的80%.因此，研究热轧工艺的生产调度对于无缝钢管的生产具有重要的现实意义.热轧无缝钢管的生产工艺较为复杂，其过程可看做是在管坯切割之后的主要变形，工序有3个：穿孔、轧管和定径，如图1所示.

图1 热轧无缝钢管的主要工艺流程图

以天津无缝钢管公司为例，热轧无缝钢管采用的自动轧管机组，切割阶段有1台切割机，穿孔阶段有2台穿孔机，轧管阶段有2台自动轧管机，定径阶段有1台定径机.所有的管坯必须在切割之后依次进行穿孔、轧管、定径等，而且每个阶段都有1台或者1台以上的同构并行机，因此上述过程可以看作是一个混合流水车间(hybrid flowshop，HFS).然而它不同于典型的HFS，因为在第一阶段加工时，一批内的所有工件属于同一根管坯，因此要求同一批内的所有工件都要在同一台切割机上进行无间断地连续切割.于是，上述钢管切割过程可以看作是第一阶段具有批处理特征的HFS调度问题.假定各加工阶段间运输时间不可忽略，所有工件动态到达第一个阶段，则形成了本文所研究的考虑运输时间的第一阶段有批处理要求的动态HFS调度问题.

1 问题描述

所要研究的问题是在s个阶段调度n个工件，且它们在第一阶段按照其切割前所属管坯组成A批进行加工，目标是最小化所有工件的加权完成时间.当工件在第一阶段组批时，每批l包含的工件数al是已知的，同一批内工件之间必须按照已知的优先级关系顺序，在第一阶段的一台机器上连续加工.需要注意的是，由于同一批中的工件切割前属于同一根钢管，故同一批内的前al-1个工件的加工时间相同，而当前al-1个工件切割完后，第al个工件即已成型，因此，第al个工件的加工时间为0.

此外，在建模中，还有如下假设：①允许每个工件动态到达第一个阶段.②一个工件在前一个阶段加工结束之后才可进行下一个阶段的加工.③一个工件在一个阶段没有加工完成之前不允许中断.④机器的调整时间忽略不计.

2 模型建立

2.1 参数的设置

2.2 变量的定义

i∈I,j=1,2…,s,k=1,2,…,K;Bij为工件i在第j阶段加工的开始时间；Cij为工件i在阶段j上的完成时间(它是一个时间点，Cij=k表示工件i的阶段j在时刻k的末段完成加工).

2.3 模型的构建

模型构建如下：

(1)

s.t.Bi1≥ri,i∈I,

(2)

(3)

Cij+tj,j+1+pi,j+1≤Ci,j+1,i∈I,j=1,2，…,s-1,

(4)

Cblf，1+pbl,f+1,1=Cbl,f+1,1，l∈{1,2,…,A},f=1,2,…,al-1,

(5)

(6)

kδijk≤Cij,j∈I,j=1,2,…,s,

(7)

δijk∈{0,1},i∈I,j=1,2,…,s,k=1,2,…,K，

(8)

Bij,Cij∈ {1,2,…,K},i∈I,j=1,2,…,s.

(9)

在上述模型中，目标函数(1)最小化所有工件的加权完成时间；约束(2)表示每个工件只有到达第一个阶段的机器之后，才能开始加工；约束(3)确保所有工件对机器的需求不能超过在相应时间段可使用的机器数；约束(4)表示同一工件在不同加工阶段间的工序优先级约束；约束(5)表示同一批内所有工件在第一阶段(切割阶段)的优先级约束；约束(6)表示工件在各阶段占用机器的时间区间；约束(7)定义工件开始占用机器的时间；约束(8)、(9)定义了变量的取值范围.

虽然本文所研究的问题与文献[5]的类似，但这两项研究不同：首先，研究问题的背景不同，本文所探讨的HFS问题来源于钢管生产的工艺流程，故而第一阶段具有批处理特征，而文献[5]则是从钢铁行业炼钢-热轧-连铸阶段提炼出来的，且最后一阶段是具有批处理特征的HFS调度问题；其次，目标函数不同，本文以最小化工件加权总完成时间为目标，而文献[5]则考虑了总加权完成时间和对工件等待的惩罚；最后，本文考虑了工件的动态到达时间，从而表现了一定的动态特性，而文献[5]则是假定所有的工件在时间1都是可用的，即不考虑工件的动态到达时间.

3 改进LR的求解方法构造

以往关于求解HFS调度的研究较多.文献[6]中对HFS调度问题的求解方法有总结和归纳，主要有精确算法、启发式算法和混合启发式算法等.由于精确算法在解决复杂问题时往往耗时较长，而启发式算法虽然能在较短时间内得到可行解，但解的质量难于评价，又鉴于所建立的模型是“可分离的”(目标(1)是加和的形式，且耦合不同工件的机器能力约束是线性的)，因此，提出改进的LR算法求解2.2节所建模型，求解过程构造如下.

3.1 拉格朗日松弛

由于约束(3)耦合不同的批，利用拉格朗日乘子μjk将其松弛到目标函数中，形成LR问题

(10)

满足约束(2)，(4)～(9)和

μjk≥0,j=1,2,…,s,k=1,2,…,K，

(11)

从而得到拉格朗日对偶问题

满足(2)，(4)～(9)，(11).给定一组拉格朗日乘子{μjk}，分解后对应于每批l的子问题为

(12)

满足(2)，(4)～(9)，(11).因此，L(μ)也可以写为

(13)

3.2 拉格朗日乘子的更新过程设计

求解对偶问题过程中，常采用次梯度算法来更新拉格朗日乘子，μh+1=μh+ahgh，其中，gh=g(μh)是L(μ)的次梯度，ah是第h次迭代的步长.

3.3 原问题可行解的构造

由于约束(3)被松弛，因此对偶问题的解在某段时间内可能违背能力约束，所以它得到的解通常是不可行的.为构造可行解，基于局域搜索和文献[7]提出的列表调度构造一个两阶段启发式算法.

3.4 子问题的求解过程设计

图2 一批的出树结构

将文献[8]所提出的动态规划应用推广到上述的批级子问题，令一个节点表示一个工序(i,j)，假定同一批内有3个工件，共有4个阶段，即al=3,s=4，则每个批级子问题中的所有工序构成与文献[5]中子问题结构相反的出树结构(图2).图中虚线框内的所有工序是作为一批在一台机器上按顺序加工且不允许中断，实箭头表示物流的流向，虚箭头表示工序之间的加工顺序.

以往也有一些研究对工件间存在优先级或一个工件内的各工序间存在优先级的LR问题应用动态规划(dynamic programming,DP)进行求解[9-11].然而，作者所研究的子问题和文献提到的子问题不同，主要区别在于处理第一道工序的那台机器的生产方式：在该批处理机上有一序列工序，它们是作为一批进行处理，并且除了批中的最后一个工件加工时间为零之外，其他工件的加工时间均相等，且在第一阶段同一批内工件的加工顺序一定.为此，设计了求解该子问题的改进DP算法.

(14)

令Ph表示工序h(h= 1,2,…,sal)的紧后工序的集合，令Fh(k)表示调度工序h和它的紧后工序在时刻k之前完成的最小总费用.后向动态规划(BDP)从最后一个节点开始，一直到节点1结束.

工序h=(s-1)al+1,(s-1)al+2,…,sal的费用给定为

Fh(Cih jh)=Vh(Cih jh).

(15)

当工序h(h∈{al,…,(s-1)al})的累计费用为

(16)

当工序h=1,2,…,al-1的累积费用为

(17)

在计算Fh(Cihjh)时，关于工序h的紧后工序的函数Fx(Cixjx)和Fy(Ciyjy)都是已知量.由于每批内第一道工序是所有其他sal-1道工序的先前工序，因此，可计算得到下界

(18)

最后沿着最优路径向后追踪得到对应子问题的最优解.

4 算例

以一个有3个工件的批级子问题为例，假设这3个工件{1，2，3}依次经过3个阶段进行加工，在第一阶段上，它们组成一批并按照1-2-3的顺序在一台机器上进行加工，运输时间t12和t23分别为1和2.表1给出了每个工件在每个阶段的加工时间、在第一阶段的动态到达时间、工件的权重以及在每个阶段可用的机器能力数.

在求解拉格朗日对偶问题时，将拉格朗日乘子{μjk}的初始值设为0.5，第一次迭代时利用改进DP求解这个批级子问题的详细过程如表1.

表1 算例数据

Step1按照从第一阶段到最后阶段及工序在批内的位置排列所有工序，与图2相似(无第4阶段).

Step2确定每道工序的紧前工序，并对它们进行分类.工序7,8,9无紧后工序；工序3,4,5,6有一道紧后工序，分别为6,7,8,9，它们属于x类型；工序1,2有两道紧后工序：包括x类型工序{4,5}和y类型的工序{2,3}.

Step3根据式(4)和(5)，计算每个工件的可能的工序完成时间.该例中，每个工件的每道工序的完成时间集合为：C11∈{2,3,4,5,6}，C12∈{6,7,8,9}，C13∈{9,10,11,12}，C21∈{4,5,6,7,8}，C22∈{6,7,8,9,10}，C23∈{9,10,11,12,13}，C31∈{6,7,8,9}，C32∈{9,10,11,12,13}，C33∈{14,15,16,17}.

Step4根据式(14)，计算

F7(9)= 18.5;F7(10)=20.5;F7(11)=22.5;F7(12)=24.5;

F8(9)=9.5;F8(10)=10.5;F8(11)=11.5;F8(12)=12.5;F8(13)=13.5;

F9(14)=29.5;F9(15)=31.5;F9(16)=33.5;F9(17)=35.5.

Step5根据式(15)和(16)，计算F3(C31)，F4(C12)，F5(C22)和F6(C32).

F6(9)=V6(9)+F9(14)=30.5;F6(10)=V6(10)+F9(15)=32.5;

F6(11)=V6(11)+F9(16)=34.5;F6(12)=V6(12)+F9(17)=36.5;

F5(6)=V5(6)+F8(9)=10;F5(7)=V5(7)+F8(10)=11;F5(8)=V5(8)+F8(11)=12;

F5(9)=V5(9)+F8(12)=12;F5(10)=V5(10)+F8(13)=13;

F4(6)=V4(6)+F7(9)=19.5;F4(7)=V4(7)+F7(10)=21.5;

F4(8)=V4(8)+F7(11)=23.5;F4(9)=V4(9)+F7(12)=25.5;

F3(6)=V3(6)+F6(9)=30.5;F3(7)=V3(7)+F6(10)=32.5;

F3(8)=V3(8)+F6(11)=34.5;F3(9)=V3(9)+F6(12)=36.5.

Step6根据式(17)，计算F1(C11)，F2(C21).

F2(4)=V2(4)+F5(6)+F3(6)=41.5;F2(5)=V2(5)+F5(7)+F3(7)=44.5;

F2(6)=V2(6)+F5(8)+F3(8)=47.5;F2(7)=V2(7)+F5(9)+F3(9)=50.5;

F2(8)=V2(8)+F5(10)+F3(10)=53.5;

F1(2)=V1(2)+F2(4)+F4(6)=62;F1(3)=V1(3)+F2(5)+F4(7)=65;

F1(4)=V1(4)+F2(6)+F4(8)=68;F1(5)=V1(5)+F2(7)+F4(9)=71;

F1(6)=V1(6)+F2(8)+F4(10)=74.

Step7通过向前追踪得到子问题的解.

C11=2;C12=6;C13=9;C21=4;C22=6;C23=9;C31=6;C32=9;C33=14.

5 结束语

对考虑运输时间的第一阶段具有批处理特征的动态HFS调度问题进行了研究,将此问题建模为一个整数规划模型，并设计了改进LR算法的求解过程.通过松弛机器能力约束，将原问题分解成多个独立的批级子问题，用动态规划求解子问题，并用实例来说明第一次迭代时利用改进DP求解批级子问题的详细过程；用次梯度方法求解拉格朗日对偶问题；两阶段启发式算法构造原问题的可行解.下一步研究利用钢管厂的实际生产数据来验证所提出的模型和算法过程.

[1] Atighehchian A,Bijari M,Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production[J].Computers & Operations Research,2009,36(8): 2450-2461.

[2] Tang Lixin,Luh P B,Liu Jiyin，et al.Steel-making process scheduling using Lagrangian relaxation[J].International Journal of Production Research,2002,40(1): 55-70.

[3] Li Dawei,Wang Li,Wang Mengguang.Genetic algorithm for production lot planning of steel pipe[J].Production Planning and Control,1999,10(1): 54-57.

[4] Xuan Hua.A Lagrangian relaxation algorithm for the order planning of steel pipe[J].International Conference of Management Science and Information System,2009(1/2/3/4): 685-688.

[5] Xuan Hua,Tang Lixin.Scheduling a hybrid flowshop with batch production at the last stage[J].Computer & Operations Research,2007,34(9): 2718-2733.

[6] Ruiz R,Vazquez-Rodriguez J A.The hybrid flow shop scheduling problem[J].European Journal of Operational Research,2010,205:1-18.

[7] Hoitomt D J,Luh P B,Pattipati K R.A practical approach to job-shop scheduling problems[J].IEEE Transactions on Robotics and Automation,1993,9(1): 1-13.

[8] Oguz C,Tang L.A Lagrangian relaxation method for hybrid flow-shop scheduling with multiprocessor tasks to minimize total weighted completion time[C]//Proceedings of the 1st Multidisciplinary International Conference on Scheduling:Theory and Applications.Nottingham,2003: 638-653.

[9] Abdul-Razaq T S,Potts C N,Van Wassenhove L N.A survey of algorithms for the single machine total weighted tardiness scheduling problem[J].Discrete Applied Mathematics,1990,26(2/3):235-253.

[10] Chen Haoxun,Chu Chengbin,Proth J M.An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method[J].IEEE Transactions on Robotics and Automation,1998,14(5):786-795.

[11] Tang Lixin,Xuan Hua,Liu Jiyin.Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling[J].Computers & Operations Research,2007,34(9): 2625-2636.