求解炼钢—连铸排产问题FCFS算法周永良，刘浏，何平，贺庆(钢铁研究总院冶金工艺研究所北京100081)摘要：根据车间的客观条件，对经典FCFS算法进行了改进，得到了一种新方法，使之应用于炼钢排产，取得稳定、可靠效果。关键词：排产；计划；FCFS1引言为了提高炼钢连铸生产的合理性，避免调度工作中人为因素的盲目性，计算机化生产调度已提上日程。转炉-连铸生产要求所有同一浇次的钢水都以同一时间频率到达铸机，而且钢水到达时的温度也有严格限制。通常条件下，一个转炉炼钢厂都拥有多台转炉、多台精炼设备和多台连铸机。所以，调度问题面对的生产模式多数都是比较复杂的，给调度工作带来极大难度。由理论分析可知此类问题是NP—难的，也就是说此类问题没有可行的多项式解法。另一方面，从现实的情况看，炼钢生产波动大、不确定性大、计划中途修改的可能性大，更增加了炼钢生产调度的难度。本文着重考虑炼钢连铸生产的特殊要求即：铸机连续生产要求钢水以离散方式准时、均匀供应，提出一种基于规则的FCFS(FirstComeFirstServiced)算法，来求得一个可行的调度方案。2产生式系统2.1产生式系统概述产生式系统是专家系统的先驱，也可认为是专家系统的较初级、较简单的阶段。在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物事件和它们之间的关系；用产生式规则表示推理过程和行为［1］。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统(rule-based-system)［1］。一个产生式系统有工作存储器(WorkingMemory，简称WM)、产生式规则库(ProductionRuleBase)和规则解释程序3部分组成，规则解释程序包括匹配器、冲突集和冲突消解器及解释器，其基本结构见图1。产生式规则库存储专业知识、长期经验和人为设定。规则解释程序负责系统的运行。用工作存储器存储当前一致的数据，包括推理过程的中间结论。这些数据有解释器中的规则解释程序及或相应的规则。要用产生式系统，还要有一个能代表人类知识与经验的规则库。2.2炼钢一连铸调度的核心调度规则炼钢-连铸生产是离散-连续系统，与一般意义的流程工业系统有显著不同，设备多且操作变数大、限制条件多、整体稳定性差，调度工作难度比较大。大多数工厂都是依靠人的经验进行判断，由供货合同主观设定一个主计划，在此基础上再细分成详细调度计划时刻表。不管是排定主计划，还是排列详细生产调度时刻表，都要以车间实际要求为出发点。·炼钢车间的核心是连铸生产，非特殊情况连铸不断流。从计划的角度讲，就是保证按连铸机的生产时间、温度要求提供钢水。·调度的核心问题是：合理利用有限的时间和设备增加铸坯产量、扩大经济效益。·由于时间节奏的不平衡性和波动性，不管是三炉配三机还是三炉配四机，一般都要在转炉和连铸机之间预留一定的缓冲时间。通常都是以提高出钢温度或是利用LF等设备的升温能力的办法来获得缓冲能力。·对于多台连铸机连续生产，当有两台连铸机同时需要钢水时优先满足处理时间较短的连铸机的要求。·非特殊情形，要求每台转炉负荷相当，分配均匀。以上所述各点都是建立一个调度系统所必须考虑的问题，可以把这些条件理解为规则，运用产生式系统的理论，将其转变为计算机语言，成为计算机调度系统的基础。上述规则和本文讨论的思想是所有调度系统共有的基础，必须有更复杂、更实用的客观条件才有实际指导意义。3改进FCFS算法3.1算法的提出FCFS是简单易用的排序方法，任务以到达时间的先后排序来获得机器处理时间。这个思想在计算机、工业调度、仿真模拟领域都有广泛的应用。连铸生产的一个浇次由多炉钢水组成，各个炉次处理时间稳定，各炉次时间之间位置固定，整个流程结构紧凑。对于每炉钢水来说，由于是高温作业，温度会随着时间流失而损失，所以要求时间没有延误，即JIT(JustInTime)生产。每炉钢水从转炉转到钢包后，在运到连铸工位进行浇注前，除去正常工序与必要运输时间，最好没有不必要的耽搁。FCFS可保证钢水没有无谓耽搁，这正是将此思想用于转炉炼钢生产的调度原因。但是，从实际来看，经典的FCFS算法无法直接应用，这也是将产生式系统与FCFS思想结合的出发点。...
