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

AUTOR(ES)

Emerson Carlos Colin

DATA DE PUBLICAÇÃO

1997

RESUMO

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.

ASSUNTO(S)

beam search beam search production scheduling inserção de ociosidade idle time insertion just-in-time programação de uma máquina just-in-time programação da produção single machine scheduling

Documentos Relacionados

• Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date.
• Integrated two-stage lot sizing and scheduling problem
• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• Distribuição de carga e variação de capacidade na programação da produção: resultados na inserção de espera e na utilização de capacidade adicional.
• Um ambiente para avaliação de algoritmos de aprendizado de máquina simbólico utilizando exemplos.