The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

AUTOR(ES)

Ronconi, Débora P., Kawamura, Márcio S.

FONTE

Computational & Applied Mathematics

DATA DE PUBLICAÇÃO

2010-06

RESUMO

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. Mathematical subject classification: 90C11, 62P30, 90B35.

Documentos Relacionados

• Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date.
• ESTRATÉGIAS PARALELAS INTELIGENTES PARA O MÉTODO BRANCH-AND-BOUND APLICADAS AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
• Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB)
• Um algoritmo branch-and-bound para o problema de programação de projetos com custo de disponibilidade de recursos e múltiplos modos
• SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES, WITH EARLINESS AND TARDINESS PENALTIES: A CASE STUDY IN A MACHINING PROCESS