Int J Adv Manuf Technol (2006) 28: 129–136 DOI 10.1007/s00170-004-2345-7

ORIGINAL ARTICLE

Suk Jae Jeong · Seok Jin Lim · Kyung Sup Kim

Hybrid approach to production scheduling using genetic algorithm and simulation

Received: 14 April 2004 / Accepted: 14 July 2004 / Published online: 30 March 2005 © Springer-Verlag London Limited 2005 Abstract In the production scheduling problem, due to various kinds of uncertain factors such as queuing, breakdowns and repairing time of machines, the optimal solution considering the stochastic behaviour of a real operation cannot be easily solved. To solve the problem, we present a hybrid approach with a genetic algorithm (GA) and a simulation. The GA is used for optimization of schedules, and the simulation is used to minimize the maximum completion time for the last job with fixed schedules from the GA model. We obtain more realistic production schedules with an optimal completion time reflecting stochastic characteristics by performing the iterative hybrid GA – simulation procedure. It has been shown that the hybrid approach is powerful for complex production scheduling. Keywords Genetic algorithm · Hybrid approach · Production scheduling · Simulation

1 Introduction Scheduling problems, such as flow, job and open shop problems, are widely used in the modelling of industrial production processes and are receiving an increasing amount of attention from researchers. Among them, the production scheduling problem is given a set of jobs and a set of machines. Each machine can handle, at most, one job at a time. Each job consists of a chain of operations, each of which needs to be processed during an uninterrupted time period of a given length on a given machine. This problem is among the hardest combined optimization problems. In fact, the optimal solution is not necessarily needed in many practical situations, because the computation time for an optimal solution are usually so large that one can hardly afS.J. Jeong (u) · S.J. Lim · K.S. Kim Department of Industrial Systems Engineering, Yonsei University, 134, Sinchon, Seodaemun, Seoul, South Korea E-mail: [email protected] Tel.: +82-2-21232724 Fax: +82-2-3647807

ford it, and a good suboptimal solution can be well accepted. Since the early 1980s, much interest has been devoted to the development and application of the meta-heuristic algorithms. Among the meta-heuristic algorithms, genetic algorithms (GA) has been recognized as a general search strategy and an optimization method which is often useful for finding combined problems and has been used with increasing frequency to address scheduling problems. However, to implement production scheduling in the real world, it should be modelled by a stochastic method. Most realistic problems are not simple enough to apply the GA. Operations of each job can produce a wide variety of dynamic behaviours, such as in queuing, breakdown time and repair time. To solve this problem, the concept of the hybrid method is applied, combining independently developed GA and a simulation model of the system. The GA model is set up for deciding optimal schedules to minimize makespan time, the maximum completion time of the last job. The simulation model is used for finding the simulation runtime of the fixed schedules from the GA model. During the past decade, research on stochastic search methods to solve production scheduling have been widely conducted, such as simulated annealing, tabu search and GA. Among them, the GA has been used with increasing frequency to address scheduling problems. Bierwirth [1] and Syswerda [2] proposed a new chromosome representation to job shop scheduling. Dorndorf and Pesch [3] and Yamada and Nakano [4] used some variations on standard genetic operators and the hybridization of some existing job shop algorithms. Dorndorf and Pesch [5] proposed a machine-based encoding for the job-shop problem and developed a hybrid version of the GA. Additionally, Sakawa and Mori [6] put forward a GA for job-shop scheduling with a fuzzy processing time and fuzzy due date. Ghedjati [7] used a GA to solve job-shop scheduling with unrelated parallel machine and precedence constraints. Haibin and Wei [11] put forward the combining of the neural network and GA for sequence optimization to expanded job-shop scheduling. Yun [12] proposed the hybrid GA with a fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems.

130

