Greedy Constructive Procedure－Based Hybrid Differential A lgorithm for Flexible Flowshop Group Scheduling

ZHENG Yong－qian(鄭永前)，YU Meng－meng(于萌萌)，XIE Song－h(huán)ang(謝松杭)

College of Mechanical Engineering，Tongji University，Shanghai201804，China

Greedy Constructive Procedure－Based Hybrid Differential A lgorithm for Flexible Flowshop Group Scheduling

ZHENG Yong－qian(鄭永前)，YU Meng－meng(于萌萌)*，XIE Song－h(huán)ang(謝松杭)

College of Mechanical Engineering，Tongji University，Shanghai201804，China

Aim ing at the flexible flowshop group scheduling problem，taking sequence dependent setup time and machine skipping into account，a mathematical model for m inim izing makespan is established，and a hybrid differential evolution(HDE)algorithm based on greedy constructive procedure(GCP)is proposed，which combines differential evolution(DE)with tabu search(TS)．DE is app lied to generating the elite individuals of population，while TS is used for finding the optimal value bymaking perturbation in selected elite individuals．A lower bounding technique is developed to evaluate the quality of proposed algorithm．Experimental results verify the effectiveness and feasibility of proposed algorithm．

flexible flowshop;group scheduling;hybrid differential evolution(HDE)algorithm;greedy constructive procedure(GCP); lower bound

Introduction

The flexible flowshop scheduling problem has received a great deal of attention during recent years due to its increasing applicability in the realworld.Compared with regular flowshop cell，multiple identicalmachines are assigned in parallel to some bottleneck stages in order to elim inate the bottleneck production constraints and improve the productivity.Assume that several groups of jobs including differentnumbers of jobs in each group are assigned to a flexible flowshop cell.Each group needs a setup on amachine in each stage to be processed.The setup is done based on the previously processed group on thatmachine. This problem is called flexible flowshop sequence－dependent group scheduling(FFSDGS)problem.

Most of prior researches on group scheduling have been performed in the area of flowshop.Cheng et al．［1］presented a comprehensive literature review of flowshop group scheduling problems.Schaller et al．［2］approached the flowshop sequencedependent group scheduling(FSDGS)problem for the first time.They proposed several heuristic algorithms to solve the problem.Franca et al．［3］developed two meta－h(huán)euristic algorithms based on genetic algorithm(GA)and memetic algorithm(MA)to solve the research problem proposed by Schaller［2］.Logendran and Salmasi［4］proposed meta－h(huán)euristic algorithms based on tabu search(TS)for FSDGS problems，and developed a lower bounding technique to evaluate the performance of the proposed TS algorithms.Salmasi and Logendran［5］developed amathematical programmingmodel for minimizing the total flow time of the FSDGS problems.Salmasi et al．［6］presented a hybrid ant colony optimization(HACO) algorithm for this problem，and a lower bounding technique based on relaxing a few constraints of themathematicalmodel to evaluate the quality of the HACO algorithm.

Logendran et al．［7］considered the generalized version of flexible flowshop with m stages for the first time，and developed three constructive algorithms for FFSDGS problems.Logendran et al．［8］developed a TS algorithm for the same problem.A detailed statistical experiment based on split－plot design was performed to analyze both makespan and computation time. Zandieh et al．［9］proposed two meta－h(huán)euristic algorithms based on simulated annealing and GA for FFSDGS problems.Shahvari et al．［10］proposed a mathematical model and another TS algorithm for FFSDGS problems and showed that their algorithm had a superior performance to the proposed algorithm by Logendran et al．［8］Later，Li et al．［11］proposed a constructive heuristic algorithm for two－stage flexible flowshop scheduling problem with head group constraintand release date tominimize themakespan.Keshavarz et al．［12］developed a meta－h(huán)euristic algorithm based on MA to efficiently solve FFSDGS problems. Although there are a few available meta－h(huán)euristic algorithms as upper bounds for FFSDGS problems，there is not any available lower bounding technique.Thus，there are rooms for generating a lower bounding technique to evaluate the efficiency of the proposed upper bounds.

