Improved Cross Entropy Algorithm for Steelmaking Continuous Casting Production Scheduling with Minimum Power Consumption

WANG Gui-rong (王桂荣), LI Qi-qiang (李歧强), YANG Fan (杨 凡)

1 School of Control Science and Engineering, Shandong University, Jinan 250061, China 2 Key Laboratory of Renewable Energy Utilization Technologies in Buildings, Ministry of Education, Jinan 250101, China

Improved Cross Entropy Algorithm for Steelmaking Continuous Casting Production Scheduling with Minimum Power Consumption

WANG Gui-rong (王桂荣)1, 2, 3, LI Qi-qiang (李歧强)1*, YANG Fan (杨 凡)1

1SchoolofControlScienceandEngineering,ShandongUniversity,Jinan250061,China2KeyLaboratoryofRenewableEnergyUtilizationTechnologiesinBuildings,MinistryofEducation,Jinan250101,China

3SchoolofThermalEnergyEngineering,ShandongJianzhuUniversity,Jinan250101,China

A matrix encoding scheme for the steelmaking continuous casting (SCC) production scheduling (SCCPS) problem and the corresponding decoding method are proposed. Based on it, a cross entropy (CE) method is adopted and an improved cross entropy (ICE) algorithm is proposed to solve the SCCPS problem to minimize total power consumption. To describe the distribution of the solution space of the CE method, a probability model is built and used to generate individuals by sampling and a probability updating mechanism is introduced to trace the promising samples. For the ICE algorithm, some samples are generated by the heuristic rules for the shortest makespan due to the relation between the makespan and the total power consumption, which can reduce the search space greatly. The optimal sample in each iteration is retained through a retention mechanism to ensure that the historical optimal sample is not lost so as to improve the efficiency and global convergence. A local search procedure is carried out on a part of better samples so as to improve the local exploitation capability of the ICE algorithm and get a better result. The parameter setting is investigated by the Taguchi method of design-of-experiment. A number of simulation experiments are implemented to validate the effectiveness of the ICE algorithm in solving the SCCPS problem and also the superiority of the ICE algorithm is verified through the comparison with the standard cross entropy (SCE) algorithm.

steelmakingcontinuouscasting(SCC);productionscheduling;powerconsumption;crossentropy(CE);probability

Introduction

The steelmaking continuous casting (SCC) is the critical process in iron and steel industry. It runs in a continuous high-temperature material flow with complicated technological processes needing to satisfy the constraints of the limits of temperature dropping and waiting time, and to meet the requirements of production continuity. Meanwhile it is also energy intensive. Under the circumstances of rising energy prices and implementation of time-of-use (TOU) prices, the steel enterprises have placed great emphasis on making optimized production scheduling not only to increase productivity but also to save energy and decrease energy cost. So the study of SCC production scheduling (SCCPS) problem with energy consumption and energy cost is important.

The SCCPS problem is always an important topic for researchers in the field of production scheduling. Reviews of previous studies on the steel production planning and scheduling can be found in Ref.[1]. Tangetal.[2]constructed a novel integer programming formulation and used a solution methodology combining Lagrangian relaxation, dynamic programming and heuristics to solve it. Harjunkoski and Grossmann[3]presented a decomposition strategy for solving large scheduling problems using mathematical programming method. Liu and Li[4]established a mixed-integer linear programming (MILP) model for the SCCPS problem and a heuristic algorithm was given to solve the model. Lietal.[5-6]abstracted the SCCPS problem as a hybrid flow shop scheduling problem and established the 0-1 MILP model and a two-stage genetic algorithm combined genetic algorithm (GA) and linear programming (LP) was proposed. A novel hybrid algorithm for the SCCPS problem was proposed in Atighehchianetal.[7], which was based on a combination of ant colony optimization (ACO) and non-linear optimization method. Maoetal.[8]established an MILP model for the SCCPS problem with the objective of minimizing the total weighted penalties of the earliness/tardiness and the job waiting. Lagrangian heuristic was developed to solve it.

