Production
https://prod.org.br/article/doi/10.1590/0103-6513.058512
Production
Article

Formulações matemáticas e estratégias de resolução para o problema job shop clássico

Mathematical models and resolution strategies for the classical job shop problem

Morales, Sergio Gomez; Ronconi, Debora Pretti

Downloads: 2
Views: 884

Resumo

O problema de sequenciamento de tarefas no ambiente de produção job shop se caracteriza por conter n tarefas que devem ser processados por m máquinas, em que cada tarefa a ser realizada é constituída por um roteiro específico de operações com ordem de precedência preestabelecida. O objetivo deste trabalho é realizar uma análise comparativa das formulações matemáticas para este ambiente, minimizando o tempo total de execução de todas as tarefas em todas as máquinas (makespan). Modelos conhecidos e um novo modelo são avaliados e comparados através de testes computacionais em problemas-teste da literatura. Adicionalmente, estratégias de resolução são propostas. Experimentos computacionais utilizando um software comercial conhecido indicam que as estratégias propostas são eficientes para a redução do gap de otimalidade.

Palavras-chave

Job shop. Programação da produção, Makespan, Modelos de programação linear inteira mista.

Abstract

The scheduling problem in a job shop production environment is characterized by containing n jobs to be processed by m machines, where each job is represented by a specific sequence of operations with an established precedence order. The aim of this work is to perform a comparative analysis of the mathematical formulations for this environment by minimizing the makespan, i.e., the total time to complete all n jobs. Popular models and a proposed model are compared and evaluated through computational tests using cases from the literature. In addition, resolution strategies are proposed. Computational experiments using a well-known commercial software package indicate that the proposal strategies can promote a reduction of the optimality gap.

Keywords

Job shop, Scheduling, Makespan, Mixed integer linear programming models.

References

Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391-401. http://dx.doi.org/10.1287/mnsc.34.3.391.

Arenales M., Armentano, V. A., Morabito, R., & Yanasse, H. H. (2007). Pesquisa operacional. Rio de Janeiro: Elsevier.

Armentano, V. A., Ronconi, D. P., Scrich, C. R., & Shiguemoto, A. L. (2013). Busca tabu: implementação de estratégias de memórias de curto e longo prazo. In H. S. Lopes, L. C. A. Rodrigues & M. T. A. Steiner (Orgs.), Meta-heurísticas em pesquisa operacional (pp. 367-384). Curitiba: Omnipax.

Baker, K. R. (1974). Introduction to sequencing and scheduling. Operations Research, 23, 62-73. http://dx.doi.org/10.1287/opre.23.1.62.

Baker, K. R., & Keller, B. (2010). Solving the single machine sequencing problem using integer programming. Computers & Industrial Engineering, 59(4), 730-735. http://dx.doi.org/10.1016/j.cie.2010.07.028.

Baker, K. R., & Trietsch, D. (2009). Principles of sequencing and scheduling. New York: John Wiley and Sons.

Beasley, J. E. (2012). OR-Library. Recuperado em 11 de julho de 2014, de http://people.brunel.ac.uk/~mastjjb/jeb/info.html

Chang, Y. L., Sueyoshi, T., & Sullivan, R. S. (1996). Ranking dispatching rules by data envelopment analysis in a job shop environment. IIE Transactions, 28, 631-642.

French, S. (1982). Sequencing and scheduling: an introduction to the mathematics of the job shop. Chichester: Horwood.

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.

International Business Machines. (2014a). Branch and cut in CPLEX. Recuperado em 11 de julho de 2014, de http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefcppcplex%2Fhtml%2Fbranch.html

International Business Machines. (2014b). Setting the initial solution. Recuperado em 11 de julho de 2014, de http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.ide.help%2FOPL_Studio%2Fopllanguser%2Ftopics%2Fuss_langtut_fc_default_behavior_6.html

Koné, O., Artigues, C., Lopez, P., & Mongeau, M. (2013). Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources. Flexible Services and Manufacturing Journal, 25(1-2), 25-47. http://dx.doi.org/10.1007/s10696-012-9152-5.

Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Relatório técnico). Pittsburgh: Carnegie Mellon University.

Liao, C. J., & You, C. T. (1992). An improved formulation for the job shop scheduling problem. Operational Research Society, 11(11), 1047-1054. http://dx.doi.org/10.1057/jors.1992.162.

Mainieri, G., & Ronconi, D. P. (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.

Manne, A. S. (1960). On the job shop scheduling problem. Operations Research, 8(2), 219-223. http://dx.doi.org/10.1287/opre.8.2.219.

Öncan, T., Altinel, I. K., & Laportec, G. (2009). A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3), 637-654. http://dx.doi.org/10.1016/j.cor.2007.11.008.

Pan, C. H. (1997). A study of integer programming formulations for scheduling problems. International Journal of System Science, 28(1), 33-41. http://dx.doi.org/10.1080/00207729708929360.

Pham D.-N. (2008). Complex job shop scheduling: formulations, algorithms and healthcare application (Tese de doutorado). University of Fribourg, Suiça.

Pinedo, M. (2008). Theory, algorithms and systems. New York: Springer.

Raman, R., & Grossmann, I. E. (1994). Modelling and computational techniques for logic based integer programming. Computers & Chemical Engineering, 18(7), 563-578. http://dx.doi.org/10.1016/0098-1354(93)E0010-7.

Ravindran, A., Phillips, D. T., & Solberg, J. J. (1987). Operations research: principles and practice. New York: John Wiley & Sons.

Ronconi, D. P., & Birgin, E. G. (2012). Mixed-Integer programming models for flow shop scheduling problems minimizing the total earliness and tardiness, in Just-in-Time systems. In Y. A. Ríos-Solís & R. Z. Ríos-Mercado (Eds.), Springer series on optimization and its applications (pp. 91-105). New York: Springer.

Stafford, E. F., Tseng, F. T., & Gupta, J. N. D. (2004). Comparative evaluation of MILP flow shop models. The Journal of the Operational Research Society, 56(1), 88-101. http://dx.doi.org/10.1057/palgrave.jors.2601805.

Wagner, H. M. (1958). An integer linear programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2), 131-140. http://dx.doi.org/10.1002/nav.3800060205.

Wilson, J. M. (1989). Alternative formulations of flow shop scheduling problem. Operational Research Society, 4(4), 395-399. http://dx.doi.org/10.1057/palgrave.jors.0400410.
5883a4657f8c9da00c8b48e6 production Articles
Links & Downloads

Production

Share this page
Page Sections