Title | ||
---|---|---|
Solving multi-agent scheduling problems on parallel machines with a global objective function. |
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 f, while maintaining the regular objective function of each agent, f(k), at a level no greater than a fixed value, epsilon(k) (f(k) E {A., E 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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1051/ro/2014005 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Scheduling,multi-agent,complexity,dynamic programming | Flow network,Dynamic programming,Mathematical optimization,Preemption,Disjoint sets,Job shop scheduling,Computer science,Scheduling (computing),Time complexity | Journal |
Volume | Issue | ISSN |
48 | 2 | 0399-0559 |
Citations | PageRank | References |
4 | 0.42 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
F. Sadi | 1 | 4 | 0.76 |
Ameur Soukhal | 2 | 119 | 10.15 |
Jean-charles Billaut | 3 | 273 | 21.65 |