A bi-layer optimization approach for a hybrid flow shop scheduling problem involving controllable processing times in the steelmaking industry

Shenglong Jiang ^a, Min Liu ^a,, Jinghua Hao ^a, Wangping Qian ^b

^a Department of Automation, Tsinghua University, Beijing 100084, PR China

^b Center for Computer Application, Jiangsu Shagang Group Co., Ltd, Zhangjiagang 215625, PR China

ARTICLE INFO

Article history:

Received 16 September 2014

Received in revised form 31 May 2015

Accepted 2 June 2015 Available online 9 June 2015

ABSTRACT

A steelmaking-continuous casting (SCC) scheduling problem is an example of complex hybrid flow shop scheduling problem (HFSSP) with a strong industrial background. This paper investigates the SCC scheduling problem that involves controllable processing times (CPT) with multiple objectives concerning the total waiting time, earliness/tardiness and adjusting cost. The SCC scheduling problem with CPT is seldom discussed in the existing literature. This study is motivated by the practical situation of a large integrated steel company in which the just-in-time (JIT) and cost-cutting production strategy have become a significant concern. To address this complex HFSSP, the scheduling problem is decomposed into two subproblems: a parallel machine scheduling problem (PMSP) in the last stage and an HFSSP in the upstream stages. First, a hybrid differential evolution (HDE) algorithm combined with a variable neighborhood decomposition search (VNDS) is proposed for the former subproblem. Second, an iterative backward list scheduling (IBLS) algorithm is presented to solve the latter subproblem. The effectiveness of this bi-layer optimization approach is verified by computational experiments on well-designed and real-world scheduling instances. This study provides a new perspective on modeling and solving practical SCC scheduling problems.

2015 Elsevier Ltd. All rights reserved.

Keywords: Steelmaking; Hybrid flow shop; Scheduling; DE; VNDS

1. Introduction

The hybrid flow shop scheduling problem (HFSSP), which is also referred to as the flexible flow shop scheduling problem (FFSSP) or flow shop with multiple processors scheduling problem (FSMPSP), has attracted the attention of numerous researchers (Ribas, Leisten, amp; Framintilde;an, 2010; Ruiz amp; Vaacute;zquez-Rodriacute;guez, 2010). It is a complex problem that is applied in many industry fields, such as the chemical industry, the paper-making industry, the food industry, and the metallurgical industry (Hakimzadeh Abyaneh amp; Zandieh, 2011). Fig. 1 illustrates the production process flow in a steelmaking plant.

The general steelmaking process always involves three stages: (1) The steelmaking stage, in which the pig iron and the scrap steel are converted into liquid steel in the basic oxygen furnace (BOF) or electric arc furnace (EAF). The liquid steel is poured into a ladle and transferred to the next stage with an idle crane. (2) The refining stage, in which the chemical composition and the temperature of liquid steel are adjusted to the predetermined level in a refining machine, such as a ladle furnace (LF) and a Rheinstahl–Heraeus (RH). For some high-precision steel grades, more than one refining machine is employed. (3) The casting stage, in which the liquid steel is cast and cut into slabs or bullets through continuous casting machines (CCM) operated continuously. In some practical situations, the processing speed of each CCM can be controlled to satisfy the continuity constraint of the CCM and to stabilize the temperature (Missbauer, Hauber, amp; Stadler, 2009).

With regard to an integrated steel company, the steelmakingcontinuous casting (SCC) is pivotal for boosting productivity, reducing production costs and achieving sustainable scheduling of manufacturing systems. However, it is also the bottleneck between ironmaking and rolling mills. This paper addresses the previously mentioned concerns and presents the results of our industrial scheduling work using a bi-layer optimization approach. The remaining contents are organized as follows. In Section 2, the literature about scheduling problems related to the SCC production and controllable processing times (CPT) is reviewed. In Section 3,the mathematical model of the SCC scheduling problem is provided. In Section 4, a hybrid differential evolution (HDE) algorithm enhanced by a variable neighborhood decomposition search (VNDS) is proposed after the essential elements are discussed in details.

