Development of a method for optimized manufacturing route selection

(1)

Institut für Fertigungstechnik und Werkzeugmaschinen

Prof. Dr.-Ing. B. Denkena

Master thesis

"Method for optimized manufacturing route selection"

Verfasser: Sofia Parrucci Matrikel-Nr.: 10016461 Betreuer: M. Sc. S. Wilmsmeier Garbsen, den 26.03.2018

(2)

Abstract

Thema der Arbeit: Method for optimized manufacturing route selection

Erstellt von: Sofia Parrucci

Matrikelnummer 10016461

Kenn-Nr.: -

Abgabedatum: 26.03.2018

Betreuer: M. Sc. S. Wilmsmeier

This thesis introduces a Genetic Algorithm for the holistic optimized manufacturing route selection. Two different approaches, such as the adaptive Planning and Pro-duction Control, and the Flexible Job Shop Problem, are combined. The new method given by this combination allows to develop an evaluation of manufacturing routes, by optimizing the production system as a whole, but not by developing a rigid schedule, in order to recalculate alternative work plans everty time that changes af-fect the production environent. Through a comparison with a Machine Assignament Rule, the results show that the proposed algorithm works as expected in a maximum number of components, within the production layout, which ranges from one hundred to one thousand, in terms of total throughput. However, there aren't benefits in terms of avarage cost and avarage waste rate. Nevertheless, if the objective function of the Genetic Algorithm is given by time, cost and quality separately, the algorithm per-forms in the right way, in therm of total thoughput, avarage cost, and quality. In addi-tion, the advantage in using this method, is related to the fact that it can face produc-tion changes and route constraints, through the iterative setting up of all the possible production routes for each job in a certain moment of the production.

(3)

Statement

I hereby certify that I have prepared the present master thesis without outside help and have not used any other than the aid I have indicated.

Hannover, 26/03/2018 _________________

(4)

List of figures

Fig. 1 Example of Open Shop ... 3

Fig. 2 Example of Flow Shop ... 4

Fig. 3 Example of Job Shop ... 5

Fig. 4 Genetic Algorithm flow chart ... 14

Fig. 5 One point crossover ... 15

Fig. 6 Two-point crossover ... 15

Fig. 7 Uniform crossover ... 16

Fig. 8 Use case production layout ... 41

Fig. 9 Flow chart of the algorithm to set the work plans ... 43

Fig. 10 Flow chart of the methodology to test the algorithm ... 51

Fig. 11 Test scenario on Plant Simulation ... 52

Fig. 12 Exit strategy of the machine Turning 1 ... 53

Fig. 13 Custom attributes of machine Turning 2 ... 54

Fig. 14 Tables of processing times, costs and quality within the "TargetValues" folder ... 55

Fig. 15 Manual inputs ... 55

Fig. 16 Custom attributes of Job 1 ... 56

Fig. 17 Work plan tables for each job ... 57

Fig. 18 Work Plan table of Job 1 ... 62

Fig. 19 Machine matrix of Job 1 ... 63

Fig. 20 Six columns of the table "InitialPop" ... 64

Fig. 21 One call of the method "DeleteMUs" ... 65

Fig. 22 Flow chart of the method to inizialize the population ... 66

Fig. 23 "GeneticAlgorithm" folder ... 67

Fig. 24 Explaination of the two possible starting situations ... 69

(7)

Fig. 26 Example of "EndTimes" table with ten active MUs ... 71

Fig. 27 Example of "Mst" table ... 71

Fig. 28 Example of "Met" table ... 72

Fig. 29 Exaple of "Costs" table with ten jobs ... 73

Fig. 30 Example of "RejectRates" table with ten jobs ... 74

Fig. 31 Ten individuals of the "TargetValues" table ... 75

Fig. 32 Ten individuals of the "NormTargetValues" table ... 75

Fig. 33 Example of the "Selection" table ... 76

Fig. 34 Example of "MatingPool" table ... 77

Fig. 35 Example of "Output_Heuristic" table with ten active MUs ... 79

Fig. 36 Flow chart of the "GeneticAlgorithm" method ... 80

Fig. 37 "Selection" table for operation 1 of job 1 ... 81

Fig. 38 "Random" table with fiftheen active MUs ... 83

Fig. 39 Twelve individuals of the"MatingPool1" table with five active Mus ... 85

Fig. 40 Seven individuals of "NewGeneration1" table with five active MUs ... 85

Fig. 41 Some individuals of the "Mut" table with one active MU ... 86

Fig. 42 Some indiviuals of the "Cross" table with one active MU ... 87

Fig. 43 Best fitness value trend with five active MUs ... 87

Fig. 44 Best fitness value trend with 25 actvie MUs ... 88

Fig. 45 Best fitness value trend with fifty active MUs ... 89

Fig. 46 Routes of the jobs with the maximum number of MUs set up to one ... 90

Fig. 47 Experiment Manger settings and input values ... 92

Fig. 48 Objective function comparison between the three methods ... 93

Fig. 49 Total throughput comparison between the three methods ... 94

Fig. 50 Total throughput comparison with the GA and MAR which evaluate only the time ... 95

Fig. 51 Sankey diagram of GA with 8 maximum active MUs ... 97

(8)

Fig. 53 Machines utilization of MAR with 8 maximum MUs ... 98

Fig. 54 Machines utilization of GA with 8 maximum MUs ... 98

Fig. 56 Sankey diagram of MAR with 30 maximum active MUs ... 99

Fig. 57 Machine utilization of GA with 30 MUs ... 99

Fig. 59 Machines utilization of GA with 100 maximum MUs ... 100

Fig. 62 Sankey diagram of MAR with 100 maximum active MUs ... 102

Fig. 63 Overview of the working areas of GA ... 104

Fig. 64 Avarage cost comparison between the three methods ... 105

Fig. 65 Avarage cost comparison with GA and MAR which evaluate only the costs106 Fig. 66 Avarage waste rate comparison between the three methods ... 106

Fig. 67 Waste rate comparison with GA and MAR which evaluate only the waste rate ... 107

(9)

List of tables

Tab. 1 Results of the problem ... 30

Tab. 4 Ranking of the solutions ... 33

Tab. 5 Differences between PPC and FJSP ... 34

Tab. 6 Operations component 1 ... 36

Tab. 14 Saaty scale ... 45

Tab. 15 Evaluation ... 45