These study payed more attention to increasing productive efficiency and decreasing productive cost, which mainly referred to the penalty fee for not meeting some constraints. In energy terms, Zhou and Li[9]proposed a converter-continuous casting production schedule model. A local searching algorithm based on 2-opt method was iteratively used to solve an actual scheduling problem. The energy consumption which was indirectly represented by total temperature drop in the literature was considered as one of the optimization targets. Lietal.[5-6]thought about reducing energy consumption through decreasing the sojourn time between the end at steelmaking stage and the start at casting stage for each charge and balancing them of all charges. Bellabdaoui and Teghem[10]presented a formulation with MILP and solved it using standard software packages. A limitation of the sojourn time of each charge was considered due to the necessity to keep a sufficient temperature before its starting at casting stage, and consequently reduce energy consumption for reheating. However, they didn’t regard the total energy consumption as the optimal objective directly. In this study, we just do that and we take into account the energy consumption when machines are idle. During the period of idle, machines also consume some energies to maintain the continuous production process, and the idle time has great influence on decreasing electric power cost in the situation of TOU power price (this content is not included in this paper).

The cross entropy (CE) method is based on Markov method and an important sampling technology, through statistical learning and updating, the probability of occurrence of the optimal solution increases gradually and stabilizes eventually which tends to be 1. During the search process for the optimal solution, the gradually increasing probability guides the most promising search direction rather than blind search. It is the unique feature and advantage of not comparable for other search algorithms, such as GA and ACO. In addition, a precise and complicated mathematical model is not necessary, and only the coding and its decoding method for the problem is needed, which is impossible for the mathematical programming method. So, the CE method has been successfully applied to a diverse range of optimization problems, Casertaetal.[11]proposed a cross entropy based algorithm for the integer knapsack problem with setups. Bendavid and Golany[12]addressed a problem of scheduling activities in projects with stochastic activity durations and employed the CE method to solve it. Other applications such as solving the vehicle routing problem, the multi-item capacitated lot-sizing problem with setup times, signal optimisation and optimal fuzzy control system can be found in literatures[13-16]. However, there is few studies about the CE method for the SCCPS problem, so in this paper, the CE method is adopted. And in order to reduce the search space, avoid blind search, and enhance the local exploitation capability of the CE method, an improved cross entropy (ICE) algorithm is proposed to improve the algorithm performance. Details on the ICE algorithm are described in the following.

The rest of the paper is organized as follows: In section 1, the SCCPS problem is introduced. In section 2, the CE method is described briefly. Then based on it the encoding scheme, decoding method for the SCCPS problem and the probability updating mechanism are proposed. Further, the ICE algorithm is presented. A number of simulation experiments and computational results are provided in section 3. Finally, we end the paper with some conclusions in section 4.

1 Problem Description

Before the beginning of this section, the notations used in this paper are defined as follows.

i: index of charge;

q: index of cast;

s: index of stage;

j: index of machine;

L: number of charges;

Q: number of casts;

H: number of stages;

SIi j: the successor charge of chargeion machinej;

Iq: set of charges in castq;

Ij: set of charges on machinej;

M: set of machines;

Ms: set of machines at stages;

sti j: start time of chargeion machinej,sti j∈;

sti s: start time of chargeiat stages,sti s∈R;

cti j: end time of chargeion machinej,cti j∈;

cti s: end time of chargeiat stages,cti s∈R;

pti j: processing time of chargeion machinej,pti j∈;

wti s(s+1): wait time of chargeibetween stagesands+1,wti s(s+1)∈;

iti S Ii j: idle time of machinejbetween chargeiand its successor chargeSIi j,iti S Ii j∈;

MT: limit of the maximum sojourn time,MT∈;

ps: unit power consumption of machine at stages,ps∈;

pwait: converted unit power consumption for waiting of charge,pwait∈;

pidle: converted unit power consumption for idle of machine,pidle∈.