Ironmaking Production SCC Production Hot Rolling Production Fig. 1. The process flow diagram for a steelmaking plant.

In Section 5, a novel heuristic approach, named iterative backward list scheduling (IBLS), is presented for the scheduling problem in the upstream stages. To obtain appropriate performance of the algorithm, the parameters of HDE-VNDS are tuned by the Taguchi method in Section 6. The experimental results and comparisons are listed and analyzed in this section. Section 7 provides some conclusions from this paper. All involved algorithms are coded by Visual C 2012 and run on a PC- with an Intel Coretrade; i5 CPU and 8 GB RAM, using Gurobi 6.0 for solving linear programming problems.

2.Literature review

2.1Steelmaking-continuous casting scheduling problem

The SCC scheduling problem, which is regarded as a special HFSSP with strong constraints, is an important research topic extensively investigated in academic and industrial communities. Various algorithms for the SCC scheduling problem have been discussed in the literature. They can be categorized into three types: the exact method, the heur

剩余内容已隐藏，支付完成后下载完整资料

---

炼钢行业内基于双层优化方法的

带有可控加工时间的混合流水车间调度问题

Shenglong Jiang,Min Liu,Jinghua Hao,Wangping Qian

摘要

持续炼钢铸造(SCC)调度问题是一个拥有强大工业背景的复杂的混合流水车间调度问题的例子。探讨SCC调度问题涉及到可控加工时间（CPT）与多个目标包括总等待时间、提前/延后和成本调整。可控加工时间的SCC调度问题在现有文献中很少讨论。本文的研究是根据大型综合性钢铁公司的实际情况，准时制和成本削减生产策略已成为一个重要的问题。为解决这个复杂的混合流水车间调度问题，将调度问题分解为两个子问题：一个最后阶段的平行机调度问题和一个上游阶段的混合流水车间调度问题。首先，针对前一个子问题提出结合变邻域分解搜索的混合差分进化算法。第二步，提出迭代反向调度列表解决后者的子问题。这种双层优化方法的有效性通过精心设计的计算实验和实际生产调度实例进行验证。本文提出了一个新的建模视角解决实际持续炼钢铸造调度问题。

关键词：炼钢；混合流水车间；调度；差分进化；变邻域分解搜索

1.介绍

混合流水车间调度问题（HFSSP）也称作柔性流水车间调度问题（FFSSP）或多个处理器的流水车间调度问题（FSMPSP），吸引了众多研究者的注意(Ribas et al., 2010 和 Ruiz and Vaacute;zquez-Rodriacute;guez, 2010)。这是一个复杂的问题，已经应用于许多工业领域，如化工、造纸工业、食品工业和冶金工业(Hakimzadeh Abyaneh amp; Zandieh, 2011)，图1说明了炼钢厂的生产流程。

一般的炼钢过程包括三个阶段：（1）炼钢阶段，生铁和废钢在氧气顶吹转炉或电弧炉中转化成钢水，将其注入钢水包中，利用闲置的起重机转移到下一阶段。（2）精炼阶段，在精炼机中将钢水的化学成分和温度调整到预定的级别，如钢包炉（低频）和Rheinstahl–Heraeus（RH），对于一些高精度的钢则需要不止一台精炼机。（3）铸造阶段，在这一阶段钢水通过连续铸造机进行铸型并切成厚品或子弹状。在实际情况中，每台连铸机的处理速度可控，满足连铸机的连续性约束和稳定温度(Missbauer, Hauber, amp; Stadler, 2009)。