Tab. 16 Normalized evaluation ... 46

Tab. 17 Final weights ... 46

Tab. 18 Inizial price, amortization fee and annual maintenance cost ... 59

Tab. 19 Cost per year and per hour ... 60

Tab. 20 Processing times, costs and reject rates for operations of job 1 ... 61

Tab. 21 Manual calculation of the total throughput ... 90

Tab. 22 Time gap between GA, MAR and Random ... 96

Tab. 23 Cost gap between GA, MAR and Random ... 102

Tab. 24 Waste rate gap between GA, MAR and Random ... 103

(10)

Tab. 26 Processing times, cost and reject rates for operations of job 3 ... 112

Tab. 34 Processing times, costs and rejec rates for operations of job 11 ... 119

Tab. 36 Processing times, costs and reject rates for oeprations of job 13 ... 121

Tab. 37 Processing times, costs and rejec rates for operations of job 14 ... 122

Tab. 39 Time, total cost, avarage cost and total throughput of GA ... 124

Tab. 40 Total rejected parts and avarage waste rate of GA ... 125

Tab. 41 Time, total cost, avarage cost and total thoughput of Random method ... 126

Tab. 42 Total rejected parts and avarage waste rate of Random method ... 127

Tab. 43 Time, total cost, avarage cost and total throughput of MAR ... 128

Tab. 44 Total rejected parts and avarage waste rate of MAR ... 129

Tab. 45 Weighted sum values of the GA, MAR and RANDOM algorithms ... 130

Tab. 46 Total throughput of GA with only time evaluation ... 131

(11)

List of abbreviations

Symbols Description Unit

PPC Production Planning and Control [...]

FJSP Flexible Job Shop Problem [...]

JSP Job Shop Problem [...]

MAR Machine Assignment Rule [...]

GA Genetic Algorithm [...]

PSO Particle Swarm Optimization [...]

SA Simulated Annealing [...]

(12)

1 Introduction

Static prerequisites are assumed in work planning, and optimal production se-quences are defined. Dynamic influences (for example limited availability of the ma-chines) require short-term rescheduling within production control and, generally, this is carried out manually. In the case of manual rescheduling, alternative production sequences are not systematically evaluated and inefficent planning is the result. The goal of this thesis is to develop a method for the holistic optimized manutafcturing route selection, by not working on a component-specific basis, but optimizing the production system as a whole.

Thereby, in chapter two, after an overview of the different types of manufacturing production layouts, it emerges that there are two different kinds of approaches which face the problem of the manufacturing route selection, such as Flexible Job Shop Problem and Production Planning and Control. For the first type of problems, the so-lutions based on the literature, give results for which the routes are selcted by optimi-zing the production system as a whole, but without facing the real time environment, in that, they create a rigid schedule. On the contrary, with Production Planning and Control solutions, the schedule can be modified each time that a disturbance affects the production, but the optimization is performed by taking into account one compo-nent at a time. For this reason, the new approach consists in combining the two prob-lems, in order to select the best manufacturing route, by optimizing the entire produc-tion system, in terms of time, cost and quality, but in a real time producproduc-tion environ-ment. As a result, the Genetic Algorithm of Zhang et al., which gives the best solution to the Flexible Job Shop Problem, is transformed and adapted to a real time manu-facturing environment, in order to not create a rigid schedule, but one that can face production changes.

In chapter three and four, the production test scenario is developed by selecting fift-heen kinds of mechanical compontents, and, based on the machining operations needed to manufacture them, thirtheen machines are chosen. Thus, the production scenario is composed by a turning, milling, drilling, grinding, and multipurpose de-partment. Once the test scenario has been set up, a test methodology is developed. Through the methodology, it is explained how to create the initial work plans and the detailed plan, how the objective function of the problem is calulated and which target

(13)

criteria are used, how to set up the expertiments in order to evaluate the algorithm, and, finally, how the results are evaluated. In order to evaluate the goodness of the Genetic Aalgorithm, the resluts of a Machine Assignment Rule and of a random me-thod are compared with it.

In chapter five, the test scenario is built in an event driven material flow simulation software called Plant Simulation, where the Genetic Algorithm and the other two me-thods are programmed and implemented, with the aim of investigating scientifically their behavior in extensive series of experiments.

Finally, in chapter six, after a verification of the model and the setting up of the expe-riments plan, the reults of the series of expeexpe-riments are considered critically and the suitability of the alternative solutions is evaluated. The master thesis ends with the discussion of the results of the experiments and with considerations about the be-nefits that the GA brings and its limitations.

(14)

2 State of art review

2.1 Manufacturing production environments

Based on the number of the operations of each job and precedence relations between operations for the same job, as mentioned by Puppato et al. [PUPP10], the-re athe-re five models which describe how a job can be processed: open shop, flow shop, flexible flow shop, job shop and flexible job shop.

2.1.1 Open shop

In this kind of production, the number of the operations is constant for each job and each operation is performed, without precedence constraints, by the machine dedi-cate to it. There isn’t a particular order to follow, therefore, a schedule determines the execution order of the operations in the machines and the order of the jobs between the machines [PUPP10].

Fig. 1 Example of Open Shop

2.1.2 Flow shop

The machines are in series, and each job has to be performed by each machine af-terwards. This means that the routing is fixed, because the job order performed by each machine, has to be the same for each job. In addition the processing flow is

(15)

unidirectional. The routings is fixed but the working time on each machine can vary from job to job [PUPP10].

Fig. 2 Example of Flow Shop

2.1.3 Flexible flow shop

The flexible flow shop is a generalization of the flow shop with parallel machines. In-stead of the single machines, there are production stages in series, each with the same number of parallel machines. In each stage the job can be performed by any machine of that stage [PUPP10].

2.1.4 Job shop

In this case there is an amount of machines but each job has its own order to visit them. It can be said that job shop is a generalization of flow shop but without an uni-directional processing flow. Like the example in the figure, it can be seen that the routing (order of operations) is fixed for each job but it varies from job to job. Fur-thermore the processing time on each machine can be different for each job [PUPP10].

(16)

Fig. 3 Example of Job Shop

2.1.5 Flexible job shop

The flexible job shop is a generalization of job shop with parallel machines. Instead of single machines, there are workcenters (for example production areas, cell, produc-tion islands), each with the same machine number in parallel. Each job has to be per-formed, following a predefined order, by each workcenter, and it can be processed by any machine of that workcenter [PUPP10].

