Multicriteria hybrid flow shop scheduling problem: literature review, analysis, and future research

Main Article Content

Marcia de Fatima Morais
Thays Josyane Perassoli Boiko
Leandro dos Santos Coelho
Rony Peterson da Rocha
Paulo Roberto Paraíso

Abstract

This research focuses on the Hybrid Flow Shop production scheduling problem, which is one of the most difficult problems to solve. The literature points to several studies that focus the Hybrid Flow Shop scheduling problem with monocriteria functions. Despite of the fact that, many real world problems involve several objective functions, they can often compete and conflict, leading researchers to concentrate direct their efforts on the development of methods that take consider this variant into consideration. The goal of the study is to review and analyze the methods in order to solve the Hybrid Flow Shop production scheduling problem with multicriteria functions in the literature. The analyses were performed using several papers that have been published over the years, also the parallel machines types, the approach used to develop solution methods, the type of method develop, the objective function, the performance criterion adopted, and the additional constraints considered. The results of the reviewing and analysis of 46 papers showed opportunities for future researchon this topic, including the following: (i) use uniform and dedicated parallel machines, (ii) use exact and metaheuristics approaches, (iv) develop lower and uppers bounds, relations of dominance and different search strategiesto improve the computational time of the exact methods,  (v) develop  other types of metaheuristic, (vi) work with anticipatory setups, and (vii) add constraints faced by the production systems itself.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

Article Details

Section
Articles
Author Biographies

Marcia de Fatima Morais, Department of Industrial Engineering, State University of Paraná (UNESPAR), Campo Mourão, Paraná, Brazil

Professor in the Department of Industrial Engineering of State University of Paraná (UNESPAR), Campo Mourão/Paraná, Brazil. She received his BS from UNESPAR (2002) and MS from University of São Paulo (USP), Brazil. She is currently a PhD student at the Department of Industrial Engineering and Systems, Pontifical Catholic University of Paraná (PUCPR), Paraná, Brazil. She is also a Researcher from the Research Group on Processes and Operations Management and she’s interested in Production Management and Operations Research with emphasis on scheduling problems.

Thays Josyane Perassoli Boiko, Department of Industrial Engineering, State University of Paraná (UNESPAR), Campo Mourão, Paraná, Brazil

Professor in the Department of Industrial Engineering of State University of Paraná (UNESPAR), Campo Mourão/Paraná, Brazil. She received his BS from UNESPAR/FECILCAM (2002) and MS from University of São Paulo (USP), Brazil. She is currently a PhD student at the Department of Industrial Engineering, USP, Brazil. She is also a Researcher from the Research Group on Processes and Operations Management and she´s interested in Production Management and Operations Research with emphasis on scheduling problems.

Leandro dos Santos Coelho, Department of Automation and Systems, Pontifical Catholic University of Parana (PUCPR), Curitiba, Brazil and Federal University of Parana (UFPR), Curitiba, Brazil.

Received a BS in Computer Science and a BS in Electrical Engineering from the Federal University of Santa Maria (UFSM), Brazil, in 1994 and 2000, respectively. He earned his MS and Doctoral degrees in Computer Science and Electrical Engineering from the Federal University of Santa Catarina (UFSC), Brazil, in 1997 and 2000, respectively. He is currently an Associate Professor at the Department of Automation and Systems, Pontifical Catholic University of Parana (PUCPR) and Federal University of Parana (UFPR), Brazil. He is interested in natural computing, power systems, nonlinear identification, optimization methods, biomechanics, and advanced control systems.

Rony Peterson da Rocha, Department of Industrial Engineering, State University of Paraná (UNESPAR), Campo Mourão, Paraná, Brazil

Professor in the Department of Industrial Engineering of of State University of Paraná (UNESPAR), Campo Mourão/PR, Brazil. He received his BS from UNESPAR (2004) and MS from State Universty of Maringá (UEM), Brazil. He is currently a PhD student at the Department of Chemical Engineering, UEM, Brazil. He is also a Researcher from the Research Group on Processes and Operations Management and his interested in Production Management and Operations Research.

Paulo Roberto Paraíso, Department of Chemical Engineering, State University of Maringá (UEM), Maringá/PR, Brazil

