自动化学报
ACTA AUTOMATICA SINICA
1998年 第24卷 第1期  Vol.24  No.1 1998



基于准时制的炼钢-连铸生产
调度问题研究
唐立新　杨自厚　王梦光
摘　要　在钢铁CIMS下对于在安排炼钢-连铸调度中的机器冲突问题建立了基于准时制调度思想的数学模型，经过变换， 将非线性规划问题转化为线性规划问题，用标准线性规划程序进行求解， 使这一模型能够用于生产实际. 最后给出了一个应用实例. 
关键词　钢铁CIMS， 炼钢-连铸调度，机器冲突，线性规划. 
RESEARCH ON STEELMAKING AND CONTINUOUS
CASTING PRODUCTION SCHEDULING
TANG LIXIN　　YANG ZIHOU　　WANG MENGGUANG
(Institute of System Engineering of Northeastern University, Shenyang 110006)
Abstract　In this paper the JIT (just in time) idea based mathematical model is presented for solving machine conflict in steelmaking & continuous casting production scheduling under CIMS environment. By conversion strategy the non-linear programming model is converted into linear programming which can be solved by standard linear programming software. It is proved that this model can apply to actual production. An application example is given at the end.
Key words　CIMS of iron & steel industry, steelmaking & continuous casting scheduling, machine conflict, linear programming.
1　引言
　　钢铁产品竞争的焦点在于产品质优价廉、准时交货、多品种小批量. 生产计划与调度的最优化是实现上述目的重要途径. 炼钢-连铸是钢铁生产的瓶颈工序［1］，科学确定其生产调度可以充分提高大型设备的生产效率，减少工序等待时间，降低物耗和能耗，从而降低成本、提高产品竞争力. 因此，这一课题的研究在国际上极为重视， 澳地利Gmbh钢厂给出炼钢-连铸调度的建模关键因素［2］， 并对炉次在机器上的分配给出了调度模式； Numao等［3］用人工智能和人机交互结合解决炼钢-连铸调度问题， Dorn等［4］提出了基于Fuzzy集合和人工智能结合研究炼钢-连铸调度问题. 关于炼钢-连铸调度问题公开发表的成果较少，而且这些文章主要采用人工智能和人机交互方法，没能给出最优的数学模型，难以保证最优性. 
　　本文以某钢铁企业生产实际为背景，对于炼钢-连铸调度问题，建立了非线性规划的数学模型， 这一模型除了考虑生产工艺约束和中间工序的连续生产问题外， 还在目标函数中引进了准时制(JIT)的思想， 考虑了合同的准时交货问题， 使得炉次中的板坯提前或拖期生产都要受到费用惩罚. 为了便于求解， 提出了一种变换方法，将非线性规划问题转化为线性规划问题，运用标准线性规划程序进行求解， 使这一模型能够用于生产实际. 
2　机器冲突消除的最优调度问题的数学模型
　　炼钢-连铸调度的作业程序为［5］： 首先进行连铸机上浇次排序与调度， 在此基础上确定子调度和粗调度(子调度叠加)， 获得的粗调度存在机器冲突. 本文的工作是建立优化模型来消除机器冲突，最后形成最优炼钢-连铸调度. 
2.1　建模因素抽取
　　1) 变量的选择
　　因每一炉次在各工序使用的机器是固定的(由粗调度和子调度确定)，因此选择变量时只是选择任一炉次i在机器j上的开始处理时间Xij. 
　　2) 目标函数的确定
　　(1) 尽量保证每一炉次的板坯准时交货， 用提前/拖期惩罚达到这一目的. 
　　(2) 对于相邻两工序的时间间隔， 使等待时间最少，以达到由于时间等待而引起的钢水温降最小. 
　　(3) 尽量保证同一浇次的炉次连浇，即进行连铸断开损失惩罚. 
　　3) 约束考虑
　　(1) 同一炉次的相邻工序要等前一工序处理结束，才能开始下一工序. 
　　(2) 对于在同一工序中的同一机器上处理的相邻炉次， 要等前一炉次处理结束，才能开始下一炉次
　　(3) 同一连铸机不同浇次之间需要调整时间和间隔时间. 
　　4) 基本条件
　　(1) 不改变子调度前后顺序(不可改变顺序)；
　　(2) 同一机器同时只能加工一个零件. 
2.2　符号定义
　　定义1.与项目i在机器j直接相连的后序项目为紧邻后序项目，表示为SI(i,j). 
　　定义2.项目i的与机器j直接相连的后道工序的机器为项目i在机器j的紧邻后序机器，表示为SP(i,j). 
　　定义3.　Ω——全部炉次集合　Ω={1,…,N}；
　　定义4.　Ωk——第k个CAST(浇次)的炉次集合；k∈{1,…,M}. 对于任何j≠k，j,k∈{1,…,M},Ωj∩Ωk=O,且Ω1∪Ω2∪…∪ΩM=Ω;
　　定义5.　Jk——第k个浇次的炉次数，
　　定义6.　П——全部机器的集合，П={1,…,J}；
　　定义7.　Φ——全部连铸机的集合，｜Φ｜=C,且；
　　定义8.　Пi　——第i个炉次使用的所有机器集合. Пi　包含于П.
2.3　炼钢-连铸调度数学模型
　　炼钢-连铸调度问题的数学模型如下：
　　(P)