The SCC process primarily consists of three stages: steelmaking, refining and continuous casting. At the steelmaking stage the hot metal is smelted in converter and turns into molten steel with the main alloy elements, which is defined as a “charge” in this paper. Each charge can be processed on any one of the identical parallel machines at this stage and it is true for other stages. Then the molten steel is poured into ladles and transported to a ladle furnace for refining so as to meet the requirements of chemical composition and temperature. If no ladle furnace is available the arriving charge has to wait until some one becomes available, which leads to temperature drop and then reheating is needed. After refining, the molten steel is transported to a continuous casting machine (CCM) machine and cast into qualified slab for the downstream operations to use. At the casting stage, a group of charges satisfying some technological constraints related to steel grade are cast continuously, which is defined as a “cast” in this paper. After a cast is finished on a CCM, setup time is required for changing crystallizer, cleaning equipments and tools, and then the successor cast on the same CCM can be cast.

The optimized scheduling of the SCC process needs to coordinate the rhythm of steelmaking, refining and casting operations, and on the premise of continuous casting, determine the machine, the sequence on the machine, the start time and end time of the molten steel to be processed from steelmaking to casting, so as to acquire satisfactory objective of production. Considering that the power consumption of refining process is influenced most by the scheduling in the converter steelmaking process, because more power will be consumed to reheat the charge to compensate for its temperature drop due to the waiting, we take the minimum of total power consumption as the objective of the SCCPS problem in this study. The objective function is formulated as Eq. (1).

(1)

wti s(s+1)=sti(s+1)-cti s,∀i∈I, s∈S, s≠H,

(2)

iti S Ii j=stSIi jj-cti j,∀i∈I, j∈M, j∉MH,

(3)

From Eq. (1) we can see that besides the power consumption for processing of machine and waiting of charges, the power consumption for idle of machines is considered due to the necessity to normal running of machines. In particular, for the continuous production, idle time before the first charge on each machine at each stage is not calculated.

Equations (4) - (10) formulate the production constraints for the SCCPS problem.

sti j≥0,∀i∈I, j∈M,

(4)

stik≥sti j+pti j,∀i∈I, j∈Ms1,

k∈Ms2, s1, s2∈S& s2=s1+1,

(5)

cti j=sti j+pti j,∀i∈I, j∈M,

(6)

stSIi jj=cti j,∀i, SIi j∈Iq, q∈K, j∈MH,

(7)

MT≥sti j-ctik,∀i∈I, j∈MH, k∈M1,

(8)

I1∩I2∩…∩IQ=φ,

(9)

I1∪I2∪…∪IQ=I.

(10)

Equation (4) ensures the start time of all charges should be greater than zero; Eq.(5) is the precedence constraints of operations which are defined by processing route; Eq. (6) ensures the processing of operation cannot be interrupted; Eq. (7) is the precedence and the no-break constraints within one cast; Eq. (8) ensures constraints of the maximum sojourn time for a charge between the steelmaking stage and the start of continuous casting stage; Eqs. (9) and (10) ensure that a charge can only be included in one cast.

To simplify the problem some assumptions are given in advance: (1) all charges have the same processing route; (2) a machine can process at most one charge at a time and a charge can be processed on at most one machine; (3) for each cast the CCM assigned to it and the start time of casting are given by planning level; (4) charges included in a cast and their sequence are given by planning level; (5) the process time for each charge at each stage is known.

2 The CE Method

2.1 The SCE algorithm

In order to distinguish the above mentioned CE method with the ICE algorithm we proposed, it is referred henceforth as the SCE algorithm.

2.2 Encoding, decoding and probability updating mechanism

(11)

(12)

