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

Abstract

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

How to cite

top

Sadi, 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. [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. [2] A. Agnetis, D. Pacciarelli and A. Pacifici, Multi-agent sincle machine scheduling. Ann. Oper. Res.150 (2007) 3–15. Zbl1144.90375MR2304126
  3. [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. [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. [5] K.R. Baker and J.C. Smith, A multiple-criteria model for machine scheduling. J. Scheduling6 (2003) 7–16. Zbl1154.90406MR1999987
  6. [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. [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. [8] P. Brucker, Scheduling algorithms. Fifth Edition. Springer (2005). Zbl1126.90001
  9. [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. [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. [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. [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. [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. [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. [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. [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. [17] H. Hoogeveen, Multicriteria scheduling. Eur. J. Oper. Res.167 (2005) 59–623. Zbl1154.90458MR2157061
  18. [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. [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. [20] E.L. Lawler, Optimal sequencing of a single machine subject to precedence constraints. Manage. Sci.19 (1973) 544–546. Zbl0254.90039
  21. [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. [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. [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. [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. [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. [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. [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. [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. [29] V. T’kindt and J.-C. Billaut, Multicriteria scheduling. Second Edition. Springer (2006). Zbl1126.90002
  30. [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. [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 ?

top

You must be logged in to post comments.