2.2 Manufacturing route problems

Scheduling or routing decisions are important activities in any manufacturing en-vironment. They are key factors for enhancing manufacturing productivity. The pur-pose of scheduling is to allocate resources to the jobs. Efficient schedules yield, in-deed, great savings in the overall manufacturing environment. A scheduling problem consists in to determine the optimal allocation of activities that have to be performed with the available resources. With the term machine is indicated any resource like a tool machine, a workcentre, an operator. In scheduling problems the activities, that can be one or more elementary operations, like milling, turning, dirilling operations, are called operations, and a job is a set of operations technologically linked. It is as-sumed that certain classes of operations can group togheter such jobs and that two

(17)

operations belonging to the same job are considered differents, if they are to be per-formed on different machines. In addition, as to have a good production scheduling, companies that aim to success, have to face their production flexibility [PUPP10]. As a matter of fact, in order to respond to frequent changing conditions of the production environment, due for example to machine breakdowns, unespected costumer orders, lack of raw material, poor quality of a processing, it is required to dynamically adjust the production schedule. Otherwise, these changes can distrupt the production and bring to an increase of lead time and, as a consequence, the impossibility to respect delivery deadlines. Therefore, it’s preferible to not just using rigid and predefined producion schedules [DENK11].

2.2.1 Production Planning and Control

The Production Planning and Control (PPC) is a problem which consists in planning of routing, and scheduling and the controlling of materials, methods, machines, tools and operating times. In this kind of problem it’s considered the real production enriv-ronment with disturbances, such as machine breakdowns, missing devices or broken tools, and other things that may appen during a real-time manufacturing production. By solving this problem it would be permitted the decreasing of the effects of such disturbances through an early recognition of deviations and a promt replanning [DENK06].

2.2.2 The Flexible Job Shop Scheduling Problem

The Flexible Job Shop Scheduling Problem (FJSP) is an extenction of the classical Job Shop Scheduling Problem (JSP), which allows an operation to be processed by some machines from a given set. The problem consists in to assign each operation to a machine, and to order the operations on the machines, such that the maximal completion time (makespan) of all operations is minimized [BRAN93]. The machines are named parallel, if they all can execute the same operations and dedicated, if they are specialized to execute just specific operations. There are three types of parallel machines depending on their speed: identical, if they work at the same speed, uni-form, if they work at different speeds but it keeps constant, and uncorrelated, if the speed depends on the operation to be realized. In FJSP, the same operation can be processed on more than one machine, thus, there are alternative machines available to process a particular job. If an operation can be performed on a subset of machine

(18)

the flexibility is “partial”, and when an operation can be executed on all machines then the flexibility is “total” [PUPP10]. The FJSP problem is considered as one of the most difficult combinatorial optimization problems, and it was even shown that is strongly NP-hard because the classical JSP has proven to be strongly NP-hard by [GARE76]. To explain what NP-hard means it is necessary to write some considera-tions about the complexity theory given by Garey et al. [GARE79]. The complexity theory is designed to be applied to decision problems which means that the output range is {yes, no}. Decision problems are commolny distinguished in two classes. First, the class calles "P" contains all decision problems for which a polynomial-time deterministic algorithm exists. The second class, "NP", is to the class of all decision problems that can be solved by polynomial-time nondeterministic algorithms. Obvi-ously, P ⊆ NP. A decision problem Π is called polynomial-time reducible to a decision problem Π’ if the following two conditions hold:

• There is a polynomial-time computable function f transforming inputs for Π to inputs for Π’.

• For all inputs, the output of Π for an instance is ‘yes’ if and only if the output of Π’ for the the instance is ‘yes’.

If Π is polynomial-time reducible to Π’, it is denoted by Π∝Π’. A decision problem Π is NP-hard if Π’∝ Π for all other decision problems Π’∈NP. If addicionally Π∈NP holds, then Π is called NP-complete.

Returning to the FJSP, it can be divided in two passages [BRAN93]:

• The sequencing sub-problem whose purpose is to establish a sequence of operations on all resources to obtain a feasible schedule minimizing a prede-fined objective function;

• The routing sub-problem whose purpose is to assign each operation to a re-source selected from a given set.

As compared to classical job shop, where each job is required to be processed on only one machine, the allocation of tasks in FJSP is more challenging as it requires a proper selection of a machine from a set of given machines to process each operati-on. The FJSP is composed of the following elements [CHAU13]:

(19)

• Jobs J = {J1, J2,...,Jn} is a set of n independent jobs to be scheduled. Each job Ji consists of a sequence Oi1, Oi2,...,Oin of operations to be per-formed one after the other according to a given sequence. All jobs are avai-lable at time 0.

• Machines I = {M1, M2,..., Mm} is a set of m machines. Every machine pro-cesses only one operation at a time. All machines are available at time 0. • The processing time of each operation is machine-dependent and machines

are independent from each other.

• Pre-emption of operations is not allowed, for example, each operation once started must be completed without interruption.

• Setup time required to setup a machine to process an operation is included in the job processing time of the job.

• Transportation of jobs from one machine is negligible and is included in the job processing time.

• Objective function: The problem is to assign each operation to an appropriate machine (routing problem), and to sequence the operations on the machines (sequencing problem) in order to minimize the make span (Cmax) that is given by the completion time of the last job performed. The make span represents the measure of the time needed to finish all the activities.

Moreover, for each job it could be defined [CHAU13]:

• Processing time tij: it represents the time that the job j needs to be performed

in the machine i.

• Release date rj: it is the time before which it isn’t possible to start the

execu-tion of job j. For example, it could represent the instant where raw materials are available for the process.

• Due date dj: it represents the time within the execution of job j should be

end-ed.

• Weight wj: it is the importance of the job j in front of the other jobs. For

exem-ple, it could represents the mantenance cost in the wharehouse. It is hence a priority index of job j.

(20)

2.3 Solutions for manufacturing route problems

2.3.1 Solutions for PPC

