Abstract
A linguistic-based meta-heuristic modeling and solution approach for solving the flexible job shop scheduling problem (FJSSP) is presented in this study. FJSSP is an extension of the classical job-shop scheduling problem. The problem definition is to assign each operation to a machine out of a set of capable machines (the routing problem) and to order the operations on the machines (the sequencing problem), such that predefined performance measures are optimized. In this research, the scope of the problem is widened by taking into account the alternative process plans for each part (process plan selection problem). Probabilistic selection of alternative process plans and machines are also considered. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls (Baykasoğlu, 2002). Using these controls and Giffler and Thompson's (1960) priority rule-based heuristic along with the multiple objective tabu search algorithm of Baykasoğlu et al. (1999) FJSSP is solved. This novel approach simplifies the modeling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its fast solution. Instead of scheduling job shops with inflexible algorithms that cannot take into account the flexibility which is available in the job shop, the present algorithm is developed which can take into account the flexibility during scheduling. Such an approach will considerably increase the responsiveness of the job shops.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
AI-Fawzan, M. A. and AI-Sultan, K. S. (1996) A tabu search algorithm for minimizing the makespan in a job shop scheduling. Proceedings of the 5th Industrial Engineering Research Conference, Minneapolis, MN, USA, May 1996, pp. 115–119.
Baykasoğlu, A. (2002) Linguistic based meta-heuristic optimisation model for flexible job shop scheduling. International Journal of Production Research, 40(17), 4523–4543.
Baykasoğlu, A., Owen, S. and Gindy, N. (1999) A taboo search based approach to find the Pareto optimal set in multiple objective optimisation. Journal of Engineering Optimization, 31, 731–748.
Baykasoğlu, A., Saad, S. M. and Gindy, N. (1998) A loading approach for cellular manufacturing systems. FAIM'1998: 8th International Conference on Flexible Automation and Intelligent Manufacturing, July 1–3 1998, Portland, Oregon, USA, pp. 215–226.
Ben-Daya, M. (1994) Solution methodologies for scheduling problems in flexible manufacturing systems. International Journal of Manufacturing Systems Design, 1(4), 315–328.
Blackstone, J. R., Phillips, D. T. and Rogg, G. L. (1982) A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1), 27–45.
Chambers, J. B. (1996) Classical and flexible job shop scheduling by Tabu search, Ph.D. Thesis, Operations Research and Industrial Engineering, The University of Texas at Austin.
Cheng, R., Gen, M. and Tsujimura, Y. (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms-I, Representation. Computers and Industrial Engineering, 30(4), 983–997.
Domdorf, U. and Pesch, E. (1995) Evolution based learning in a job shop scheduling environment. Complex Systems, 22, 25–40.
Fu, K. S. (1974) Syntactic Pattern Recognition, Academic Press, London.
Giffler, B. and Thompson, G. (1960) Algorithms for solving production scheduling problems. Operations Research, 8, 487–503.
Glover, E (1990) Tabu search: a tutorial. Interfaces, 20, 7494.
Jansen, K., Mastrolilli, M. and Solisaba, R. (2000) Approximation algorithms for flexible job shop problems. Proceedings of Latin American Theoretical Informatics (LATIN'2000), LNCS 1776, July 21, 2000, pp.68–77.
Kusiak, A. (1990) Intelligent Manufacturing Systems, Prentice Hall, U.S.A.
Kusiak, A., Chen, M. (1988) Expert systems for planning and scheduling manufacturing systems. European Journal of Operational Research, 34, 113–130.
Mastrolilli, M. and Gambardella, L. M. (2000) Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling, 3(1), 3–20.
Maturana, E, Gu, P., Naumann, A. and Norrie, D. H. (1997) Object oriented job-shop scheduling using genetic algorithms. Computers in Industry, 32, 281–294.
Mesghouni, K., Hammadi, S. and Borne, P. (1998) On modelling genetic algorithms for flexible job-shop scheduling problems. Studies in Informatics and Control, 7(1).
Pinedo, M. (1995) Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, New Jersey.
Sönmez, A. I. and Baykasoğlu, A. (1998) A new dynamic programming formulation of (n*m) flowshop sequencing problems with due dates. International Journal of Production Research, 36(8), 2269–2283.
Upton, D. M. and Barash, M. M. (1988) A grammatical approach to routing flexibility in large manufacturing systems. Journal of Manufacturing Systems, 7(3), 209–221.
Van Laarhoven, P. J. M., Aarts, E. H. L. and Lenstra, J. K. (1992) Job shop scheduling by simulated annealing. Operations Research, 40, 113–125.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Baykasoğlu, A., özbakir, L. & Sönmez, A.İ. Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems. Journal of Intelligent Manufacturing 15, 777–785 (2004). https://doi.org/10.1023/B:JIMS.0000042663.16199.84
Issue Date:
DOI: https://doi.org/10.1023/B:JIMS.0000042663.16199.84