An exact method for the bi-objective one-machine problem with maximum lateness and unit family setup cost objectives

Artigues, Christian; Jozefowiez, Nicolas; Aloulou, Mohamed Ali

Artigues, Christian; Jozefowiez, Nicolas; Aloulou, Mohamed Ali (2010), An exact method for the bi-objective one-machine problem with maximum lateness and unit family setup cost objectives, ISCO International Symposium on Combinatorial Optimization, 2010-03, Hammamet, Tunisie

Type

Communication / Conférence

External document link

http://hal.archives-ouvertes.fr/hal-00492202/fr/

Date

2010

Conference title

ISCO International Symposium on Combinatorial Optimization

Conference date

2010-03

Conference city

Hammamet

Conference country

Tunisie

Journal name

Electronic Notes in Discrete Mathematics

Volume

Publisher

Elsevier

Pages

1233-1240

Abstract (EN)

This paper deals with an NP-hard bi-objective one-machine problem with ready times involving maximum lateness and unit family setup cost objectives. Considering separately both objectives, the maximum lateness one-machine problem is also NP-hard but efficiently solved by Carlier's algorithm while the unit family setup cost one machine-problem with two families can be solved in polynomial timeby Darte's algorithm, even when precedence constraints are considered. Under the epsilon (Porson)-constraint framework we propose a branch-and-bound method to minimize the first objective with a given upper bound on the second.

Subjects / Keywords

bi-objective one-machine scheduling; maximum lateness; unit family setup costs; branch-and-bound