There are different approaches for process planning such as the Dynamic process planning, the Just in Time planning, the Alternative planning, the Nonlinear planning, and the Hierarchical planning, and, it is shown that the flexibility of PPC can be signi-ficantly improved only when alternative techonological solutions can be adopted during the replanning o manufacturing operations [E1MA92]. In order to reach a high level of flexibility, Denkena and Battino [DENK06] have developed a model called Adaptive Planning and Production Control, which allows an adequate integration of process planning and production control. As a matter of fact, with this model, it’s pos-sible to have a feedback of current production information, and thus, there is more flexibility in the process plans. The factors to develop this model are based on guide-lines, which combine different types of flexibility, and the fact that the flexbility can be increased by preparing process planning and prduction controlling activities. There are, in fact, three different kinds of flexibility [ElMA06]:

1. Flexibility via alterantive operations: in order to process a given component, there is a definition of alternative and appropiate operations (production pro-cesses).

2. Flexibility via alternative operation sequences: in order to process a given component, there is a definition of alternative operation sequences.

3. Flexibility via alternative manutacturing resources: the available manufacturing resources determine the definition of varying operation and operation se-quences. Selecting redundant resources and by the feasibility of choosing dif-ferent manufacturing processes to perform a component, it allows to reach a high degree of flexibility.

Like explained by Denkena et al. [DENK11], this model is created by combining three of the conventional approaches mentioned above such the hierarchical, the nonlinear and the dynamic planning. The hierarchical approach consists in two stages, where, in the first one, a rough plan, which contains the operations seqance is developed, and in the second one, there is an exact assignement of operations to specific

(21)

manu-alternative operation sequences are not plenned. On the other hand, in the nonlinear planing there are alternative opration sequences, which are planned before the start of the production process, written in a process plan network. In this case, when a dis-turbance appears, another sequence is selected in accordance with the process plan network. The last approach, that is used to develope the adaptive planning, is the dynamic planning, where there isn’t a predefined plan before the start of the produc-tion process, but the individual operaproduc-tions are planned and allocated to the available resources directly. The adaptive planning combines the advantages of these three approaches, such as the division into rough and detailed planning, the creation of process plan networks, and taking into the account the current production workload and resource availability. Thus, during the preliminary planning, the operation se-quences are determined and prioritized, and then, the final operation sequence is set dinamically during the manutacturing process. In this way, the ingration of respective process planning activites into the course of prodcution control, and a flexible response to failures is guaranteed. The phase of the rough plan creation consists of creating a nonlinear process plan and evaluate each process chain in order to select the best one in therms of cost, quality and processing time. Once the best alternative route is selected, this stage ends with the estimation of detailed planning times, in order to have a cordination between the detailed planning, concerning the order scheduling and the techonologically oriented process, related to the detailed plan-ning. In the stage of the detailed planning, already available systems, which are part of the manufacturing environment for PPC, are re-accessed in order to allow the in-coroporations of the current production information in the context of the detailed planning stage. The detailed planning has to be based on current information on the available resources and machine utilization, therefore, the Manufacturing Exectution System (MES) enables a key-performance-indicator (KPI), based control and monito-ring of the entire production in real time. Thus, by compamonito-ring the present information with the process chain hierarchy, established during the rough planning stage, the process chains suitable for the manufacturing process are determined on the basis of the current resource availability. In addition, all remaining valid process chains are evaluated parallel to the current manufacturing process and prior to the potentially following process. In this way it’s possible to react to problems that born during the production process, by switching to alternative processing stations, by taking into ac-count the recent data from the MES.

(22)

2.3.2 Solutions for FJSP

Generally, to solve any kind of scheduling problem, are used exact algorithms and heuristic methods. The difference between this two solutions is explained below [BLAZ94].

o Exact Algorithms:

An exact algorithm is a set of steps that allows to find, if it exists, the optimal solution of a problem. In addition, if the problem doesn’t have any feasible solution, it’s pos-sible to know it for sure. The main approaches that are used to solve scheduling problems are listed below:

• Mixed integer linear programming

• Enumerative methods (branch and bound, dynamic programming)

o Heusristic methods:

To solve scheduling problems, the exact algorithms can’t return solutions for large problem instances in reasonable time, hence the heuristic methods can produce the approximate solution that are needed. This is because the problems are NP-hard. The time of reaching an approximate solution is, indeed, much less that of reaching the optimal solution. A list of heuristic methods is given below:

• Machine assignment rules: procedures to assign an operation to one of its machines. A list of assignement rules is given below[URLI10]:

1. Random assignament rule: for each operation, a machine is selected ran-domly from a set of candidate machines. The main advantage is its compu-tational simplicity, while the disadvantage is that there isn’t a machine workload balance.

2. Minimum processing time rule: for each operation, the machine with mini-mum processing time in the set of candidate machines is selected. This rule helps to reduce the total processing load over all the machines and the completion time.

3. Earliest completion time: for each operation, the machine that can com-plete the operation earliest is selected. In this way the makespan and the

(23)

completion time are reduced.

4. Earliest preparation next stage: the machine that can prepare the job earli-est to the next operation is selected. In this way it can be considered the delay between the current and the next operation.

• Operation sequencing (dispaching) rules: are procedures that select a job from the set of jobs that are waiting for the processing, whenever a machine is available. The most common rules for the FJSP are [URLI10]:

1. Service In Random Order: the job is sequenced randomly.

2. Job slack: this rule gives the priority to the job with the least slack time, which means the difference between the due date and remaining pro-cessing requirement.

3. Earliest due date: it sequences the jobs according to their decreasing order of due dates.

4. Earliest release date first: the job that arrives first is processed first. In this way the variation in waiting time of the jobs is minimized.

5. Shortest processing time first: it sequences the jobs in non decreasing or-der of their total processing times. In this way the sum of total completion time of jobs is minimized.

6. Longest processing time first: it sequences the jobs in non increasing order of their total processing times. In this way the workload over the machines is balanced.

7. Shortest setup time first: it selects the job with minimum setup time to min-imize the total processing load.

8. Least flexible job first: it selects the job with minimum processing alterna-tives to give a priority to the job having less chance for assignement.

• Local search methods (tabu search, simulated annealing, genetic algorithm, partical swarm optimization).

Moreover, the problem can be solved following two different approaches [BRAN93]: • Hierarchical approach: the assignement of operations to their respective

(24)

ma-chines are initially made and well after that sequencing procedure starts. • Integrated approach: both assigning and sequenching decisions are made

concurrently.

The NP-hardness of the flexible job shop scheduling problem suggests to use heuris-tics and approximate algorithms because they produce good schedules in a reasonable time, instead of looking for an exact solution [BLAZ94]. Detailed explaina-tions of local search methods with the most important results are given below.

