SOLVING MULTI-AGENT SCHEDULING PROBLEMS ON PARALLEL MACHINES WITH A GLOBAL OBJECTIVE FUNCTION

作者：Sadi F^*; Soukhal A; Billaut J C

来源：RAIRO - Operations Research, 2014, 48(2): 255-269.

DOI：10.1051/ro/2014005

• Scheduling
• multi-agent
• complexity
• dynamic programming

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.

• 出版日期2014-6