A Time-Indexed Formulation for Single-Machine Scheduling Problems: Branch-and-Cut

Janna M. van den AKKER, C.A.J. Hurkens and M.W.P. Savelsbergh
Additional contact information
Janna M. van den AKKER: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium
C.A.J. Hurkens: Department of Mathematics and Computing Science, Eindhoven University of Technology, EIndhoven, The Netherlands
M.W.P. Savelsbergh: School of Industrial ans Systems Engineering, Georgia Institute of Technology, Atlanta

No 1996016, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In Van den Akker, Va, Hoesel, and Savelsbergh [1994], we have studied a tume-indexed formulation for single-machine scheduling problems and have presented a complete characterization of all facet inducing inequalities with right-hand side 1 and 2 for the convex hull of the monotone extension of the set of feasible schedules. In this paper, we discuss the development of a branch-and-cut algorithm based on these facet inducing inequalities. We describe separation algorithms for each class of these inequalities, and elaborate on various other important components of the branch-and-cut algorithm, such as branching strategies, cut generation schemes, and primal heuristics. We present our computational experiences with the algorithm for the problem of minimizing the total weighted completion time on a single machine subject to release dates.

Keywords: scheduling; separation; branch-out-cut (search for similar items in EconPapers)
Date: 1996-04-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1996.html (text/html)

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:cor:louvco:1996016

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().