To date there exists little research that addresses the hybrid approach, though Shanthikumar and Sarent [8] discussed comparative advantages and disadvantages of analytic versus simulation models, giving a unifying definition for both hybrid approaches and modelling. Byrne and Bakir [9] studied a hybrid approach for a manufacturing system. Also, Lee and Kim [10] proposed the more realistic solution procedure through hybrid approaches. This paper is organized as follows. In Sect. 2, the production scheduling problem is described. The GA, the heuristic method for representing various constraints and solving the completion time of jobs, is introduced in Sect. 3. Simulation with fixed schedules, considering stochastic characteristics, is modelled in Sect. 4. The hybrid approach based GA and simulation is presented in Sect. 5. Experiments, concluding remarks and further research are presented in Sect. 6 and Sect. 7.

Nq Set of operations requiring machine q, q ∈ [1, 2, . . ., m] H Arbitrary positive large number til Processing time of operations l of job i, l ∈ [1, 2, . . ., n i ] xik Starting time of operations k of job i, k ∈ [1, 2, . . ., n i ] x[i Starting time of the first operations of job i xi] Completion time of the last operations of job i di Delivery due date of job i i, k The kth operation of job i, also called operation k in short if no confusion is caused
1, if operation k precedes operation l ykl = 0, otherwise where {k, l} ∈ Q i , i = 1, 2, . . . , n
1, if operation i precedes operation j z ij = 0, otherwise where {i, j} ∈ Nq , q = 1, 2, . . . , m.

2 Production scheduling problem Generally, production scheduling is a deterministic and static scheduling problem. There are m distinct machines to process n jobs that have their specific processing routines. Each job’s operation has its precedence and takes up a deterministic time period at a specific machine. At any time, there is only one operation at a machine and the job does not leave this machine until the operation is completed. Also, the operation starting time of each job must be within predefined regions, which are subject to the available time and due dates of jobs. The objective is to find the optimal scheduling, i.e. the schedule of the operation schedules and the minimal makespan. The production scheduling problem is represented in Fig. 1. 2.1 Notations The symbols for modelling production scheduling problems are as follows: Index of jobs (n = 1, 2, . . . , N) Index of machines (m = 1, 2, . . . , M) Number of operations of job i Set of pairs of operation {k, l} belonging to job i, where operation k precedes operation i Q i Set of pairs of operation {k, l} belonging to job i, for any operation k and operation i

n m ni Ri

Fig. 1. Production scheduling problem

2.2 Modelling and analysis for production scheduling Min Z = max(xi] + ti] ) i

s.t xil − xik − tik ≥ 0, ∀i, if {k, l} ∈ Ri

(1)

x jl − xik − tik + H(1 − z kl ) ≥ 0 , ∀q, if {k, l} ∈ Nq

(2)

xik − x jl − t jl + Hz kl ≥ 0, ∀q, i f {k, l} ∈ Nq

(3)

xil − xik − tik + H(1 − ykl ) ≥ 0, ∀i, i f {k, l} ∈ Q i

(4)

xik − xil − til + Hykl ≥ 0, ∀i, if {k, l} ∈ Q i

(5)

di − ti] − xi] ≥ 0 , ∀i

(6)

Our objective is to minimize the completion time of the last completed job. A feasible solution means that the scheduling satisfies all constraints. Our modelling has two types of major constraints for any operation, precedence and machine. Constraint Eq. 1 indicates a precedence constraint. It is indicated that some jobs must be processed at different machines in fixed precedence sequence. Concretely, the ith operation of job i must be before the kth operation of the same job, if {k, l} ∈ Ri . Constraints Eqs. 2 and 3 represent machine constraints. These mean that any machine can only provide service for one operation at a time. That is to say, machine q can only select one job to process among jobs waiting to be processed in the queue

131

at any time. Also, Eqs. 2 and 3 show that the operation k and l requiring the same machine q should not be processed at the same time. Constraints Eqs. 4 and 5 represent job constraints. Although there may be no precedence constraint among some operations of the job, the constraint that the operations l and k could not be processed at the same time still exists because these two operations were done at the same job. Constraint Eq. 6 shows the completion time constraint. The completion time of any job is restricted by the job available time and the due date of delivery.