对于一个集成的钢铁公司，SCC是提高生产率、降低生产成本，实现可持续制造系统调度的关键。然而，它也是炼铁和轧钢厂之间的瓶颈。本文解决了前面提到的问题，并且提出了使用双层优化方法的工业调度工作成果，余下部分内容总结如下。在第二节中，查阅了有关带有可控加工时间的SCC生产调度问题的文献。在第三节中，建立了SCC调度问题的数学模型。在第四节中，详细讨论基本要素后提出通过变量邻域分解搜索提高混合差分进化算法。在第五节中，对于调度问题的上游阶段提出了一个新颖的启发式方法，名叫迭代反向列表调度。在第六节中，利用田口方法调谐基于变邻域分解搜索的混合差分进化的参数以便获取适当的算法性能，实验结果的分析与比较也在这一节中列出。第七节提供了结论，本文涉及到的所有算法编码由Visual C 2012完成，并在Intelreg;核心trade;i5处理器和8 GB内存的PC上进行了运行，使用Gurobi 6.0求解线性规划问题。

炼钢生产 SCC 生产 热轧生产 图1 炼钢厂生产流程

2.文献综述

2.1SCC调度问题

SCC调度问题，被认为是带有强有力约束的一种特殊的混合流水车间调度问题，作为一项重要的研究课题在学术和工业领域内进行了广泛的调查和交流。SCC调度问题的各种算法在文献中已经讨论过，总结可分为三种类型：精确算法、启发式算法和元启发式算法。

根据准时制（JIT）生产策略，Tang, Liu, Rong, and Yang (2000)建立了一个非线性模型，并转换成一个线性规划模型。专注于一个来源于现实应用程序中的模型，Bellabdaoui 和 Teghem (2006)开发了一个混合整数线性规划公式，经过放松一些约束，这两种模型可以解决标准软件包。Tang et al., 2006 和Xuan and Tang, 2007运用拉格朗日松弛法将SCC调度问题分解成基于块的子问题，开发动态规划方法解决。Mao, Pan, Pang，和Chai (2014)通过放松容量限制将SCC调度问题分解成两个易处理的子问题，并提出了一种改进的次梯度算法。Pacciarelli和 Pranzo (2004)提出了一种可替代的图表模型来描述SCC调度问题的约束条件，并设计出一种定向搜索算法。Atighehchian, Bijari, 和Tarkesh (2009)提出了一个名为因素的的混合算法，结合了蚁群优化算法和非线性优化算法。Tang 和 Wang (2010)提出了一种改进的粒子群优化算法，最小化加权总完工时间，展现出炼钢行业的背景。根据一些特定问题的特征，Pan, Wang, Mao, Zhao, and Zhang (2013)设计了一个基于工件排列的人工蜂群算法，其中包含几个改进的启发式程序。Tang, Zhao, and Liu (2014)提出了一种基于增量机制的改进的微分进化算法来解决动态SCC调度问题。为解决实际SCC调度问题，Li, Pan, Mao, and Suganthan (2014)提出了一个有效的果蝇优化算法，其解决方案是利用前导式链表排程方法进行解码。

2.2涉及可控加工时间（CPT）的调度问题

涉及可控加工时间（CPT）的调度问题的最初研究是由Vickson(1980)完成的。Shabtay和 Steiner (2007)在2007年前总结了之前完成的研究。最近，有更多的研究人员将他们的注意力集中于这个领域。Mokhtari, Abadi,和Cheraghalikhani (2011)提出了混合离散变量微分进化（HDDE）和邻域搜索（VNS）算法来解决依赖资源处理时间的多目标流水车间调度问题。Mokhtari, Abadi, 和 Zegordi (2011)对于可控加工时间不作业车间调度问题设计了一个两阶段遗传算法（GA）。Bensoussan,和 Kaspi (2012)针对因资源配置使得加工时间可控的准时制流水车间调度问题提出了伪多项式时间算法。Behnamian 和 Fatemi Ghomi (2011)对于依赖资源处理时间的混合流水车间调度问题提出了一个基于遗传算法和邻域搜索的混合方法。Kayvanfar, Mahdavi, 和 Komaki (2013)针对给定序列的单机排序问题的优化处理时间提出了一个净效益压缩-净效益扩张的启发法。为解决带有可控加工时间的无关平行机调度问题，Kayvanfar, Komaki, Aalaei, 和 Zandieh (2014)提出了一个并行净效益压缩-净效益扩张启发式优化作业处理时间以及一些进化算法优化每台机器上的工作序列。

