Este trabalho avalia a utilização do beam search filtrado (BSF) combinado com um algoritmo de inserção de ociosidade (AIO). O caso estudado é baseado 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, o BSF é utilizado para gerar as seqüências, e o AIO, para definir os programas. Assume-se que a dificuldade de solução do problema é dependente de dois parâmetros: fator de atraso médio e amplitude relativa das datas de entrega. Testes empíricos comparativos são realizados por meio de simulação computacional, no qual se mede o tempo de solução e o valor alcançado pela função-objetivo. Os resultados indicam que de uma forma geral, o procedimento proposto propicia uma diminuição no custo total e, além disso, que para a escolha de um procedimento apropriado, o ideal é se conhecer o valor dos parâmetros.

This work evaluates the use of a filtered beam search (FBS) combined with an ociosity insertion algorithm (OIA). 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. For this, the FBS is used to construct sequences, and the OIA is used to obtain schedules. It is assumed that the degree of difficulty of solving the problem is dependent on two parameters: average tardiness factor and relative range of due dates. Comparative empirical tests were conducted with computational simulation, where computational solution time and the objective function value were evaluated. The results indicate that in general, the proposed procedure favours a decrease in total cost and, in addition, that before choosing an appropriate procedure, the ideal situation is to know the value of the parameters.