Such a sample can not represent a complete scheduling. But the start casting time of each cast and the process time and order of charges included in the cast are known in advance. So, first we can calculate the start time of each charge at the casting stage. Then, for each charge, we can calculate its start time at the refining stage based on its process time at this stage and its start time at the casting stage without considering waiting time between the two stages. Further, based on the assignment state of the refining stage given by a sample, we can determine the assigned machine for each charge and its start time on the machine. But it is possible that there are machine conflicts for some charges, that is to say, on the same machine a charge will start to be processed but the prior charge is not processed completely. In order to eliminate the machine conflicts, we first sort the charges on the same machine according to their caculated end time increasingly, then keep the end time of the last charge unchanged and others moved forward in turn until all conflicts are eliminated. By the same method, we can determine the assigned machine at the steelmaking stage for each charge and its start time on the machine. If the start time of one or more machines at the steelmaking stage precedes the earliest available time, then the whole scheduling moves backward with the maximum lead time. Up to this, a complete scheduling is constructed, which is the decoding process. We use a matrix STn×mwith the same dimensions with matrix An×mto express the scheduling. The elementsti jrepresents the start time of chargeion machinej. If chargeiisn’t assigned to machinej,sti jis set to be a large constant.

In the SCE algorithm, a sample is randomly generated according to some probability distribution. For the SCCPS problem, we define the probability model as a matrix with the same dimensions with matrix An×m, expressed as Pn×m. The elementpi jrepresents the probability of chargeibeing assigned to machinejto process. Equation (13) gives the details of Pn×m. In particular, because the part of assignment state of casting stage in matrix An×mis determined, the corresponding elements in Pn×mare 1. Thus, In order to reduce the algorithm time we just use the part of the steelmaking stage and the refining stage in Pn×mto generate the corresponding part in An×m.

(13)

The updating process of probability distribution is the critical step of the SCE algorithm. In this paper, we apply the updating mechanism as described in Eq. (14). Similarly, we only update the part of the steelmaking stage and the refining stage in Pn×m.

∀i∈I, j∈Ms, s∈S& s≠H,

(14)

2.3 The ICE algorithm

In the SCE algorithm, the probability of the optimal solution increases gradually through multilevel iterations and tends to be 1 eventually. During iterations, if the stop criterion is reached then the algorithm ends and the optimal or near-optimal solution is generated. However, simulation results show that the convergence speed is too fast and it is easy to fall into local optimum which can be seen in section 3. So the ICE algorithm is developed. In comparison with SCE, the ICE algorithm has several improvements as follows. The encoding, decoding and probability updating mechanism are the same.

2.3.1 Generation of sample

In this study, we take the minimum total power consumption as the objective. While, heuristic rules in this respect can not be found easily. It’s comforting that there are many heuristic rules aiming at the shortest makespan. If we know some relations between them, then perhaps we can be inspired by them to solve the SCCPS problem with the minimum total power consumption. For this, a number of simulation experiments are carried out. Figure 1 (a) shows the relation between the power consumption and the makespan of one group of data. We selected plenty of reasonable scheduling and grouped them according to their makespan with every 10 min a group (e.g., some scheduling with their makespan in interval [471, 480] were divided into a group, others with their makespan in interval [461, 470] were divided into a group, and so on). In particular, the scheduling with makespan less than 391 min was divided into the group in interval [391, 400] because such scheduling is little. Then we selected 15 schedulings from each group, the average of makespan of the every 15 schedulings is the abscissa of a point on the curve, the average of power consumption of these 15 schedulings is the ordinate of the point on the curve. Obviously, the scheduling with lower power consumption has shorter makepan. Based on it, the SCE algorithm is improved in the composition of samples. That is, a certain number of samples generated by the heuristic rules of the shortest makespan are used besides the samples generated by the probability model. But the power consumption of the scheduling with the shortest makespan is not sure to be the lowest, such as shown in Fig.1(b). So, these added samples are not put into the set of elite samples. They are sorted with other samples according to their power consumptions to find the elite samples. In addition, for the global optimization, these samples account for only 20% of the elite samples. In section 3, the simulation experiments prove that the search space of the ICE algorithm is reduced greatly because of this improvement.

Fig.1 Relation between power consumption and makespan

2.3.2 Retention mechanism of the optimal sample

In the SCE algorithm, a sample is generated by sampling using probability. With the updating of the probability through iterations, the probability of occurrence of the optimal or near-optimal sample increases gradually and stabilizes eventually, so the optimal or near-optimal sample is generated. However, small probability events could still happen, which can bring about that the objective value of the optimal sample in some iteration is not better than it in the last iteration. So in the ICE algorithm we propose a retention mechanism of the optimal sample. That is, the optimal sample in an iteration is retained and added to the set of samples in the next iteration. In this case, the results of the iterations can change monotonically and the quality of samples is also improved.