3 Genetic algorithm As opposed to many other optimization methods, the GA works with a population of solutions instead of just a single solution. The GA assigns a value to each individual in the population according to a problem-specific objective function. A survivalof-the-fittest step selects individuals from the old population. A reproduction step applies operators such as crossover or mutation to these individuals to produce a new population that is fitter than the previous one. In applying the GA, we have to analyze specific properties of problems and decide on a proper representation, an objective function, a genetic operator and a genetic parameter. 3.1 Representation In solving the production scheduling problem by GA, the first task is to represent the solution of a problem as a chromosome. We utilize an operation-based representation that encodes a schedule as a sequence of operations and each gene stands for one operation. One natural way to name each operation is using a natural number, like the permutation representation for Fig. 2. Representation based operation

Fig. 3. Order crossover operation

Fig. 4. Swap mutation operator

the traveling salesman problem (TSP). For an n job and m machine problem, a chromosome contains n × m genes. It is easy to see that any permutation of the chromosome always yields a feasible schedule. Representation of a chromosome is shown in Fig. 2. 3.2 Crossover The crossover is considered to be the main process for exploration in a GA. The crossover is done by exchanging the information of two parents to provide a powerful exploration capability. We utilize the order crossover (OX). OX selects a substring randomly from one parent, finds their place in the other parent, and copies the remaining items into the second parent in the same order as they appear in the first parent. The substring from the parent is randomly selected. The OX process is shown in Fig. 3. 3.3 Mutation A Swap mutation operator is used in this paper, which simply selects two positions at random and swaps their contents as shown in Fig. 4. The number of swapping performed depends on the increase and decrease of the mutation rate setting. 3.4 Selection When a new organism is to be created, two parents are chosen from the current population. Organisms that have high fitness values are more likely to be chosen as parents. In this paper, parents are chosen with a rank-based mechanism. Instead of some genetic algorithm systems, where a parent’s chance to be selected for reproduction is directly proportional to its fitness, a ranking approach offers a smoother selection probability curve. This prevents good organisms from completely dominating the evolution from an early point.

132

3.5 Objective functions In this paper, the makespan represents a good performance measure. The schedules with the minimal makespan often imply little idle time of machines. The makespan objective is selected for comparison of the performance of the schedules in this paper. When a chromosome is represented as a permutation type, the makespan is produced by the process that assigns operations to the machines by the sequence of each job, scanning the permutation from left to right.

4 Simulation modelling reflecting stochastic characteristics In many research efforts, the operation time of each job is known and fixed in the production scheduling. However in real world systems, operation time cannot be considered as one of the static factors, because the consumed time to process the operation in general is a dynamic characteristic. The GA model of production scheduling with a fixed operation time cannot describe systems in reality. Therefore, the simulation model for our study accommodates the characteristics of dynamic production scheduling, such as machine breakdown and repair, queuing and delays. For random machines, we suppose that mean times between failures for each machine follow exponential distributions with a mean of 500 hr, and mean times to repair follow exponential distribution with a mean of 2 hr for each machine respectively. The simulation model for this paper is coded by ARENA 5.0.

5 A hybrid GA-simulation approach A hybrid approach involving the GA and simulation is presented in this paper to solve the production scheduling problem. The GA is used for optimization of schedules and the simulation

Fig. 5. The hybrid solution procedure

is used to minimize the maximum completion time of the last job reflecting the stochastic characteristics with a fixed schedule based GA model. The hybrid procedure of production scheduling is illustrated in Fig. 5. The completion time is defined as the simulation runtime in the simulation model, which is the overall simulation time spent in the system to process all operations based on the production schedules of the GA. Therefore, operation time in the GA model is adjusted by the results of the simulation, and the GA model regenerates new operation schedules by the adjusted operation time. The iteration stops when the different rate between preceding simulation time and the current simulation time is close enough to be acceptable. The procedure of the hybrid GA – simulation approach consists of the following steps: Step 1 Solve genetic algorithm based on the objective function and generate production schedules. Step 2 Run a simulation model based on the generated production schedules from the GA. Step 3 Obtain feasible simulation completion time. Step 4 Decide on the appropriate result, which yields the required values. Step 5 Change constraints in the GA using current simulation completion time and go to step 1. Step 6 Determine the production scheduling which is considered to be the realistically optimal solution.

