We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Solving multi-agent scheduling problems on parallel machines with a global objective function.
- Authors
Sadi, F.; Soukhal, A.; Billaut, J.-C.
- Abstract
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 f0, while maintaining the regular objective function of each agent, fk, 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.
- Subjects
MACHINE theory; MULTIAGENT systems; COMPUTER scheduling; PROBLEM solving; MATHEMATICAL functions; DYNAMIC programming
- Publication
RAIRO -- Operations Research, 2014, Vol 48, Issue 2, p255
- ISSN
0399-0559
- Publication type
Article
- DOI
10.1051/ro/2014005