The rest of the paper is organized as follows.The characteristics of the problem are described and themathematical model for the research problem is proposed in section 1.The hydrid differential evolution(HDE)algorithm for obtaining approximate solutions to the problem is presented in section 2. Lower bounding technique is described in section 3.Results of computational experiments to evaluate the performance of the proposedmeta－h(huán)euristic algorithm and lower bounding technique are reported in section 4.Finally，section 5 concluding remarks are addressed.

1 Problem Description

Suppose that g groups including a different number of jobs in each group are assigned to amanufacturing flexible flow shop cell with m stages.At leastone of the m stages has two ormore identical parallelmachines.The goal is to find the bestsequence of processing the groups as well as the jobs belonging to each group in order tominim ize themakespan.Based on Pinedo［13］，the problem can be noted as FFmflexible flowshop with m stages(FFm)，group scheduling problem (fmls)，sequence dependent set－ups(Shgi)，and makespan minim ization(Cmax).Other assumptionsmade in this research are as follows.(1)There is unlim ited buffer for the jobs between the stages.(2)The set－ups are assumed to be anticipatory.(3)Non－permutation scheduling is permissible for the groups as well as the jobs.(4)Group technology assumptions are valid in this research.

The jobs can skip some stages.

A binary m ixed integer linear programming model is developed for the research problem.The size of thismodel is much smaller than themathematicalmodel proposed by Shahvari et al．［10］The notations are listed in Table1，and themodel is as follows.

Table 1 Notations used in mathematicalmodel

Themodel:

Themakespan minimization is expressed by Formula(1) as the objective function.Constraint(2)ensures that each group is processed after exactly another group at each stage. Constraint(3)implies that each group has at most one successor group at each stage.At each stage，each two groups such as groups h and g may have three different positions compared with each other:(1)group h is processed immediately before group g，(2)group h is processed immediately after group g，and(3)these two groups are not processed exactly after each other.Constraint(4)is incorporated to the model for this reason.Constraint(5) ensures that Mimachines are scheduled at stage i.At each stage，the sequence of each two jobs in the same group is unique.Constraint(6)is incorporated to the model for this reason.The completion time of its immediate predecessor group plus the required setup time of thatgroup and its processing time is less than or equal to the completion time of each job in groups on each machine.Constraint(7)is incorporated to the model for this reason.Constraint(8)ensures that the completion time at the previous stage plus its processing time is less than or equal to its completion time of each job ateach stage.Constraints(9) and(10)are incorporated to themodel in order to support this fact.The completion time of each group is longer than the completion times of its jobs.Constraint(11)is incorporated to themodel for this reason.Constraint(12)is incorporated to the model to calculate the value ofmakespan.

Lee and Vairaktarakis［14］recognized that the FF‖Cmaxwas NP－h(huán)ard.Since the research problem can be relaxed to FF‖Cmaxby considering only one job in each group as well as ignoring the sequence dependency of setup times of groups，it can be concluded that the proposed research problem is NP－h(huán)ard as well.Since the research problem is recognized to be NP－h(huán)ard，meta－h(huán)euristic algorithms are the only available tools to solve industry－size problems.

2 HDE Algorithm

2．1 Procedure for constructing a com plete schedule

For FFSDGS problem，the group and job sequences determ ined on all machines in all stages are regarded as a solution.In this research，solution representation for the first stage is presented as a(g+1)×h pseudomatrix.

Assume that Xidenotes an individual as

The first grow presents the sequence of jobs in groups，and the last row presents the sequence of groups;h is equal to the maximum number of jobs in a group and the number of groups.

Based on the ranked order value rule［15］，the continuous position value of the individuals is converted to the group sequence and the job sequence in each group in the first stage.

Since the permutation rule cannot be applied in flexible flow shop problems，a greedy method based on the first available machine(FAM)rule is developed to find the sequence of processing groups as well as jobs in the follow ing stages，which is named as the greedy constructive procedure (GCP).In GCP，choosing the sequence of processing the groups in a stage is based on the first－in－first－out(FIFO)rule，and the assignment of groups to themachines in a stage having more than one machine is performed based on“the minimum sum of completion time of immediately preceding group on a machine and the setup time required to process the group on the samemachine”.Ties groups are broken in favor of the smallest machine number，if necessary.Allow ing jobs to skip some stages，updating sequence of jobs，which is based on their completion time at the previous stage，may be more efficientrather than considering a unique sequence of jobs at all stages. After assignment of groups and jobs at all stages，a complete schedule in all stages can be obtained and the maximum completion time of jobs at the last stage is equal tomakespan.