2.3.2.1 Genetic Algorithms

Genetic algorithms (GAs) are search heuristics introduced by John Holland in the early 1970’s that mimic the process of natural evolution [HOLL92]. There are two mechanisms that link a genetic algorithm to the problem. First, evolution takes places on chromosomes, which are represented by solutions of a combinatorial problem. Secondly, in order to mimc the process of natural selection, an evaluation function is essential, returning a measurment of the worth of any chromosome in the context of the problem. In the following points, a description of a gentic algorithm based on Da-vis [DAVI91] is given:

1. Inizialize a population of chromosomes, for example, an initial set of feasible solutions to the problem.

2. Evaluate each chromosome in the population.

3. Create new chromosomes by mating current chromosomes. Apply mutation and crossover as the parent chromosomes mate. Generally the best chromo-some is still reproduced in the next generation, in order not to risk losing the precious genetic heritage.

4. Delete members of the population to make room for the new chromosomes. 5. Evaluate the new chromosomes and insert them into the population.

A flow chart of a generic genetic algorithm is shown in Fig. 4 [CAHU13]. However, the main difference between genetic algorithms and other heuristics it that GAs maintains a population of solutions rather than a unique solution.

(25)

Fig. 4 Genetic Algorithm flow chart

According to the theory of "Meta-heuristics and evolutionary algorithms for enginee-ring optimization" [SOLG17], there are different ways to perform the processes of the parents selection and the crossover. About the parents selection, the main methods are listed below:

• Roulette wheel selection: the probability of selecting an individual is directly propotional to the value returned by the fitness function. This technique pre-sents problems in case there are large differences in values because the worse solutions would be selected too rarely.

• Stocastic universal sampling: this method is a development of the Roulette wheel selection but it uses a single random value to sample all the solution, by choosing them at evenly spaced intervals. This gives weaker members of the population (according to their fitness) a chance to be chosen, and thus it re-duces the unfair nature of fitness-proportional selection methods.

• Tournament selection: this approach involves running several "tournaments" among a few individuals chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. If the tournament size is larger, weak individuals have a smaller chance to be se-lected.

(26)

• Truncation selection: this technique orders the individuals according to their fitness. Then, only a certain portion of the fittest chromosomes are selected and reproduced.

The main methods to perform the crossover are the following:

• Single point crossover: this operator cuts the chromosomes from a certain point, in order to obtain two heads and two tails. The first new solution will be given by the combination of the head of the first solution with the tail of the se-cond, while the second new one, will be given by the tail of the first solution with the head of the second.

Fig. 5 One point crossover

Fig. 6 Two-point crossover

• Two-point crossover: this operator cuts the chromosomes in two points in or-der to obtain a head, a central part, and a tail. The first new solution will be given by the head and the tail of the first solution and the central part of the

(27)

second solution. The second new solution will be given by the central part of the first solution and by the head and tail of the second solution.

• Uniform crossover: this operator exchanges randomly some bits between the chromosomes.

Fig. 7 Uniform crossover

The genetic algorithm is applied to the flexible job shop scheduling problem by many scholars with different variants. Davis L. was the first who suggested and demonst-rated the application of GAs to a simple job shop scheduling problem. Since then a number of researchers have applied GAs various types of manufacturing systems. Similarly there has been a growing trend towards the GA applcation to flexible job shop scheduling problem. All the approaches that are presented below have the sa-me objective function, which consists in minimize the makespan.

An application was developed by Pezzella et al. [PEZZ07] where they adopted the approach by localization of Kacem et al. to find initial assignments, improving it by reordering the jobs and the machines, and by searching for the global minimum in the instance table. The Most Work Remaining (MWR), the Most Operation Remai-ning (MOR), and random selection of the next job dispatching rules were then adop-ted to sequence the operations, generating the initial population. Different crossover and mutation genetic operators were adopted, both for the assignment and for the sequencing. In particular, they introduced in this context an intelligent mutation as-signment operator. Furthermore, to built the initial population, there was an adoption of a mix of two assignment rules. The first assignement rule consisted to search for the global minimum in the processing timetable. The second consisted in randomly permute jobs and machines in the table. The adoption of a mix of these two rules

(28)

could be for example 20% of initial population generated with the first rule and the 80% by the second. In this approach, hence, a goal was to find a robust tuning of this mix for different classes of problem instances. In the phase of the choice of chromo-somes for reproduction it was possible to choose betwen three criteria:

• Binary tournament: Two individuals are randomly chosen from the population and the best of them is selected for reproduction.

• n-size tournament: The individual for reproduction is chosen among a random number of individuals.

• Linear ranking: Individuals are sorted according to their fitness and a rank ri ∈

{1,...,N} is assigned to each, where N is the population size. The best individu-al gets rank N while the worst gets rank 1.

In this method, the mating pool was completely renewed at each interation, then the chosen criterion had to be repeated until the number of individuals in the mating pool equals the population size. After, in the phase of offspring generation, for intelligent mutation it meant the selection of an operation on the machine with the maximum workload and the assignament of it to the machine with the minimum workload, if compatible. In conclusion their computational result showed that the integration of more strategies in a genetic framework could lead to better results as opposed to other genetic algorithms.

De Giovanni and Pezzella [DEGI09] developed an improved GA for makespan opti-mization in the distributed flexible job shop and where jobs are performed by a sys-tem of several Felxible Manufacturing Units. Compared to the solution representation for non-distributed job shop scheduling problem, gene encoding is extended to con-tain information on job-to-Flexible Manufacturing Units assignment, and a greedy de-coding procedure exploites flexibility and determines the job routings. In addition, to improve the available solutions is used a new local search based operator, which refines the most promising individuals of each generation.

Zhang et al. [ZHAN10] have designed an improved chromosome representation me-thod called “Machine selection and operation sequence” because of its two elements that represent it. In this way they try to find an efficent coding scheme of the individu-als which respects all constraints of the FJSP. For the the machine selection part,

(29)

there is an array of integer values and each integer equals the index of the array of alternative machine set of each operation. For the operation sequence part, all ape-rations for a job are defined with the same symbol and are interpreted according to the sequence of a given chromosome. The new coding scheme consists in interpre-ting each chromosome into a feasible active schedule. Furthermore, a new initial as-signment method which is composed by the global, local and random search, is de-signed to generate a high-quality initial population integrating different strategies to improve the convergence speed and the quality of final solutions.