2.3.3 Local search mechanism

3 Simulation Experiments and Computational Results

Because there are no standard data of the SCCPS problem and complete actual production data are not acquired easily, the simulation data used for experiments are generated randomly on the basis of conforming to the actual production. A steel plant has 3 converters (LD), 3 refinery furnaces (RF) and 3 CCMs. At each stage the machines are identical. Every workday is divided into three shifts, every shift lasts up to 8 h. Planners need to carry out the SCC scheduling in every shift for the next shift. So, in this study the planning horizon is set to be 8 h, that is 480 min. Generally, the SCC schedule includes 16-18 charges and a cast consists of 3-5 charges. Based on it, the number of charges to be scheduled is set to be 18 for each instance, and the number of casts is set to be 3, 4 and 5 respectively. For these three cases of different number of casts, 5 groups of instances are designed respectively in each case. The processing times for charges at each stage are generated randomly from a uniform distribution [30, 50]. Because of different processing characteristics, the power consumptions for steelmaking, refining and continuous casting are different distinctly. They are generated randomly from the uniform distributions [10, 20], [45, 60] and [15, 25] respectively. The power consumptions of waiting for charge and idle of machine are generated from a uniform distribution [3, 10]. The unit of power consumption is kW·h. Since the minimum scheduling time unit in the steel plant is in an exact number of minutes, so the minute is taken as the basic time unit.

3.1 Parameters design of the ICE algorithm

Parameters with different values have great influence on the performance of the ICE algorithm. In this study we select a representative instance of 3 machines and 4 casts and adopt the Taguchi method of design-of-experiment (DOE)[20]to investigate the influence of parameter setting on algorithm performance. These parameters are the numberNof samples, quantileρof elite samples, learning rateαand the numberLSof local search. Each parameter has 4 factor levels. Table 1 shows the details. The rank denotes how important of each parameter to the algorithm performance, which can be acquired by sorting the variances of the objective values of the 4 factor levels of the parameters in descending order. For each parameter combination, the ICE algorithm runs 20 times independently. The stop criterion is the differences of each pair of corresponding elements in the two probability matrices in the continuous two iterations are all smaller than 0.0005 or the results of 15 continuous running are not changed. The response variable value is the average power consumption. The orthogonal arrayL16(44) is used in the experiment. It can be seen from Table 1 thatNis the most significant one among the 4 parameters, next isLS, thenρandαis the last. The influence of each parameter with different values can be seen from Fig.2. The abscissa of the point on curve is the value of a parameter and the ordinate is the average value of the response variable value in the orthogonal array when the parameter takes this value. We can see from Fig.2, whenN=300, the objective value is optimal. Similarly,ρ=0.05,α=0.8 andLS=30. They constitute a better parameter combination.

Table 1 Parameter value and rank

1234RankN501002003001ρ0.050.10.20.33α0.20.40.60.84LS102030402

Fig.2 Influence on algorithm performance of the parameters

3.2 Results and analysis

For all instances, the SCE and ICE algorithms are implemented by using Matlab 7.0, and the experiments are carried out on a PC of Pentium(R) Dual-Core CPU, 2.6 GHz and 2 GB RAM. Table 2 shows the computational results. For each instance the two algorithms get satisfying results within 30 s. And it is clear that the ICE algorithm has better results than SCE for all instances although it consumes more CPU time. The comparisons of their convergence performances are shown in Fig.3. The ordinate of the point on curve is the average value of the results of 10 times running. Obviously, the search space in the early iteration of the ICE algorithm is reduced greatly benefiting from the heuristic rules and its exploitation capability in the late iteration is improved greatly benefiting from the local search mechanism. For the instances of 4 casts and 5 casts, two casts will be processed on a CCM. The time for changing crystallizer increases the makespan but it is not treated as the idle time for calculating power consumption, so the relation between power consumption and makespan is less prominent than the case of 3 casts. In these two cases, a smaller number of samples generated by the heuristic rules were used in the ICE algorithm.