6 Experiments Experiments have been provided in order to demonstrate the effectiveness and viability of the proposed hybrid approach. We implemented examples of different sizes 5 × 5, 10 × 5, 10 × 7 using a GA tool based on Microsoft Excel, Evolver, and a simulation tool based C++ language, Arena. The parameters for the GA are presented in Table 1.

133 Table 1. GA parameters of each example

GA parameters

Values

Population size Number of generations Crossover probability Mutation probability

30 50 0.5 0.06

Table 3 and Fig. 6. The makespan time of the optimal schedules is 369 sec. However, this result does not reflect dynamic situations such as random breakdowns or repair times. The scheduling results of the 10 × 5 and 10 × 7 problems are represented in Figs. 7–8. Table 4 and Fig. 9 show that the makespan time based GA is represented in the hybrid GA and simulation procedures. It is noted that although the makespan time is fluctuated, the width of fluctuations are steadily decreased as iteration is increased. The results derived by the proposed hybrid approach in the case of simulated random failures and repair times are displayed

We begin with the GA procedure based on the proposed production scheduling model without stochastic characteristics. For the 5 × 5 problem, operations, job ID, machines and the processing time of each operation are given in Table 2. The optimal schedules based on the GA for the problem is represented in

Fig. 6. Gannt chart for the optimal schedules (5 × 5 problem)

Table 2. Initial values (5 × 5 problem) Operations Job ID/ machines

Job ID

Machines

Processing time(hr)

Operations

Job ID/ machines

Job ID

Machines

Processing time(hr)

1 2 3 4 5 6 7 8 9 10 11 12 13

1 1 1 1 1 2 2 2 2 2 3 3 3

1 2 3 4 5 1 2 3 4 5 1 2 3

12 86 66 95 90 77 30 53 99 68 7 52 16

14 15 16 17 18 19 20 21 22 23 24 25 -

34 35 41 42 43 44 45 51 52 53 54 55 -

3 3 4 4 4 4 4 5 5 5 5 5 -

4 5 1 2 3 4 5 1 2 3 4 5 -

13 35 81 18 14 94 3 41 11 88 55 42 -

11 12 13 14 15 21 22 23 24 25 31 32 33

Table 3. GA modified/Optimal schedules (5 × 5 problem) Operations Job ID/ machines

Job ID

Machines

Processing time (hr)

Operations

Job ID/ machines

Job ID

Machines

Processing time (hr)

3 1 24 9 10 12 11 23 22 25 7 21

1 1 5 2 2 3 3 5 5 5 2 5

3 1 4 4 5 2 1 3 2 5 2 1

66 12 55 99 68 52 7 88 11 42 30 41

2 5 20 8 16 13 6 15 19 4 18 -

12 15 45 23 41 33 21 35 44 14 43 -

1 1 4 2 4 3 2 3 4 1 4 -

2 5 5 3 1 3 1 5 4 4 3 -

86 90 3 53 81 16 77 35 94 95 14 -

13 11 54 24 25 32 31 53 52 55 22 51

134 Fig. 7. Gannt chart for the optimal schedules (10 × 5 problem)

Fig. 8. Gannt chart for the optimal schedules (10 × 7 problem)

Table 4. Experimental results for the makespan time Iteration numbers Makespan time 5×5

10 × 5

10 × 7

Iteration numbers Makespan time 5×5

10 × 5

10 × 7

1 2 3 4 5 6 7 8 9 10

1537 695 706 740 672 667 622 654 625 616

1720 826 807 725 812 810 756 794 747 752

11 12 13 14 15 16 17 18 19 20

619 618 612 578 582 581 570 570 570 570

747 747 725 725 728 725 710 707 707 707

701 410 435 446 431 431 470 449 469 429

427 412 432 444 369 378 433 379 378 -

