Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date. / Aplicação do método branch-and-bound na programação de tarefas em uma única máquina com data de entrega comum sob penalidades de adiantamento e atraso.

AUTOR(ES)

Márcio Seiti Kawamura

DATA DE PUBLICAÇÃO

2006

RESUMO

The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak &Sethi, 1991; Hoogeven &van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.

ASSUNTO(S)

programação de produção brand-and-bound operations research pesquisa operacional branch-and-bound scheduling

Documentos Relacionados

• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• Metaheurísticas para o problema de Flowshop flexível com penalidades de adiantamento e atraso
• ESTRATÉGIAS PARALELAS INTELIGENTES PARA O MÉTODO BRANCH-AND-BOUND APLICADAS AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
• Heurísticas híbridas para o problema de programação de tarefas em máaquinas paralelas não relacionadas com penalidades por antecipação e atraso
• SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES, WITH EARLINESS AND TARDINESS PENALTIES: A CASE STUDY IN A MACHINING PROCESS