Alcan and Basligil [ALCA11] dealt with the problem with non-identical parallel machi-nes (with different speeds), using fuzzy processing times. In this version of the prob-lem, triangular fuzzy processing times are used, in order to adapt the genetic algoritm to non-identical parallel machine scheduling problem (fuzzy numbers are sets of con-tinuous real numbers). Fuzzy systems are indeed excellent tools for representing heuristics and commonsense rules.

A modified GA given by Teekeng and Thammano [TEEK12], instead, consists in an effective selection method called “fuzzy roulette wheel selection”, a new crossover operator that uses a hierarchical clustering concept to cluster the population in each generation, and a new mutation operator that helps in mantaining population diversity and overcoming premature convergence. The first element consist in place two chromosomes next to each other with some degree of overlap in the roulette wheel. The similarity between two chromosomes consist to have the position and content identical to those of the other chromosomes. The second element permits to improve the quality of the solutions that can be developed as follows: once is created a prede-fined population size, the chromosomes of the mating pool are divided in two clusters with a hierarchical clustering algorithm. The last element performs the function of mantaining the diversity of the population and mantaining the diversity of it, to over-come premature convergence.

Driss et al. [DRIS15] have created a new chromosome representation called “permu-tation job”, that permits to find a new coding scheme of the individuals respecting all constraints of the flesxible job shop scheduling problem. This consists in using array of integers and each integer value equals the index of array of job correspondent. There are three components such as the operations for each job, the machine

(30)

assig-nement and the processing time. These components must be the same length. They have also developed different strategies for crossover and mutation operators.

2.3.2.2 Tabu Search

The tabu search is a technique that uses a local search to solve combinatorial opti-mization problems. This technique was proposed for the first time by Fred Glover in 1989. The problem as to be presented in this form [GLOV89]:

𝑀𝑖𝑚𝑖𝑧𝑒 𝑐 𝑋 : 𝑥 ∈ 𝑋 𝑖𝑛 𝑅_! (2.1)

In this procedure there is a sequence of moves that permits to swich to a trial soluti-on, selected x ∈ X, to another. A mapping defined on a subset X(s) ⊆ X could be cal-led move s. The set of all moves is calcal-led S. The set S(x) := {s ∈ S : x ∈ X(s)} re-presents those moves s ∈ S that can applied to x ∈ X. This one can represent a neighborhood function. There are two main elements that caracterize the tabu search technique. The first rule is that there are some moves that are forbidden (for this reason the name tabu) and secondly, the fact of freeing the search by a short term memory that permits “strategic forgetting". Accroding to Brandimarte [BRAN93], the tabu search is suitable with the flexible job shop scheduling problem because it can be used as a hierarchical algorithm, through its ability to deal with different memory levels (short, medium and long term memory). It can also adapted to different objec-tive funcions more easly than other techniques. Here below are presented examples that solve the problem minimizing the makespan.

In particular, Brandimarte [BRAN93] has developed a solution for the FJSP using for the first time a hierarchical approach, that means first solving the routing problem and secondly finding a schedule like a classic job shop scheduling problem. The use of tabu search heuristic allows use this kind of approach because this can be decompo-sed in two levels, through the different memory levels. In particular the long term memory deals with the routing selections and the short term memory deals with the classic job shop problem given a neighborhood strucutre. The medium term memory, instead, has the role to set some parametres of the tabu navigation algorithm and to monitor the search progress. To solve the classic job shop scheduling sub-problem Brandimarte proposes to adopt a local search approach too because is the fasted

(31)

method, even if any heuristic and exact alrogithm (for small instances) can be used. To solve the routing sub-problem two types of hierarchical architectures can be defi-ned. The one-way scheduler represents the fastest way to solve the routing problem because it uses dispatching rules. Otherwise, a balancing procedure can be used, which means that the operations are assigned to the machine to distribute the load and, hence, to avoid the creation of static bottleneck machines. The other structure is the two way scheduler, that consists in using the critical path concept to identify and cope with dynamic bottlenecks. In this approach it’s added a tabu navigation proce-dure for the long term memory, where the taboos are represented by forbidden ope-ration-machine pair. In this memory there is added tabu when a machine is chosen computing the effect of assigning each operation of the critical path on the alternative machines. This techique can be adapted also to minimize the total weighted tardi-ness, if the number of tardy jobs is limited.

An approach that uses more sofisticated neighborhood is adopted by Hurink et al. [HURI93]. They give two neighborhoods based on a theorem that describes how a solution of the problem can be improved. These two neighborhood are call connec-ted, that means it’s possible to reach form any feasible solution to an optimal solution in a finite number of steps. In addition, this approach considers a reassignament of operation in each step of the tabu search algorithm, while in Brandimarte metohd a reassignement is done after a predefined number of steps. They also use a concur-rent approach instead of a hierarchical approach used by Brandimarte. Therefore, routing and scheduling problems are solved together.

Another interesting application of tabu search algorithm on a flexible job shop scheduling problem is given by Mastrolilli and Gambardella [MAST99]. Their main contribution is a reduction of a set of possible neighbors to a subset for which can be proved that it always contains the neighbor with the lowest makespan. In this ap-proach only neighbors obtained by reinserting operations belonging to a critical path are considered. Otherwise, the neighbor would have a longest path in its solution graph, which is at least as long as the longest path in the solution graph of the cur-rent schedule. This can be explained by the fact that the longest path of the curcur-rent schedule remains present in the solution graph such a neighbor. Due to this structure the tabu search algorithm works faster and more efficiently.

(32)

2.3.2.3 Hybrid genetic and tabu search algorithm

In this section are illustrated two cases where genetic algorithm and tabu search are combined to find a better solution in a lower computation time.

Zhang et al. [ZHAN11] have developed a model combining genetic algorithm and tabu search. They deal with a flexible job shop scheduling problem with trasnportati-on ctrasnportati-onstraints and bounded processing times, in order to minimize the makespan. In this problem they solve the assignment problem with transportation through the ge-netic algorithm and they use tabu search to find and improve the sequence on each research during a limited number of iterations. In particular, in each generation, crossover and mutation operations create offspring that will compose the new popu-lation for the next generation. In order to mantain the convergence, the best individu-al found during the past generation is individu-always mantained in the population to replace the worst one in the new population.