在现有SCC调度问题的研究中，工件的加工时间被视为固定参数。然而，在实际的生产环境中，铸造阶段的加工时间可以通过调整板宽度或链数进行控制。包含可控加工时间的SCC调度问题只在Missbauer et al. (2009)中讨论过，用来制定一个没有计算结果的数学规划模型。本文相较于之前的研究提出了一个新的说法，忽略一些冗余约束（钢包、废料和热铁），并提出一种元启发式算法。

3.问题定义

在本节中，我们依据持续炼钢铸造生产过程提供了一个详细的调度问题数学模型，这是本文的最初目的。

3.1先决条件

SCC调度问题可以看作是一个特殊的混合流水车间调度问题，因为所有工作在多个并行机同一方向的几个阶段进行，必须解决下面的多余约束：

1. 因为不同钢材可能有不同的工艺路线，可以跳过一些精炼机；
2. 在铸造阶段，每台连铸机的加工速度是可控的。因此，每个工作的处理时间是一个决策变量，提供额外空间来提高系统性能；
3. 因为连铸机的一个关键组成部分，即每个中间包的生命是有限的，最后阶段的所有工作应该按批次连续加工。
4. 同一批次的所有工作必须在同一台连铸机上连续加工；
5. 每一个批次的工作数量可以根据中间包的生命进行预定，但工作序列无法定义；
6. 当一个新的中间包安装在连铸机上，每个顺序独立的装设时间被认为是一个批次。
7. 批处理最后一阶段的加工机器预分配如下。

其中R_g,k 是机器m_g,k 上最后一批计划完成时间，接下来，分配每一批次d_l 的计划开始时间

这种方法导致每个批处理具有一个相对紧凑的起始时间，因为它忽略了上游阶段的所有约束。SCC调度问题的主要目标如下：

1. 等待目标。由于温度损失，同一工作的两个相邻操作之间的总等待时间必须最小化；
2. 准时制目标。根据准时制原理，每一批计划起始时间的总拖延和提前时间必须最小化；
3. 调整目标。当加工速度偏离标准值，总机器调整成本必须最小化。

这些特殊的约束条件和目标使SCC调度问题相较于标准的混合流水车间调度问题更为复杂。根据Vignier,Billaut和Proust(1999)提出的扩展符号alpha;、beta;、gamma;，本文中讨论的调度问题可以表示如下：

3.2符号

表1 符号说明

符号 表示含义

i 阶段指数，iisin;{1,2hellip;,g},g是总阶段数

j 工作指数，jisin;{1,2hellip;,n},n是工作总数

l 批次指数，lisin;{1,2hellip;,h},l是批次总数

m_i,k i阶段的第k个机器，nk_i是i阶段的机器总数

n_l 第l批次的工作总数，

B_k 最后一阶段第K个机器的分配设置，b_k是B_k的大小，B_k,q是第q个因素

Q_i,j i阶段工作j的操作

P_i,j 第i阶段工作j的加工时间

u_l 最后阶段开始之前l个批次的设置时间

t_{i,i 1} 阶段i到阶段i 1的传递时间

S_i,j i阶段工作j的起始时间

C_i,j i阶段工作j的完成时间

v_l 最后一阶段第l批次的可控加工速度，精度为0.1

v_l^-,v_l 最后阶段第L批次的最小和最大可控加工速度

d_l 由设计者给出的第l个批次的提前分配起始时间

gamma;₁ 等待目标的成本系数

gamma;₂ 准时制目标的成本系数

gamma;₃ 可调整目标的成本系数

l 一个充分大的正数常量

3.3数学模型

（1）决策变量

S_i,j :工作j在第i阶段的起始时间；一个整数变量。

V_l:批次l的可控加工速度；一个实型变量。

（2）目标

基于这些SCC调度问题的符号，目标制定如下：

(2)

(3)

(4)

最小化 (5)

（3）约束条件

(6)

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[147657]，资料为PDF文档或Word文档，PDF文档可免费转换为Word