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.

    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:

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