Job-shop scheduling with genetic algorithms.

Lestan, Zoran ; Brezocnik, Miran ; Brezovnik, Simon 等

1. INTRODUCTION

In the job-shop problem a set of jobs must be processed on a set of machines. Each job consists of a sequence of operations, where each operation must be processed on a predefined machine for an exact time (Buchmeister, 2008). All operations of a job must be processed one after another in the given order. The machine can process only one operation at a time. The objective is to minimize the makespan, i.e., the maximum of job completion times.

Because the job-shop scheduling problem is a very difficult NP problem, it has captured the interest of a significant number of scientists. A lot of algorithms have been proposed for solving it (Brucker, 2007). The algorithms which base on the method branch and bound are useful only for solving small instances. Instances with a larger number of operations cannot be solved in a reasonable time (Brucker & Knust, 2006). For large scale problems approximation algorithms are used: shifting bottleneck, genetic algorithm, simulated annealing, tabo search, priority dispatch, etc. (Polajnar, 2005). Although it is not possible to solve even modest sized instances to optimality, a number of important algorithmic advances have been made in the past few years (Mitsuo & Runwei, 1997), (Pinedo, 2005). The latest studies indicate that the best results are obtained with the use of hybrid methods involving genetic algorithms, tabo search, simulated annealing and the shifting bottleneck approach (Zhang et at., 2006).

2. GENETIC ALGORITHM FOR JOB-SHOP SCHEDULING

The researchers studied two important issues over the past decade. The first one is how to encode the solution of the problem into a chromosome to ensure a feasible solution. The other issue is how to enhance performance of genetic algorithms by incorporating traditional heuristic methods.

In this paper a genetic algorithm is used to treat the job-shop problem. This algorithm was developed independently, without regard for the work of other researchers. The intention was to make a simple algorithm which will try to find the schedule with the smallest makespan. Only genetic operations are used in order to achieve this (Mernik & Crepinsek, 2003). It is possible to schedule a various number of jobs, but neither release times nor due dates are considered. The algorithm uses random moves to search for the optimal schedule in the solution space.

The solution is encoded in form of a string which consists of operations of all the jobs of the instance. Table 1 shows an example of a 3x3 instance; 3 jobs (9 operations) must be scheduled on 3 machines (M1, M2, M3) to achieve the smallest possible makespan.

From the Table 1 it is possible to write the operation sequence for each job:

J1 (J1 M1 29) (J1 M2 78) (J1 M3 9)

J2 (J2 M1 43) (J2 M3 90) (J2 M2 28)

J3 (J3 M2 91) (J3 M1 85) (J3 M3 74)

Job J1 must first be processed on machine M1 for 29 time units. After that on machine M2 for 78 units and the last is machine M3 for 9 units. Similar goes for the other two jobs.

The schedule for this instance is encoded into a string, where the position of the operation in the string (chromosome) plays an important role. A possible encoded solution could look like this:

((J2M1 43) (J1 M1 29) (J1 M2 78) (J3 M2 91) (J2 M3 90) (J3 M1 85) (J2 M2 28) (J1 M3 9) (J3 M3 74))

It is very important that the encoding process gives a feasible solution (Runwei & Mitsuo, 1996). The solution is feasible if all the operations of the jobs are included in the chromosome and if the processing orders of individual jobs stays intact. Why this is so important is explained in the next lines.

The evaluation of the solution is done with the help of a Gantt chart. The operations are added to the Gantt chart one after another directly from the chromosome, starting with the first operation in the chromosome. The operations which are at the beginning of the string have a higher processing priority than those at the end. The Gantt chart for the solution above is shown on Figure 1.

Because this particular evaluation method it is crucial that the processing order of the jobs does not change. If this is not taken into account, the evaluation of the chromosome would be false. Because the processing order of individual operations is determined with its position in the chromosome, it is possible to change the schedule just by changing the position of an operation in the string. These modifications of the chromosomes are known as genetic operations.

[FIGURE 1 OMITTED]

In this algorithm only two genetic operations are used; the tournament selection and the permutation. The only thing that has to be considered when changing the chromosome is the processing order of individual jobs. The permutation procedure which is used in this algorithm moves one operation to another place in the chromosome at a time. The space in which the operation is free to move is limited. The operation of a job cannot be moved over another operation of the same job, because this would change the processing order of the job. The following example shows how a permutation is done:

Before the permutation:

((J2M1 43) (J1 Ml 29) (J1 M2 78) (J3 M2 91) (J2 M3 90) (J3 M1 85) (J2 M2 28) (J1 M3 9) (J3 M3 74))

After the permutation:

((J1 M1 29) (J1 M2 78) (J2 M1 43) (J3 M2 91) (J2 M3 90) (J3 M1 85) (J2 M2 28) (J1 M3 9) (J3 M3 74))

1. A random operation from the chromosome is chosen. In our case let this operation be (J2 M1 43).

2. The left and the right limit of the space in which the operation can be moved are determined. In this example the left limit is the beginning of the chromosome and the right limit is the operation (J2 M3 90).

3. The chosen operation is placed on a random place in the limited space.

