In this study, we consider a scheduling environment with m(m ≥ 1) parallel machines. The set of jobs to schedule is divided into K disjoint subsets. Each subset of jobs is associated with one agent. The K agents compete to perform their jobs on common resources. The objective is to find a schedule that minimizes a global objective function f 0, while maintaining the regular objective function of each agent, f k, at a level no greater than a fixed value, εk (fk ∈ {fkmax, ∑fk}, k = 0, ..., K). This problem is a multi-agent scheduling problem with a global objective function. In this study, we consider the case with preemption and the case without preemption. If preemption is allowed, we propose a polynomial time algorithm based on a network flow approach for the unrelated parallel machine case. If preemption is not allowed, we propose some general complexity results and develop dynamic programming algorithms.
Keywords: scheduling, multi-agent, complexity, dynamic programming
@article{RO_2014__48_2_255_0,
author = {Sadi, F. and Soukhal, A. and Billaut, J.-C.},
title = {Solving multi-agent scheduling problems on parallel machines with a global objective function},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {255--269},
year = {2014},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
doi = {10.1051/ro/2014005},
mrnumber = {3264378},
zbl = {1295.90012},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014005/}
}
TY - JOUR AU - Sadi, F. AU - Soukhal, A. AU - Billaut, J.-C. TI - Solving multi-agent scheduling problems on parallel machines with a global objective function JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2014 SP - 255 EP - 269 VL - 48 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014005/ DO - 10.1051/ro/2014005 LA - en ID - RO_2014__48_2_255_0 ER -
%0 Journal Article %A Sadi, F. %A Soukhal, A. %A Billaut, J.-C. %T Solving multi-agent scheduling problems on parallel machines with a global objective function %J RAIRO - Operations Research - Recherche Opérationnelle %D 2014 %P 255-269 %V 48 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014005/ %R 10.1051/ro/2014005 %G en %F RO_2014__48_2_255_0
Sadi, F.; Soukhal, A.; Billaut, J.-C. Solving multi-agent scheduling problems on parallel machines with a global objective function. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 255-269. doi: 10.1051/ro/2014005
Cité par Sources :