AN EXACT APPROACH FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLY AND QUADRATIC TARDY PENALTIES

Jorge M. S. Valente ()
Additional contact information
Jorge M. S. Valente: LIAAD, Faculdade de Economia, Universidade do Porto, Portugal

Asia-Pacific Journal of Operational Research (APJOR), 2008, vol. 25, issue 02, 169-186

Abstract: 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.

Keywords: Scheduling; single machine; linear earliness; quadratic tardiness; lower bound; branch-and-bound (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595908001730
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:25:y:2008:i:02:n:s0217595908001730

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595908001730

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().