# Solving multi-agent scheduling problems on parallel machines with a global objective function

F. Sadi; A. Soukhal; J.-C. Billaut

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 2, page 255-269
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topSadi, F., Soukhal, A., and Billaut, J.-C.. "Solving multi-agent scheduling problems on parallel machines with a global objective function." RAIRO - Operations Research - Recherche Opérationnelle 48.2 (2014): 255-269. <http://eudml.org/doc/275097>.

@article{Sadi2014,

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.},

author = {Sadi, F., Soukhal, A., Billaut, J.-C.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {scheduling; multi-agent; complexity; dynamic programming},

language = {eng},

number = {2},

pages = {255-269},

publisher = {EDP-Sciences},

title = {Solving multi-agent scheduling problems on parallel machines with a global objective function},

url = {http://eudml.org/doc/275097},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 2

SP - 255

EP - 269

AB - 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.

LA - eng

KW - scheduling; multi-agent; complexity; dynamic programming

UR - http://eudml.org/doc/275097

ER -

## References

top- [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. Zbl1144.90375MR2304126
- [3] A. Agnetis, P. Mirchandani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents. Oper. Res.52 (2004) 229–242. Zbl1165.90446MR2066398
- [4] A. Agnetis, G. Pascale and D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents. J. Scheduling12 (2010) 401–415. Zbl1185.90063
- [5] K.R. Baker and J.C. Smith, A multiple-criteria model for machine scheduling. J. Scheduling6 (2003) 7–16. Zbl1154.90406MR1999987
- [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. Zbl1176.90193MR2522643
- [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). Zbl1165.90009
- [8] P. Brucker, Scheduling algorithms. Fifth Edition. Springer (2005). Zbl1126.90001
- [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. Zbl1100.68007MR2259636
- [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. Zbl1129.90023MR2386750
- [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. Zbl0455.90043MR629191
- [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. Scheduling14 (2011) 471–481. Zbl1280.90042
- [15] D. Elvikis and V. T’kindt, Two-agent scheduling on uniform parallel machines with min-max criteria. Ann. Oper. Res. (2012) 1–16. Zbl1296.90043
- [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. Zbl0411.90044MR558574
- [17] H. Hoogeveen, Multicriteria scheduling. Eur. J. Oper. Res.167 (2005) 59–623. Zbl1154.90458MR2157061
- [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. Zbl0266.05114MR337699
- [19] N. Huynh Tuong, A. Soukhal and J.-C. Billaut, Single-machine multi-agent scheduling problems with a global objective function. J. Scheduling15 (2012) 311–321. Zbl1280.90074MR2925022
- [20] E.L. Lawler, Optimal sequencing of a single machine subject to precedence constraints. Manage. Sci.19 (1973) 544–546. Zbl0254.90039
- [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. Zbl1205.68516MR2541970
- [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. Zbl1233.90163MR2674809
- [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. Zbl1217.90108MR2763860
- [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. Zbl1103.90048MR2254324
- [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). Zbl1126.90002
- [30] G. Wan, J.-Y. Leung and M. Pinedo, Scheduling two agents with controllable processing times. Eur. J. Oper. Res.205 (2007) 528–539. Zbl1188.90114MR2602759
- [31] J. Yuan, W.-P. Shang and Q. Feng, A note on the scheduling which two families of jobs. J. Scheduling8 (2005) 537–542. Zbl1123.90040MR2179410

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.