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} (f^{k} ∈ {f^{k}_{max}, ∑f^{k}}, 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}, publisher = {EDP-Sciences}, volume = {48}, number = {2}, year = {2014}, doi = {10.1051/ro/2014005}, mrnumber = {3264378}, zbl = {1295.90012}, language = {en}, url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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, Volume 48 (2014) no. 2, pp. 255-269. doi : 10.1051/ro/2014005. http://archive.numdam.org/articles/10.1051/ro/2014005/

[1] Nondominated schedules for a job-shop with two competing users. Comput. Math. Organ. Theor. 6 (2000) 191-217.

, , and ,[2] Multi-agent sincle machine scheduling. Ann. Oper. Res. 150 (2007) 3-15. | MR | Zbl

, and ,[3] Scheduling problems with two competing agents. Oper. Res. 52 (2004) 229-242. | MR | Zbl

, , and ,[4] A Lagrangian approach to single-machine scheduling problems with two competing agents. J. Scheduling 12 (2010) 401-415. | Zbl

, and ,[5] A multiple-criteria model for machine scheduling. J. Scheduling 6 (2003) 7-16. | MR | Zbl

and ,[6] Scheduling interfering job sets on parallel machines. Eur. J. Oper. Res. 199 (2009) 55-67. | MR | Zbl

, , and ,[7] Handbook on scheduling: From Theory to Applications. International handbooks on information systems. Springer (2007). | Zbl

, , , and ,[8] Scheduling algorithms. Fifth Edition. Springer (2005). | Zbl

,[9] Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor. Comput. Sci. 362 (2006) 273-281. | MR | Zbl

, , ,[10] Multi-agent scheduling on a single machine with max-form criteria. Eur. J. Oper. Res. 188 (2008) 603-609. | MR | Zbl

, and ,[11] A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Comput. Ind. Engrg. 60 (2001) 534-541.

, , , and ,[12] Preemptive scheduling of independent jobs with release and due times on open, flow and job shops. Oper. Res. 29 (1981) 511-522. | MR | Zbl

and ,[13] Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms. In Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS), Anchorage, AL, USA, IEEE Comput. Soc. (2011) 1177-1186.

, , and ,[14] Scheduling two interfering job sets on uniform parallel machines with makespan and cost functions. J. Scheduling 14 (2011) 471-481. | Zbl

, and ,[15] Two-agent scheduling on uniform parallel machines with min-max criteria. Ann. Oper. Res. (2012) 1-16. | Zbl

and ,[16] Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287-326. | MR | Zbl

, , and ,[17] Multicriteria scheduling. Eur. J. Oper. Res. 167 (2005) 59-623. | MR | Zbl

,[18] A n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 (1973) 22-231. | MR | Zbl

and ,[19] Single-machine multi-agent scheduling problems with a global objective function. J. Scheduling 15 (2012) 311-321. | MR | Zbl

, and ,[20] Optimal sequencing of a single machine subject to precedence constraints. Manage. Sci. 19 (1973) 544-546. | Zbl

,[21] Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Inform. Process. Lett. 16 (2009) 913-917. | MR | Zbl

, , and ,[22] S.-k. Chen and C.-C. Wu, Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem. Exp. Syst. Appl. 37 (2010) 6594-6601.

,[23] Competitive two agent scheduling and its applications. Oper. Res. 58 (2007) 458-469. | MR | Zbl

, and ,[24] Two-agent single-machine scheduling problems under increasing linear deterioration. Appl. Math. Model. 35 (2011) 2290-2296. | MR | Zbl

, and ,[25] Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. Eur. J Oper. Res. 18 (2005) 1501-1518. | MR | Zbl

, and ,[26] Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria. Exp. Syst. Appl. 37 (2010) 5951-5959.

, and ,[27] Parallel machine scheduling with interfering jobs, in 8th International Conference on Multiple Objective and Goal Programming (MOPGP'08), Portsmouth, UK (2008).

, and ,[28] Méthodes exactes et approchées pour l'ordonnancement de travaux interférant (in French), in Int. Symposium on Oper. Res., ISOR'08 Algers, Algeria (2008).

, and ,[29] Multicriteria scheduling. Second Edition. Springer (2006). | Zbl

and ,[30] Scheduling two agents with controllable processing times. Eur. J. Oper. Res. 205 (2007) 528-539. | MR | Zbl

, and ,[31] A note on the scheduling which two families of jobs. J. Scheduling 8 (2005) 537-542. | MR | Zbl

, and ,*Cited by Sources: *