Professor and Research at the Department of Chemical Engineering of State University of Maringá (UEM), Maringá/PR, Brazil. He received his BS (1980) from Federal University of Minas Gerais (UFMG), MS (1986) from Federal Universty of Santa Catarina (UFSC) and Doctoral degrees (2001) in Chemical Engineering from State University of Campinas (UNICAMP).

References

AKRAMI, B.; KARIMI, B.; MOATTAR-HOSSEINI, S. M. (2006) Two metaheuristic methods for the common cycle economic lot sizing and scheduling in flexible flow shops with limited intermediate buffers: the finite horizon case. Applied Mathematics and Computation, v. 183, n. 1, p. 634–645.

ALLAHVERDI, A.; CHENG, T. C. E.; KOVALYOV, M. Y. (2008) A survey of scheduling problems with setup times or costs. European Journal of Operational Research, v. 187, p. 985–1032.

ALLAHVERDI, A.; GUPTA, J. N. D.; ALDOWAISAN, T. (1999) A review of scheduling research involving setup considerations. Omega - The International Journal of Management Science, v. 27, p. 219-239.

ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, I. (2007) Pesquisa Operacional. Rio de Janeiro: Elsevier.

BAKER, K. R. (1974) Introduction to sequencing and scheduling. New York: John Wiley & Sons, Inc.

BEDWORTH, D. D.; BAILEY, J. E. (1987) Integrated Production Control Systems: management, analysis, design. 2 ed. New York: John Wiley & Sons, Inc.

BEHNAMIAN, J.; FATEMI GHOMI, S. M. T.; ZANDIEH, M. (2009a) A Multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Systems with Applications, v. 36, n. 8, p. 11057-11069.

BEHNAMIAN, J.; ZANDIEH, M.; FATEMI GHOMI, S. M. T. (2009b) Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms. International Journal Advanced Manufacture Technology, v. 44, p. 795–808.

BEHNAMIAN, J.; ZANDIEH, M. (2011) A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Systems with Applications, v. 38, p. 14490-14498.

