车间调度算法

2012 2nd International eConference on Computer and Knowledge Engineering (ICCKE), October 18-19, 2012

A New Method for Hybridizing Metaheuristicsfor Multi-Objective Flexible Job Shop Scheduling

Roohollah Javadi,Maryam Hasanzadeh

Department of IT and Computer Engineering

Shahed UniversityTehran, Iran

heuristics such as Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) for multi-objective FJSP. Xia and Wu [1] proposed a hybrid algorithm, combining PSO with SA to solve the multi-objective FJSP. Gao et al. [2] also proposed a hybrid algorithm of GA and variable search descent for the FJSP. Zhang applied a hybrid algorithm of PSO and TS as a local search algorithm in [3]and proposed a hybrid algorithm GA and TS to solve the multi-objective FJSP in [4].

Liouane et al. [5]combined the Ant system optimisation meta-heuristic with local search methods, including Tabu Search to solve FJSP. Ho and Tay [6]proposed an efficient approach by combining evolutionary algorithm and guided local search and Li, Pan and Xie [7]proposed a novel hybridvariable neighborhood search algorithm combining with the genetic algorithm for solving the multi-objective FJSP.

Liu, Abraham and Wang [8]proposed a Multi-Particle Swarm Optimization approach which its behavior is

Keywords- flexible job shop scheduling; multi-objective somewhat similar to that of our algorithm. All the swarms optimization; metaheuristic algorithms; genetic algorithm; local search the optimal solution synergistically and refer to the search balance between diversity of particles and search space.

In most of hybrid methods, especially combination of evolutionary algorithms with local search methods, the role I. I NTRODUCTION

Flexible job shop scheduling problem (FJSP) is very of local search is to increase the average fitness of all or part important in many fields such as production management, of the population in the current generation and to produce resource allocation and combinatorial optimization. In the better individuals as future parents. And there is no real manufacturing systems, each operation could be significant innovation in the evolutionary algorithm. In processed on more than one machine and each machine can addition, applying local search in each iteration imposes a also process several operations. This feature is known as large processing overhead.

But, in this paper, we utilized the genetic algorithm, as a flexibility.

The problem of scheduling jobs in FJSP could be population-based search algorithm, for distributed

exploration of good solutions in the search space, regardless decomposed into two sub-problems: the routing sub-problem; in which each operation is assigned to a suitable of focusing on findingthe global optimum. The search

machine, and the scheduling sub-problem; in which the process will be completed by a local search method is in the operations are sequenced in order to obtain a feasible next step as a final post-processing.

In this paper, a new approach is proposed to solve the schedule, minimizing the predefined objective functions.

This indicates that the computational complexity of FJSP is multi-objective FJSP. In the first step, an initial population of

feasible solutions with good dispersion in the search space is more than JSP. The general JSP is NP-hard, the multi-created. Then an improved genetic algorithm based on objective FJSP is strongly NP-hard and well combinatorial

fitness and neighborhood parameters, explores the search [4].

space until it will form several dynamic clusters around the In the literature, different hybrid approaches are proposed

to solve multi-objective FJSP. In recent years many studies good areas, including local optimums. The main goal of this

step is just exploration. Finally, in parallel, a Tabu Search have focused on developing hybrid algorithm by using meta-Abstract —Flexible job shop scheduling problem (FJSP) is an

important extension of the classical job shop scheduling problem, where each operation could be processed on more than one machine and vice versa. Since it has been proven that this problem is strongly NP-hard, it is difficult to achieve an optimal solution with traditional optimization algorithms. In this paper a new approach is proposed to solve the multi-objective FJSP. This new approach has three steps. First, an initial population of feasible solutions with good distribution in the search space is created by using a parameter called neighborhood . Second, this population, based on fitness and neighborhood parameters, explores the search space until it will form several dynamic clusters around good areas, including local optimums. Finally, in parallel, a local search is performed on the best solution for each cluster by using Tabu Search algorithm and eventually the optimal solution is obtained among them. Computational results on benchmark problems show that the optimal solutions are obtained much faster than other approaches.

alternative machines Mij which is sub-set of M.

Hypotheses which areconsidered in thisproblem are summarized as follows:

xThe processing time of operations on each machine

is predefined.

xThe interruption during the process of an operation

on a machine is impossible. (atomicity)

xEach machine can process only one operation at a

time.

