论文部分内容阅读
钢铁企业生产设备大、运行成本高、工艺复杂,为了适应多品种、小批量的市场需求,需要将工艺要求相似的工件组成批进行生产,从而达到节约生产成本,提高设备利用率和产能的目的。因此,批量生产是钢铁企业主要的生产组织模式。按照设备加工方式的不同,批模式可分为并行批、串行批及半连续型批等类型。本文以钢铁企业典型工序为背景,针对从生产实际中提炼的一类新的并行批生产决策与调度问题进行了系统研究。该研究不但扩展与丰富了现有的批决策与调度理论,其应用对于钢铁企业挖掘机组产能、降低生产成本、节能降耗、提高产品质量也具有重要意义。并行批生产模式区别于串行批生产模式的主要特征在于一台机器是同时(并行)而不是分时加工多个工件。与一般并行批决策与调度问题不同,本文所研究的并行批生产决策与调度问题具有如下特点:1)组批时需要考虑工件之间的多维属性差异;2)机器具有异构特征且工件允许剩余;3)工件的处理时间与等待时间相关。这些新的特征使得一般并行批决策与调度理论难以直接应用。本文以均热工序和罩式退火工序为背景,对均热工序中的分散和集中两种供热模式下的批决策问题以及罩式退火工序的静态和动态批决策问题等一类典型并行批决策问题,分别从模型描述、理论分析、算法设计及实际应用等方面进行了研究,并对从中提炼出的单批处理机调度问题、具有恶化特征的并行批处理机调度问题等一类并行批调度问题,分别设计了基于大规模邻域的智能优化算法用于快速近似求解。主要工作概述如下:1)以钢铁企业均热工序为背景,提炼出分散供热模式下的批决策问题。由于分散供热模式下均热炉内的多个均热坑是单独供热的,因此可以将每个均热坑看成是一个批处理机。该模式下批决策问题的任务是在满足能力约束的条件下,从多个待均热的钢锭中确定出适合于不同均热坑的钢锭批(均热批)。该问题的特征在于均热坑具有不同的初始温度,钢锭允许剩余,且组批质量与钢锭之间的轧制温度差及钢锭与均热坑之间的初始温度差等多维因素相关。本文以提高设备利用率、增效降耗为目标,对于该问题建立了数学规划模型,并根据问题的结构特点将其转化为Set-Packing模型,设计了分支价格最优算法。在求解过程中,将列生成算法嵌入到分支定界框架中为分支树的每个节点提供紧界,同时提出了两种分支策略。通过对随机产生的算例进行测试,可以证明两种分支策略对于求解该问题均有效,且所提出的分支价格算法可以在合理时间内最优求解该问题中规模算例。2)以钢铁企业均热工序为背景,提炼出集中供热模式下的批决策问题。该问题与分散供热模式下的批决策问题的主要差别在于,属于同一均热炉的多个均热坑是集中供热的,这就决定了每个坑的批决策不但要考虑自身的能力约束,还要考虑均热炉的同步供热方式要求。由于上述特征,使得在批决策过程中需要对属于同一炉内的多个均热坑集成考虑,因此大大增加了问题的求解难度。本文通过分析问题的结构特征,对其建立了Set-Packing模型,并设计了分支价格算法对其最优求解。在采用列生成算法获得问题下界过程中,每个价格子问题可以看做一个强NP难的多背包问题,针对其难于求解的特性,设计了一个能够最优求解价格子问题的两阶段迭代式算法,为了加快算法求解速度,克服算法每次迭代只能阻止一个不可行解产生的缺点,提出了一组基于钢锭聚合的有效不等式。通过对随机产生的算例求解线性松弛解及最优解的两个计算实验,证明了引入加速策略后,两阶段迭代式算法能够快速求得价格子问题的最优解,且所提出的分支价格算法能够最优求解该问题中规模的算例。3)针对钢铁企业罩式退火工序中实际的静态批决策问题进行了研究。该问题的任务是在满足罩式炉能力约束的条件下,从待退火板卷集合中选出若干个板卷组成一定数量的批分配给各个空闲的罩式炉,同时确定各个批的中心板卷。该问题的特征在于,组批时需要为每个批选择一个中心板卷且板卷允许剩余,批的质量通过批内中心板卷与其他板卷之间的多维属性差异、板卷与罩式炉的匹配度及装炉量等因素衡量。本文深入分析了影响罩式退火工序生产运作与管理水平的关键因素,以提高机组产能、降低生产成本、提高产品质量,满足生产管理需求为目标,以实际的工艺规程及设备要求为约束条件,对于该静态批决策问题建立了能够准确描述生产实际的数学规划模型,并针对实际问题约束复杂、难于求解的特征,设计了能够快速获得问题近优解的禁忌搜索算法。在算法中,根据问题的结构特点分别提出了变邻域搜索策略及基于Filter-and-Fan算法的混合交换链邻域以提升算法性能。为了对禁忌搜索算法做出客观评价,采用列生成算法获得该问题的上界。通过对实际生产数据的测试,可以证明禁忌搜索算法可以在较短时间内求出问题的近优解,且所提出的变深度混合交换链邻域可以有效地帮助算法跳出局部最优。最后,基于所提出的模型及算法,开发了罩式退火工序组炉计划决策支持系统,并已在国内某钢铁企业稳定运行,系统的应用克服了板卷退火质量不高、装炉量低、排产效率低、人为因素干扰大等人工编制计划的不足,有效提升了罩式退火工序的生产运作水平。4)以钢铁企业罩式退火工序为背景,提炼出不同生产条件的静态批决策问题。这些问题包括:(1)板卷规格相近情况下的静态批决策问题;(2)中心板卷给定情况下的静态批决策问题;(3)板卷分组适配情况下的静态批决策问题;(4)大批量、少品种生产模式下的静态批决策问题。对于上述四种静态批决策问题,从问题结构、最优解性质等方面进行了理论分析,并分别设计了基于动态规划技术或线性规划的多项式时间最优算法。5)以钢铁企业罩式退火工序为背景,提炼出动态批决策问题。该问题与罩式退火工序板卷静态批决策问题的主要区别在于,考虑了板卷的动态到达及罩式炉的动态可利用。在动态批决策问题中,等待不可利用的板卷可以提高组批质量,但同时会降低生产效率,因此,需要协调组批质量与生产效率之间的矛盾。本文基于离散时间建模策略,对问题建立了数学规划模型,并设计了基本拉格朗日松弛算法对问题进行求解。同时,为了进一步提升下界,将变量分离策略引入到拉格朗日松弛算法中,设计了拉格朗日分解算法。通过单周期及滚动周期实验,可以证明所提出的两种算法都能够在较短时间内求出问题的近优解,加入变量分离策略后有效地提升了问题的下界,同时改进了解的质量。6)以钢铁企业罩式退火工序为背景,研究了单批处理机调度问题。该问题的任务是在满足机器能力约束的条件下对所有工件进行组批,目标是最小化最大完工时间。该问题已被证明是NP难解的,因此,本文设计了禁忌搜索算法对其近似求解。在禁忌搜索算法中,针对问题的结构特征提出了两个基本搜索邻域,为了克服搜索过程易于陷入局部最优的缺点,构造了变深度搜索邻域以进一步提高算法性能。最后采用随机生成的算例对禁忌搜索算法进行测试,并与标准求解软件进行比较,实验结果证明了禁忌搜索算法的有效性,同时验证了所提出的变深度邻域能够有效帮助搜索过程跳出局部最优。7)以钢铁企业均热工序为背景,提炼出带有恶化特征的并行批处理机调度问题。该问题的特征在于,工件的加工时间随着等待时间的增加而恶化。问题的任务是以最小化最大完工时间为目标,将所有工件组成批并分配给并行批处理机,同时决策各个批在机器上的加工顺序。本文对于该问题建立了数学规划模型,并针对问题的强NP难解性,设计了Filter-and-Fan算法。在算法中,根据问题特点设计了三种搜索邻域,并提出了能够提高搜索灵敏度的解的选取策略。为了进一步提高算法性能,避免算法陷入局部最优,提出了解的重构策略以增加搜索的分散性。通过采用随机产生的算例对Filter-and-Fan算法测试,并与标准求解软件进行比较,证明了所提出的解的选取策略及解的重构策略能够有效提升算法性能,且Filter-and-Fan算法对于小规模算例可以求出最优解,而对于大规模算例,其计算结果及计算时间均优于标准求解软件。