BLUM, C.; ROLI, A. (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, v. 22, n. 2, p. 241-264.

BOIKO, T. J. P.; MORAIS, M. F. (2009). The activity of production programming about the operational research view: a theorical conceptual approach. In: VI ENCONTRO TECNOLÓGICO. Proceedings... Campo Mourão: ENTEC, 2009.

BONABEAU, E.; DORIGO, M.; THERAULAZ, G. (1999) Swarm intelligence: from natural to artificial systems, NewYork, Oxford University Press.

BOSCHETTI, M. A.; MANIEZZO, V.; ROFFILLI, M.; ROHLER, A. B. (2009) Metaheuristics: optimization, simulation and control. Lecture Notes in Computer Science, v. 5818.

BOZORGIRAD, M. A.; LOGENDRAN, R. (2013) Bi-criteria group scheduling in hybrid flowshops. International Journal of Production Economics, v. 145, p. 599–612.

BURTSEVA, L.; YAURIMA, V.; PARRA, R. R. (2010) Scheduling methods for hybrid flow shops with setup times. In: Handbook Future Manufacturing Systems. InTech.

CARVALHO, J. D. A. (2000) Production programming. Notes. Sistems and Production department, Engineering School from Minho University. Available in http://pessoais.dps.uminho.pt/jdac/apontamentos/Cap03_Program.pdf.

CHO, H-M.; BAE, S-J.; KIM, J.; JEONG, I-J. (2011) Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, v. 61, p. 529-541.

DAVOUDPOUR, H.; ASHRAFI, M. (2009) Solving multi-objective SDST flexible flow shop using GRASP algorithm. International Journal Advanced Manufacturing Technology, v. 44, p.737–74.

DREO, J.; AUMASSON,J-P.; TFAILI, W.; SIARRY, P. (2007) Adaptive learning search, a new tool to help comprehending metaheuristics. International Journal on Artificial Intelligence Tools, v. 16. n. 3, p. 483-505.

DUGARDIN, F.; YALAOUI, F.; AMODEO, L. (2010) New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, v. 203, p. 22-31.

EBRAHIMINY, S. M. T.; FATEMI GHOMI, S. M. T.; KARIMI, B. (2013) Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates. Applied Mathematical Modelling, v. 38, n. 09-10, p. 2490-2504.

FADAEI, M.; ZANDIEH, M. (2013) Scheduling a bi-objective hybrid flow shop with sequence-dependent family setup times using metaheuristics. Arabian Journal of Science Engineering, v. 38, p. 2233-2244.

FAHKRZAD, M. B.; HEYDARI, M. (2008) A heursitc algorithm for hybrid flow-shop production scheduling to miminize the sum of the earliness and tardiness cost. Journal of the Chinese Institute of Industrial Engineers, v. 25, n. 2, p. 105-115.

FRENCH. S. (1982) Sequencing and scheduling: an introduction to the mathematics of the job shop. New York: Wiley.

GLOVER, F.; KOCHENBERGER, G. A. (2003) Handbook of Metaheuristics. Kluwer Academic Publishers, Boston.

GODINHO FILHO, M.; MORAIS, M. F.; BOIKO, T. J. P.; MIYATA, H. H.; VAROLO, F. W. R. (2013). Scheduling in flow shop with sequence-dependent setup times: literature review and analysis. International Journal of Business Innovation and Research, v. 7, n. 4, p. 466-486.

GUPTA, J. N. D.; KRUGER, K.; LAUFF, V.; WERNER, F.; SOTSKOV, Y. N. (2002) Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers & Operations Research, v. 29, p. 1417-1439.

HAN, Z.; SHI, H.; YUAN, W.; ZHANG, Z. (2012) Hybrid PSO/DE solution for the earliness/tardiness case of hybrid flow-shop scheduling problem. In: INTERNATIONAL CONFERE ON MODELING, IDENTIFICATION AND CONTROL, Wuhan, Proceedings… Wuhan: ICMIC, 2012.

HAYRINEN, T.; JOHNSSON, M.; JOHTELA, T.; SMED, J.; NEVALAINEN. O. (2000) Scheduling algorithms for computer-aided line balancing in printed circuit board assembly. Production Planning and Control, v. 11, n. 5, p. 497–510.

JANIAK, A.; KOZAN, E.; LICHTENSTEIN, M.; OGUZ, C. (2007) Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production Economics, v. 104, p. 407-424.

JANIAK, A.; LICHTENSTEIN, M. (2001) Comparison of some heuristic algorithms for the flow shop problem with parallel machines to minimize the total earliness, tardiness and waiting time, Operations Research Proceedings, v. 2000-2001, p. 378-383.

JENABI, M.; GHOMI, S. M. T. F.; TORABI, S. A.; KARIMI, B. (2007) Two hybrid meta-heuristics for the finite horizon ELSP in flexible flow lines with unrelated parallel machines. Applied Mathematics and Computation, v. 186, n. 1, p. 230-245.

JOHNSON S. M.; MONTGOMERY D. C. (1974) Operations Research in Production, Planning, Scheduling and Inventory Control. New York: Wiley.

JOHNSON, S. M. (1954) Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, Hoboken, v. 1, p. 61-68.

JOLAI, F.; ASEFI, H.; RABIEE, M.; RAMEZANI, P. (2013). Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem. Scientia Iranica, v. 20, n. 03, p. 861-872.

JUNGWATTANAKI, J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2005). An Evaluation of Sequencing Heuristics for Flexible Flowship Scheduling Problems with Unrelated Parallel Machines and Dual Criteria. Magdeburg: Otto Von Guericke, Universität Magdeburg Fakultät für Mathematik.

JUNGWATTANAKI, J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2007) Construtive and Tabu Search for hybrid flow shop problems with unrelated parallel machine and setup times. International Journal of Computational Science, v. 1, n. 2, p. 204-214.

JUNGWATTANAKI, J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2008). Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Introduction Journal Advanced Manufactury Technology, v. 37, p. 354–370.

JUNGWATTANAKI, J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2009) A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Computers & Operations Research, v. 36, n. 2, p. 358-378.

KARIMI, N.; ZANDIEH, M.; KARAMOOZ, H. R. (2010) Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach. Expert Systems with Applications, v. 37, p. 4024-4032.