xJobs and also machines are independent.

xIndependent jobs, can be processed in parallel. xAll jobs are available at t0.

xThe order of operations for each job is

predetermined.

xSetting up times of machines and move times

between operations are negligible.

In order to describe the proposedalgorithm more easily, an instance of FJSP is given in Table 1 in which there are 3 jobs and 5 machines. In this table, the “-” means that the machine can not process the corresponding operation and each valuemeans the time required forprocessing. This instance has partial flexibility.

In general, if some machines can not perform all operations, that instance has partial flexibility. Otherwise, it has total flexibility.

TABLE I.A N INSTANCE OF FJSP method is performed on the best solution for each cluster and

eventually the optimum solution is obtained among them.M 5Job Operation M 1M 2M 3M 4

The new hybrid approach is categorized in high-level

O 1138362relay hybrid (HRH) class in the taxonomy of hybrid J 1

O 12- 5-3-metaheuristics proposed by Talbi [9]. In HRH hybrid, self-contained metaheuristics are executed in a sequence. For O 212-4-5

example, in this paper clustering method and Tabu Search

O 21475--J 2

algorithm are employed after genetic algorithm.

O 23-6859The rest of the paper is organized as follows: the problem

description is introduced in section II. Section III presents O 31-55--J 3the proposed strategy and framework of the hybrid

O 322--43

algorithm. In Section IV, the results of computational experiments of our proposed approach are reported followed

by the comparison with other heuristic methods. Finally, in B. M ulti-Objective FJSP Optimizationsection V some concluding remarks are made.

A multi-objective optimizationgenerally includes numbers ofobjectives that eachobjective has its own

II. P ROBLEM D ESCRIPTION

importance.

In a minimization multi-objective problem, each element A. Flexible Job Shop Scheduling Problem

The job shop scheduling problem is a kind of constraint of n-dimensional vectorx contains proportionate valueto optimization problems (COP) in which jobs are scheduled corresponding objective. When no value of x 2is less than x 1

and at least one value of x 2is greater than x 1, then it can be and operations are assigned to specific machines. In addition,

in the flexible type of this problem, each operation could be mentioned that the solution x 1dominate the solution x 2. processed on more than one machine and each machine can Otherwise, the solution x 1and the solution x 2are non-dominated solutions.also process several operations.

For example, consider a bi-objective functions, f 1(x)and In the formal expression, there are a set of N jobs J = {J1,

J 2, ..., Ji , ..., JN } and a set of M machines M = {M1, M2, ..., f 2(x). In the figure 1, it could be seen that solution “a” M j , ..., MM }. Each job Ji consists of a predetermined dominates solution “b”. But solution “a” does not dominate sequence of operations. For each operation, there is a set of solution “c”.

f 12Figure 1.Comparison between solutions in the bi-objective problem

In this paper, the considered objectives are CM , WM and W T which are defined as follows:

xC M is the maximal completion time of machines, i.e.,

the make span.

xW M is the maximal machine workload, i.e., the

maximum processing time spent at any machine. xW T is considered as the total workload of machines. In order toevaluate the solutionsmore easily, there are many methods for finding a solution for a multi-objective optimization problem. Using a single aggregate objective function (AOF) is the most common method.

In this paper, a weighted linear aggregate function (Equation 1) is used and the proposed algorithm assigns most weight to the first objective because of its importance.

f (x ) 0. 5C M (x ) 0. 3W M (x ) 0. 2W T (x )

(1)

III. P ROPOSED H YBRID A LGORITHM

The proposed hybrid algorithm consists of three general steps that represent the overall strategy of problem solving. In the following, details of each step are explained.

A. Exploration Step

The main objective in this step is exploring the entire search spaceto find promising areas. However,since it is impossible toevaluate all solutions, it is necessary to use an algorithm which properly explores the search space. The goal of this algorithm is only identifying and discovering areas with high average fitness, not to find the global optimum solution.

The improved genetic algorithm which is called NGA (Neighborhood-based Genetic Algorithm), is an appropriate method for this step. Operators of this algorithm have been adjusted in order to focus more on exploration.

The majorinnovations in NGA are in thecreation ofinitial population, parent selection and finallyin survivors’ selection steps, whichwill be explainedin the next sections.1) Representation of Individuals

The FJSP problem is a combination of machine assignment and operation scheduling, so a solution can be represented by two vectors: Machine Selection (MS) vector and Operation Sequence (OS) vector.

