Genetic Algorithm Based on Duality Principle for Bilevel Programming Problem in Steel-making Production☆Shuo Lin1,*,Fangjun Luan1,Zhonghua Han1,Xisheng Lü2,Xiaofeng Zhou2,Wei Liu3

Information&Control Engineering Faculty,Shenyang Jianzhu University,Shenyang 068,China

2Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang 110016,China

3School of In formation Science&Engineering,Northeastern University,Shenyang 110004,China

Genetic Algorithm Based on Duality Principle for Bilevel Programming Problem in Steel-making Production☆
Shuo Lin1,*,Fangjun Luan1,Zhonghua Han1,Xisheng Lü2,Xiaofeng Zhou2,Wei Liu3

1Information&Control Engineering Faculty,Shenyang Jianzhu University,Shenyang 110168,China

2Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang 110016,China

3School of In formation Science&Engineering,Northeastern University,Shenyang 110004,China

A R T I C L E I N F O

Article history:

Received 27 December 2013

Received in revised form 19 February 2014 Accep ted 3 March 2014

Available on line 25 June 2014

Steel-making and continuous/ingot casting are the key processes of modern iron and steel enterprises.Bilevel programming problems(BLPPs)are the optimization problems with hierarchical structure.In steel-making production,the plan is not only decided by the steel-making scheduling,but also by the transportation equipment. This paper proposes a genetic algorithm to solve continuous and ingot casting scheduling problems.Based on the characteristics of the problems involved,a genetic algorithm is proposed for solving the bilevel programming problem in steel-making production.Further more,based on the simplex method,a new crossover operator is designed to improve the efficiency of the genetic algorithm.Finally,the convergence is analyzed.Using actual data the validity of the proposed algorithm is proved and the application results in the steel plant are analyzed.

?2014 Chemical Industry and Engineering Society of China,and Chemical Industry Press.All rights reserved.

1.Introduction

During recent years,the continuous casting technology developed in the 1950s underwent a rapid grow th.Because the continuous casting technology can save more energy consumption in the production process from hot steel to slab,the main steels are produced by continuous casting. During the process of steel-making and continuous casting,most of the material transportations within the whole process are finished by cranes. The crane scheduling is the scheduling important branch to assist the scheduling of the main equipments(steel-making,refining,continuous casting machines).A coordinating steel-making and continuous casting system consists of the scheduling of main equipments and assist transportation equipments.Because a good iron and steel making scheduling system could not only realize the reduction of the energy but also improve the production,and the steel-making and continuous casting is the bottleneck of thew hole iron and steel production,the crane scheduling p lays an important role in the w hole process.The major problem of this paper is how to make a good crane schedule in a computationally efficient manner and effectively assist the scheduling of the main equipments in order to ensure a well-organized rhythm in thew hole production and to improve the transportation efficiency of the cranes.

Harjunkoski and Grossmann[1]developed a decomposition strategy for solving large scheduling problems using mathematical programming methods.Lee et al.[2]solved a scheduling problem for operating the continuous caster by using the concept of a special class of graphs known as interval graphs.Ouelhadj et al.[3]described a new model for robust predictive/reactive scheduling of SCC based on the use of multi-agents,tabu search and heuristic approaches.At Stahl Linz GmbH,Neuwirth[4]reported a linear programming model with machine convicts and provided key modeling factors of SCC scheduling and charge allocation scheme in the furnace,but the mathematical representation of the model was not given.An expert system was used by Jimichi et al.[5]to determine parameters and operational conditions to match slab production with customer orders.

Stahl Linz GmbH,Stohl and Spopek[6]established a hybrid co-operative expert system model for the SCC scheduling problems,but they were unable to construct an optimized mathematical model.Ferretti et al.[7]presented the algorithmic solution based on an ant system metaheuristic for an industrial production inventory problem in a steel continuous casting plant.The model took into account the relevant parameters of the finite-capacity production system.The study focused on the optimization of the production sequence of the billets.Blackburn and Millen[8]examined the impact of a rolling-schedule implementation on the performance of three of the better known lot-sizing methods for single-level assembly systems.Atighehchian et al.[9]developed a novel iterative algorithm for scheduling steel-making continuous casting production,named HANO.This algorithm was based on a combination of ant colony optimization(ACO)and non-linear optimization methods.Zhu et al.[10]set a novel optimization model to improve the efficiency and performance for production planning in steel making and continuous casting(SCC)process.