　　　　　　　　　(1)
subject to:
　　　　　　　　　(2)
　　　　　　　　　(3)
　　　　　　　　　(4)
　　　　　　　　　　　　　　(5)
其中已知量为：N——生产炉次总数；J——全部机器总数；M——全部浇次总数；di——炉次i的合同交货时间；C1k——浇次k的连铸断开损失惩罚费用系数； C2ij——炉次i在机器j单位等待时间的惩罚费用系数；C3i——炉次i在合同要求时间之前生产的惩罚费用系数；C4i——炉次i拖期生产的单位时间惩罚费用系数；Tij——炉次i在机器j的处理时间；tjm——机器i到机器m的运输时间；Skj——烧次k在机器j上的调整时间；μ——浇次之间的间隔时间. 决策变量为Xij——炉次i在机器j上的开始时间. 
　　目标函数(1)使得在下面四个部分的总的费用之和最小：(a) 连铸断开损失惩罚费用，尽量保证同一CAST中的炉次连浇；(b) 炉次等待处理时间的惩罚费用；(c) 炉次的板坯在合同要求的时间之前生产的惩罚费用； (d) 炉次的板坯拖期生产的惩罚费用. 以保证炉次准时交货. 约束(2)表示对于在同一工序中的同一机器上处理的相邻炉次，要等前一炉次处理结束才能开始下一炉次. 约束(3)表示同一炉次的相邻工序要等前一工序处理结束， 才能开始下一工序. 约束(4)表示同一连铸机不同浇次之间需要调整时间和间隔时间. 即同一铸机上的上一个浇次的最后一个炉次的断浇时间和紧邻后一浇次的第一个炉次的开浇时间之间要留有一定的调整时间和时间间隔. 这是一个按照JIT思想建立的模型，但同时考虑了工序之间的等待时间最小，炉次连续的炉数最大，这是一个非线性的数学模型， 下面提出一种变换的求解方法. 
3　炼钢-连铸调度数学模型的求解方法
　　因原问题目标函数属于非线性问题， 为了便于求解， 可进行下面的转换. 
假设　　Zij=-Min(0,Xij+Tij-di-1),　i∈Ω,j∈Пi∩Φ,
　　　　Yij=Max(0,Xij+Tij-di-1),　i∈Ω,j∈Пi∩Φ,
则　　　Yij-Zij=Xij+Tij-di-1,
即　　　Xij=Yij-Zij-Tij+di+1，　i∈Ω,j∈Пi∩Φ.
则模型变为如下形式：
(TP)