Machine Selection vector:An array of integers with length L - the sum of all operations of all jobs - that each number represents a machine that is responsible to processing operation with the corresponding index. For instance, in figure 2, M5is selected to process operation O23. Operation Sequence vector:This vector is also an array of integers with length L that each number representsan index of a job. According to the predefinedsequence of operations which are related to a job, for everyoperation, the index of related jobis replacedin thearray. It can avoid creating an infeasible schedule. Figure 2 shows that how operation sequence 2-2-1-3-1-2-3 could be translated into a list of ordered operations: O21-O 22-O 11-O 31-O 12-O 23-O 31. Machine Selection (MS)

distance with all of othersolutions. The purpose of this constraint is a nearly uniform distribution of initial population in the search space. So each area of the search space will have at least one agent in initial population.

Generally, theneighborhood parameter is determinedbased on the distance betweentwo solutionsin thesearch space and depends on theproblem. For example, Euclidean distance between two pointsor two solutions in a problemwith search spacein Cartesian coordinate system, indicatesthe value oftheir neighborhood.

In this paper, theneighborhood concept in [10]is usedto calculate thevalue of thisparameter in FJSP. Basedon [10], distanceor difference betweentwo solutionsis determined according to thepermutation ofoperations. Ifthe difference between twosolutions Sp and Sq is only the order ofoperation Oij which have to be executed on the same machine (Figure 3, solutions S1and S2), the distance between these solutionsis O(1). But ifoperation Oij in solution Sp to beprocessed by machine Mp and insolution S r to beprocessed by machine Mr , such that Mp z M r (Figure 3, solutions S1and S3), the distance betweenthese solutions is O(n).

(a) Solution S1

(b) Solution S2

Operation Sequence (OS)

ppppppppppppppO 11 O 12 O 21 O 22 O 23 O 31 O 32 O 11 O 31 O 12 O 21O 32O 22O 23

Figure 2.Chromosome representation

Figure 3.Examples for illustration the difference between solutions

2) Initial Population

To create the initial population, in addition to being random, it is necessary that solutions are adequatelydispersed throughout the search space. So the parameter “neighborhood ” formed to represent the distance between two solutions. Eachnew solutioncan be consideredas a member of initialpopulation, ifit has at least a predefined

So the neighborhoodbetween thetwo solutionsis determined according toall permutations of operations.

Since this parameter is defined between everytow solutions, a data structure

with size ofO(P2) is required to store and update corresponding values, whichPis the size of population.

3) Parent Selection

Using the neighborhoodparameter in parent selectionis also necessary andeffective. If theselection criteriais only based onfitness, worsesolutions will haveless chanceof being selected and theireffects will begradually eliminated. So in order to employ most potential of all individuals, a new parent selection method which is called Neighborhood-based Selection, is proposed.

The first parent solution for the crossover operator, should be selected among all existing solutions in the current population (Equation 2).Consequently, allof the individuals participatein creating the nextgeneration. The second parent is randomlyselected among nearestand fittest solutions to the first parent.In other words, the second parent is selected by using Roulette Wheel random selection based on the described probability in equation 3.P 1:P 2:

Solution i i = {1, 2, … , P} Solution j j = {1, 2, … , P}-{i}randomly based on:

fitness(Solutionj ) uneighborhood(P1, Solutionj )

(2)(3)

OS 11

Figure 4.Example of POX

5) Mutation

This operator is also performedon eachsegment of thechromosome separately.

After randomly selecting agene of the Machine Selection vector, one machine is selected from alternative machine set to replace current machine.

For the Operation Sequence vector, two genes randomly selected and swapped.

It should be noted thatbecause of focusing on exploration in this step, thisalgorithm has a verylittle emphasis on themutation operator.

6) Survivors Selection

Considering that allindividuals are selected for the crossover operator, for selecting survivors andcreating the next generation, a corresponding child whohas the most fitness among all children of a supposedindividual and its parent, isreplaced byit.

In early iterations, according to the uniform distribution of population, the fitness parameter plays a greater role for selection of second parent. But gradually the fitness values will be similar to each others and distances will be different. Then neighborhood parameter will play a greater role and each individual will be more likely to combine with a closer one. Therefore finding local optimums and moving toward them is more probable.

B. C lustering Step