2.Genetic Algorithm for Bilevel Problem

Bilevel-programming techniques were initiated by Von Stackelberg [11]for bilevel programming problems(BLPPs)based on the dual programming of the follower's problem and the dual theorem.The region of the leader's variables was divided in to several sub-regions,such that for all values of the leader's variables in each sub-region,the follower's problem had the same solution expression.Furthermore,a genetic algorithm was used to solve the leader's problems,in which a new crossover operator was designed based on the simplex method. An advantage of the proposed genetic algorithm was that the optimal solutions to the follower's problem can be obtained very easily without massive calculation of the follower's problem.Also,a method of dynamic penalty function was presented.

2.1.Bilevel problem

The bilevel problem is as follows:

{u1,u2,…,uk}is the basic feasible solution of problem(2).{B1,B2,…,Bk}Bi.The necessary and sufficient condition that Biis the optimal feasibleDomain i is the divided domain of inequality i.If leader variable χ satisfies inequality i,it belongs to domain i.According to the dualityThere are two steps in the calculation.

(1)Solve the domain i of leader variable χ,calculate

(2)Calculate the problem:

2.2.Fitness function

Set R(χ)=F(χ,y(χ))+Mgand max{G(χ,y(χ)),0,i=1,2,…,p}is individual fitness.Where g is the iteration of genetic;G(χ,y(χ))is the component of G(χ,y(χ)),Mgis the dynamic penalty factor and M1is a p re-given positive integer decided by the point in population. Set χ0,χ1,χ2,…,χnis n+1 optimal and no identical points which are collected by fitness.Calculate

If n+1 points are affine independence,{χ0,χ1,χ2,…,χn}is a simplex. With an increasing iteration number,points in population tend to accordance,when Mgtends to infinity.

2.3.Crossover operator

psis population size.Sort the fitness of pop(k)points ascendingIf there are not n affine independence points,χ1is the vertex and construct other n?1 points in its neighborhood.Make sure n points are affine independence;The construction method is from Takahama T.and Sakai S.[11].Re-sort the population,delete the worst n?1Offspring of crossover individual χ,is

where,r∈[0,1]is random number,δ and Δ is positive constant.When r=1,ocreaches boundary of search field.χ1is the best point in population.When crossover individual χ and points in S is affine independence,there is a simplex which can use the simplex algorithm.

2.4.Mutation operator

^χis the father individual:

Ifχ1?^χ‖‖≤ε，mutation offspring om=^χ+Δ1;else om=^χ+diagΔ2（）χ1?^χ（）; whereΔi=(Δi1,Δi2,…,Δin)T,i=1,2;Δ1j～N(0,),j=1,2,…,n;Δ2j～N(1,),j=1,2,…,n;N(u,σ2)is the Gaussian d istribution,u is the m ean andσ2is the variance.

2.5.Genetic algorithm

The genetic algorithm is as follows:

Step 0:Calculate the feasible basis of follower dual problem B1,…,Bk;

Step 1:Generate pspoints χi,i=1,2,…,psin boundary constraintset X uniform ly.Substitute eachχiin to the exp licit exp ression in the fo llower level.To get y(χi),let all pointsχibe the popu lation pop(0)whose size is ps.Calcu late the fi tness of each individual and sorfi tnessin? order.For conscience,denote pop（0）=χ1，χ2，…，χps,let k=0;

Step 2:pcis the crossover probability.Get crossover individual χ from pop(k),χis the crossover offspring of;O1 is set of all crossover off spring;

Step 3:For each individual χ in pop(k),mutate with probability pm,get mutation offspring^χ.O2 is set of mutation off spring;

Step 4:Calculate fitness of all off spring individual,get N1(N1＜ps)best individuals from pop(k)∪O1∪O2.Get the next generation population pop(k+1)from other ps?N1individuals;

Step 5:If match terminating condition,algorithm end,else let k=k+1, go to Step 2.

2.6.Convergence analysis

Definition 1.{ξi}is a vector sequence of probability space.If ξ exists,{ξi}converge to ξ on probability 1.

