An exact approach for scheduling jobs with regular step cost functions on a single machine - Mines Saint-Étienne Access content directly
Journal Articles Computers and Operations Research Year : 2012

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.

Dates and versions

emse-00613039 , version 1 (02-08-2011)

Identifiers

Cite

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, 2012, 39, pp.1033-1043. ⟨10.1016/j.cor.2011.06.006⟩. ⟨emse-00613039⟩
68 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More