A column generation algorithm for common due date scheduling

J.M. Akker, van den, J.A. Hoogeveen, S.L. Velde, van de

Research output: Book/ReportReportAcademic

43 Downloads (Pure)


We consider the single-machine problem of scheduling n jobs to minimize the total weighted deviation from a given common due date where the weights for early and tardy completion are asymmetric. First, we assume that the common due date is large. We formulate this problem as an integer linear program with an exponential number of variables and present a column generation algorithm to solve efficiently the linear programming relaxation. Our comprehensive computational study shows that this lower bounding approach performs exceptionally well on randomly generated instances: the solution to the linear program was integral for all randomly generated instances. In this fashion we were able to solve instances with up to 60 jobs. Our computational results suggest that the integrality of the optimal solution of the linear programming relaxation is a structural property. We show by example that the integrality gap can be positive however. To start up the column generation algorithm we need a heuristic to generate reasonably good solutions. A simple multi-start iterative improvement algorithm turned out to have a compelling empirical performance: it found an optimal solution for each of our randomly generated instances. We conclude with showing how the column generation approach can be adapted to deal with a small common due date.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages16
Publication statusPublished - 1997

Publication series

NameMemorandum COSOR
ISSN (Print)0926-4493


Dive into the research topics of 'A column generation algorithm for common due date scheduling'. Together they form a unique fingerprint.

Cite this