Table 5. Experimental results from the proposed hybrid approach Iteration number

Simulation runtime 5×5

10 × 5

10 × 7

Difference rate 5×5

10 × 5

10 × 7

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

736 626 548 598 543 583 517 567 523 478 517 470 496 457 487 451 434 432 427 441 420

2004 940 950 1048 855 891 740 826 763 776 809 792 789 774 754 742 740 721 754 743 729

2364 1235 972 1106 984 1174 991 1038 1086 1202 1100 1238 1074 1016 1131 1013 1039 1070 957 963 956

0.176 0.142 0.084 0.101 0.069 0.128 0.088 0.084 0.094 0.075 0.100 0.052 0.085 0.062 0.080 0.039 0.005 0.012 0.032 0.050

1.132 0.011 0.094 0.226 0.040 0.204 0.104 0.083 0.017 0.041 0.021 0.004 0.019 0.027 0.016 0.003 0.026 0.044 0.015 0.019

0.914 0.271 0.121 0.124 0.162 0.185 0.045 0.044 0.097 0.093 0.111 0.153 0.057 0.102 0.116 0.025 0.029 0.118 0.006 0.007

135 Fig. 9. Makespan time for each problem in case of GA

Fig. 10. Simulation runtime for each problem in case of simulation

Fig. 11. Difference rates in simulation runtimes for each problem

in Table 5 and plotted in Fig. 10. In Fig. 10, we indicate that the completion time of the simulation for a number of iterations fluctuates. Although we could not guarantee convergence in general, our procedure resulted in convergence of the expected rate with

a reasonable number of iterations. The difference rate is less than 0.03, that is the stop condition in this paper after iteration 18 for all examples, and we accept the real production schedules with completion time of the iteration 18.

136

7 Concluding remarks and further research A hybrid approach involving a genetic algorithm and simulation is presented in this paper. The GA is used for optimization of schedules and the simulation is used to minimize the makespan that maximizes completion time for the last job with fixed schedules. The production scheduling based on the GA solutions could not be accepted in a real world system having stochastic characteristics. The simulation model accommodates the characteristics of dynamic production scheduling. Through experiments of examples of the proposed hybrid approach, the experimental results indicate that the adjusted operation time of systems significantly affects production scheduling. Therefore, we obtain more realistic production schedules, with optimal completion time reflecting stochastic characteristics, by performing the iterative hybrid GA – simulation procedure. This hybrid approach may be considered as a guideline for the tactical production scheduling problem reflecting stochastic characteristics.

References 1. Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spektrum 17(213):87–92

2. Syswerda G (1991) Schedule optimization using genetic algorithms. In: Davis L (ed) Handbook of genetic algorithms. Van Nostrand Reinhold, New York, pp 332–449 3. Dorndorf U, Pesch E (1993) Combing genetic and local search for solving the job shop scheduling problem. APMOD93 Proc, pp 142–149 4. Yamada T, Nakano R (1992) A genetic algorithm applicable to largescale job shop problems, vol 2. Parallel problem solving from nature. North Holland Publishers, Amsterdam, pp 281–290 5. Dorndorf U, Pesch E (1995) Evolution based learning in a job shop scheduling environment. Comput Oper Res 22(1):25–40 6. Sakawa M, Mori T (1999) An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy due date. Comput Ind Eng 36(2):325–341 7. Ghedjati F (1999) Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: heuristic mixing method machines and precedence. Comput Ind Eng 37(1-2):39–42 8. Haibin Y, Wei L (2001) Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling. Comput Ind Eng 39:337–356 9. Yun YS (2002) Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems. Comput Ind Eng 43:623–644 10. Shanthikumar JG, Sargent RG (1983) A unifying view of hybrid simulation/analytic models and modelling. Oper Res 31(6): 1030–1052 11. Byrne MD, Bakir MA (1999) Production planning using a hybrid simulation-analytical approach. Int J Prod Eco 59:305–311 12. Lee YH, Kim SH (2002) Production-distribution planning in supply chain considering capacity constraints. Comput Ind Eng 43: 169–190