2．2 Population initialization

Taking both accuracy and diversity of the proposed algorithm into consideration，the initial population of feasible solutions is composed of two portions.One is generated random ly as follows:

Xi=lower(Xi)+rand(0，1)*(upper(Xi)－lower(Xi))，i=1，2，…，PS/2，

where PS denotes the population size.

The other is obtained by a two－stage heuristic named as Sigmoid function vary step(SVS)－algorithm，which is proved to have a better performance than the existing heuristics in literature for flowshop group scheduling problem.The stepw ise procedure of initializing the population is presented as follows.

Step 1 Perform NEH method to obtain optimal job sequenceπg(shù)of each group successively，whereπg(shù)is the job sequence，?g=1，2，…，G．

Step 2 Calculate the makespan for sequencesδ1=(πi，πj)andδ2=(πj，πi)and let f(δ1)and f(δ2)be themakespan associated with sequenceδ1andδ2respectively，where i=1，2，…，G－1 and j=i+1，i+2，…，i+G．

Step 3 If f(δ1)＜f(δ2)，set W(i)=W(i)+1;if f(δ1)＞f(δ2)，set W(j)=W(j)+1．

Step 4 If all pairs of sequences have been compared，then sequence groups in decreasing order of corresponding W value; otherw ise go to step 2.

2．3 Fram ework of HDE algorithm

2．3．1 DE search

DE is a novel parallel direct search method introduced by Storn and Price［16］for complex continuous optim ization problems.The key parameters in DE are size of population (PS)，scaling factor(F)and crossover parameter(CR).The common format of DE is DE/x/y/z，where x represents a base vector to be mutated/perturbed，y is the number of difference vectors used for perturbation of x，and z stands for the type of crossover being used.

In this paper，DE/rand－to－best/1/exp scheme is adopted and the procedure of HDE is summarized as follows.

Step 1 Let G denote a generation，Pop(t)a population with size PS in generation t，Xi(t)the i th individual，and random(0，1)the random value in the interval［0，1］.

Step 2 Mutation phase.For each Xi(t)，amutant vector Vi(t+1)is generated by adding the weighted difference between a defined number of individuals random ly selected from the previous population to another individual，which is described by the follow ing equation:

Here random ly select r1and r2∈(1，2，…，PS)，r1≠r2≠i，random ly select an individual from S as best，F(xiàn) controls amplification of the differential variation，and Xi(t)is the base vector to be perturbed.

Step 3 Crossover phase.For each target Xi(t)，a trial vector Ui(t+1)is generated by procedures as follows:

Here Xik(t)is column vector，k∈{1，2，…，h}and CR∈［0，1］controls the diversity of the population.

Step 4 Selection phase.For each target Xi(t)，Ui(t+1) is compared with the initial target individual Xi(t)by using a tournament selection criterion:

where f is the objective function and Xi(t+1)is the individual of the new population.

2．3．2 Local search

Assume that Xi(t)is an individual in the current population.If the positions of any two arbitrary groups in the vector related to the group sequence(the last row)are changed，a new neighborhood for the research problem will be generated.Compared with several commonly used operators，the diameter of Insert is one of the shortest ones，which means the solutions caused by Insertare closer to each other than those caused by other operators.Therefore，Insert is adopted here as the neighborhood for local search.

Pseudo code of the Insert－based local search is given as follows.

Step 1 Convert the last row of an individual Xi(t)to a group permutationδi_0based on the ranked－order－value(ROV) rule.

Step 2 Random ly select u and v，where u≠v;δi= Insert(δi_0，u，v).

Step 3 Set loop=1;

Step 4 If f(δi)＜f(δi_0)，thenδi_0=δi.

Step 5 Convert backδi_0to Xi(t)．

