Elena Perez web page: top image

HOME | RESEARCH | PROJECTS

 

 

 

JOB SHOP SCHEDULING PROBLEM

                                                                                                                                                                                                                                                               

 

Last update: 06/2011

 

 

The JOB SHOP SCHEDULING PROBLEM (JSSP) consists of scheduling the n jobs on m machines, where each one of the n job has its own movement within m machines and each of the m machine has its own sequence of n jobs, in order to optimize an objective function. The optimization function can define: termination times, delay times or total flow times, among others.

 

Multi-Modal Genetic Algorithms (MMGAs) are used to solve this problem because several global and local optima exist.

 

 

   BENCHMARKING INSTANCES

 

We have selected eight benchmarking instances of OR-:

 

 

    CODING (DECODING)

 

Coding the solutions is the most important decision you have to make when facing a JSSP. There are different possibilities to code the solution of a JSSP:

 

We focus on Permutational with repetition.

 

■ Direct

Bruns, R. (1993). Direct chromosome representation and advanced genetic operators for production scheduling. In Forrest, S. (Ed.). Proc. Of the 5th international conference on genetic algorithms (Pp. 352-359), Kaufmann. San Mateo.

Kobayashi, S.; Ono, I., Yamamura, M. (1995). An efficient genetic algorithm for the job shop scheduling problem. In Eschelman, L. (Ed.). Proceedings of the sixth international conference on genetic algorithms. (Pp 506-511) Kaufmann. San Francisco.

Binary

Nakano, R., Yamada, T. (1991). Convencional genetic algorithms for job shop problems. In Belew, R. and Booker, L. B. (Eds) Proc. of the 4� International conference on genetic algorithms. (Pp. 474-479). Kaufmann California. USA

Circular

Fang, H-L.,  Ross, P.,  Corne ,  D. (1993) A Promising Genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Problems. Proceedings of the Fifth International Conference on Genetic Algorithms, S. Forrest (ed.) San Mateo: Morgan Kaufmann, 375-382.

■ Permutational with repetition

Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin

 

 

    PARENTS SELECTION

 

During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where filter solutions (as measured by a fitness function) are typically more likely to be selected.

 

 

    REPRODUCTION: CROSSOVE OPERATOR

 

Crossover is used to vary the programming of a chromosome in the next generation population of solutions (children) which is generated from the selected population (parents) through genetic operators.

 

We focus on Order Crossover (OX) operator.

 

■ Generalized position crossover (GPX)

Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin

■ Position based crossover (PBX)

Syswerda, G. (1991). �A study of reproduction in generational and steady-state genetic algorithms�. Foundations of Genetic Algorithms 1. Rawlins G.(Ed). Kaufmann. San Mateo. Pag. 94-101.

(Originally it was developed for the TSP and used later for the Flow Shop Problem)

■ Generalized order crossover (GOX)

Bierwirth C., Mattfeld D. C., Kopfer H. (1996): On Permutation Representations for Scheduling Problems, in: Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, Hans-Paul Schwefel (eds.), Parallel Problem Solving from Nature IV, Springer publisher, 310-318

■ Order based crossover (OBX)

Syswerda, G. (1991). �A study of reproduction in generational and steady-state genetic algorithms�. Foundations of Genetic Algorithms 1. Rawlins G.(Ed). Kaufmann. San Mateo. Pag. 94-101.

■ Generalized uniform crossover (GUX)

Fang, H-L.,  Ross, P.,  Corne ,  D. (1993) A Promising Genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Problems. Proceedings of the Fifth International Conference on Genetic Algorithms, S. Forrest (ed.) San Mateo: Morgan Kaufmann, 375-382.

(It was developed  specially for circular coding for the JSSP)

Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin

(It was adapted to the permutational coding with repetition)

■ Cycle crossover (CX).

Goldberg, D.E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley. Massachusetts

(It was developed  for TSP. However the adaptation to permutational coding with repetition is essay)

■ Order Crossover (OX) operator

Davis, L. (1989). �Adapting operator probabilities in genetic algorithms�. Proceedings of the third international conference on Genetic Algorithms. J. David Schaffer (Ed.). Kaufmann. San Mateo. Pag. 375-378

(It was developed for TSP. However the adaptation to permutational coding with repetition is essay)

 

 

    REPRODUCTION: MUTATION OPERATOR

 

Mutation is used to maintain genetic diversity in the next generation population of solutions (children) which is generated from the selected population (parents) through genetic operators.

 

We focus on Order Based Mutation (OBM)

 

■ Order Based Mutation (OBM)
Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin
Position based mutation (PBM)
Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin
Swap based mutation (SBM)
Mattfeld, D.C. (1995). Evolutionary search and the job shop. Investigations on genetic algorithms for production scheduling. Springer. Berlin
Scramble sublist mutation (SSM)

Davis, L. (Ed.) (1991). Handbook of genetic algorithms. Van Nostrand. NY. USA  Review

(Originally it was developed for the TSP although it can be easily adapted for the JSSP)

 

 

    REPLACEMENT

 

The offspring population is included in the population for the next generation (iteration). Different proposals can be found in the literature, for instance, elitism.

 

More information: Goldberg, D.E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley. Massachusetts

 

 

    SOLUTIONS

 

We focus on minimization the termination times. The number of different global optima known to date for each instances is:

 

  instances
 

la01

la02

la03

la04

la05

mt06

mt10

mt20

optima

26813

5321

706

143

48471

42

4

1

 

More information about these optima click here.

 

 

   REFERENCES

 

Finding multiple solutions in job shop scheduling by niching genetic algorithms

P�rez, E.; Herrera, F. ; Hern�ndez, C. (2003). JOURNAL OF INTELLIGENT MANUFACTURING 14, 323 � 339 

 

Analysis of new niching genetic algorithms for finding multiple solutions in the Job Shop scheduling

P�rez, E.; Posada, M.; Herrera, F. (2010). JOURNAL OF INTELLIGENT MANUFACTURING

   

Universidad de Valladolid. Webmaster Marta Posada