KHALOULI, S.; GHEDJATI, F.; HAMZAOUI, A. (2008). Ant Colony Optimization for solving a bi-criteria hybrid flow shop problem. In: INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS, Singapore. 2008. Proceedings…Singapore: IEEE/SMC 2008.

KHALOULI, S.; GHEDJATI, F.; HAMZAOUI, A. (2010) A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop. Engineering Applications of Intelligence, v. 23, p. 765-771.

LI, L.; WANG, L.; HUO, J. (2010) Hybrid flowshop scheduling with setup times for cold treating process in Baoshan Iron & Steel Complex. In: INTERNATIONAL CONFERENCE ON LOGISTICS SYSTEMS AND INTELLIGENT MANAGEMENT, Harbin. Proceedings…Hammamet: IEEE/LSIM, 2011.

LI, X.; CHEHADE, H.; YALAOUI, F.; AMODEO, L. (2011) Lorenz dominance based metaheuristic to solve a hybrid flowshop scheduling problem with sequence dependent setup times. In: INTERNATIONAL CONFERENCE ON COMPUTATION AND CONTROL APPLICATIONS, Hammamet. Proceedings… Hammamet: CCCA, 2011.

LIN, H. T.; LIAO, C. J. (2003) A case study in a two-stage hybrid flow shop with setup time and dedicated machines. International Journal of Production Economics, v. 86, n. 2, p. 133–43.

LIU, C.; CHANG, S. (2000) Scheduling flexible flow shops with sequence-dependent setup effect. Transactions on Robotics and Automation, v. 16, p. 408-419.

MACCARTHY, B. L.; LIU, J. Y. (1993). Adressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal of Production Research, v. 31, n. 1, p. 59-79.

MAHDAVI, I.; MOJARAD, M. S.; JAVADI, B.; TAJDIN, A. (2008) A genetic approach for solving a hybrid flow shop scheduling problem. In: INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT, Singapore. Procedings… Singapore: IEEM, 2008.

MORAIS, M. F. (2008) Constructive heuristic methods to reduce the stock being processed in hybrid flow shop production environments wirth setup times dependent from sequency. Dissertation (Master’s degree) graduation in Production Engeneering, Engeneering school from São Carlos, São Paulo University, São Carlos.

MORAIS, M. F.; GODINHO FILHO, M.; BOIKO, T. J. P. (2013) Hybrid flow shop scheduling problems involving setup considerations: a literature review and analysis. International Journal of Industrial Engineering, v. 20, n. 11-12, p. 613-629.

MORAIS, M. F.; MOCCELLIN, J. V. (2010) Constructive heuristics methods to minimizing work in process in environment production hybrid flow shop with asymmetric sequence dependent setup times. Journal of Management and Production, v. 17, n. 2, p. 367- 375.

MORTON, T. E.; PENTICO, D. W. (1993) Heuristic Scheduling Systems. Wiley, New York.

MOUSAVI, S.; ZANDIEH, M.; AMIRI, M. (2011) An efficient bi-objective heuristic for scheduling of hybrid flow shops. The International Journal of Advanced Manufacturing Technology, v. 54, n. 1-4, p. 287-307.

NADERI, B.; ZANDIEH, M.; BALAG, A.K.G.; ROSHANAEI, V. (2009) An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert systems with Applications, v. 36, n. 6, p. 9625-9633.

NADERI, B.; ZANDIEH, M.; ROSHANAEI, V. (2009) Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. International Journal Advanced Manufacturing Technology, v. 41, p. 1186–1198.

NAGAR, A.; HADDOCK, J.; HERAGU, S. (1995) Multiple and bicritério scheduling: a literature survey. European Journal of Operational Research, v. 81, p. 88-104.

OLIVEIRA, R. B. (2008) Development of a multi-agent architecture based on methaheuristics with an adaptive learning search approach. Dissertation (master’s degree). Graduation in Computational and mathematical modeling, Federal Center of Technological Education, Minas Gerais, Belo Horizonte.

PEREIRA, A. M. S. (2011) Metaheuristics for the flowshop flexible with advance and tardiness problem. Dissertation (Master’s degree) graduation in computational science, Federal University from Viçosa, Viçosa.

PINEDO, M. (2008) Theory, Algorithms and Systems. New Jersey: Prentice-Hall.

