Return to search

Beam Search e inserção de ociosidade no problema de programação de uma máquina em ambiente do tipo JIT. / Beam Search and idle time insertion in the single-machine scheduling problem in a JIT environment.

Este trabalho apresenta procedimentos que podem ser utilizados na programação da produção em um ambiente JIT. Esses procedimentos deveriam ser utilizados em sistemas clássicos de programação, onde a utilização do sistema kanban é inviável. O caso estudado se baseia em uma única máquina, com datas de entrega múltiplas e com penalidades distintas de adiantamento e de atraso para cada ordem. O objetivo a ser alcançado é a minimização do custo total. Para isso, é utilizado um procedimento de busca denominado beam search, para gerar as seqüências, e um algoritmo de inserção de ociosidade, para definir os programas. O algoritmo utilizado é uma generalização do algoritmo de GAREY et al. (1988) onde as penalidades são distintas para adiantamento e para atraso. O procedimento e o algoritmo são testados em várias condições sendo comparados com regras de despacho e com a função EXP-ET. Quando a função EXP-ET é utilizada com a possibilidade de inserção de ociosidade, o período de ociosidade ótimo é determinado. Assume-se que a dificuldade de solução do problema é dependente de dois parâmetros clássicos: fator de atraso médio e amplitude relativa das datas de entrega. Testes empíricos comparativos são realizados através de simulação computacional, onde se mede o tempo de solução e o valor alcançado pela função objetivo. Os resultados indicam que o desempenho dos vários procedimentos testados é altamente dependente dos dois parâmetros, mostrando que para a escolha de um procedimento apropriado, deve-se primeiramente conhecer o valor dos parâmetros. São fornecidos os resultados encontrados e os códigos computacionais utilizados no estudo. / This work presents some procedures which can be used in production scheduling problems in JIT environments. These procedures may be used in cases of classical production scheduling where the use of the kanban system is infeasible. The case studied is based on a single machine, with multiple due dates, and distinct earliness and tardiness penalties for each job. The objective function is to minimize total cost. A heuristic search procedure known as beam search is used to construct sequences of jobs, and an idleness insertion algorithm is used to obtain schedules. The algorithm used is a generalization of the GAREY et al. (1988) algorithm, where penalties are distinct for earliness and tardiness. The procedure and algorithm are tested in many conditions involving comparisons with dispatching rules and the EXP-ET function. When EXP-ET function is applied with possibility of idleness insertion, the optimal idleness period is provided. It was assumed that problem hardness is dependent on two classical parameters: average tardiness factor and relative range of due dates. Empirical comparative tests are conducted with computational simulation, where computational solution time and objective function value are evaluated. Results indicate that procedures performance is highly dependent on both parameters, showing that is necessary to know parameters values before choosing an appropriate procedure. The detailed results and computational code used in this study are also provided.

Identiferoai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-09122003-143854
Date14 October 1997
CreatorsColin, Emerson Carlos
ContributorsShimizu, Tamio
PublisherBiblioteca Digitais de Teses e Dissertações da USP
Source SetsUniversidade de São Paulo
LanguagePortuguese
Detected LanguagePortuguese
TypeDissertação de Mestrado
Formatapplication/pdf
RightsLiberar o conteúdo para acesso público.

Page generated in 0.0026 seconds