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
http://dx.doi.org/10.1590/S0103-65132014005000016
Production, vol.25, n1, p.79-91, 2015
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.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email