An exact approach for the single machine scheduling problem with linear early and quadratic tardy penalties

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Jorge M S Valente (Autor) FEP

Revista

Título: Asia-Pacific Journal of Operational Research

Vol. 25 Nº 2

Páginas: 169-186

ISSN: 0217-5959

Editora: World Scientific

Indexação

ISI Web of Knowledge - 12 Citações

ISI Web of Science

Scopus - 14 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia industrial

CORDIS: Ciências Sociais > Economia > Estudos de gestão

Outras Informações

ID Authenticus: P-004-099

DOI: 10.1142/s0217595908001730

Abstract (EN): In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test. The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computational results show that the branch-and-bound algorithms are capable of optimally solving, within reasonable computation times, instances with up to 20 jobs.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 18