Novas regras de prioridade para programação em flexible flow line com tempos de setup explícitos
New priority rules for the flexible flow line scheduling problem with setup times
Fuchigami, Hélio Yochihiro; Moccellin, João Vitor; Ruiz, Rubén
http://dx.doi.org/10.1590/0103-6513.089212
Production, vol.25, n4, p.779-790, 2015
Resumo
Neste artigo são propostos e avaliados 12 métodos para minimização da duração total da programação (makespan) em sistemas flexible flow line com tempos de setup independentes da sequência de execução das tarefas. Esse ambiente é caracterizado pela possibilidade de as tarefas saltarem um ou mais estágios de produção. Além disso, os tempos de setup podem ou não ser antecipados. Os desempenhos relativos dos métodos de solução foram avaliados por meio de experimentação computacional com base na porcentagem de sucesso, desvio relativo, desvio-padrão do desvio relativo e tempo médio de computação. Para avaliar-se a qualidade da solução dos métodos propostos, foi desenvolvido um limitante inferior (lower bound) para a função objetivo. Testes computacionais mostraram a maior eficácia do método que sequencia as tarefas no primeiro estágio, pela ordem decrescente da soma dos tempos de processamento e de setup de todos os estágios, e nos estágios seguintes, pela ordem em que as tarefas são liberadas para o processamento.
Palavras-chave
Programação da produção. Flexible flow line. Setup independente.
Abstract
This paper presents twelve methods for makespan minimization for flexible flow line scheduling problems. This environment is characterized by the ability of jobs to skip stages. Sequence-independent setup times, which can be either anticipatory or non-anticipatory, are also considered. The statistics used to evaluate the heuristic performances were the rate of success (in finding the best solution), the relative deviation, the standard deviation of the relative deviation and the average computation time. A lower bound for makespan was developed to evaluate the solution quality of the proposed methods. The computational tests proved the effectiveness of the heuristic based on the initial sequence using the descending order of the sum of the processing and setup times of all stages and the sequencing of subsequent stages by the order of the job release times.
Keywords
Production scheduling. Flexible flow line. Sequence-independent setup times.
References
Aldowaisan, T. (2001). A new heuristic and dominance relations for no-wait flowshop with setups. Computer and Operations Research, 28, 563-584.
Allahverdi, A. (2000). Minimizing mean flowtime in a two-machine flowshop with sequence-independent setup times. Computers and Operations Research, 27, 111-127.
Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega – The International Journal of Management Science, 27, 219-239.
Allaoui, H., & Artiba, A. (2004). Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Computers and Industrial Engineering, 47, 431-450.
Andrés, C., Albarracín, J. M., Tormo, G., Vicens, E., & García- Sabater, J. P. (2005). Group technology in a hybrid flowshop environment: A case study. European Journal of Operational Research, 167, 272-281.
Botta-Genoulaz, V. (2000). Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. International Journal of Production Economics, 64(1-3), 101-111.
Brah, S. A., & Hunsucker, J. L. (1991). Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 5(1), 88-99.
Brah, S. A., & Loo, L. L. (1999). Heuristic for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 113, 113-122.
Ding, F. Y., & Kittichartphayak, D. (1994). Heuristics for scheduling flexible flow lines. Computers and Industrial Engineering, 26, 27-34.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.
Gupta, J. N. D., & Tunc, E. A. (1994). Scheduling a two-stage hybrid flowshop with separable setup and removal times. European Journal of Operational Research, 77, 415-428.
Huang, W., & Li, S. (1998). A two-stage hybrid flowshop with uniform machines and setup times. Mathematical and Computer Modeling, 27(2), 27-45.
Jenabi, M., Fatemi Ghomi, S. M. T., 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, 186, 230-245.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2008). Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. International Journal of Advanced Manufacturing Technology, 37, 354-370.
Kis, T., & Pesch, E. (2005). A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. European Journal of Operational Research, 164, 592-608.
Kurz, M. E., & Askin, R. G. (2003). Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 85, 371-388.
Kurz, M. E., & Askin, R. G. (2004). Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research, 159, 66-82.
Lee, C-Y., & Vairaktarakis, G. L. (1994). Minimizing makespan in hybrid flowshops. Operations Research Letters, Amsterdam, 16(3), 149-158.
Leon, V. J., & Ramamoorthy, B. (1997). An adaptable problem- space-based search method for flexible flow line scheduling. IIE Transactions, 29, 115-125.
Li, S. (1997). A hybrid two-stage flowshop with part family, batch production, and major and minor set-ups. European Journal of Operational Research, 102, 142-156.
Linn, R., & Zhang, W. (1999). Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering, Oxford, 37(1-2), 57-61 .
Liu, C-Y., & Chang, S-C. (2000). Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Transactions on Robotics and Automation, 16(4), 408-419.
Logendran, R., Carson, S., & Hanson, E. (2005). Group scheduling in flexible flow shops. International Journal of Production Economics, 96, 143-155.
Low, C. (2005). Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research, 32, 2013-2025.
Naderi, B., Ruiz, R., & Zandieh, M. (2010). Algorithms for a realistic variant of flowshop scheduling. Computers & Operations Research. Computers & Operations Research, 37(2), 236-246.
Quadt, D., & Kuhn, H. (2007a). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178(3), 686-698. http://dx.doi.org/10.1016/j.ejor.2006.01.042.
Quadt, D., & Kuhn, H. (2007b). Batch scheduling of jobs with identical process times on flexible flow lines. International Journal of Production Economics, 105(2), 385-401. http://dx.doi.org/10.1016/j.ijpe.2004.04.013.
Ribas, I., Leisten, R., & Framiñan, J. M. (2010). Review and classifications of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers & Operations Research, 37, 1439-1454.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169, 781-800.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205, 1-18.
Ruiz, R., Şerifoğlu, F. S., & Urlings, T. (2008). Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, 35, 1151-1175.
Tang, L. X., & Zhang, Y. Y. (2005). Heuristic combined artificial neural networks to schedule hybrid flow shop with sequence dependent setup times. Lecture Notes in Computer Science, 3496, 788-793.
Tavakkoli-Moghaddam, R., & Safaei, N. (2007). A new mathematical model for flexible flow lines with blocking processor and sequence-dependent setup time. Multiprocessor scheduling: theory and applications (pp. 255-272). Viena: ARS Publishing, Ed. Vedran Kordic.
Vignier, A., Billaut, J. C., & Proust, C. (1999). Les problèmes d’ordonnancement de type flow-shop hybride: état de l’art. RAIRO – Recherche Opérationnelle, 33(2), 117-183.
Wang, H. (2005). Flexible flow shop scheduling: optimum, heuristic and artificial intelligence solutions. Expert Systems, 22(2), 78-85.
Wilson, A. D., King, R. E., & Hodgson, T. J. (2004). Scheduling non-similar groups on a flow line: multiple group setups. Robotics and Computer-Integrated Manufacturing, 20, 505-51.
Wittrock, R. J. (1988). An adaptable scheduling algorithm for flexible flow lines. Operations Research, 36(4), 445-453.
Zandieh, M., Fatemi Ghomi, S. M. T., & Moattar Husseini, S. M. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180, 111- 127.
Allahverdi, A. (2000). Minimizing mean flowtime in a two-machine flowshop with sequence-independent setup times. Computers and Operations Research, 27, 111-127.
Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega – The International Journal of Management Science, 27, 219-239.
Allaoui, H., & Artiba, A. (2004). Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Computers and Industrial Engineering, 47, 431-450.
Andrés, C., Albarracín, J. M., Tormo, G., Vicens, E., & García- Sabater, J. P. (2005). Group technology in a hybrid flowshop environment: A case study. European Journal of Operational Research, 167, 272-281.
Botta-Genoulaz, V. (2000). Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. International Journal of Production Economics, 64(1-3), 101-111.
Brah, S. A., & Hunsucker, J. L. (1991). Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 5(1), 88-99.
Brah, S. A., & Loo, L. L. (1999). Heuristic for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 113, 113-122.
Ding, F. Y., & Kittichartphayak, D. (1994). Heuristics for scheduling flexible flow lines. Computers and Industrial Engineering, 26, 27-34.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.
Gupta, J. N. D., & Tunc, E. A. (1994). Scheduling a two-stage hybrid flowshop with separable setup and removal times. European Journal of Operational Research, 77, 415-428.
Huang, W., & Li, S. (1998). A two-stage hybrid flowshop with uniform machines and setup times. Mathematical and Computer Modeling, 27(2), 27-45.
Jenabi, M., Fatemi Ghomi, S. M. T., 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, 186, 230-245.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2008). Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. International Journal of Advanced Manufacturing Technology, 37, 354-370.
Kis, T., & Pesch, E. (2005). A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. European Journal of Operational Research, 164, 592-608.
Kurz, M. E., & Askin, R. G. (2003). Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 85, 371-388.
Kurz, M. E., & Askin, R. G. (2004). Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research, 159, 66-82.
Lee, C-Y., & Vairaktarakis, G. L. (1994). Minimizing makespan in hybrid flowshops. Operations Research Letters, Amsterdam, 16(3), 149-158.
Leon, V. J., & Ramamoorthy, B. (1997). An adaptable problem- space-based search method for flexible flow line scheduling. IIE Transactions, 29, 115-125.
Li, S. (1997). A hybrid two-stage flowshop with part family, batch production, and major and minor set-ups. European Journal of Operational Research, 102, 142-156.
Linn, R., & Zhang, W. (1999). Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering, Oxford, 37(1-2), 57-61 .
Liu, C-Y., & Chang, S-C. (2000). Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Transactions on Robotics and Automation, 16(4), 408-419.
Logendran, R., Carson, S., & Hanson, E. (2005). Group scheduling in flexible flow shops. International Journal of Production Economics, 96, 143-155.
Low, C. (2005). Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research, 32, 2013-2025.
Naderi, B., Ruiz, R., & Zandieh, M. (2010). Algorithms for a realistic variant of flowshop scheduling. Computers & Operations Research. Computers & Operations Research, 37(2), 236-246.
Quadt, D., & Kuhn, H. (2007a). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178(3), 686-698. http://dx.doi.org/10.1016/j.ejor.2006.01.042.
Quadt, D., & Kuhn, H. (2007b). Batch scheduling of jobs with identical process times on flexible flow lines. International Journal of Production Economics, 105(2), 385-401. http://dx.doi.org/10.1016/j.ijpe.2004.04.013.
Ribas, I., Leisten, R., & Framiñan, J. M. (2010). Review and classifications of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers & Operations Research, 37, 1439-1454.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169, 781-800.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205, 1-18.
Ruiz, R., Şerifoğlu, F. S., & Urlings, T. (2008). Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, 35, 1151-1175.
Tang, L. X., & Zhang, Y. Y. (2005). Heuristic combined artificial neural networks to schedule hybrid flow shop with sequence dependent setup times. Lecture Notes in Computer Science, 3496, 788-793.
Tavakkoli-Moghaddam, R., & Safaei, N. (2007). A new mathematical model for flexible flow lines with blocking processor and sequence-dependent setup time. Multiprocessor scheduling: theory and applications (pp. 255-272). Viena: ARS Publishing, Ed. Vedran Kordic.
Vignier, A., Billaut, J. C., & Proust, C. (1999). Les problèmes d’ordonnancement de type flow-shop hybride: état de l’art. RAIRO – Recherche Opérationnelle, 33(2), 117-183.
Wang, H. (2005). Flexible flow shop scheduling: optimum, heuristic and artificial intelligence solutions. Expert Systems, 22(2), 78-85.
Wilson, A. D., King, R. E., & Hodgson, T. J. (2004). Scheduling non-similar groups on a flow line: multiple group setups. Robotics and Computer-Integrated Manufacturing, 20, 505-51.
Wittrock, R. J. (1988). An adaptable scheduling algorithm for flexible flow lines. Operations Research, 36(4), 445-453.
Zandieh, M., Fatemi Ghomi, S. M. T., & Moattar Husseini, S. M. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180, 111- 127.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email