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