QUADT, D.; KUHN, H. (2005) Conceptual framework for lot-sizing and scheduling of flexible flowlines. International Journal of Production Research, v. 43, n. 11, p. 2291–308.

QUADT, D.; KUHN, H. (2007) Batch scheduling of jobs with identical process times on flexible flowlines. International Journal of Production Economics, v. 105, n. 2, p. 385–401.

RASHIDI, E.; JAHANDAR, M.; ZANDIEH, M. (2010) An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. International journal advanced manufacturing technology, v. 49, n. 9-12, p. 1129-1139.

RUIZ-VANOYE, J.; DÍAZ-PARRA, O.; COCÓN, F.; SOTO, A. (2012) Meta-heuristics algorithms based on the grouping of animals by social behavior for the traveling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, v. 3, n. 3, p.104-123.

SANG, H-Y. (2013) Erratum to ‘‘A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadric tardiness penalties’’[Expert Syst. Appl. 38 (2011) 14490–14498]. Expert Systems with Applications, v. 40, p. 4270-4272.

SAWIK, T. (2005) Integer programming approach to production scheduling for make-to-order manufacturing. Mathematical and Computer Modelling, v. 41, n. 1, p. 99–118.

SAWIK, T. (2007) A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing. European Journal of Operational Research, v. 180, p. 1060–1075.

SERAPIÃO, A. B. S. (2009) Optimization fundamentals by swarm inteligence: a global view Contrlole & Automação journal, v. 20, n. 3, p. 271-304.

SETHANAN, K. (2001) Scheduling flexible flowshops with sequence dependent setup times. These (Doctored). College of Engineering and Mineral Resources, West Virginia University, Morgantown.

SIMON, D. (2013) Evolutionary optimization algorithms: biologically inspired and population-based approaches to computer intelligence. New York: John Wiley & Sons, Inc.

SOUZA, A. B. D.; MOCCELLIN, J. V. (2000) Hybrid metaheuristic genetic algorithm Busca-Tabu for flow shop operations programming.In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, XXXII, Rio de Janeiro, Proceedings… Rio de Janeiro: SBPO, 2000.

TANG, L.; LUH, P. B.; LIU, J.; FANG, L. (2002) Steel-making process scheduling using Lagrangian relaxation. International Journal of Production Research, v. 40, n. 1, p. 55-70.

TAVAKKOLI-MOGHADDAM, R.; RAHIMI-VAHED, A.; MIRZAEI, A. (2007) A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness. Information Sciences, v. 177, p. 5072–5090.

TORABI, S. A.; FATEMI-GHOMI, S. M. T.; KARIMI, B. (2006) A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains. European Journal of Operational Research, v. 173, p. 173–189.

WENG, W.; FUJIMURA, S. (2009a) Online Scheduling of Flexible Flow Shop Manufacturing. In: INTERNATIONAL JOINT CONFERENCE ON COMPUTATIONAL SCIENCES AND OPTIMIZATION, Sanya, Hainan, China. Proceedings… Sanya, Hainan, China.: IJCCSO, 2009. 978-0-7695-3605-7/09.

WENG, W.; FUJIMURA, S. (2009b) Distributed Feedback Mechanism for Just-In-Time Scheduling Problem. IN: INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCE, 8, Shanghai, China. Proceedings… Shanghai, China: Eigth IEEE/ACIS, 2009.

WENG, W.; WEI, X.; FUJIMURA, S. (2012) Dynamic routing strategies for JIT production in hybrid flow shops. Computers & Operations Research, v. 39, p. 3316-3324.

XUAN, H; TANG, L. X. (2007) Scheduling a hybrid flow shop with batch production at the last stage. Computers & Operations Research, v. 34, n. 9, p. 2718–33.

YANG, W.; LIAO, C. (1999) Survey of scheduling research involving setup times. International Journal of Systems Science, Abington, v. 30, n. 2, p. 143-155.

YENISEY, M. M.; YAGMAHAN, B. (2014) Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, v. 45, p. 119-135.

ZANDIEH, M.; KARIMI, N. (2011) An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times. Journal of Intelligence Manufacturing, v. 22, p. 979-989.