This example shows only one move of an operation in the context of the permutation. For a more extensive change of the chromosome several permutations are executed one after another (Brezocnik, 2000).

3. RESULTS

The algorithm was written in the LISP (Brezocnik, 2005) programming language. It was tested on the notorious 10x10 and 20x5 instances which were proposed by Fisher in Thompson (Blazewicz 2007). The results and evolution parameters are shown in table 2. The search was in both cases executed with the same evolution parameters.

As it can be seen from Table 2, the algorithm did not manage to find the optimal solution for the problem, but due its simplicity, the algorithm was able to obtain good solutions.

4. CONCLUSION

It is obvious that job-shop scheduling plays an important role in the modern industry. The demanding market forces manufacturers to implement fast changes in their manufacturing space. These can be achieved only with the presence of a fast and powerful scheduler. Job-shop scheduling presents a hard combinatorial problem which is not easy to solve optimal. One of the methods for solving this stubborn problem is the genetic algorithm. Of course the performance of the algorithm depends on its design, which is linked with the experience and knowledge of the author. The truth is that not every evolution is a good evolution.

In this paper is shown that even a relatively simple evolution algorithm is capable of finding good solutions for the job-shop problem. Because the genetic algorithms are not well suited for fine-tuning of solutions around optima the next step for this algorithm would be an upgrade to a hybrid algorithm. Combining this algorithm with a heuristic method would increase searching speed and improve the quality of final results. In further researches we will try to upgrade the algorithm with the local search algorithm.

5. REFERENCES

Blazewicz, J., K. H. Ecker, E. Pesch, G. Schmidt, J. Weglarz: Handbook on sheduling, Springer-Verlag Berlin Heidelberg, 2007

Brezocnik, M.: The use of genetic programming in intelligent manufacturing systems (Uporaba genetskega programiranja v inteligentnih proizvodnih sistemih), Faculty of mechanical engineering, University in Maribor, 2000 (Fakulteta za strojnistvo, Univerza v Mariboru, 2000)

Brezocnik, M.: Guide for the use of the autolisp tool in the AutoCAD environment (Prirocnik za uporabo orodja autolisp v okolju AutoCAD), Faculty of mechanical engineering, University in Maribor, 2005 (Fakulteta za strojnistvo, Univerza v Mariboru, 2005)

Brucker, P., S. Knust: Complex scheduling, Springer-Verlag Berlin Heidelberg, 2006

Brucker, P.: Scheduling algorithms: Fifth edition, SpringerVerlag Berlin Heidelberg, 2007

Buchmeister, B., I. Palcic, J. Pavlinjek, INOKS d.o.o., Murska Sobota, University in Maribor Faculty of mechanical engineering (Univerza v Mariboru, Fakulteta za strojnistvo): Unconventional methods for job-shop scheduling (Nekonvencionalne metode terminiranja proizvodnih procesov): Toolmaking 2008. Organizationt as driver for business improvements: consultation review, Portoroz, 7.--9. October 2008 (Orodjarstvo 2008. Organizacija kot gonilo poslovnih izboljsav : zbornik posvetovanja, Portoroz, 7. do 9. oktober 2008.)

Mernik, M. Crepinsek, V. Zumer: Evolutionary algorithms (Evolucijski algoritmi), Faculty of electrical engineering, computer and information, Institute for computer science, University in Maribor 2003, (Fakulteta za elektrotehniko, racunalnistvo in informatiko, Institut za racunalnistvo, Univerza v Mariboru, 2003)

Mitsuo G., Runwei Cheng: Genetic Algorithms and engineering design, John Wiley & Sons, Inc, New York, 1997

Pinedo, M. L.: Planning and scheduling in manufacturing and services, Springer Science+Business Media, New York, 2005

Polajnar, A., B. Buchmeister, M. Leber, K. Pandza, N. Vujica-Herzog, I. Palcic, T. Fulder: Management of manufacturing systems--modern approaches (Menedzment proizvodnih sistemov--sodobni pristopi), Faculty of mechanical engineering, University in Maribor, 2004 (Fakulteta za strojnistvo, Univerza v Mariboru, 2004)

Runwei, C., Mitsuo, G., Yasuhiro, T., A tutorial survey of job-shop scheduling problems using genetic algorithms--I. representation, Computers ind. Engng, Vol. 30, No. 4, pp. 983-997, 1996

Zhang, C., PeiGen Li, YunQing Rao, ZaiLin Guan: A very fast TS/SA algorithm for the job shop scheduling problem, School of Mechanical Science & Engineering, Huazhong University of Science & Technology, Wuhan, 2006

Tab. 1. 3x3 instance

JOBS PROCESSING PROCESSING ORDER
 TIMES

 operations operations

 1 2 3 1 2 3
J1 29 78 9 machine machine machine
 M1 M2 M3
J2 43 90 28 machine machine machine
 M1 M3 M2
J3 91 85 74 machine machine machine
 M2 M1 M3

Tab 2. Results for the 10x10 and 20x5 instances

 10x10 20x5

population size 200 200
number of generations 500 500
number of independent 100 100
civilizations
optimal solution 935 1165
best solution obtained 941 1211