IDSIA - Istituto Dalle Molle di Studi sull'Intelligenza Artificiale Monaldo Mastrolilli

Flexible Job Shop Problem

Contents :   The problem



 Problem instances and computational study

The problem

The Flexible Job Shop Problem (FJSP) is an extension of the classical job shop scheduling problem which allows an operation to be processed by any machine from a given set. The problem is to assign each operation to a machine and to order the operations on the machines, such that the maximal completion time (makespan) of all operations is minimized.


There is a great variety of real-world problems that can be modelled as a FJSP. They occur, e.g., in

Some References

This is a selective list of references concerning the FJSP. If you miss your favourite reference or if you know any reference that should be in the list please send me an e-mail ( ). I will complete the list.
  1. Kacem, I., Hammadi, S., Borne, P., 2002 . Pareto-optimality Approach for Flexible Job-shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic. Journal of Mathematics and Computers in Simulation,  Elsevier.
  2. Kacem, I., Hammadi, S., Borne, P., 2002. Lower bounds for evaluating schedule performances in flexible job shops. Performance Metrics for Intelligent Systems Workshop, PerMIS'02, Gaithersburg, MD, 2002. USA.
  3. Kacem, I., Hammadi, S., Borne, P., 2002. Approach by Localization and Multi-objective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems. IEEE Transactions on Systems, Man, and Cybernetics. Part C, 2002, Vol 32. N1, pp 1-13.
  4. Jansen K., Mastrolilli M., Solis-Oba R., (1999) "Approximation Algorithms for Flexible Job Shop Problems", Proceedings of Latin American Theoretical Informatics (LATIN'2000), LNCS 1776, pp. 68-77. ( gzipped ps-file )
  5. Mastrolilli M., Gambardella L.M. , (1998) "Effective Neighborhood Functions for the Flexible Job Shop Problem", Journal of Scheduling, Volume 3, Issue 1, 2000. Pages: 3-20. ( pdf-file )
  6. Brucker, P., Neyer, J., (1998): "Tabu-search for the multi-mode job-shop problem'' , OR Spektrum 20, 21-28.
  7. Dauzere-Peres S., Roux J., Lasserre J.B., (1998): "Multi-resource shop scheduling with resource flexibility'', European Journal of Operational Research 107, 289-305.
  8. Balas, E., Vazacopoulos, A., (1998): "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling'', Management Science 44, 262-275.
  9. Dauzere-Peres S., Paulli, J., (1997): "An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search'', Annals of Operations Research 70, 281-306.
  10. Barnes, J. W., Chambers, J. B., (1996): "Flexible Job Shop Scheduling by Tabu Search'', Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, Technical Report Series, ORP96-09, .
  11. Nowicki, E., Smutnicki, C., (1996): "A fast taboo search algorithm for the job shop problem'', Management Science 42, 797-813.
  12. Vaessens, R.J.M., (1995): "Generalized Job Shop Scheduling: Complexity and Local Search", Ph.D. thesis, Eindhoven University of Technology.
  13. D.B. Shmoys, C. Stein and J. Wein (1994), "Improved approximation algorithms for shop scheduling problems", SIAM Journal on Computing 23, 617-632.
  14. Hurink,E., Jurisch, B., Thole, M., (1994): "Tabu search for the job shop scheduling problem with multi-purpose machine'', Operations Research Spektrum 15, 205-215.
  15. Brandimarte, P., (1993): "Routing and scheduling in a flexible job shop by tabu search'', Annals of Operations Research 22, pp 158-183.
  16. Dell'Amico M., Trubian, M., (1993): "Applying tabu-search to the job shop scheduling problem'', Annals of Operations Research 22, 15-24.
  17. Jurisch, B., (1992): "Scheduling Jobs in Shops with Multi-purpose Machines'', Ph.D. thesis, Fachbereich Mathematik/Informatik, Universitat Osnabruck.
  18. Brucker, P., Schlie R., (1990): ``Job-shop scheduling with multi-purpose machines'', Computing 45, 369-375.

Problem Instances and Computational Study