Table 2 Algorithm results

SimulationinstancesICEObjectivevalues/(kW·h)MaxMinAverageCPU(s)SCEObjectivevalues/(kW·h)MaxMinAverageCPU(s)3castsGroup1693406834068947.7519.444694806891069163.006.435Group2700006953569854.2515.393706306976070173.756.419Group3698856945069721.2518.905706206989570150.006.892Group4676056734067491.0018.267680756742067646.757.003Group5666106628066488.7512.018673456651566920.007.0534castsGroup1660706542565791.2523.342665156565566017.758.579Group2637206314063493.0023.777640806339563659.58.200Group3618156134061622.2521.723620006161061752.58.298Group4644306402064246.0023.472645806414064336.258.322Group5650106429564775.2520.901651856449064865.257.9545castsGroup1698256930569545.2515.589699356938069648.58.654Group2706006981570218.2517.2277075069985703926.797Group3704656973070221.7517.240707406980570406.56.330Group4616256107061385.7520.553617806125061485.008.953Group5627406228062486.0018.832629156231062531.008.954

(a) 3 machines and 3 casts

(b) 3 machines and 4 casts

(c) 3 machines and 5 casts

The above analysis shows the superior performance of the ICE algorithm in solving the SCCPS problem. However, as shown in the decoding process, on the basis of the optimal assignment states of all charges, a complete scheduling is constructed through calculation backward from casting stage and elimination conflicts of machines. This leads to the scheduling compressed to right side, which makes the search space limited. So, referring to the right-shift method proposed by Du[21]and modifying it, we proposed a local left-shift (LLS) method for some charges to obtain further optimization. Considering the characteristics of the SCC process, the left shifting process is not implemented to the charges at casting stage and the first charge on each machine at steelmaking and refining stages. Figures 4 and 5 show respectively the Gantt charts of one instance before shift and after shift. The marked part in Fig.5 is the shifted part. The power consumption of this instance is 66280 kW·h before shift and 66190 kW·h after shift. The makespan is not changed, which is 393 min. What are changed are the waiting time of some charges and the idle time of some machines. Apparently, this change can reduce the total power consumption further, but it consumes little CPU time so as to be neglected.

Fig.4 Gantt chart before shift

Fig.5 Gantt chart after shift

4 Conclusions

This paper studied the SCCPS problem with the objective being to minimize the total power consumption. A CE method was adopted to solve the problem and simulation experiments showed its effectiveness. In order to improve the performance of the CE method an ICE algorithm was proposed. Generating some samples by heuristic rules for the shortest makespan can reduce search space greatly and avoid blind search in the early iteration. The introduction of the retention mechanism of the optimal sample and local search mechanism can retain the historical optimal sample and avoid falling into local optimal in the late iteration. We designed a number of simulation instances in three different cases to verify the effectiveness and superiority of the ICE algorithm. Meanwhile, for the limitation of the decoding method, we applied an LLS method on the optimal scheduling acquired by the ICE algorithm to coordinate the waiting time of charges and the idle time of machines so as to make the total power consumption reduced further. However, as a global optimization algorithm, the ICE algorithm still has some randomness in generating of sample. How to make it develop gradually to certainty is a challenging problem.

[1] Tang L X, Liu J Y, Rong A Y,etal. A Review of Planning and Scheduling Systems and Methods for Integrated Steel Production[J].EuropeanJournalofOperationalResearch, 2001, 133(1): 1-20.

[2] Tang L X, Luh P B, Liu J Y,etal. Steel-Making Process Scheduling Using Lagrangian Relaxation[J].InternationalJournalofProductionResearch, 2002, 40(1): 55-70.

[3] Harjunkoski I, Grossmann I E. A Decomposition Approach for the Scheduling of a Steel Plant Production[J].ComputersandChemicalEngineering, 2001, 25(11/12): 1647-1660.