Lemma 1.(Borel-Cantelli)If A1,A2,…,Am,…,is a vector sequence of probability space,setm u tual independence,so p rob

Upper space projection of IR is S′(X)={χ∈X|?y,let(χ,y)∈IR}. There are 5 assumptions:

Assumption 1.Feasible region of follower problem and dualproblem is bounded.

Assumption 2.There is only optimal solution for each χ in upper level.

Assumption 3.S′(X)is a bounded closed set,and F(χ,y)is continuous onΩ.

Assumption 4.There is a global minimizer χ*at least;?δ＞0, the Lebesgue measure of set S′(X)∩{χ|‖χ?χ*‖＜δ}is m o re than 0.

Assumption 5.?χ∈X,the follower problem is nondegererate.

For?ε＞0,Q1={χ∈S′(X)|‖F(xiàn)(χ,y(χ))?F*‖＜ε},Q2=S′(X)Q1;

F*=m in{F(χ,y):(χ,y)∈IR}={F(χ*,y(χ*)):χ*∈S′(X)}.So there are two states S1and S2:

S1:If there is a point that belongs to Q1at least,pop(k)is in S1;

S2:If there is on point that belongs to Q1,pop(k)is in S2.

Theo rem 1.pij(i,j=1,2)means pop(k)in state Si.The probability that pop(k+1)is in state Sjis as follows:

(a)For each pop(k)in state S1,p11=1.

(b)For each pop(k)in state S2,?c∈(0,1),p22＜c.

Proof.If pop(k)∈S1,pop(k)∈S1,pop(k+1)∈S1,so(a)is tenable.S0is the optimal solution set.?χ*∈S0which satisfies Assumption(4). When→χ*,y(χ)→y(χ*),where y(χ)is the follower optimal solution corresponding to χ.Set χ=χ*+Δχ,B is the optimal solution feasible basis of problem(1)corresponding to χ*.From linear programming theo-and y(χ)→y(χ*),so y(χ)is continuousat χ*.

Because F(χ,y)is continuous,?ε＞0,?γ＞0,when χ∈S′(X)and‖χ?χ*‖≤γ,

When χ∈S′(X)∩{χ|‖χ?χ*‖≤γ},|F(χ,y(χ))?F*|＜ε.Let Nγ(χ*)= {χ∈Rn|‖χ?χ*‖＜γ}.When pop(k)is in state S2,and omis the mutation off spring of^χ∈pop k（）,so om=^χ+Δ1or om=^χ+diagΔ2（）χ1?^χ（）. Because each component of Δiis independent,and Gaussian distribution i=(1,2).So each component of omis independent and Gaussian distribution.Denote om～N(μ,σ2).μ and σ2is continuous about^χ.The probability of om∈S′(X)∩Nγ(χ*)is as follows:

where μiis component of μ.DenoteSo the probability that point^χ can get into Q1is p2（^χ）=pmp1（^χ）.S′(X)∩Nγ(χ*)is bounded closed set and Lebesgue measure ismore than 0.From Eq.(8),0＜p1（^χ）＜1,and p1（^χ）is continuous in bounded closed set X. So?μ∈X:

p21means that pop(k)is in state S2,from Eq s.(8)and(9),p21≥p2p21+p22=1,p22=1?p21≤c.So(b)is tenable.

Theo rem 2.{pop(k)}is a population sequence created by algorithm. There is one point in pop(0)that belongs to S′(X).χ*(k)is the optimal point in pop(k).When Assumptions(1)-(5)are satisfied:

Proof.?ε＞0,denote pk=p rob(|F(χ*(k),y(χ*(k)))?F*|≥ε),so

3.Mathematical Model

During the process of steel-making and continuous casting,based on the scheduling of the main equipments and the corresponding steel ladle destination,the routes of the ladle could be divided into the following modes:

1)LD?no finery?casting mode:after receiving the molten steel when the process of LD process is finished,the crane transports the motel steely by steel ladle to the casting,takes it for preprocessing and takes the steel ladle to the continuous casting by crow n crane.

2)LD?no finery?IC mode:after receiving the molten steel when the LD process is finished,the crane transports the charge to the casting line.In the casting line,the crow n crane transports it by steel ladle to take the pre-process and transports the steel ladle by crane to another casting line,and the crow n crane will take the steel ladle to the ingot casting finally.