Li and Gao [LIGA16] combine the powerful global searching ability of the genetic al-gorithm and the valuable local searching ability of tabu searh to minimize the makesoan. In this way, it’s possible to have an effective searching ability and to ba-lance the intensification and diversification very well. In this approach the tabu search algorithm is inserted into the procedure of the genetic algorithm in the step of local searching to improve the quality of every individual.

2.3.2.4 Particle swarm optimization

Particle swarm optimization, which was proposed by Kennedy and Eberhart [KENN95], is based on the imitation of a school of flying birds. As opposed to the ge-netic algorithm, which uses gege-netic operators, this method lets to evolve the individu-als through cooperation and competition among the individuindividu-als themselves by gene-rations. The feasible solution to the optimization problem is represented by each indi-vidual, that is named as a partical. Furthermore, the flying experience of each particle and its companions flying experience are used to adjust its flying. According to Shi and Eberhart [SHIE98], the features that can be associated to each particle are a point with coordinate in D-dimensional space, the best previous position of the partic-le respect to a predetined fitness function related to the probpartic-lem, and a velocity, that

(33)

pulation of particle is given by:

v_{i,d = vi,d + c1}R₁(p_{i,d − xi,d}) + c₂R₂(p_{g,d − xi,d) (2.2)}

x_{i,d = xi,d + vi,d}_(2.3)

for d = 1,..,D, where g is the index of the best particle in the population respect to the fitness function. Furthermore, R1 and R2 are two random functions with values in [0,1]

and c1 and c2 are two positive constants, that represent two learning factors. The

se-cond addend of the equation (V) represents the egoistic thinking of each individual flying towards the position of its own best experience. The third addend represents the companionable thinking of each individual flying towards the position of the group’s best experience.

An interesting application was developed by Liu et al. [LIUA09] to solve a multi-objective FJSP and it consists in a Multi Partice Swarm Optimization, a method that uses multi-swarm of particles, which searches for the operation order update and machine selection. With this approach, they try to solve some problems of the classic PSO. As a matter of fact, with the classical method, it’s possible to assist to the stag-nation or premature convergence which means that there is a faster convergence speed in the first part of the search, and then there is a slowdown or a stop when the number of generations increases. For this reason it’s difficul to achieve better fitness values. There are indtroduced multi-swarms of particles to map differnt odrers to the multi-objective FJSP, where some particles look for operation order update and others search for machine selection. Then, all the swarms look for the optima colla-borating with eachother and mamantaining the balance between diversity of particles and search space. The modification of the encoding representation and its related operator, so as to generate feasible solution and avoiding the use of repair mecha-nism, have permitted to reach a better efficiency of the search. The representation of the position and velocity of the particles in PSO are extended using a metrics Bi-nary encoding approach. Furthermore, the proposed algorithm converges with the probability of 1 towards the global optimum.

Moslehi and Mahnam [MOSL10] developed an approach based on a hybridization of the particle swarm optimization and local search algorithm to solve the multi-objective

(34)

flexible job shop scheduling problem. The multi-objective consists in minimize the makespan, the total workload of the machines (the total working time of all machi-nes), and the critiacal marchine workload. In particular, partical swarm optimization allows an extensive search of solution space, while the local search algorithm is used to reassign the machines to operations and to reschedule the results obtained from the first algorithm. The particle are composed by two parts, the machine assignement operations, and the sequence of the operations on each machine, that means the operations priority. As for the first part, the particle position corresponds to a machine assignement of all operations. Every bit of the particle position should be an integer but after being computed by the equations listed above, some bit can appear as real values so an approximation to the nearest integer should be done. For the second part, each element in the particle represents an operation and the corresponding va-lue of each element designates the priority of that operation. The partical swarm op-timization is used for this approach because the priorities are real numbers. In each iteration, the algorithm updates the particles based on their best value and then they are improved by the local earch algorithm.

A method which considers a real-world industrial environment was elaborated by Nouiri et al [NOUI16], where there could be unplanned events and unforseen in-cidents. In particular they take in consideration a flexible job shop under machine breakdowns (only one breakdown) in order to minimize the makespan. Their idea is to find a predictive schedule referred as pre-schedule that minimizes the effect of machine breakdowns in the overall performance through a two-stage particle swarm optimization algorithm. They use three approaches for the creation of the initial popu-lation, which are rhe random rule [Li et al. 2010], the localization approach [Kacem et al. 2002] and a modified new approach [Nouiri et al. 2013]. They want to integrate simultaneously the knowledge of the machine breakdown probability distribution a-long with the available flexible routing of machines. In this way, the predictive schedule is capable of assigning and sequencing operations on machines, such that a minimum impact is related to how much the distruptions will affect the quality of the solution. The first stage of the algorithm consists in optimizing the primary objective function (minimize the makespan) without distruptions and therefore, just with deter-ministic parameters. The second stage consists in improving the solutions conside-ring random machine breakdown.

(35)

2.3.2.5 Hybrid approaches

Ho and Tay [HOTA04] presented an efficient methodology called GENACE for sol-ving the flexible job shop scheduling problem with recirculation. Here, Composite Dispatching Rules are used to provide a bootstrapping mechanism to initialize GE-NACE. As a second step, they adopt a cultural evolutionary architecture to mantain knowledge of schermata and resource allocations learned over each generation. The computation time is reduced through avoiding the repair process, which is due to the fact that the results of crossover and mutation always mantain solution feasibility. However, they have assumed that all machines would be available at time 0 and all jobs could be processed at time 0, that in the real manufacturing environment is not always true because each job has a release date and due date so each machine may not be available at time 0.

An approach that mixes the particle swarm optimization with simulated annealing that aim to solve a multi-objective FJSP was elaborated by Xia and Wu [XIA05]. Simula-ted annealing is a local search algorithm that gives a certain probability to avoid becoming trapped in a local optimum and has been proved to be effective for a vari-ety of situations, including scheduling and sequencing. Firstly, it’s necessary to ex-plain how simulated annealing works. This methodology was developed by Kirk-patrick et al and it takes inspiration from the annealing process in metallurgy, wich consists in a gradual cooling of a metal to bring it to a optimal steady structure. The algorithm generates a set of configurations for each temperature with features that the energies of the different configurations can be represented by Boltzmann distribu-tion. Therefore an initial configuration is created with a certain amount of energy. Af-ter that, the algorithm generates small perturbations in order to create other configu-rations, and then it’s decided if accept them, by evaluating the difference between the current energy and the new configuration energy. In this hybrid method the particle swarm optimization creates the initial solution for simulated annealing, and each par-ticle’s fitness value is computed by SA algorithm. As a matter of fact simulated anne-alinf is only a syb-algorithm for the entire serach process. Finally, PSO uses the solu-tions evaluated by SA to continue evolution.

