An effective DE algorithm for hybrid flow shop load balancing scheduling problem

In this paper, an improved DE algorithm called double population self-adaptive differential evolution (DPSADE) algorithm is used to solve the hybrid flow shop load balancing scheduling problem (HFS-LBSP) which combines a novel double population cooperative evolution mechanism with a special self-adaptive parameter adjusting strategy. A mathematical model in which the weighted summation of the processing time load balancing cost and the total parallel machine waiting time is set as load balancing comprehensive evaluation index is formulated for this problem. In the last, The comparison between DPSADE and DE, SADE demostrates the effectiveness of DPSADE in solving HFS-LBSP.


ⅠINTRODUCTION
The workshop load balancing scheduling problem was first conducted by Thomopoulos N T [1] , much progress has been made ever since then. Researchers mainly focus on permutation flow shop, flexible job shop and parallel machine shop [2][3][4][5] while little literature concentrate on HFS-LBSP, literature [6] pointed out that keep load balancing in parallel machine is the key to improve the level of manufacturing performance, and a neighborhood search-based method is used together with genetic algorithm to solve this problem. Literature [7]

Ⅱ FORMULAITON OF HFS
The HFS scheduling problem can be described as follows: (1) there are n jobs which will be processed; (2) each job will experience m stages in the same direction; (3) there has at least one machine at each stage; (4) there are at least one stage which include more than one machines; (5)  is the end of processing time of job i at stage j on machine k . , , i j k Tw is the processing time of job i at stage j on machine k . , j k n is the number of jobs allocated on machine k at stage j .

B Model Variables and Constraints
is a binary variable which is equal to 1 if job i is assigned to machine k at stage j and is equal to 0 otherwise; In the above constraints, constraint (1) describes the relationship between the start and the end of job i , no matter which stage it is; constraint (2) ensures that a job can't be processed at next stage until it has being processed in the current one; constraint (3) shows that the total number of jobs on machine k is equal to the number of all jobs which assigned to machine k .

A. The HFS-LB Cost Based on
Workstation Processing Time In equation (4), In equation (5), j Tw is the average value of the j M parallel machines at stage j .

B. Total Parallel Machine Processing Waiting Time
In equation (7)   Twt Tms In equation (8), Twt is the total waiting time of all parallel machines, which is the sum of waiting time of all parallel machines in processing, and then make it as the auxiliary evaluation index to measure the parallel machines' load balancing degree.

C. Comprehensive Cost of HFS-LB
Before taking the weighted summation, normalization processing is need to be done to make the two evaluation index are within one magnitude, which help to control the effect of the two index on HFS-LBSP more effectively, TLB f and WT f is the normalizated value of Tlb and Twt . 1 2

A. Encoding and Decoding
A real coding method based on matrix is proposed in this paper [9] , using vector

B. Novel Evolution Mechanism
Before the evolutionary computation ofeach generation, classify the population into two parts based on fitness value, the individuals according with evolutionary trend is classified into elite population, otherwise to common population. 1) Respective evolution mode of the two population: DE/rand/1/bin [10] .
2) Cooperative evolution mode of the two population: DE/best/2/bin [10] , select two individual from the two Sub-population, then do a crossover operation to construct a new individual.

C. Special Self-adaptive Parameter Adjusting Strategy
The cross operator CR and mutation The two population have their own cross operators and mutation operators variation range, the cross operator and mutation operator adjustment range of elite population is small, which contribute to keep the stability of excellent individual while the cross operator and mutation operator adjustment range of common population is big to strengthen the evolution energy.

D. Procedure of The DPSADE Algorithm
Step1 Initialize population,evolution parameters and iteration times value 0 gen  .
Step2 Classify initial population into elite population 1 Pop and common 2 Pop ,the total number of

A. Evaluation Index Design
The load balancing costTlb ,total processing waiting time of workstationTwt ,comprehensive cost LB f and max C were set as the evaluation index.

B. Simulation Results
In this section, a problem with 3 stages and 8 jobs is used to test the performance of the proposed algorithm and comparison. The number of machines in each stage is 3, 2, 2. The processing time of each job in every machine is a random number between [15,30]. Each algorithm run 10 times, select the best solution to fill in Table 1.