3)LD?fi nery?casting mode:after receiving the molten steel when the LD process is finished,the charge is sen t to the casting line.After the p re-process,the charge is sent to the refining stage,the crow n cranes take the action of loading and unloading,and the crown crane takes the charge in to the casting line.

4)LD?fi nery?IC mode:after receiving the molten steel when the

LD process is finished,the charge is sent to the casting line.After the pre-process,the charge is sen t to the refining stage,the crow n

cranes take the action of loading and unloading,and the crown crane

takes the charge in to the ingot casting line.

To describe the continuous/ingot casting production process,we introduce the following special term s:

3.1.The scheduling model of continuous and ingot casting

Half-charge plan adjustment keeps processing equipment yijkinvariant,which is located in the nonproducing work station.Making plan of equipment's processing starting time stijk.

The mathematical model for the mixed half-charge plan and scheduling problem is formulated as follows:

to maintain the shortest distance δ between two adjacent cranes.

Introduce the following variables:

The objective is to minimize the sum of project completion time.The objective function is as follows:

Constrain t(11)rep resents that the charges in a same continuous casting must have close cohesion,pre and post.This station is the miprocess which is also the last process.Constrain t(12)represents that there is a setup time interval between adjacent ingot castings.Constrain t(13)rep resents that each charge cannot be interrupted when it is processing on a station.Constraint(14)represents the constraints of the equipment.The same equipment can only process the next charge when the last one is over.Constrain t(15)represents the constraints of the job order.The same charge can only continue the next station when the last one is over.Constraint(16)rep resents the starting time of the station.

3.2.Crane schedule

In order to facilitate the mathematical analysis of the crane scheduling problem,several conditions are assumed.

?The finishing operation order of every plan is decided.

?Every plan must be only the overall production and cannot be divided

into multiple parts.

?More of the same quality product cannot be produced as aw hole.?Each processing time on the device is known.

?The crane position in the same rail remains the same sequence

Fig.1.The finish time/min comparison.

Constrain t(18)requires that every Oijmust been assigned to a device.Constraints(19)and(20)give a relationship betweenandConstrain ts(21)and(22)m eanthat the p re-order job must be completed before the follow-up job starting in the same device.Constrain ts(23)and(24)are the requirement of crane transportation.Constraint(25)ensures that every Oijhas a crane.Constraint(26)means one crane must have a job.Constrain t(27)shows that the processing position and the position assigned to Oijis the same.Constrain t(28) means the crane has its maximum speed.Constrain t(29)shows the shortest distance δ between two adjacent cranes.

4.Numerical Results

In the plant,the scheduling plan is a manual plan.The steel making plant has so many equipments:3 converters,7 refineries,3 continuous casters,3 ingot casting lines and 4 cranes.

Set the parameter of the algorithm with the steel making plant plan and steel species.Save the parameter to rule base.Get the parameter from rule base based on schedule plan and steel species each time.A comparison is made between the scheduling method and model system that is used in steel plant.The finish time of each heat is shown in Fig.1. Using the scheduling method,the average heat finish time is reduced by 13.5 m in.The average rate of this scheduling method in the steel making plant is shown in Fig.2.The method has a better performance.

After being applied in the operation in the steel plant at Shanghai, the performance index is as follows:The average planning time is 8.4 s and the dynamic ad justing time is about 4.5 s in the production m ode such that the daily average production is 66 heats.Comparing with the manual and general model systems,the average daily load of the converter increases from 60.85%to 67.04%,the average daily load of the refinery increases from 42.21%to 45.00%,the average rate of equipment load increases from 50.44%to 55.16%and the average heat completion time goes from 195.88m in down to 176.38 min.

Fig.2.The scheduling improvem ent in the steelplant.

5.Conclusions

Bilevel programming problems(BLPPs)are nonconvex optimization problems with hierarchical structure.The vast majority of the existing research works on BLPPs is concentrated on linear BLPPs and some special nonlinear BLPPs in which all of the functions involved are convex and twice differentiable.In this paper,a genetic algorithm used in steel plant is given to solve the bilevel problem.The convergence of the algorithm is verified.The algorithm result is verified that the scheduling method and policy of the steel making continuous and ingot casting are efficient.

Nomenclature

aijposition of device which processes Oij

adjtingotthe standard interval time between ingot castings

CT(a,b)crane running time from position a to position b

dliftsand drops time when crane transports the ladle

ETijprocessing end time of Oij

etijkthe work station j's processing end time of charge i processed on equipment k

j serial number of work station,1≤j≤mi

K the total amount of equipments;

Kjthe parallel machine number of work station j

k,k′serial number of equipment.1≤k,k′≤K

M number of available crane

mithe total work station amount of charge i

Nimanufacturing procedure set of charging plan i,i∈U

n serial numbers of cast,N is the total amount of continuous casting batch casts,n=1,2,…,N

nithe number of plan i's processes,ni=|Ni|

Oijthe process j of plan i,j=1,…,ni

OMijdevice collection can be used for Oij

OTijprocess time of Oijposition of crane k at time t

Pmposition of device m

ptijkthe work station j's standard processing time of charge i processed on equipment k

SI(i,j,k)the charge after process j of charge i processed on equipment k

STijprocessing start time of Oij

stijkthe work station j's processing start time of charge i processed on equipment k

Tnowcurrent time;

U={J1,J2…Ji…}charging plan set,Jiis charging plan i

v crane speed,it is a constant

yijkif the work station j of charge i processed on equipment k,yijk=1,else yijk=0

δ the shortest distance between two adjacent cranes

Ω the set of waiting continuous casting charge i∈Ω,|Ω|is the totalamount of continuous casting charge

Ω?the set of no-producing ingot casting charge

|Ω?|the total amount of ingot casting charge

[1]I.Harjunkoski,I.E.Grossmann,A decomposition approach for the scheduling of a steel plant production,Com put.Chem.Eng.25(2)(2001)1647-1652.

[2]K.Lee,S.Y.Chang,Y.Hong,Continuous slab caster scheduling and interval graphs, Prod.Plan.Control 15(5)(2004)495-501.

[3]D.Ouelhad j,P.I.Cow ling,S.Petrovic,Utility and stability measures for agent-based dynamic scheduling of steel continuous casting,IEEE International Conference on Robotics and Automation,University of Nottingham,UK,131-138(Nakaoka,S.).

[4]J.Neuwirth,A production scheduling system at the Stah l Linz Gm bh,in:D.K.Baik (Ed.),International Conference on Computerized Production Control in Steel Plant, Korean Institute of Metals and Materials,Korea,1993,pp.142-347.

[5]Y.Jimichi,A.Hori,H.Ishihara,T.Odira,An expert system of automatic slab assignment for hot strip mill,ISIJInt.30(1990)155-159.

[6]K.Stoh l,W.Spopek,VAI-Schedex:a hybrid expert system for co-operative production scheduling in steel plant,in:D.K.Baik(Ed.),International Conference on Computerized Production Control in Steel Plant,Korean Institute of Metals and Materials,Korea,1993,pp.207-211.

[7]I.Ferretti,S.Zanoni,L.Zavarella,Production-inventory scheduling using ant system m etaheuristic,Int.J.Prod.Econ.104(2)(2006)317-323.

[8]Joseph D.Blackburn,Robert A.Millen,Heuristic lot-sizing performance in a rollingschedule environment,Decis.Sci.11(4)(2007)691-701.

[9]Arezoo Atighehchian,MehdiBijari,Ham ed Tarkesh,A novel hybrid algorithm for scheduling steel-making continuous casting production,Com put.Oper.Res.36 (2009)2450-2461.

[10]D.F.Zhu,Z.Zheng,X.Q.Gao,Intelligent optimization-based production planning and simulation analysis for steel making and continuous casting process,J.Iron Steel Res. Int.17(9)(2010)19-29.

[11]H.V.Stackelberg,Theory of the Market Economy,Ox ford Univ.Press,New York, 1952.231-238.

☆Supported by the Educational Commission of Liaoning Province Science and Technology Research Projects(L2013237).

*Corresponding author.

E-mailaddress:farewell_lin@163.com(S.Lin).

Steel-making

Genetic algorithm Bilevel problem

Scheduling