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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, 39, pp.1033-1043. 〈10.1016/j.cor.2011.06.006〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00613039
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : mardi 2 août 2011 - 11:48:40
Dernière modification le : mercredi 11 octobre 2017 - 01:08:04

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

85