论文部分内容阅读
大型钢铁企业的炼钢工序通常都具有多个并行生产车间,如何将客户订单分配给不同的炼钢车间来均衡机组负荷、提高生产效率,是钢铁生产运作管理中的一个重要决策问题。此外,炼钢车间的转炉和连铸机等大型生产设备都以批的模式组织生产,而客户订单需求呈现多品种、小批量特征。因此,如何对客户订单进行组批,制定合理的批量计划以吻合大型生产设备的批生产模式,是钢铁生产运作管理层面的另一个重要决策问题。订单分配和批量计划是密切相关的两个问题,并且相互之间的决策具有强耦合性,本文从整体协调的角度出发,研究订单分配与批量计划的集成优化问题。主要研究内容如下:(1)以订单选择车间、钢级和宽度为决策变量,考虑订单与炼钢车间兼容性、钢级间优充替换关系、浇铸宽度要求、转炉容量限制、多个车间负荷均衡等约束条件,以最小化余材发生量、优充板坯发生量、切坯损耗量、订单与车间匹配成本为目标,建立了问题的新型整数规划模型,定量刻画了问题的关键组合特征。(2)模型的组合特征带来计算上的复杂度,导致商业优化软件难以在有限时间内直接求得实际规模问题的最优解甚至可行解。提出利用Dantzig-Wolfe(D-W)分解技术将原模型分解为一个主问题和一系列子问题,每个子问题对应给定车间,钢级,宽度三元组下的0-1背包问题。采用列生成算法对主问题和子问题进行迭代求解得到原问题的下界,以列生成算法作为定界机制嵌入分支-定界框架中形成分支-定价算法,执行分支搜索过程可获得整数最优解。(3)常规D-W分解的子问题数量多,主问题难以有效协调子问题间的耦合性。本文进一步提出多约束聚合的新型D-W分解策略。该策略将原模型按钢级(或钢级组)进行分解,每个子问题对应给定车间,钢级(或钢级组)二元组下的多背包问题,本质上是对常规D-W分解的多个子问题约束进行聚合。所提出的新分解策略降低了子问题数目及子问题间的耦合度,能够有效简化主问题求解和提升下界。在个人计算机(Intel Core(TM)2 Quad 2.83 GHz CPU 和 3.25GB 内存)上,使用C++语言实现了求解多个D-W分解模型的列生成算法,并进行数值计算实验,实验结果验证了基于多约束聚合D-W分解策略的有效性。