An exact approach for scheduling jobs with regular step cost functions on a single machine

Abstract : This paper studies a single machine scheduling problem whose objective is to minimize a regular step total cost function. Lower and upper bounds, obtained from linear and Lagrangean relaxations of di erent Integer Linear Programming formulations, are compared. A dedicated exact approach is presented, based on a Lagrangean relaxation. It consists of finding a Constrained Shortest Path in a specific graph designed to embed a dominance property. Filtering rules are developed for this approach in order to reduce the size of the graph, and the problem is solved by successively removing infeasible paths from the graph. Numerical experiments are conducted to evaluate the lower and upper bounds. Moreover, the exact approach is compared with a standard solver and a naive branch-and-bound algorithm.
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00613039
Contributor : Stéphane Dauzère-Pérès <>
Submitted on : Tuesday, August 2, 2011 - 11:48:40 AM
Last modification on : Saturday, March 23, 2019 - 1:22:47 AM

Identifiers

Citation

Boris Detienne, Stéphane Dauzère-Pérès, Claude Yugma. An exact approach for scheduling jobs with regular step cost functions on a single machine. Computers and Operations Research, Elsevier, 2012, 39, pp.1033-1043. ⟨10.1016/j.cor.2011.06.006⟩. ⟨emse-00613039⟩

Share

Metrics

Record views

164