[4] Liu G H, Li T K. A Steelmaking-Continuous Casting Production Scheduling Model and Its Heuristic Algorithm[J].SystemsEngineering, 2002, 20(6): 44-48. (in Chinese)

[5] Li T K, Su Z X. Two-Stage Genetic Algorithm for SMCC Production Scheduling[J].ChineseJournalofManagementScience, 2009, 17(5): 68-74. (in Chinese)

[6] Su Z X, Li T K, Wang W L. Improved Algorithm for SM-CC Production Scheduling Problem[J].ComputerEngineeringandApplications, 2011, 47(5): 242-245. (in Chinese)

[7] Atighehchian A, Bijari M, Tarkesh H. A Novel Hybrid Algorithm for Scheduling Steel-Making Continuous Casting Production[J].Computer&OperationResearch, 2009, 36(8): 2450-2461.

[8] Mao K, Pan Q K,Tasgetiren M F. Lagrangian Heuristic for Scheduling a Steelmaking-Continuous Casting Process[C]. Computational Intelligence in Scheduling (SCIS), Singapore, 2013: 68-74.

[9] Zhou Y L, Li T K. Study on LD-CC Production Scheduling Model and Its Solution Aiming at Energy Saving [J].MetallurgicalIndustryAutomation, 2012, 36(5): 20-23, 28. (in Chinese)

[10] Bellabdaoui A, Teghem J. A Mixed-Integer Linear Programming Model for the Continuous Casting Planning[J].InternationalJournalofProductionEconomics, 2006, 104(2): 260-270.

[11] Caserta M, Quionez-Rico E, Márquez-Uribe A. A Cross Entropy Algorithm for the Knapsack Problem with Setups[J].Computers&OperationsResearch, 2008, 35(1): 241-252.

[12] Bendavid I, Golany B. Setting Gates for Activities in the Stochastic Project Scheduling Problem through the Cross Entropy Methodology[J].AnnalsofOperationsResearch, 2011, 189(1): 25-42.

[13] Chepuri K, Homem-de-Mello T. Solving the Vehicle Routing Problem with Stochastic Demands Using the Cross Entropy Method[J].AnnalsofOperationsResearch, 2005, 134(1): 153-181.

[14] Caserta M, Quionez-Rico E. A Cross Entropy-Lagrangean Hybrid Algorithm for the Multi-item Capacitated Lot-Sizing Problem with Setup Times[J].Computers&OperationsResearch, 2009, 36(2): 530-548.

[15] Maher M, Liu R, Ngoduy D. Signal Optimization Using the Cross Entropy Method[J].TransportationResearchPartC:EmergingTechnologies, 2013, 27: 76-88.

[16] Haber R E, del Toro R M, Gajate A. Optimal Fuzzy Control System Using the Cross-Entropy Method: a Case Study of a Drilling Process[J].InformationSciences, 2010, 180(14): 2777-2792.

[17] De Boer P T, Kroese D P, Mannor S,etal. A Tutorial on the Cross-Entropy Method[J].AnnalsofOperationsResearch, 2005, 134(1): 19-67.

[18] Rubinstein R Y. The Cross-Entropy Method for Combinatorial and Continuous Optimization[J].MethodologyandComputinginAppliedProbability, 1999, 1(2): 127-190.

[19] Rubinstein R Y, Kroese D P. The Cross-Entropy Method: a Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning[M]. Berlin: Springer, 2004: 29-57.

[20] Liu W Q. Design of Experiments[M]. Beijing: Tsinghua University Press, 2005: 64-67. (in Chinese)

[21] Du B. Research on Models and Optimization Methods for Scheduling Batch Processing Machines[D]. Hefei: University of Science and Technology of China, 2011: 69-70. (in Chinese)

Foundation items: Key Project of Shandong Provincial Natural Science Foundation, China (No. ZR2010FZ001); National High-Tech Research and Development Program of China (863 Program) (No. 2007AA04Z157)

TP301 Document code: A

1672-5220(2015)01-0023-07

Received date: 2013-10-21

* Correspondence should be addressed to LI Qi-qiang, E-mail: qqli@sdu.edu.cn