A cutting plane algorithm for the single machine scheduling problem with release times

G.L. Nemhauser, M.W.P. Savelsbergh

Onderzoeksoutput: Boek/rapportRapportAcademic

77 Downloads (Pure)

Samenvatting

We propose a mixed integer programming formulation for the single machine scheduling problem with release times and the objective of minimizing the weighted sum of the start times. The basic formulation involves start time and sequence determining variables, and lower bounds on the start times. Its linear programming relaxation solves problems in which all release times are equal. For the general problem, good lower bounds are obtained by adding additional valid inequalities that are violated by the solution to the linear programming relaxation. We report computational results and suggest some modifications based on including additional variables that are likely to give even better results.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's21
StatusGepubliceerd - 1991

Publicatie series

NaamMemorandum COSOR
Volume9105
ISSN van geprinte versie0926-4493

Vingerafdruk Duik in de onderzoeksthema's van 'A cutting plane algorithm for the single machine scheduling problem with release times'. Samen vormen ze een unieke vingerafdruk.

Citeer dit