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.
Applications
There is a great variety of real-world problems that can be modelled as a
FJSP. They occur, e.g., in
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 (monaldo@idsia.ch
). I will complete the list.
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.
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.
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.
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
)
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
)
Brucker, P., Neyer, J., (1998): "Tabu-search for the multi-mode job-shop
problem'' , OR Spektrum 20, 21-28.
Dauzere-Peres S., Roux J., Lasserre J.B., (1998): "Multi-resource
shop scheduling with resource flexibility'', European Journal of Operational
Research 107, 289-305.
Balas, E., Vazacopoulos, A., (1998): "Guided Local Search with Shifting
Bottleneck for Job Shop Scheduling'', Management Science 44, 262-275.
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.
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, http://www.cs.utexas.edu/users/jbc/
.
Nowicki, E., Smutnicki, C., (1996): "A fast taboo search algorithm
for the job shop problem'', Management Science 42, 797-813.
Vaessens, R.J.M., (1995): "Generalized Job Shop Scheduling: Complexity
and Local Search", Ph.D. thesis, Eindhoven University of Technology.
D.B. Shmoys, C. Stein and J. Wein (1994), "Improved approximation
algorithms for shop scheduling problems", SIAM Journal on Computing 23, 617-632.
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.
Brandimarte, P., (1993): "Routing and scheduling in a flexible job
shop by tabu search'', Annals of Operations Research 22, pp 158-183.
Dell'Amico M., Trubian, M., (1993): "Applying tabu-search to the job
shop scheduling problem'', Annals of Operations Research 22, 15-24.
Jurisch, B., (1992): "Scheduling Jobs in Shops with Multi-purpose
Machines'', Ph.D. thesis, Fachbereich Mathematik/Informatik, Universitat
Osnabruck.
Brucker, P., Schlie R., (1990): ``Job-shop scheduling with multi-purpose
machines'', Computing 45, 369-375.
Problem Instances and Computational Study
A library of problem instances is given in
FJSPLIB
.
The complete computational study concerning
this paper is available here for download:
Mastrolilli M., Gambardella L.M., (1998) "Effective Neighborhood Functions
for the Flexible Job Shop Problem: appendix",
Download as ... .pdf
(163k) ... .ps
(1655k) ... .ps.zip
(473k)