The previous step of algorithm(Section A) is repeatedas

4) Crossoverlong asthe general fitness of population is significantly This operator has a key role indiscovering new improved. Also according toinvolve the neighborhoodindividuals in the search space. Therefore, the proposedcriteria inthe algorithm, the process ofpopulation algorithm has great emphasison crossover. displacement is suchthat a set ofdynamic clusters are The crossoveroperator is performedon eachsegment of formed. Figure 5simulates the movement ofa sample the chromosome separately. UniformCrossover has been population. Picture(a) showsthe distribution ofinitial used for the Machine Selection vector. This type of population. According to third part of Section A, the crossover uses a mixing ratio between two parents and movement of populationis similar to picture(b) during the enables the parent chromosomes to contribute the gene level search processand picture(c) shows the population in the rather than the segment level.last iteration.For the Operation Sequence vector, an improved Therefore, after finishingthe first step, anappropriate Precedence Preserving Order-based crossover (POX) is clustering algorithm, can separate the identified areasin the adopted [11]. The POX works as follows:search space. Here, thehierarchical clustering algorithm is xStep 1: Generate two sub-set Js1/Js2from all jobs. used [12]. xStep 2: Copy any element in OS1/OS2that belong to

Js1/Js2 into child individual OS’1/OS’2, and retain in the same position in OS’1/OS’2.

xStep 3: Delete the elements that are already in the

sub-set Js1/Js2from OS1/OS2.

xStep 4: Orderly fill the empty position in OS’1/OS’2

with the reminder elements of OS2/OS1.

Figure 4 illustrate the procedure of generating two child

(a) Initial population(b) Mid-runpopulation (c) Clustering of

individuals. Two sub-sets are Js1={2}, Js2={1,3}.final population

Figure 5.Simulation of population displacement

C. Local Search Step

For each identified cluster,one individual with thehighest fitness is selectedand usedas a starting pointin a local search. Alsodue tothe independence ofthe clusters, there isthe possibility ofparallel processingfor this step. At the end, thebest solutionamong theclusters is chosen as an optimal solution. Here, Tabu search algorithm is used[13].

IV.

C OMPUTATIONAL R ESULTS

The proposed NGATS method is implemented in Java on a 4.2 GHz Pentium and tested on XWdata that is a set of four problems from Kacem et al. [14]and Xia and Wu [1].The result of proposed algorithm is compared with other algorithms in Table 2. In this table, AL+CGA is the algorithm proposed by Kacem et al. [14]. PSO+SA is the algorithm proposed by Xia and Wu [1], PSO+TS is proposed by Zhang et al. [3]and hGA is proposed by Gao et al. [2]. HGATS is applied by Zhang et al. [4]. And the NGATS is our proposed effective hybrid algorithm.

In addition to good computational resultswhich are better or equal to the reported ones in Table 2, the

TABLE II.

Problem n u m4u 5 8u 8 10u10

15u10

Obj. C M W M W T C M W M W T C M W M W T C M W M W T

AL+CGA PSO+SA

1610 34 15 1613 13 79 75 7 5 45 24 1191

N/A N/A N/A 15 161213 75 73 7 6 44 12 1191

PSO+TS1110 32 14 1512 12 77 75 7 6 43111193

computational time of proposedalgorithm is remarkable in comparison with othersimilar algorithms.

It can be seen from Table 2 that our algorithm dominates the AL+CGA algorithm in solving problem 4 u5. It can also obtain optimal solutionsby only 15individuals in 30milliseconds.

NGATS algorithm can obtain optimal solutions for problem 8 u8by only 50individuals in 310milliseconds, while hGA solves this problemby 300individuals.

Table 2 also shows that our algorithm dominates most of algorithms in solving problem 10 u10. It can obtain optimal solutions byonly 100individuals in 1.49seconds, whilehGA solves this problemby 300individuals.

NGATS also dominates both AL+CGA and PSO+TS algorithms for solving problem 15 u10and can obtain optimal solutions byonly 280individuals in 29.65seconds, while hGA solves this problemby 500individuals.

Other algorithms often solve these problems withmore than 1000individuals thatcertainly increase the computational time.

T HE COMPUTATIONAL RESULTS

hGA N/A N/A N/A 14 12 77 7 5 43 11 1191

HGATS N/A N/A N/A 14 12 77 7 6 42 11 1191

Proposed NGATS

