Tratamento de um problema de escalonamento considerando datas de entrega, turnos de produção e trocas de ferramentas via Busca Tabu
Scheduling problem treatment considering due dates, production turns and toll switching constraints using Tabu Search
Rodrigues, Antonio Gabriel; Gómez, Arthur Tórgo
http://dx.doi.org/10.1590/S0103-65132008000100005
Prod, vol.18, n1, p.64-75, 2008
Resumo
Neste trabalho é abordado o Problema de Escalonamento em um Job Shop aplicado a um Sistema de Manufatura Flexível (SMF), sendo consideradas restrições de datas de entrega, turnos de produção e trocas de ferramentas. O SMF considerado é composto de uma máquina versátil, um sistema de transporte e manuseio de materiais e um sistema computacional. O problema é representado por uma função objetivo f, na qual é possível definir três políticas de minimização: (i) tempo de atraso, (ii) tempo de parada para a troca de ferramentas e (iii) tempo de trocas de ferramentas. A aplicação das políticas é feita pela definição de pesos às variáveis de decisão de f. A busca pelo escalonamento que minimiza f é feita utilizando a técnica de Busca Tabu (BT). Foram realizados experimentos onde é observado o impacto de cinco regras de geração de soluções iniciais no desempenho da Busca Tabu. Também foram realizados experimentos nos quais se verifica o comportamento da busca frente à escolha das políticas de minimização. Nestes experimentos notou-se o conflito entre a política de minimização de atraso e as de minimização de trocas de ferramentas e de paradas para trocas de ferramentas. O aumento dos parâmetros da BT, nbmax (número máximo de iterações sem encontrar melhora no resultado global da busca) e tamanho da Lista Tabu, melhora o desempenho da busca para encontrar melhores resultados na minimização do atraso.
Palavras-chave
Problema de Escalonamento, Problema de Seleção de Partes, Busca Tabu, Sistema de Manufatura Flexível
Abstract
In this paper is studied the Job Shop Scheduling Problem applied to a Flexible Manufacturing System (FMS) environment, considering due dates, production turns and tool switching constraints. The FMS is composed by a versatile machine, a system for transport, handling and storage of materials and a computational system. This problem is represented through an objective function f, in which is possible to define three minimization policies: (i) tardiness time, (ii) stop time and (iii) switching tools time. The implementation of these policies is made through the definition of weights to the decision variables of f. The search for the schedule which minimizes is made through the Tabu Search (TS) technique. It was made experiments in which the impact of five initial solution rules is verified in the TS performance. Experiments with the objective of analyze the behavior of the search considering the minimization policies were performed. In these experiments, it was noticed that tardiness minimization conflicts with tool switching and stops minimization. The Increasing of TS parameters nbmax (number of iterations with no improvement in the global result of the search) and Tabu List size increasing the performance of the search in finding good solutions for tardiness minimization.
Keywords
Scheduling Problem, Part Selection Problem, Tabu Search, Flexible Manufacturing System
References
BLAEWICZ, J.; DOMSCHKE, W.; PESCH, E. The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operations Research, n. 93, p. 1–33, 1996.
GLOVER, F.; LAGUNA, M. Tabu search. Boston: Kluwer Academic, 1997, 382 p.
GÓMEZ, A. T. Modelo para Seqüenciamento de Partes e Ferramentas em um Sistema de Manufatura Flexível com restrições às datas de vencimento e à capacidade do Magazine, São Paulo, 1996. Tese (Doutorado), Instituto Nacional de Pesquisas Espaciais, São José dos Campos, São Paulo, 1996.
GONÇALVES, J. F.; MENDES, J. J. de Magalhães; RESENDE, M. G. C. A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, v. 167, p. 77–95, 2005.
GROOVER, M. P. Automation, Production Systems, and Computer-Integrated Manufacturing, United States: Prentice Hall, 2001, Segunda Edição, 856 p.
HERTZ, A.; WIDMER, M. An Improved Tabu Search Approach for solving the Job Shop Scheduling Problem with Tooling Constraints, Discrete Applied Mathematics, n. 65, p. 319-345, Elsevier Science, 1996.
JAIN, A. S.; MEERAN, S. Deterministic job shop scheduling: Past, present and future. European Journal of Operations Research, v. 113, p. 390-434, 1999.
NOWICKI, E.; SMUTNICKI, C. An advanced tabu search algorithm for the job shop scheduling problem, Journal of Scheduling, v. 8, p. 145-159, 2005.
PEZZELLA, F.; MERELLI, E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, v. 120, n. 2, p. 297-310, janeiro 2000.
PINEDO, M. Scheduling: Theory, algorithms and Systems. Englewood Cliffs: Prentice-Hall, 1995. 378 p. ISBN 0-13-706757-7.
STEINHÖFEL, K.; ALBRECHT, A.; WONG, C. K. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operations Research, v. 118, p. 524-548, 1999.
TANG, C. S.; DENARDO, E. V. Models arizing Flexible Manufacturing Machine Part II: Minimization of the number of switching instants. Operations Research, v. 36, n. 5, 1988.
WANG, L.; ZHENG, D.-Z. An effective hybrid optimization strategy for job-shop scheduling problems. Computer & Operations Research, v. 28, p. 585–596, 2001.
ZHANG, C. Y. et al. A very fast TS/SA algorithm for the job shop scheduling problem. European Journal of Operations Research. Article in press. abril 2006. Disponível em:
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email