Modeling and solving the steelmaking and casting scheduling problem

• Date: 01 January 2020
• Author: Luca Di Gaspero,Davide Armellini,Andrea Schaerf,Paolo Borzone,Sara Ceschia
• DOI: http://doi.org/10.1111/itor.12595
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 57–90

DOI: 10.1111/itor.12595

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Modeling and solving the steelmaking and casting

scheduling problem

Davide Armellinia, Paolo Borzonea, Sara Ceschiab, Luca Di Gasperob,∗and

Andrea Schaerfb

aDanieli Automation S.p.A., via Bonaldo Stringher 4, I-33042 Buttrio (UD), Italy/piazza Borgo Pila 39,

I-16129 Genoa, Italy

bDPIA, University of Udine, via delle Scienze 206, I-33100 Udine, Italy

E-mail: d.armellini@dca.it [Armellini]; p.borzone@dca.it [Borzone];sara.ceschia@uniud.it [Ceschia];

luca.digaspero@uniud.it [Di Gaspero]; schaerf@uniud.it[Schaerf]

Received 17 November2017; received in revised form 29 August 2018; accepted 29 August 2018

Abstract

We propose a general model for the problem of planning and scheduling steelmaking and casting activities

obtained by combining common featuresand constraints of the operations from a real plant and the literature.

For tackling the problem, we develop a simulated annealing approach based on a solution space made of

job permutations, which uses as submodule a chronological constructive procedure that assigns processing

times and resources to jobs. Our technique, properly tuned in a statistically principled way, is able to find

good solutions for a large range of different settings and horizons. In addition, it outperforms both a greedy

procedure and a constraint-based solver developed for comparison purposes on almost all instances. Finally,

we have collected several real-world instances that we make available on the web along with the solution

validator and our best results.

Keywords:steelmaking; continuous casting; simulated annealing; hybrid flow shop

1. Introduction

The steelmaking process is one of the most complex industrial production operations due to the

presence of many technological (physical, chemical, mechanical, etc.) and business constraints. The

operation of a steelmaking plant is quite costly, therefore the throughput maximization by means

of an optimized scheduling is of crucial importance to ensure productivity and competitiveness.

The steelmaking process comprises four stages outlined in Fig. 1. At first, the iron scrap is melted

in an electric arc furnace (EAF), then the liquid metal is poured in a ladle that will be used to contain

∗Corresponding author.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

58 D. Armellini et al. / Intl. Trans.in Op. Res. 27 (2020) 57–90

Fig. 1. A schematic illustration of the steelmaking and casting production process.

the steel in all the following processing steps. The next step is the ladle furnace (LF) in which some

additives are added for obtaining the desired chemical composition of the product. Afterward, the

metal undergoes the vacuum degasification(VD) process, which reduces hydrogen and nitrogengases

dissolved in the liquid steel, improving final products quality.

The last production step, called casting, consists in the controlled solidification of the liquid steel

in order to obtain the desired shape of semifinished product and might differ based on the type of

product required. Indeed, depending on the process used for the solidification, usually continuous

casting (CC) machines (for production of slabs, blooms, and billets) or ingot casting (IC) machines

(for ingots production) are employed. These semifinished products,then, could be subject to further

processing (e.g., hot rolling), which might be planned and scheduled independently from the casting

process.

The main physical constraint of the steelmaking process is the practical impossibility to buffer

jobs between different processing steps because of the cooling of the liquid metal in case of waiting.

As a consequence, the jobs should be scheduled in a just-in-time fashion.

A similar version of the problem considered in this paper was presented by Fanti et al. (2016)

who proposed an integrated system consisting of a database, an optimization engine, a simulation

module, and a user interface for the scheduling problem of a specific plant. The optimization engine

models the scheduling as a hybrid flow shop using a mixed integer linear programming (MILP)

formulation.

With respect to Fanti et al. (2016), we have made several modifications (see Section 3) to better

represent the real-world specifications, including the presence of the border data, coming from the

previous schedule. In addition, in order to obtain a model that captures the essential features of the

problem, we have simplified the problem statement, so as to remove low level details too specific

for the situation at hand. On the other side, we have generalized the problem including features

specified by Danieli Automation1that were not included in the original model of Fantiet al. (2016),

but are common across different plants.

For this problem, we propose a metaheuristic method based on simulated annealing (SA) that

operates at the level of job sequencing, so that the solution is represented as a permutation of the

1Danieli Automation is part of the Danieli Group, one of the world-leading suppliers of equipment and plants to the

metal industry.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

D. Armellini et al. / Intl. Trans.in Op. Res. 27 (2020) 57–90 59

jobs. The actual schedule is obtained by a deterministic subprocedure that computes start times

and resources of all operations, onejob at the time, following the order on the current permutation.

The neighborhood structure is based on the movement of either a single job or a group of setup-

compatible ones.

We collected a dataset of real-world instances coming from the same plant of Fanti et al. (2016),

but with a different and larger set of operating conditions. Instances and results are available at

https://opthub.uniud.it, and hopefully could be used as a benchmark for future researches and

comparisons, given also the lack of available ones in the literature. To this aim, the website includes

an online solution validator that provides against possible misinterpretations of the formulation.

The experimental results show that for many instances, we can find a solution that schedules a

number of jobs relatively close to the upper bound, and without violating any important opera-

tional conditions. Conversely,both a greedy procedure and a constraint-based solver, developed for

comparison, have not being able to reach similar results.

2. Problem formulation

In this section we describe the formulation of the steelmaking and casting scheduling problem

(SMCP), which represents the essential part of the real-world problem under consideration. The

formal description of the constraint-based model is provided in Appendix.

2.1. Problem structure

The problem structure can be described through the following basic notions.

Machine: There are five differen t machine types, corresponding to the four main stages of the

process: EAF for melting, LF for refining, VD for degassing, and CC or IC for continuous or

ingots casting. Each machine, except CCs and ICs, belongs to a line that identifies the habitual

process flow of jobs throughthe plant. In addition, machines have a processing time,amax stretch

time that is the maximum time a machine can slow down its process before the next stage, and

possibly a production standstill time window (MachineStops) due to maintenance services or

temporary machine breakdowns (Tang et al., 2014).

Job: Jobsare grouped by steel grades, depending on the required chemical composition and the type

of process needed (i.e., continuous or IC); moreover a job specifies further processingdetails such

as the section width and its possible incompatibility with some of the casters (e.g., because the

job section cannot be processed by the machine). A machine can process only one job at a time,

and after the processing is completed the job is moved forward to a different machine of the next

stage. The movement between two machines takes up a constant transportation time, depending

on the distance between the two machines (Distances). Finally, because of the independent

planning of the postprocessing activities, a job can have an appointment, that is a time window

for its completion time.

Ladle: The molten steel is poured in a container, called ladle, which is moved through the plant till

the end of the process. A job can wait in the ladle for the next production step for a maximum

fixed amount of time (MaxWaitingTimeInLadle). At the end of the process, the ladle has

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies