Modeling and Hybrid Optimization of Batching Planning System for steel making-continuous Casting Process

Tianmu Ma Xiaochuan Luo Tianyou Chai

I.INTRODUCTION

THE integrated iron and steel enterprise is a typical process industry.The whole production process in large-scale steel enterprise includes three stages,i.e.,ironmaking,steel making and rolling(Fig.1).steel making stage is the key process,as it is an important connection between ironmaking and rolling.This stage has the characteristic of continuous high temperature,and its capacity in general is lower than the other two.In real production,steel making throughput should be fully utilized to produce more slabs for satisfying the capacity requirements of downstream production lines in order to finish more work orders.Therefore,effective planning and scheduling in steel making stage are vital to improve the performance of the whole production system,including profit increase,production cost savings,material and energy consumption reduction,and customer satisfaction[1,2].

The planning and scheduling in steel making production mainly include two types of decisions,i.e.,batching decision and scheduling decision[3].In this paper,we focus our study on batching decision,and we call it as steel making batching planning(SBP).The tasks of SBP are to make the decisions as follows.

1)How to select slabs and determine their width from the slab set given by plant?

2)How to group the selected slabs into charges,then group the charges into tundishes,and determine the sequence of charges in each tundish?

3)How to group the tundishes into cast,and determine the sequence of tundishes in each cast?

At present,SBP is mainly made by manual.However,it is hard to make a good SBP by manual,due to differences between planners′experience,large quantity of production data,and multiple process constraints.Because of the hierarchy of SBP,we adopt the decomposition strategy to divide the whole problem into three sub-problems,i.e.,charge design,tundish design and cast design.For each sub-problem,we build a mathematical model.The selection of slab width has an important influence on the quality of SBP.For keeping the searching space of the width as large as possible,we transform the width interval into a numerical value in charge design and tundish design,and determine the width in cast design.We present iterated neighborhood search(INS)algorithm combined with variable neighborhood search(VNS)algorithm to solve charge design problem and tundish design problem.For cast design problem,we applied the two-layer ant colony algorithm.

The rest of the paper is organized as follows.In Section II,related works are reviewed.In Section III,we briefly describe the production process and define SBP.In Section IV,we give the mathematical description of SBP and problem model.Based on the analysis of width,we give the decomposition strategy to divide the system into three sub-models by adding some objectives and constraints in Section V.In Section VI,according to the characteristics of each sub-model,hybrid optimization algorithms are presented.Section VII shows computational experiments using actual data.Finally,we draw the conclusions in Section VIII.

II.RELATED WORKS

Various research issues are involved in planning and scheduling of iron and steel production process from slab design to finishing line.Zhu et al.[4]presented a novel optimization model considering the limitation of traditional mathematical model for production planning,and combined with a simulation model to evaluate and adjust the production plan.Dawande et al.[5]presented a slab design problem in a large steel plant.They took three constraints into account,and developed a three-step heuristic solution based on matching and bin packing.Dash et al.[6]solved the production design problem for rectangular plate products in steel plant.They decomposed this problem into sub-problems that corresponded to the production stages,and developed a solution approach which combined mathematical programming models with search techniques from artificial intelligence.For example,the design of mother plates consisted of a two-dimensional packing problem,and applied column generation method to solve the problem.Lee et al.[7]defined a scheduling problem for the continuous slab caster,which was regarded as a variant of the clique partitioning problem defined on interval graph,and developed an optimal algorithm.Chang et al.[8]studied the lot planning problem to group charges into casts for a continuous slab caster.Tang and Liu[9]presented a deterministic mixed integer programming model for scheduling production order of some critical and bottleneck operations,and developed a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation,linear programming and heuristic.Tang and Jiang[10]investigated the charge batching problem in which the production orders were transformed into various charge batches,presented a mixed integer programming model,and proposed two kinds of Lagrangian relaxation to solve the model.Tang and Luo[11]formulated a quadratic programming model for charge grouping problem,and developed an iterated local search(ILS)algorithm to solve it.Tang and Wang[3]integrated slab grouping model and charge grouping model to solve batching problem in steel plant.Dong et al.[12]aimed at charge planning problem,proposed a multi-objective model,and designed two meta-heuristics based on VNS to solve the model.Given charges and casts,scheduler could assign them to equipment and build production timetable.Many people researched in this field.Tang et al.[13]presented a mathematical model based on just in-time idea,for solving machine conflicts in steel making-continuous caster production scheduling after charges were assigned to continuous caster,Linz-Donawitz(LD)converter and Ruhrstahl-Hereaeus(RH)converter.Pacciarelli and Pranzo[14]modeled the steel making-continuous casting production using alternative graph and solved it by beam search.Roy et al.[15]developed a knowledge model,which described the reasoning process in mismanaging schedule disturbance in steel making.Missbauer et al.[16]described the model,algorithm and implementation results of a computerized scheduling system for the steel making-continuous casting process of a steel plant.More details of planning and scheduling in steel making-continuous casting can be found in[17]and[18].As mentioned above,we can see batching planning is the process between designing for slab and scheduling for steel making-continuous caster.Research in batching planning mainly focuses on a single model,but not on a batching planning system.However,the single model cannot address all the problems in batching planning for steel making-continuous casting.

Fig.1.Production process from ironmaking to rolling.

III.PRODUCTION PROCESS

We now describe the specific steel production process modeled in this paper.The goal of steel production process is to satisfy work orders for slabs,productive power and slabs′requirements of downstream production lines.Work orders specify the properties of each slab(for example,width interval,length interval,thickness,weight,steel grade,priority and delivery date)and the total number of slabs.Fig.1 shows the production process from ironmaking stage to rolling stage in an iron and steel enterprise in China.

Molten iron from the basic oxygen furnace in ironing stage is refined by LD converter in batches of about 250 to 300 tons,and then forms molten steel.A batch is called a charge.The metallurgical ingredients in one change are the same.These batches of molten steel could be refined by RH refining furnace,or directly poured to tundish which is a component of continuous caster.Every tundish has a work life which varies with metallurgical compositions of molten steel.When the utilization time of a tundish reaches its work life,the tundish must be replaced by a new one.Tundish replacement results in productivity loss and high maintenance cost.Then molten steel is cast to form solid steel pieces,called slabs with various metallurgical compositions and sizes.Molten steel from a sequence of multiple charges is called a cast which is a group of charges to be cast in the continuous caster between turnarounds.

The slabs produced in steel making stage will be processed further.In hot rolling mill,a sequence of slabs are transformed to hot coils.When rolling slabs,new rolls cannot roll the slabs of high steel grade,but need some special slabs(called warm-up materials)to heat rolls by rolling them with friction.So the weight of warm-up materials must satisfy the requirement of hot rolling mill.After hot rolling mill,cold coils will be created as a cold rolling mill.Then cold coils can be processed in a lot of machines,for example,bell-type furnace and hot galvanizing machine.Each machine processes different cold coils varying with their steel grades.So slabs with various steel grades must be produced to satisfy the downstream.We call the direction in which slabs are to be processed by machines after hot rolling mill as flow direction,and call the direction in which slabs are rolling in the hot rolling mill as destination.

From the description above,we can see that steel grade is an important factor in the whole production process.Molten steel in one charge must have the same steel grade.Similar steel grade must be used in one tundish in the continuous caster.And molten steel of multiple charges must have similar steel grade to be cast in the same cast.But the machines in downstream may need different steel grades or widths.In working order,the width of slab is selected from the width interval assigned to each slab,and the selected width must guarantee contiguous caster continuously cast molten steel to slabs.Once width is changed,the changed value cannot satisfy the constraint of the continuous caster,then the process will be stopped and require more time to prepare for the next cast.Therefore,setup cost will increase.The width of each slab could be adjusted once in order to satisfy the requirement that the difference of the maximum and minimum width of the slabs in one change should be within 100mm at most.It is the same for the slabs in one tundish.But in continuous caster,the adjustment is allowed as many times as required.

Now we can define SBP as the problem of determining the following(see Fig.2):

1)How many slabs will be selected to produce a given work order,and which width is selected?

2)The set of charges along with the constituent selected slabs in this charge.

3)The set of tundishes,and for this tundish,its constituent charges and their sequence in this tundish.

4)The set of casts,and for this cast,its constituent tundishes and their sequence in this cast.

These must be determined while satisfying all capacity limits and targets,manufacturing constraints,and maximizing various objectives and production metrics.For example,the total number of changes must satisfy the steel making capacity limits,and the total weight of all selected warm-up materials must satisfy the requirement of hot rolling mill.Later,we will abstract the detailed objectives and constraints for models from real-life works.

IV.STRUCTURE OF DECOMPOSITION STRATEGY

We can hardly make decisions to confirm the four sets simultaneously,because there exist conflicts among the constraints of four sets.For example,the charge set is composed of the slab set by dividing it,and the tundish set is composed of the charge set,so the total number of ingredients in slab set can impact the other two sets.If the total number of ingredients is too large,the number of charges and the number of tundishes are also very large.When considering the width of slab set,we have similar conclusion.For reducing the impact,we adopt the decomposition strategy in Fig.3 to make batching planning.From Fig.3,we can see the whole strategy composed of three steps.

Fig.2. Problem description of SBP.

Fig.3.Structure of decomposition strategy.

1)Charge design model(CHDM).Its function is grouping all slabs into charges while taking into account the constraints of converting furnace through a mathematical model.

2)Tundish design model(TDM).Its function is grouping the charges created by CHDM into tundishes while considering the production indices and the constraints of tundish.

3)Cast design model(CDM).Its function is grouping the tundishes into cast and confirming the width.

Next we discuss the three steps in detail.

A.The Problem Description and Formulation of CHDM

1)Problem description of CHDM:The function of CHDM is grouping slabs into charges.Each slab has the properties of steel grade,weight,interval of width,priority,delivery date,flow code,refine code and destination code.In this process,the following factors must be considered.

1)Ingredients of molten steel

Each slab has a steel grade property,which describes the ingredient of molten steel.The ingredient of slabs in one charge must be the same.

2)Volume of converter furnace

Volume of converter furnace considered in this paper is about 300 tons.The complete volume of the converter furnace must be filled with molten steed.If there are remaining volume,and no slab customer ordered can be put in,the planner should fill some special slabs into the converter furnace to make maximum volume production.These slabs are called open order slabs,not associated with any customer orders,and are kept in the warehouse.So we try our best to minimize the amount of open order slabs.

3)Width

In a charge,slab width must satisfy the following constraints.

a)Continuous caster only casts slabs according to the nonincreasing order of width.

b)The difference between the maximum width and the minimum width in one charge is no more than 100mm.

c)The width adjustment is allowed only once.

For example,if a charge includes a maximum width of 1000mm,it can only select either slabs with 950mm or 900mm,but not both.In CHDM,we do not select an exact width,but consider a width interval in the model.

4)Priority

The priority of slab is represents the emergency of contract to some degree.If the slab with high priority is not grouped into a charge,the production date of the slab will be close to the delivery date of the corresponding contract.When the priority of slab is high enough,it will be produced at any cost.This situation will increase the cost of production.So the slab with higher priority should be given higher priority in production.

5)Other factors

If slabs with similar properties produced in the same charge,it should decrease the cost,for example,the cost for preparing hot rolling to move slabs in a slab yard.So minimizing the differences between the slabs in the same change can be regarded as an optimized objective.This consideration is also applicable to tundishes.

2)Dealing with width interval:If intersection of the slab width intervals in one charge is bigger,continuous caster works better.This is also applicable to grouping charges into tundishes.At present,there are two methods to deal with width interval[3,10].One is regarding the width interval as penalty,modeled as objective.The other is to model it as constraint.However,there are two difficulties in these methods.Firstly,when there exists an intersection,how to measure the overlap degree.For example,in Fig.4,Slab 1 and Slab 2 have the intersection interval of[1200,1300],Slab 3 and Slab 4 have the intersection interval of[1150,1300].Obviously,the interval[1150,1300]is wider.Secondly,if there is no intersection,how to ensure that the difference between two width intervals satisfies the requirement of a continuous caster.For the second problem,we can use formulations(10)～(14)to overcome.For measuring the overlap degree of two width intervals,we use the method of comparing interval numbers,and transform the width interval of charge into a corresponding number[19],then use both this number and width interval in the model.The steps of transforming width interval are as follows.

Step 1.Using(1)to do a pairwise comparison for width intervals,we denoteP(Ii≻Ij)aspij,then build a matrixP=(pij)n×nas

Here,Ii=[wLi,wHi]andIj=[wLj,wHj]represent width intervals of two slabs respectively.L(Ii)=wHi-wLi,andL(Ij)=wHj-wLj.

Fig.4. Description of slab width interval.

3)Formulation for CHDM:CHDM is similar the bin packing problem(BPP).Each slab can be seen as an item,and charge corresponds to bin.But besides the objective of minimizing the number of bins,we consider the penalty of slabs not having been grouped into charges,the cost of remaining volume of the charges and the penalty cost of the difference between slabs in one charge.In the following,CHDM is formulated as an extension of BPP.

Parameters.

N:the set of slabs,N={1,2,···,i,j,···,n}.

M:the set of charges,L={1,2,···,k,l,···,m}.

di:the delivery date of slabi.

ai:the priority of slabi.

sgi:the steel grade of slabi.

hi:the flag of warm-up material of slabi.

rsi:the refine flag of slabi.

Ii=[wLi,wHi]:the width interval of slabi.

vi:the number corresponding to the width intervalIi.

wti:the weight of slabi.

dei:the destination of slabi.

fdi:the flow direction of slabi.

fk:the cost of chargek.

lek:the cost of leftover of the chargek.

LDk:the capacity of LD converter.

△w:the maximum change of width.

θ1:the utilization of the charge.

D:a large positive number.

Variables.

sik:binary variable,equal to 1 if slabiis allocated to chargek,equal to 0,otherwise.

tk:binary variable,equal to 1 if chargekis used,equal to 0,otherwise.

The formulation of CHDM is

In objective(7),the first item represents the cost of charges,the second item represents the penalty cost of slabs not having been grouped into charge,the third item represents the cost of the leftover of the charge,and the fourth item represents the penalty cost of the difference between slabs in this change.Constraint(8)ensures that the total weight of slabs does not exceed the charge′s capacity.Constraint(9)ensures that each slab can only be grouped into one charge at most.Constraint(10)is the requirement of the same ingredient in one charge.Constraints(11)～(13)ensure the slabs in the charge satisfy the width limitation.Constraint(14)is the definition of leftover of charge.Constraint(15)defines the range of the variable values.

B.The problem Description and Formulation of TDM

1)Problem description of TDM:The main function of TDM is grouping the charges into tundishes while considering the production constraints and indices.Among them,the production constraints include width constraint,ingredient constraint and service life constraint.Width constraint in TDM is the same as in CHDM.

1)Ingredient constraint

Ingredients of charges used in the same tundish should only vary in a small range.When the difference between two ingredients is bigger than a certain range,the continuous caster cannot go on working,and spends more time on preparing the next production.If two kinds of molten steel with different ingredients cast by continuous caster,a special slab will appear,called joint slab(slab b in Fig.5),which is not directly used in production.

2)The service life of tundish

The tundish is used to pour molten steel into the continuous caster,which has a service life varying with the ingredients of charge.Once a tundish is utilized,no matter whether it reaches the end of its service life,some repair operations are imposed on it,and thus require higher cost.So the less its remaining service life is,the better the tundish is utilized.

Besides the constraints mentioned above,TDM considers the requirements of processes capability.Under the condition of normal production in all processes,each machine in all process has a productive power.Downstream needs intermediate products generated by upstream.If the quantity of products is not enough to keep downstream working,the rhythm of the entire production line will be in disorder.Even if some bottleneck processes(for example,continuous caster)do not play the most important role,they will also affect the entire production line.So some objectives or constraints must be satisfied,including that

1)The total number of charges should satisfy the interval of charges given by plant.

2)The total number of RH-refining charges should satisfy the interval of RH-refining charges given by plant.

3)The total weight of warm-up materials can satisfy the interval given by plant.

4)The total weight of each flow direction should satisfy the interval given by plant.

Fig.5. Description of a joint slab.

2)Formulation of TDM:Parameters.

M:the set of charges,L={1,2,···,k,l,···,m}.

E:the set of tundishes,E={1,2,···,p,q,···,e}.

F:the set of flows,F={1,2,···,s,···,f}.

Ik=[lwLk,lwHk]:width interval of chargek.

△w:the maximum change of width.

vk:the number corresponding to the width intervalIk,calculated using the method in Section IV-A-2.

lsgk:the steel grade of chargek.

rhk:the RH-refining flag of chargek.

htk:the total weight of warm-up materials in chargek.

flks:the total weight of flowsin chargek.

ftp:the cost of tundishp.

ltp:the cost of the leftover of tundishp.

tlp:the service life of tundishp.

θ2:the utilization of tundish.

CHG:the required target number of charges.

CHU:the required upper bound of the number of charges.

CHL:the required lower bound of the number of charges.

RHG:the required target number of RH-refining charges.

RHU:the required upper bound of the number of RH-refining charges.

RHL:the required lower bound of the number of RH-refining charges.

HG:the target weight of all warm-up materials.

HU:the upper bound of weight for all warm-up materials.

HL:the lower bound of weight for all warm-up materials.

FsG:the target weight for flow direction l.

FsU:the upper bound of weight for flow direction l.

FsL:the lower bound of weight for flow direction l.

c2kl:the similarity coefficient of chargekand chargel,i.e.,

r1-r12:constants.

D:a large positive number.

Variables.

up:binary variable,if tundishpis used,up=1,otherwise,up=0.

vkp:binary variable,if chargekis grouped into tundishp,vkp=1,otherwise,vkp=0.

The formulation of TDM can be modeled as follows.

In TDM,objective function(19)expresses to minimize the difference between charges in each tundish and minimize the cost of tundishes in use.Objective function(20)expresses to minimize the difference between the total number of selected charges and the target number of charges given by plant.Objective function(21)expresses to minimize the difference between the total number of refining charges and the target number of refining charges given by plant.Objective function(22)expresses to minimize the difference between the total weight of warm-up materials and the target weight given by plant.Objective function(23)expresses to minimize the difference between the total weight of each flow direction and the target weight of each flow direction given by plant.Constraint(24)ensures that the total number of charges within one tundish should not exceed the working life of the tundish.Constraint(25)ensures that each charge can be grouped into only one tundish.Constraint(26)guarantees that the component of molten steel in the charges grouped in one tundish should satisfy the requirement.Constraints(27)and(28)guarantee that the difference of width between charges grouped in one tundish should satisfy the limitation of width changeover.Constraint(30)ensures that the total number of charges grouped in tundish should not exceed the range given by plant.Constraint(31)ensures that the total number of refining charges should not exceed the range given by plant.Constraint(32)ensures that the total weight of warm-up materials contained in grouped charges should not exceed the range given by plant.Constraint(33)ensures that the total weight of each flow direction contained in grouped charges should not exceed the range given by plant.Formulations(34)and(35)are variable definitions.

C.The Problem Description and Formulation of CDM

1)Problem description of CDM:Through CHDM and TDM,the slab set to be produced and the tundish set are determined respectively,while the cast set and the width of slabs is up to CDM.When tundishes are grouped into casts,two main factors must be considered,i.e.,the ingredient and the width of charges in tundish.When grouping tundishes into casts,we hope that the charges with the same ingredient and width are cast continuously.It is better to adjust ingredient and width less in order to achieve more continuous cast.

There exists a wide relationship among slabs,charges and tundishes.Given the width of slabs,the width of charges and tundishes can be determined.Given width of charges,the width of slabs and tundishes can be determined.Given width of tundish,it is the same.For example,Fig.6 shows a charge with 8 pieces of slabs.Each slab has a width interval of[1250,1450].From width of slabs,we can determine the width of charge to be a pair chosen in(1450,1450),(1450,1400),(1450,1350),(1400,1400),(1400,1350),(1400,1300),etc.If we set the width of the charge to be(1450,1450),then the width of slabs in the charge can be determined,and vice versa.

2)Formulation of CDM:In CDM,if we regard the charge with a pair of width values as customer,and the tundish as vehicle,in the meanwhile,if we regard the tundish as customer,and the cast as vehicle,CDM can be seen as a two-layer vehicle route problem(VRP).In the following,we formulate CMD.

Parameters.

M:the set of charges,L={1,2,···,k,l,···,m}.

E:the set of tundishes,E={1,2,···,p,q,···,e}.

G:the set of casts,G={1,2,···,r,···,g}.

tsgi:the code of continuous casting in tundish.

csgi:the code of continuous casting in cast.

△wL:the minimum change of width.

△wH:the maximum change of width.

tlr:the service life of tundishr.

c3pq:the similarity coefficient of tundishespandq.

Bk={(bwk1,ewk1),(bwk2,ewk2),···,(bwkbk,ewkbk)}for all width values that can be assigned to chargek,and(bwkbk,ewkbk)denotes the begin width and end width,respectively.We have

Fig.6. Part of the manual casting planning.

r1-r12:constants.

D:a large positive number.

Variables.

vkp:binary variable,if chargekis grouped into tundishp,vkp=1,otherwise,vkp=0.

wklp:binary variable,if chargekis cast immediately after chargelin tundishp,wklp=1,otherwise,wklp=0.

ypr:binary variable,if tundishpis assigned to castr,ypr=1,otherwise,ypr=0.

zpqr:binary variable,if tundishpis cast immediately after tundishqin castr,zpqr=1,otherwise,zpqr=0.

ekα:binary variable.ekα=1,if chargekselects theαth element inBk.

twHp,twLp:the maximum and minimum width of tundishp,respectively.

The formulation of CDM can be modeled as follows.

In CDM,Bis a very large constant number.Objective(37)represents minimizing the number of tundishes and the difference between charges.Objective(38)represents minimizing the number of casts and the difference between tundishes.Constraint(39)guarantees a charge only has one begin width and one end width.Constraints(40)～(42)ensure the casting width satisfies the technical requirement.Constraint(43)ensures the ingredients in cast satisfy the requirement.Constraints(44)～(52)are standard constraints in VRP.Formulation(53)is the definition of variables.

V.SOLUTION APPROACH

Now we give the algorithm to solve the three models,i.e.,CHDM,TDM and CDM,respectively.In this section,we first analyze the characteristics of model,based on which,we adopt VNS algorithm to solve CHDM and then TDM,and use ant colony optimization(ACO)to solve CDM.VNS is a recent metaheuristic for solving combinatorial and global optimization problems.Its basic idea is systematic change of the neighborhood within a local search.In all algorithms based on neighborhood search,VNS has an outstanding performance in the aspects of high efficiency,robustness,ease of use and hummization,and has obvious advantages in large scale and multi-constraint problem[20].Hemmelmayr et al.[21]used VNS to solve variable sized bin packing problem(VSBPP)and obtained better solution than the solution obtained by generic algorithm(GA)and set covering(SC).ACO is a kind of metaheuristic algorithm for NP-hard problem in discrete optimization.ACO has been widely used in many fields.Reference[22]presented an improved ant system algorithm for the VRP with one depot and identical vehicles.Reference[23]developed a new ACO for the problem of scheduling in permutation on flow shop with the objective of minimizing the maximum completion time.Reference[24]introduced the use of a swarm algorithm,derived from ACO,to solve path planning problems for autonomous vehicles.

A.Variable Neighbourhood Descend(VND)for CHDM

In CHDM,ifcijequals zero,and priority,ingredient and width interval of all slabs are identical,the model is a variant of classic BPP,a well-known NP-hard problem called variable cost and size bin packing problem(VCSBPP).So CHDM is also a NP-hard,and generally,the number of slabs which is the input data of the model is from 2000 to 6000.Exact algorithm cannot be used to solve it.Hence,efficient algorithm is developed to generate an acceptable solution.We develop VND algorithm for CHDM as shown in Algorithm 1.

1)Generate initial solution:The well-known algorithms,for example, first fit(FF),best fit(BF), first fit decreasing(FFD),best fit decreasing(BFD), first fit increasing(FFI),best fit increasing(BFI),offer good performance for classical BPP.We use FF and BF to generate two solutions,for the slabs sorted arbitrarily according to their left points of the width intervals,use FFD and BFD for the slabs sorted according to the non-increasing order of their left points of the width intervals,and use Ffi and Bfifor the slabs sorted according to the non-decreasing order of their left points of the width intervals.After we generate solution initial,we get a solution setx.

Algorithm 1.Basic VND

1)Define the set of neighbourhood structuresNk,fork=1,2,···,kmax

2)x=GenerateInitialSolution

3)Repeat

4)k←1

5)Repeat

6)x′=argminy∈Nk1(x′)f(y)

7)Iff(x′)＜f(x)then

8)x←x′,k←1

9)Else

10)k←k+1

11)Untilk=kmax

12)Untiltermination condition met

2)Neighbourhood structure:1)Operator NS1SwapSlab.This operator selects two different charges,denoted by Charge 1 and Charge 2 randomly in solutionxwhen stop condition is not satisfied.Then it selects a slab in Charge 1,and a slab in Charge 2,denoted by Slab 1 and Slab 2.If Slab 1 and Slab 2 can exchange,and the exchange can optimize the objective,it is accepted,otherwise,it is refused.Notice that the selected bin is not virtual bin which is used to pack the rejected items.

2)Operator NS2RemoveCharge.This operator aims at optimizing the cost of charges.This operator first finds the charge with the biggest remaining volume,then empties the charge and packs slabs in a virtual charge.If this can optimize the objective,then we go on,otherwise,we undo this operation and quit this neighborhood structure.

3)Operator NS3SwapVSlab.This operator randomly selects a charge(except the virtual charge)in the current solutionx,then randomly selects a slab in the selected charge and a slab in the virtual charge,denoted by Slab 1 and Slab 2,respectively.If exchanging Slab 1 and Slab 2 can optimize the objective and satisfy the constraints,it is accepted.This operation does not stop until the stop condition is met.

4)Operator NS4InsertVSlab.This operator first finds the charge with the biggest remaining volume,and then selects a slab in the virtual charge to pack it into the selected charge,if the objective can be optimized,the item is packed into the charge.This operation continues until the stop condition is satisfied or the objective cannot be optimized any more.

5)Operator NS5PackingVSlab.This operator is the inverse of operator NS4InsertVSlab.It groups the slabs in the virtual charge into a charge,adds the charge to the current solutionx,and delete the slab from the virtual one.If this can optimize the objective,we go on packing another charge from the virtual charge,until the stop condition is satisfied or the objective cannot be optimized any more.

B.Double-layer VND with Variable Weights for TDM

TDM is a multi-objective nonlinear programming model.As a method for solving multi-objective problem,we should obtain the pareto front.But in practice,decision makers are not interested in obtaining the entire set of efficient solutions to real-world problems.Through observation,we find the objectives and constraints can be classified into two types.The first class is related to the technical requirement of tundish,including objective(25)and constraints(30)～(34),(39),(40),while the second one is related to production capacity,including objectives(26)～(29)and constraints(35)～(38).

The first class can be seen as BPP with rejection penalty,if we only consider constraint(30)and ignore the quadratic coefficient in objective(25).For the second class,if we change the objectives from min to max,it is similar to a knapsack problem(KP),but the difference is four capacity constraints and multiple objectives for a knapsack.If a knapsack has several capacity,there seems to exist a certain couple.So we relax constraints(35)～(38)into objectives to remove absolute value function,and transform objectives(26)～(29)into one objective,then two class models can be modeled as follows.

s.t.(25)～(34).

All items in objective(54)are given in(55)～(58).λch,λrh,λh,λflare weights,andL1ch-L4ch,L1rh-L4rh,L1h-L4h,L1f-L4fare parameters.

wherel∈F.

Thus our TDM can be seen as a combination of BPP and KP.It is hard to solve TDM,because either BPP or KP is NP-hard.As both BPP and KP are in TDM model,we must decide which is to be solved first.If we solve BPP first,this method can guarantee that the tundish is fully utilized and can minimize the difference between charges in the tundish.But if we solve KP first,it is hard to ensure this.So we adopt the former method.

There are some parameters in two sub-models.The cost of tundish,the penalty cost of remaining service and the utilization of tundish are the parameters in the first sub-model,whereas the weight is the parameter in the second sub-model.In general,these parameters are fixed before solving the model or in the process of solving the model.But this imposes two problems.

1)When the first model gets the optimal solution,whether it can ensure the second model gets the optimal solution?

2)Obtaining a solution closer to the goals of the production indices is the aim of the second model.But can the fixed weight reflect the difference?

For these reasons,we design a double-layer VND algorithm to adjust the parameters dynamically.The pseudo code can be seen in Algorithm 2,in which the Modify Lambda function is used to modify the weight,the Modify Theta function is used to modify the utilization in the first model.

Algorithm 2.DVND for TDM

1)Input problem instance

2)Repeat

3) Define the set of neighborhood structuresN1k,fork=1,2,···,km1ax

4)x=GenerateInitialSolution BPP

5)Repeat

16)x=GenerateInitialSolution KP

17)Repeat

18)k←1

19Repeat

20)x′=argminy∈Nk1(x′)f(y)

21)Iff(x′)＜f(x)then

22)x←x′,k←1

23)Else

24)k←k+1

25)Untilk=k2max

26) Modify Lambda()

27)Untiltermination condition met

28) Modify Theta()

29)Untiltermination condition met

1)Generate initial solution for BPP and KP:For BPP,we also adopt the well-known FF,BF,FFD,BFD,Ffiand BFI,as in Section V-A-1.We use FF and BF to generate two solutions,for the charges sorted arbitrarily according to their left points of the width intervals,use FFD and BFD for the charges sorted according to the non-increasing order of their left points of the width intervals,and use Ffiand Bfifor the charges sorted according to the non-decreasing order of their left points of the width intervals.

For KP,we adopt the greedy algorithm to generate the initial solution.First,we sort the tundishes according to the nonincreasing order of the number of charges in each tundish,then select the tundishes into the solutionx,until the total number of charges in the solutionxexceeds the upper limits of constraint(9).

2)Neighborhood structures:1)Operator NS1TSwapCharge.This operator tries to reduce the difference between the charges in one tundish.This operator first selects two tundishes(except the virtual tundish)in the current solution,then selects a charge in each tundish respectively.If swapping these two charges satis fies the constraints and optimizes the objective,the two charges are swapped.This operation repeats until the stop conditions are met.

2)Operator NS2RemoveTundish.This operator tries to remove tundishes to optimize the objective by looking for the tundish with maximum remaining service life in all tundishes and moving all its charges to the virtual tundish.If the operator can optimize the objective,this operation repeats until the stop conditions are met.

3)Operator NS3VSwapCharge.The function of this operator is similar to NS1TSwapCharge.The difference is that this operator swaps charges between the tundish and the virtual tundish.This operator first selects a tundish with a certain probability,then selects a charge in it,swap the charge with a charge in the virtual tundish under the condition that the constraints are satisfied.If the operator can optimize the

6)k←1

7)Repeat

8)x′=argminy∈Nk1(x′)f(y)

9)Iff(x′)＜f(x)then

10)x←x′,k←1

11)Else

12)k←k+1

13)Untilk=k1max

14)Untiltermination condition met

15) Define the set of neighborhood structuresN2k,fork=1,2,···,k2maxobjective,this operation repeats until the stop conditions are met.

4)Operator NS4VInsertCharge.This operator tries to maximize the service life of tundish.The operator looks for the tundish with remaining service life,and inserts a charge which is in the virtual tundish into the selected tundish,if the constraints are satisfied.If the operator can optimize the objective,this operation repeats until the stop conditions are met.

5)Operator NS5VGroup Charge.This operator tries to reduce the number of charges not having been grouped into tundishes.The operator uses FF algorithm to group the charges in the virtual tundish into a tundish.If adding a new tundish can optimize the objective,then we keep on grouping the charges into this tundish.This operation repeats until the objective cannot be optimized any more.

6)Operator NS6Swap Tundish.We use this operator right after generating solution for KP.This operator swaps the tundishes in solutionxwith unselected tundishes to optimize objective(18).This operation continues,until the objective cannot be optimized any more.After this operator,all unselected tundishes are destroyed,so the state of the charges in these tundishes is changed into unselected.

7)Operators NS7Swap Charge,NS8Insert Charge and NS9Delete Charge.These three operators all try to optimize objective(18).NS7Swap Charge swaps the charge in solutionxwith an unselected charge.If the swapping satis fies the constraints and optimizes the objective,this operation continues until the objective cannot be optimized.NS8Insert Charge inserts an unselected charge into solutionx.If the objective can be optimized,we go on the inserting operation.NS9Delete Charge deletes a charge in solutionx.If the deleting can optimize the objective,then this operation continues until the objective cannot be optimized.

3)Modify the weight:The function Modify Lambda is used to adjust the weight in(20).We adopt the following formula to adjust the weight

whereλrepresents the weight in objective(58),σrepresents an integer,anderepresents the difference,grepresents the goal of production index.For example,λrhis the weight of the number of refining charges in objective function.In current solution,we can compute the total number of refining chargesg′,and the goal of the number of refining charges isRH.If the difference between the two is large thanσ,we can compute the newλrhas follows.

4)Modify θ :The function Modify Theta in Algorithm 2 is used to adjust the utilization of tundish.In general,neither the cost of a tundish nor the penalty cost of the remaining service is variable,but the utilization can be changed.The parameterθcan impact the model.For example,whenθ=0.5,it means that the tundish is regarded to be fully used when half of its whole total service life passes.In this situation,the number of tundishes could be increased.Whenθ=1,it means that the whole service life of the tundish must be used.In this situation,the number of tundishes could be reduced.The number of tundishes can affect the solution.For improving the situation,we adopt the following method.First we fixθ,for example,to be 0.6,if the solution can not be improved,then we changeθas

C.ACO for CDM

After solving CHDM and TDM,we have determined the relationship between slabs and charges,the relationship between charges and tundishes,the number of charges,the number of tundishes,the amount of warm-up materials and the amount of flow materials.But we have not determined the width of slabs and charges yet.CDM completes the work by determining the number of casts and the width of charges.Then using Theorem 1,we determine the width of slabs in charges,while using Theorem 2,we determine the width of tundishes.

CDM includes two sequences,i.e.,the sequence of charges in each tundish and the sequence of tundishes in each cast.And the problem of determining the sequence is VRP.So cast design is a series of two VRPs.Individual VRP is a NP-hard problem,let alone two VRPs.

Before developing the algorithm,we do some preprocessing.A charge has several pairs of begin width and end width.So we regard each pair as a brother of the primary charge,and call these charges dummy charges,but only one dummy can be selected into solution for each primary charge.

For CDM,we design an algorithm with two-layer ant colony system(ACS)in series.ACS in the first layer is responsible for selecting the width of charges and minimizing the difference between charges in the same tundish,while ACS in the second layer is responsible for minimizing the number of casts and the difference between tundishes in the same cast.In the first layer,each ant represents a sub-solution for the sequence of charges in tundish.In the second layer,each ant represents a sub-solution for the sequence of tundishes in cast.When the first layer stops,the second layer begins running.Then the algorithm keeps a better solution.The whole algorithm iterates between the two layers until the stop criterion is satisfied.

Algorithm 3.ACS for CDM

1)Input tundish set

2)Initialize the two-layer ACS

3)Whilestop condition is not metdo

4)x′=RunFirstACS()

5)x=RunSecondACS(x′)

6)End while

7)Output the best solution

1)State transition rule:For ACS in the first layer,each dummy chargekrepresents a node that might be visited by ants.An arc(k,p)means that chargepis cast immediately after chargek.tdenotes the pheromone trail on arc(k,p).ηkldenotes the heuristic information of moving from chargekto chargep.Antalocating at nodekchooses nodepas the next location according to the following pseudo-random proportional rule:

whereβ ＞0 is a parameter that measures the relative importance of the heuristic information.qis a random value uniformly distributed in[0,1],andq0∈[0,1]is a parameter that determines the relative importance of exploitation versus exploration.The heuristic informationηkp′is defined as

whereckp′is the penalty cost of casting chargep′immediately after chargek.P∈Fakis a node that is randomly selected according to the following probability:

For ACS in the second layer,we replace the charge with tundish in(61)～(63).

2)Pheromone update:In our two-layer ACS algorithm,the following are the ways to update the pheromone.

1)Global pheromone for ACS of each layer

In ACS of each layer,only one ant(the best-so-far)is allowed to add pheromone after each iteration.The update in the first layer is implemented by the following equation:

2)Local pheromone for ACS of each layer

In addition to the global pheromone trail updating,in ACS of each layer,the ants use a local pheromone updating rule in each layers,implemented by the following equation:

where 0＜ξ1＜1 is a parameter,△τ0is the initial trail value,andfitnesssbs1is the objective of ACS in the first layer.This updating is also applied to the second layer withξ1replaced byξ2.

VI.EXPERIMENTAL RESULTS AND ANALYSIS

All algorithms are developed using C#and SQL Server 2005,carried out on a PC with Intel Core 2 Duo 2.26GHz and 2G RAM,and embedded on the simulation platform developed based on the oriented service technology.Test data used for algorithms comes from practical production data obtained from an advanced iron and steel company in China.

A.Effectiveness of Changing the Width Interval Into a Number

Table I gives an example of 10 pieces of slabs to test the method used to transform width interval of slab to a corresponding number.MatrixAis obtained by applying the method presented in this paper,while matrixBis obtained by applying the method of[10].Through the comparison,we can see our method can distinguish the overlap degree of two width intervals.For example,the upper left corner of matrixAcontains non zero items,but these items in matrixBare zero.

B.Effectiveness of CHDM,TDM and Algorithms

1)Each instance of the best solution to the correspondingθvalues are different.

2)The variable weight method can get a better solution than the fixed weight method in the sameθvalue.

3)In the same instance,the algorithm can obtain some solution for planner.

4)Compared to the planning made by manual,both the number and the remaining service life of tundish planned by our algorithm is smaller,which is beneficial for the production.

C.Effectiveness of CDM and Algorithm

Fig.7 shows a cast that contains 2 tundishes.Each tundish includes 4 charges,and each charge has eight pieces of slabs.For example,in Charges 1～3,each slab has 5 different sizes of width,i.e.,1250mm,1300mm,1350mm,1400mm,and 1450mm.The black line represents the width determined by planner working in iron and steel company.Planner selects three sizes of width.When two sizes of width connect,a special kind of slab is produced,which looks like trapezium from the upper side.Such slabs are not directly produced.So the cost will increase in order to deal with these slabs.Because of the deficient experience of planner,large scale production data,and multiple objectives and constraints,planner hardly searches each combination of width,slab,charge,tundish and cast.So planner just conservatively selects some sizes of width.The gray line is created by models presented in this paper.Models can try to select every width to group charges into tundishes and group tundishes into casts.So width sizes selected by model can reduce the number of trapezoidal slabs.

TABLEIWIDTH DATA OF SLAB AND RANKING VECTOR

Fig.7. Part of manual casting planning.

VII.CONCLUSION

In this study,the steel making batching problem has been addressed,which is important for the entire production in iron and steel company.Based on the problem description,we present the model of the primary problem.Through analysis of width,we give a decomposition strategy by dividing the primary model into three sub-models,and provide corresponding algorithms to solve.Through the validation of actual production data,our proposed method can effectively reduce the frequency of changing steel grades,width sizes and the number of tundishes,under the premise of satisfying the production indices and constraints.

[1]Ji R G,Lu Y Z.A multi-agent and extremal optimization system for steel making-continuous casting-hot strip mill integrated scheduling.In:Proceedings of IEEE International Conference on Industrial Engineering and Engineering Management.Hong Kong:IEEE,2009.2365-2369

[2]Li J,Xiao X,Tang Q H,Floudas C A.Production scheduling of a large-scale steel making continuous casting process via unit-specific event based continuous-time models:short-term and medium-term scheduling.Industrial&Engineering Chemistry Research,2012,51(2):7300-7319

[3]Tang L X,Wang G S.Decision support system for the batching problems of steel making and continuous-casting production.Omega-International Journal of Management Science,2008,36(6):976-991

[4]Zhu Dao-Fei,Zheng Zhong,Gao Xiao-Qiang.Intelligent optimization based production planning and simulation analysis for steel making and continuous casting process.Journal of Iron and Steel Research International,2010,17(9):19-24

[5]Dawande M,Kalagnanam J,Lee H S,Reddy C,Siegel S.The slab-design problem in the steel industry.Interfaces,2004,34(3):215-225

[6]Dash S,Kalagnanam J,Reddy C,Song S H.Production design for plate products in the steel industry.IBM Journal of Research and Development,2007,51(3-4):345-362

[7]Lee K,Chang S Y,Hong Y S.Continuous slab caster scheduling and interval graphs.Production Planning&Control,2004,15(5):495-501

[8]Chang S Y,Chang M R,Hong Y S.A lot grouping algorithm for a continuous slab caster in an integrated steel mill.Production Planning&Control,2000,11(4):363-368

[9]Tang L X,Liu G L.A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex.European Journal of Operational Research,2007,182(3):1453-1468

[10]Tang L X,Jiang S J.The charge batching planning problem in steel making process using Lagrangian relaxation algorithm.Industrial&Engineering Chemistry Research,2009,48(16):7780-7787

[11]Tang L X,Luo J X.A new ILS algorithm for cast planning problem in steel industry.ISIJ International,2007,47(3):443-452

[12]Dong H Y,Huang M,Ip W H,Wang X W.On the integrated charge planning with flexible jobs in primary steel making processes.International Journal of Production Research,2010,48(21):6499-6535

[13]Tang L X,Liu J Y,Rong A Y.A mathematical programming model for scheduling steel making-continuous casting production.European Journal of Operational Research,2000,120(2):423-435

[14]Pacciarelli D,Pranzo M.Production scheduling in a steel making continuous casting plant.Computers&Chemical Engineering,2004,28(12):2823-2835

[15]Roy R,Adesola B A,Thornton S.Development of a knowledge model for managing schedule disturbance in steel-making.International Journal of Production Research,2004,42(18):3975-3994

[16]Missbauer H,Hauber W,Stadler W.A scheduling system for the steel making-continuous casting process.A case study from the steel making industry.International Journal of Production Research,2009,47(15):4147-4172

[17]Lee H S,Haider S W,Morse D V.Primary production scheduling at steel making industries.IBM Journal of Research Develop,1996,40(2):231-252

[18]Tang L X,Liu J Y,Rong A Y.A review of planning and scheduling systems and methods for integrated steel production.European Journal of Operational Research,2001,133(1):1-20

[19]Xie Hai.Improved relative superiority method for ranking interval numbers.Science Technology and Engineering,2007,8(2):5983-5987(in Chinese)

[20]Hansen P,Mladenovic N.Variable neighborhood search:principles and applications.European Journal of Operational Research,2001,130(3):449-467

[21]Hemmelmayr V,Schmid V,Blum C.Variable neighbourhood search for the variable sized bin packing problem.Computers&Operations Research,2012,39(5):1097-1108

[22]Bullnheimer B H,Hartl R F,Strauss R F.An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,1999,89:319-328

[23]Ahmadizar F.A new ant colony algorithm for makespan minimization in permutation flow shops.Computers&Industrial Engineering,2012,63(2):355-361

[24]Escario J B,Jimenez J F,Giron-Sierra J M.Optimisation of autonomous ship manoeuvres applying ant colony optimisation metaheuristic.Expert Systems with Applications,2012,39(11):10120-10139