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.

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.

DOI : 10.1051/ro/2014005
Classification : 90C39
Mots-clés : 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://www.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://www.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://www.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, Tome 48 (2014) no. 2, pp. 255-269. doi : 10.1051/ro/2014005. http://www.numdam.org/articles/10.1051/ro/2014005/

[1] A. Agnetis, P. Mirchandani, D. Pacciarelli and A. Pacifici, Nondominated schedules for a job-shop with two competing users. Comput. Math. Organ. Theor. 6 (2000) 191-217.

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

[3] A. Agnetis, P. Mirchandani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents. Oper. Res. 52 (2004) 229-242. | MR | Zbl

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

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

[6] H. Balasubramanian, J. Fowler, A. Keha and M. Pfund, Scheduling interfering job sets on parallel machines. Eur. J. Oper. Res. 199 (2009) 55-67. | MR | Zbl

[7] J. Blazewicz, K.H. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Handbook on scheduling: From Theory to Applications. International handbooks on information systems. Springer (2007). | Zbl

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

[9] T.C.E. Cheng, C.T. Ng, J.-J. Yuan, 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] T.C.E. Cheng, C.T. Ng and J.-J. Yuan, Multi-agent scheduling on a single machine with max-form criteria. Eur. J. Oper. Res. 188 (2008) 603-609. | MR | Zbl

[11] T.C.E. Cheng, S.-R. Cheng, W.-H. Wu, P.-H. Hsu and C.-C. Wu, A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Comput. Ind. Engrg. 60 (2001) 534-541.

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

[13] D. Cordeiro, P.-F. Dutot, G. Mounié and D. Trystram, 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.

[14] D. Elvikis, H.W. Hamacher and V. T'Kindt, Scheduling two interfering job sets on uniform parallel machines with makespan and cost functions. J. Scheduling 14 (2011) 471-481. | Zbl

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

[16] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287-326. | MR | Zbl

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

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

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

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

[21] K. Lee, B.-C. Choi, J.Y.-T. Leung and M. Pinedo, Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Inform. Process. Lett. 16 (2009) 913-917. | MR | Zbl

[22] W.-C. Lee, 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] J.Y.-T. Leung, M. Pinedo and G. Wan, Competitive two agent scheduling and its applications. Oper. Res. 58 (2007) 458-469. | MR | Zbl

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

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

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

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

[28] A. Soukhal, N. Huynh Tuong and Z. Dao, 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).

[29] V. T'Kindt and J.-C. Billaut, Multicriteria scheduling. Second Edition. Springer (2006). | Zbl

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

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

Cité par Sources :