Skip to Main content Skip to Navigation
Journal articles

Approximating multi-objective scheduling problems

Abstract : In many practical situations, decisions are multi-objective by nature. In this paper, we propose a generic approach to deal with multi-objective scheduling problems (MOSPs). The aim is to determine the set of Pareto solutions that represent the interactions between the different objectives. Due to the complexity of MOSPs, an efficient approximation based on dynamic programming is developed. The approximation has a provable worst case performance guarantee. Even though the approximate Pareto set consists of fewer solutions, it represents a good coverage of the true set of Pareto solutions. We consider generic cost parameters that depend on the state of the system. Numerical results are presented for the time-dependent multi-objective knapsack problem, showing the value of the approximation in the special case when the state of the system is expressed in terms of time.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00830040
Contributor : Talbi El-Ghazali Connect in order to contact the contributor
Submitted on : Tuesday, June 4, 2013 - 12:23:36 PM
Last modification on : Thursday, January 20, 2022 - 5:27:54 PM

Identifiers

Citation

Said Dabia, El-Ghazali Talbi, Tom van Woensel, Ton de Kok. Approximating multi-objective scheduling problems. Computers and Operations Research, Elsevier, 2013, 40 (5), pp.1165-1175. ⟨10.1016/j.cor.2012.12.001⟩. ⟨hal-00830040⟩

Share

Metrics

Les métriques sont temporairement indisponibles