This local searchmethod is simple but efficient because of the follow ing two reasons.Firstly，in step 2，u and v performing Insert are random ly chosen and the new neighborhood is always accepted，so the local search can avoid cycling and overcome local optimum.Secondly，in step 3，two positions u and v performing Insert are random ly chosen，and the new neighborhood is accepted only if its objective value is less than the old one.

2．3．3 TS algorithm

For the elite individuals of the output population，a TS method incorporating inside and outside search is presented to determ ine the optimal group and job sequences.Inside search is applied to solving intra－group scheduling，while outside search is for inter－group scheduling.Since perform ing the inside search for each step of outside search consumes a considerable amount of time，in the interest of time，the inside search is performed for only a portion of outside neighborhoods for each seed.Before starting the inside search for each outside neighborhood，the objective function value of outside neighborhoods is estimated.Therefore，the inside search is performed for the best 30%of the best outside neighborhoods，instead of all of them.

Based on the above sub－sections，the framework of HDE is illustrated in Fig.1.

Fig.1 Framework of the HDE

3 Lower Bounding Technique

Since the researched problem is shown to be NP－h(huán)ard，the HDE solution can be compared with the optimal solution only for small－size problems.Instead of optimal solution，the lower bound of the optimal solution(as a reference)can be used to evaluate the efficiency of the proposed HDE for medium and large－size problems.Thus，a mixed integer linear model is presented for calculating the lower bound of the optimal solution of the original problem.This model is inspired from the proposed lower bounding technique by Salmasi et al．［6］for FSDGS problems.Each group is considered as an aggregated job.The processing time of this aggregated job at each stage is considered equal to the summation of the processing time of the jobs in that group.With these assumptions，the possible idle time among the jobs of each group is neglected，so the optimal solution of themodel is a lower bound for the original problem.

The parameters and decision variables used in section 2 to propose themathematicalmodelare used for the lower bounding model.However，the follow ing parameters are used for this mathematicalmodel:

SPgiis the summation of processing time of jobs in group g at stage i，i．e．，

min Pgiis theminimum processing time of jobs in group g at stage i，i．e．，minj{Pgji}．

The lower bounding mathematical model is as the follow ing:

m in Cmax

subject to:

STgi≥FThi+Shgi－M(1－Xhgi)，h=0，1，…，G，

another 5 constraint sets follow the constraints(2)－(6)and (12)in section 1，and

The starting time of that group plus the summation of processing time of jobs in thatgroup at that stage is equal to the completion time of each group at each stage.Constraint set (14)is to support this fact.A group is available to be processed at a stage when the processing of at least one of its jobs has been finished at the immediately preceding stage. Therefore，it is clear that the earliest time to start processing a group on amachine is the time that the job with them inimum processing time of the group is processed at the preceding stage. Constraint set(15)is incorporated to themodel for this reason. Descriptions of the other constraint sets are the same as the originalmodel.

4 Results and Discussion

The proposed HDE is coded with MATLAB.The Lingo (version 11.0)，a commercial optim ization software，is used to solve the exact and the lower bounding models.The HDE algorithm，the exactmodel，and the lower bounding model are run on a PC with Core i3－2370M CPU with 4 GBmemory.For evaluating the efficiency of proposed HDE algorithm，its performance is compared with the TS algorithm developed by Shahvari et al．［10］based on 45 test problems proposed by Logendran et al．［8］The ranges of test problems are shown in Table 2.

Table 2 Range of test problems

The results of both algorithms for the test problems are presented in Table 3.It can be concluded that there is a significant difference between the performances of these algorithms for all problem sizes.Since the average makespan value of the HDE is less than the TS algorithm for all three problem sizes，it can be concluded that the HDE provides better solutions for FFSDGS problem than the proposed TS by Shahvari etal．［8］By consideringmean values of results of HDE and TS，the averagemakespan of HDE is3%lower than thatof TS.

Table 3 Computational results(HDE vs.TS algorithm)

All small－size problems are solved optimally using the proposed mathematicalmodel in section 1.The lower bounding model is used for calculating the lower bound of the optimal solution formedium－size problems(problems up to 65 jobs in all groups).The comparison of experiment results is shown in Fig.2.

Fig.2 Comparison of experiment results