　　　　　　　　　　　　　　　　　　　　　　　　　　(6)
subject to:
　　　　　　　　　(7)
　　　　　　(8)
　　　　　　　　　(9)
　　　　　　　　(10)
　　　　　　(11)
　　　　　　　　　　　　　　(12)
　　　　　　　　　　　　　　(13)
　　　　　　　　　　　　　　(14)
这是一个线性规划模型问题，可用标准线性规划程序求解. 
4　应用实例
　　某炼钢厂的炼钢-连铸工艺路线如图1所示， 3个浇次， 6个炉次安排计划， 模型基础参数如表1所示， 则子调度和粗调度如图2所示， 用线性规划程序进行求解， 表2和图3显示应用上述模型使冲突消除的求解结果. 
表1　模型基础参数

浇次炉次机器加工时间(s)交货期和惩罚系数运输时间(s)
号号123456d(s)C1C2C3C4机器——机器
1

2

31
2
3
4
5
68

8

6
8
9

8


9

7
7
87

6


8

8
8
8
8
8



41
49
33
41
53
6120

30

40
30
15
20
18
21
2425
20
30
15
19
1430
10
35
18
20
185　　4
1——3——5
(3)　　(4)
(3)　5　(2)　3
2——4——6
S4,5=3,μ=2




图1　炼钢-连铸工艺路线
表2　实例的计算结果

炉次各炉次在相应机器上的开工时间(s)
1
2
3
4
5
6X11=13
X22=17
X31=5
X42=9
X51=27
X62=33X14=24
X23=29
X34=16
X43=20
X53=38
X64=46Y16=0
Y26=0
Y35=0
Y45=0
Y55=3
Y65=3Z16=0
Z26=0
Z35=2
Z45=2
Z55=0
Z65=0X16=34
X26=42
X35=24
X45=32
X55=49
X65=57
最优值的计算结果为OPT=252




图2　机器存在冲突时的炉次调度时间排程


图3　机器冲突消除后的炉次调度时间排程
5　结束语
　　对于在安排炼钢-连铸调度中的机器冲突问题， 基于准时制调度思想建立了非线性规划的数学模型，这一数学模型既考虑了合同的准时交货问题，又考虑了中间工序的连续生产问题， 非常符合现场实际生产情况，目前尚未有此类型的模型，为了便于求解， 本文提出了一种变换方法，将非线性规划问题转化为线性规划问题， 运用标准线性规划程序进行求解，使这一模型能够用于生产实际. 实践证明， 这种方法科学有效：(1) 减少了调度产生时间； (2) 降低了炉次的中间等待时间，从而提高了调度的质量. 在实际开发项目当中， 需加人机交互画面进行动态调整， 增加系统的适应性和灵活性. 

1)　国家自然科学基金和国家“八六三”高技术基金资助项目.
作者简介：唐立新　1966年生. 1995年东北大学系统工程专业博士毕业. 1996年为香港科技大学工业工程系博士后. 现为东北大学系统工程研究所副教授所长，研究方向为机械与钢铁CIMS中的生产计划与调度的理论方法. 
　　　　　杨自厚　1926年生. 1950年毕业于武汉大学电机系，现为东北大学系统工程研究所教授. 研究领域为生产排序问题、组合最优化智能算法， 决策支持系统构造及其应用. 
　　　　　王梦光　1936年生. 1958年毕业于东北工学院自动控制系. 现为东北大学系统工程研究所教授， 博士生导师. 研究领域为生产计划与调度理论与方法. 
作者单位：东北大学系统工程研究所　沈阳　110006
参考文献
[1]　Lee H S, Murthy S S, Haider, S W et al. Primary production scheduling at steelmaking industries. IBM J. Res. Develop, 1996, 40(2),231-252.
[2]　Neuwirth J. A production scheduling system at the stahl linz GMBH. In: Int. Conference on CPC-93 in Steel Plant, Korean, December, 1993, 342-350.
[3]　Numao M, Morishita S. Cooperative scheduling and its application to steelmaking process. IEEE Tansactions on Industrial Electronics, 1991,38(2),150-155.
[4]　Dorn J, Kerr R. Co-operative scheduling systems communicating through fuzzy sets. In: IFAC Intelligent Manufacturing Systems, Vienna, Austria, October, 1994. 449-455.
[5]　唐立新， 杨自厚， 王梦光.炼钢-连铸生产计划与调度结构的研究.东北大学学报，1996， 17(6)：664-667.
收稿日期　1995-09-25
