Production
https://prod.org.br/doi/10.1590/S0103-65132014005000016?lang=en
Production
Article

Regras de prioridade eficientes que exploram características do Job Shop Flexível para a minimização do atraso total

Efficient priority rules that explore Flexible Job Shop characteristics for minimizing total tardiness

Melo, Everton Luiz de; Ronconi, Debora Pretti

Downloads: 0
Views: 816

Resumo

Este trabalho aborda o ambiente de produção Job Shop Flexível (JSF), extensão do problema NP-Difícil Job Shop. O JSF envolve um conjunto de jobs compostos por operações e cada operação deve ser processada em uma das máquinas habilitadas. O critério considerado é a minimização do atraso total. Inicialmente são identificadas características relacionadas à flexibilidade do sistema de produção, mais especificamente às máquinas habilitadas por operação e aos seus tempos de processamento. A seguir são propostas novas regras que exploram tais características e que são capazes de antever estados futuros do sistema. São realizados experimentos computacionais com 600 instâncias. Comparações com regras da literatura mostram que a melhor heurística proposta supera a melhor regra conhecida em 81% das instâncias.

Palavras-chave

Job Shop. Heurística. Programação matemática. Programação da produção

Abstract

This paper presents heuristic strategies that exploit characteristics of the Flexible Job Shop (FJS) environment, an extended version of the NP-hard job-shop problem. The FJS involves a set of jobs composed of operations, and each operation must be processed on a machine that can process it. The criterion is the minimization of total tardiness. Initially, characteristics related to the production system flexibility or, more precisely, characteristics related to the machines that can process each operation and the machines' processing times are identified. Therefore, rules that explore these characteristics and foresee future states of the system are proposed. Computational experiments are conducted with 600 instances. Comparisons with rules from the literature show that the best heuristic proposed outperforms the best known rule in approximately 81 percent of instances.

Keywords

Job shop. Heuristic. Mathematical programming. Production scheduling

References



Alvarez-Valdes, R., Fuertes, A., Tamarit, J., Giménez, G., & Ramos, R. (2005). A heuristic to schedule flexible job-shop in a grass factory. European Journal of Operational Research, 165(2), 525-534. http://dx.doi.org/10.1016/j.ejor.2004.04.020

Baker, K. (1984). Sequencing rules and due-date assignments in a job shop. Management Science, 30(9), 1093-1104. http://dx.doi.org/10.1287/mnsc.30.9.1093

Baker, K., & Bertrand, J. (1982). A dynamic priority rule for scheduling against due-dates. Journal of Operations Management, 3(1), 37-42. http://dx.doi.org/10.1016/0272-6963(82)90020-1

Baykasoğlu, A., & Özbakir, L. (2010). Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system. International Journal Production Economics, 124(2), 369-381. http://dx.doi.org/10.1016/j.ijpe.2009.11.032

Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183. http://dx.doi.org/10.1007/BF02023073

Brucker, P., & Schile, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369-375. http://dx.doi.org/10.1007/BF02238804

Chan, F., Wong, T., & Chan, L. (2006). Flexible job-shop scheduling problem under resource constraints. International Journal of Production Research, 44(11), 2071-2089. http://dx.doi.org/10.1080/00207540500386012

Chen, J., Chen, K., Wu, J., & Chen, C. (2008). A study of the flexible job shop scheduling problem with parallel machines and reentrant process. International Journal of Advanced Manufacturing Technology, 39, 344-354. http://dx.doi.org/10.1007/s00170-007-1227-1

Dauzère-Pérès, 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. http://dx.doi.org/10.1023/A:1018930406487

Dolan, E., & Moré, J. (2002). Benchmarking optimization software with performance profiles, Mathematical programming, 91(2), 201-213. http://dx.doi.org/10.1007/s101070100263

Fattahi, P., Mehrabad, M., & Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18, 331-342. http://dx.doi.org/10.1007/s10845-007-0026-8

Garey, M., Johnson, D., & Sethi, R. (1976). The complexity of flowshop and jobshop Scheduling. Mathematics of Operations Research, 1(2), 117-129. http://dx.doi.org/10.1287/moor.1.2.117

Gholami, M., & Zandieh, M. (2009). Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop. Journal of Intelligent Manufacturing, 20, 481-498. http://dx.doi.org/10.1007/s10845-008-0150-0

Gutiérrez, C., & García-Magariño, I. (2011). Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem. Knowledge-Based Systems, 24, 102-112. http://dx.doi.org/10.1016/j.knosys.2010.07.010

Ho, N., Tay, J., & Lai, E. (2006). An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research, 179, 316-333. http://dx.doi.org/10.1016/j.ejor.2006.04.007

Kacem, I., Hammadi, S., & Borne, P. (2002). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, 32(1), 1-13.

Kim, Y. (1995). A backward approach in list scheduling algorithms for multi-machine tardiness problems. Computers & Operations Research, 22(3), 307-319. http://dx.doi.org/10.1016/0305-0548(94)E0019-4

Koulamas, C. (1994). The total tardiness problem: review and extensions. Operations Research, 42(6), 1025-1041. http://dx.doi.org/10.1287/opre.42.6.1025

Li, J., Pan, Q., & Liang, Y. (2010). An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 59, 647-662. http://dx.doi.org/10.1016/j.cie.2010.07.014

Mainieri, G., & Ronconi, D. (2013). New heuristics for total tardiness minimization in a flexible flowshop. Optimization Letters, 7(4), 665-684. http://dx.doi.org/10.1007/s11590-012-0448-x

Özgüven, C., Özbakir, L., & Yavuz, Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34, 1539-1548. http://dx.doi.org/10.1016/j.apm.2009.09.002

Panwalkar, S., & Iskander, W. (1977). A survey of scheduling rules. Operations Research, 25(1), 45-61. http://dx.doi.org/10.1287/opre.25.1.45

Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10), 3201-3212. http://dx.doi.org/10.1016/j.cor.2007.02.014

Scrich, C. (1997). Busca Tabu para a programação de tarefas em job shop com datas de entrega (Tese de doutorado). Universidade Estadual de Campinas, Campinas.

Scrich, C., Armentano, V., & Laguna, M. (2004). Tardiness minimization in a flexible job shop: A tabu search approach. Journal of Intelligent Manufacturing, 15, 103-115. http://dx.doi.org/10.1023/B:JIMS.0000010078.30713.e9

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285. http://dx.doi.org/10.1016/0377-2217(93)90182-M

Tay, J., & Ho, N. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54, 453-473. http://dx.doi.org/10.1016/j.cie.2007.08.008

Vepsalainen, A., & Morton, T. (1987). Priority rules for job shop with weighted tardiness costs. Management Science, 33(8), 1035-1047. http://dx.doi.org/10.1287/mnsc.33.8.1035

Vilcot, G., & Billaut, J. (2008). A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. European Journal of Operational Research, 190, 398-411. http://dx.doi.org/10.1016/j.ejor.2007.06.039

Zhang, G.,Shao, X., Li, P., & Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56, 1309-1318. http://dx.doi.org/10.1016/j.cie.2008.07.021

Zhang, H., & Gen, M. (2005). Multistage-based genetic algorithm for flexible job-shop scheduling problem. Complexity International, 11, 223-232.
5883a4527f8c9da00c8b489a production Articles
Links & Downloads

Production

Share this page
Page Sections