11 1210 8 32 32 14 1512 12 77 75 7 75 6 43 42 11 1191

280

29.65 s

100

1.49 s

0.31 s

0.03 s

C ONCLUSIONS

The mainsuperiority of proposedalgorithm is the appropriate strategy to findthe optimal solution. Thesuitable algorithm is applied to achievegoal in each step. Pervasive search in first step is performed by usingan improved genetic algorithms with a new method for parent selection which explores thesearch space purposefully. The appropriateareas identified in the second step areseparated by usingclustering techniques.

The goal of third stepis finding the optimal solutionin each cluster. Therefore,using local search algorithmssuch as Tabu search in parallelexecution is a suitable optionto achieve thisgoal.

The finalsolution ofthe problem is obtained among theoptimal solutionsin each cluster.

Compared with other existing algorithms for solving the Kacem instances, computationalresults show that the proposed algorithm either obtains similar solutions or can obtain richer non-dominated solutions faster than the other approaches. In other words, the best known results areachieved by the proposed methodwith less computational time.

R EFERENCES

[1][2]

W. Xia and Z. Wu, "An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem", Computer & Industrial Engineering, vol.48, Mar. 2005, pp. 409–425.

J. Gao, L. Y. Sun and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems”, Computer & Operations Research, vol.35, Sept. 2007, pp. 2892–2907.

[3]

[4]

[5]

[6]

[7]

G. H. Zhang, X. Y. Shao, P. G. Li and L. Gao,“An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computer & Industrial Engineering, vol. 56, 2009, pp. 1309–1318.

Guohui Zhang, Liang Gao, Yang Shi, "A Genetic Algorithm and Tabu Searchfor Multi-Objective Flexible Job Shop Scheduling Problems", International Conference on Computing, Control and Industrial Engineering, 2010.

Noureddine Liouane, Ihsen Saad, Slim Hammadi, Pierre Borne, “Ant systems & Local Search Optimization for flexible Job Shop Scheduling Production”, International Journal of Computers, Communications & Control, vol. 2, 2007, pp. 174–184.

Nhu Binh Ho, Joc Cing Tay, “Solving Multiple-Objective Flexible Job Shop Problems by Evolution and Local Search”, IEEE Transactions onSystems, Man, and Cybernetics-Part C, Applications and Reviews, vol. 38, 2008, pp. 674–685.

Jun-qing Li, Quan-ke Pan, and Sheng-xian Xie, “A Hybrid Variable Neighborhood Search Algorithm for Solving Multi-Objective Flexible Job Shop Problems”, Computer Science and Information Systems, vol. 7, 2010, pp. 907–930.

[8][9][10]

[11][12][13][14]

Hongbo Liu, Ajith Abraham, ZuwenWang, “A Multi-swarm Approach to Multi-objective Flexible Job-shop Scheduling Problems”, Fundamenta Informaticae, vol. 95, 2009, pp. 465–489.E. G. Talbi, “A Taxonomyof Hybrid Metaheuristics”, Journal ofHeuristics, vol. 8, 2002, pp. 541–564.

:RMFLHFK %R]HMNRD 0DULXV] 8FKURQVNLD 0LHF]\VáDZ :RGHFNL "The new golf neighborhood for the flexible job shop problem". International Conference on Computational Science, 2010, pp. 289–296.

Guohui Zhang, Yang Shi, Liang Gao, "A Genetic Algorithm and Tabu Search for Solving Flexible Job Shop Schedules", International Symposium on Computational Intelligence and Design, 2008.

Pang-Ning Tan, Michael Steinbach, Vipin Kumar, "Introduction to Data Mining", Addison Wesley, 2006.

Monaldo Mastrolilli, Luca Maria Gambardella, "Effective neighborhood functions for the flexible job shop problem", Journal of Scheduling, 2000, pp. 3–20.

I. Kacem, S. Hammadi, and P. Borne, “Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic”, Mathematics and Computers in Simulation, vol. 60, Sept. 2002, pp. 245–276.

2012 2nd International eConference on Computer and Knowledge Engineering (ICCKE), October 18-19, 2012

A New Method for Hybridizing Metaheuristicsfor Multi-Objective Flexible Job Shop Scheduling

Roohollah Javadi,Maryam Hasanzadeh

Department of IT and Computer Engineering

Shahed UniversityTehran, Iran

[email protected], [email protected]