For small－size problems，only in two instances the HDE fails to find the optimal solution.The percentage gap of the proposed HDE comparing with the optimal solution for smallsize problems is 0.3%.Average percentage gap of HDE for medium－size problems is3.5%.

5 Conclusions

In this paper，the FFSDGS problem with minimization of makespan as the criterionis investigated.Allow ing for sequence dependent setup time and machine skipping，a mathematical model is established to optimize proposed problem efficiently.An HDE algorithm based on GCP is proposed，which combines DEwith TS.DE is applied to generating the elite individuals of population，while TS is used for finding the optimal value by making perturbation in selected elite individuals.The results show that the proposed HDE algorithm can efficiently solve FFSDGS problems.

［1］Cheng T，Gupta J，Wang G.A Review of Flowshop Scheduling Research with Setups［J］.Production and Operations Management，2011，24(3):257－268.

［2］Schaller J E，Gupta J，Vakharia A.Scheduling a Flow Line Manufacturing Cellwith Sequence Dependent Fam ily Setup Time［J］.European Journal of Operations Research，2000，125(2): 314－339.

［3］Franca PM，Gupta J，Mendes PM.Evolutionary Algorithms for Scheduling a Flowshop Manufacturing Cell with Sequence Dependent Fam ily Setups［J］.Computers and Industrial Engineering，2005，48(3):491－506.

［4］Logendran R，Salmasi N.Two－Machine Group Scheduling Problems in Discrete Parts Manufacturing with Sequence－Dependent Setups［J］.Computers and Operations Research，2006，33(1):158－180.

［5］Salmasi N，Logendran R.Total Flow Time M inim ization in a Flowshop Sequence－Dependent Group Scheduling Problem［J］. Computers＆Operations Research，2010，37(1):199－212.

［6］Salmasi N，Logendran R，Skandari M R.Makespan M inim ization of a Flowshop Sequence－Dependent Group Scheduling Problem［J］.International Journal of Advanced Manufacturing Technology，2011，56(5/6/7/8):699－710.

［7］Logendran R，Carson S，Hanson E.Group Scheduling in Flexible Slow Shops［J］.International Journal of Production Economics，2005，96(2):143－155.

［8］Logendran R，Deszoeke P，Barnard F.Sequence－Dependent Group Scheduling Problems in Flexible Flow Shops［J］. International Journal of Production Economics，2006，102(1): 66－86.

［9］Zandieh M，Dorri B，Khamseh A R.Robust Meta－Heuristics for Group Scheduling with Sequence－dependent Setup times in Hybrid Flexible Flow Shops［J］.The International Journal of Advanced Manufacturing Technology，2009，43(7):767－778.

［10］ShahvariO，Salmasi N，Logendran R.An Efficient Tabu Search Algorithm for Flexible Flow Shop Sequence－Dependent Group Scheduling Problems［J］.International Journal of Production Research，2011，50(15):4237－4254.

［11］Li Z T，Chen Q X，Mao N.A Heuristic Algorithm for Two－Stage Flexible Flow Shop Scheduling with Head Group Constraint［J］.International Journal of Production Research，2012，51 (3):751－771.

［12］Keshavarz T，SalmasiN，SkandariM R.Makespan M inim ization in Flowshop Sequence－DependentGroup Scheduling Problem［J］. International Journal of Production Research，2013，51(20): 6182－6193.

［13］Pinedo M.Scheduling Theory，Algorithms，and Systems［M］. 3rd ed.NJ:Prentice Hall，2008.

［14］Lee C Y，Vairaktarakis G.M inim izing Makespan in Hybrid Flow Shops［J］.Operations Research Letters，1994，16(3):149－158.

［15］Zheng Y Q，Xie S H，Qian W J.Hybrid Differential Evolution Algorithm for FSDGS Problem with Lim ited Buffers［J］. Computer Integrated Manufacturing Systems，2014，20(8): 1941－1947.

［16］Storn R，Price K.Differential Evolution－a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］. Journal of Global Optimization，1997，11(4):341－359.

TP278

A

1672－5220(2015)04－0577－06

date:2014－07－20

Shanghai Municipal Natural Science Foundation of China(No.10ZR1431700)

*Correspondence should be addressed to YU Meng－meng，E－mail:yumengmeng90@163.com