Ho, Tay and Lay [HOTA06] have developed an architecture for learning and evolving the schedules for the flexible job shop scheduling problem called Learneble Genetic

(36)

Archietecture (LEGA). With this architecture it’s possible to have an effective i-netegration between evolution and learning within a random search process. Here, the knowledge extracted from previous generation by its schermata learning module is used to influence the diversity and quality of offsprings, while with the canonical evolution algorithm, a random litist selection and mutational genetics are assumed. It’s also specified a population generator module that creates the initial population of schedules and also trains the schermata learning module. To incorporate a learning meachanism, a new chromosomal rappresentation is introduced. They have dis-cussed only the FJSP with the objective function of the minimum makespan.

Rossi and Dini [ROSS07] have developed a software system to solve a FJSP with sequence-depend setup and transportation time, which is based on an ant colony optimization. This algorithm is created with the idea that the shortest path could be found by connecting source and destination on a weighted graph that represents the optimization problem. This could be realized with an effective pheromone trail coding. Therefore, the Ant Colony Optimization imitates the ant behaviour, which consists in leave a substance, called pheromone, in the nest-food path, hence, the other ants can smell it and they can be driven in the food search. In particular, their problem is based on a real environment, including parallel machines and operation lag times. Here, the path generation is reached by the local search algorithm, that drives an ant to visit the weighted disjunctive graph model. In addition, to improve the performance when compared with other systems, the routing-precedence-based visibility funcion and the method to approximate non-delay schedules are introduced. This method can be effective to solve problems with a high variety of parts and products that me-ans an high number of sequence-dependent setup activities.

To solve a multi-objective FJSP that aims to minimize the maximal completion time (makespan), the workload of the critical machine and the total workload of machine simultaneously, Zhang et al. [ZHAN08] have developed an effective hynrid particle swarm optimization algorithm. It consists in using PSO to assign operation on the machines and to schedule operation on each machine, and Tabu Search to apply the local search for the scheduling sub-problem created by each obtained solution. More specifically, at first, each particle obtains updated information from its own swarm’s experiences and as a second step, the current particle is converted to a FJSP

(37)

scheduling solution for local search, using tabu search. After, the best solutions are used by PSO to continue the search until the termination condition is reached.

Rossi and Boschi [ROSS08] have developed a software system for solving the flexib-le manufacturing systems scheduling in a job shop environment with routing fflexib-lexibility and with identical parallel machines. They mix genetic algorithms and and colony optimization with a share data structures and co-evolving in parallel in order to im-prove the performance of the constituent algorithms. Infact, the co-operation mecha-nism is based on the parallel activity of the individual algorithms, where each of these performs the proper stochastic environment and there is a cosynchronization for each epoch. Moreover, an easy scalable parallel evolutionary-ant colony is obtained through a modular approach.

A knowledge-based ant colony optimization was proposed by Xing et al. [XING09]. This algorithm combines the ant colony optimization model with knowledge model which learns some available knowledge from the optimization of ant colony optimiza-tion, and then applies the existing knowledge to guide the current heuristic searching. In this approach the structure of the knowledge is composed by an elite solution knowledge, which represents a predefined numbers of best solution, the operation assignement machine knowledge, that is the accumulative knowledge of assigning the given operation to a more appropriate machine, the operation assignement priori-ty knowledge, which contains the accumulative knowledge of the more appropriate processing priority for the given opertion, and the parameters knowledges, that need to decrease the sensitivity of parametres to the optimization. Moreover, in the phase of the operation assignment, each ant will construct a feasible assignement based on the operation assignement machine knowledge, and in the phase of operation se-quencing, each ant will build a feasible schedule based on the operation assigne-ment priority knowledge. After, the algortithm exectues the schedule improving ope-ration, after each iteration based on the elite solution knowledge through the inter-learning operation. The latter recombines the component of two solutions and crea-tes new solutions, such that the resultant solutions inherit a set of building blocks form each former solution. In the last phase, that is called knowledge learning, the elite solution knowledge will be updated by the predefined numbers of best solution of every iteration.

(38)

A very simple approach that needs just two parameters was deveoped by Chiang and Lin [CHIA12], where their objective is to minimize the makespan, the total work-load and the maximum workwork-load. The goal is to seek for the Pareto optimal solutions. They use domain heuristcs adaptively to generate the initial population with high qua-lity and diversity and they balance the exploration by refining duplicate individuals using effective mutation operators. The population size and the maximum generation number are the only parameters that need to the algorithm. Even if it’s so simple, this algorithm it the only one that, compared with seven benchmark algorithms on fifteen probelm instances, is able to find at least 70% of the non-dominated solution for all instances.

An interesting application that takes in consideration the mantainance cost is given by Dalfard and Mohammadi [DALF12], where two meta-heuristic algorithms are used for solving multi-objective FJSP with parallel machines. In particular, they combine simulated annealing with an hybrid genetic algorithm, which differs slightly from the classic genetic algorithm for the way to generate the initial solution. Specifically, they use the hybrid genetic algorithm developed by Ashwanu and Pankaj to solve a flow shop scheduling with sequence dependent set time problem.

Nouri et al. [NOUR15] have built an hybrid metaheuristic within a holonic multiagent model in order to minimize the makespan in a flexible job shop environment. The therm “holon” is referred to the fact that something can be a whole and a part at the same time and hence, an holon can be viewed like an agent able to show an archi-tectural recursiveness. This method is composed by two general steps: the first cons-insts in exploring the search space using a genetic algorithm to find promising areas and in allowing to regroup them in a set of cluster by using a clustering operator. The second step consinsts in finding the best solution for each cluster using the tabu se-arch algorithm. This metodology is implemented in two hierse-archical holonic levels adopted by a recursive multiagent model. The first level is composed by a Scheduler Agent that prepares the best promising regions of the search space, and the second is composed by a set of Cluster Agents that guides the search to the global optimum solution of the problem. Therefore, the genetic algorithm is just used to explore the search space and to select the best promising regions by the clustering operator. The use of a multiagent system allows the presence of distributed and parallel treatments