Non-disjoint Multi-agent Scheduling Problem on Identical Parallel Processors

详细信息    查看全文

• 关键词：Multicriteria optimization ; Multiagent scheduling ; Parallel processors ; Heuristics ; Dynamic programming ; Linear mathematical programming
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10018
• 期：1
• 页码：400-414
• 全文大小：313 KB
• 参考文献：1.Agnetis, A., Mirchandani, P., Pacciarelli, D., Pacifici, A.: Non-dominated schedules for a job-shop with two competing users. Comput. Math. Organ. Theory 6(2), 191–217 (2000)CrossRef
  2.Agnetis, A., Mirchandani, P., Pacciarelli, D., Pacifici, A.: Scheduling problems with two competing agents. Oper. Res. 52, 229–242 (2004)MathSciNet CrossRef MATH
  3.Agnetis, A., Billaut, J.-C., Gawiejnowicz, S., Pacciarelli, D., Soukhal, A.: Multiagent Scheduling Models and Algorithms. Springer, Heidelberg (2014). 271 pCrossRef MATH
  4.Baker, K.R., Smith, J.C.: A multiple-criteria model for machine scheduling. J. Sched. 6, 7–16 (2003)MathSciNet CrossRef MATH
  5.Balasubramanian, H., Fowler, J., Keha, A., Pfund, M.: Scheduling interfering job sets on parallel machines. Eur. J. Oper. Res. 199, 55–67 (2009)MathSciNet CrossRef MATH
  6.Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J.: Handbook on Scheduling: From Theory to Applications. International Handbooks on Information Systems. Springer, Heidelberg (2007)MATH
  7.Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2002)CrossRef
  8.Huynh Tuong, N., Soukhal, A., Billaut, J.C.: Single-machine multi-agent scheduling problems with a global objective function. J. Sched. 15(3), 311–321 (2012)MathSciNet CrossRef MATH
  9.Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. Associ. Comput. Mach. 22(4), 469–476 (1975)MathSciNet CrossRef MATH
  10.Ng, C.T., Cheng, T.C.E., Yuan, J.J.: A note on the complexity of the problem of two-agent scheduling on a single machine. J. Comb. Optim. 12(4), 387–394 (2006)MathSciNet CrossRef MATH
  11.Peha, J.M.: Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time. Comput. Oper. Res. 22(10), 1089–1100 (1995)CrossRef MATH
  12.Sadi, F., Soukhal, A., Billaut, J.-C.: Solving multi-agent scheduling problems on parallel machines with a global objective function. RAIRO - Oper. Res. 48(2), 225–269 (2014)MathSciNet CrossRef MATH
  
• 作者单位：F. Sadi (19) (20)
  T. Van Ut (19) (21)
  N. Huynh Tuong (22)
  A. Soukhal (19)
  
  19. Laboratory of Computer Science (EA 6300), Team Recherche Opérationnelle, Ordonnacement et Transport ROOT ERL-CNRS 6305), 64 Avenue Jean Portalis, 37200, Université François Rabelais Tours, France
  20. INSA Centre Val de Loire, 3 rue de la chocolaterie, 41000, Blois, France
  21. Can Tho University of Technology (CTUT), 256 Nguyen Van Cu Street, Ninh Kieu District, Can Tho City, Vietnam
  22. Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, VNU-HCM, 268 Ly Thuong Kiet Street, Ho Chi Minh City, 740500, Vietnam
  
• 丛书名：Future Data and Security Engineering
• ISBN：978-3-319-48057-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10018

文摘

Scheduling problems in which agents (users, customers, application masters, resource manager, etc.) have to share the same set(s) of resources are at the frontier of combinatorial optimization and cooperative game theory. This paper deals with scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on two common identical parallel machines. Each agent aims at minimizing a certain objective function that depends on the completion times of its jobs only. The objective functions we consider in our study are makespan and number of tardy jobs. The agents may share some jobs and this problem is called non-disjoint multi-agent scheduling problem [3]. Finding the optimal solution for one agent with a constraint on the other agent’s cost function is known to be \(\mathcal {NP}\)-hard. To obtain best compromise solutions for each agent, we propose polynomial and pseudo-polynomial heuristics. Two mixed integer linear programming models are developed to calculate exact non-dominated solutions. Experimental results are conducted to measure the solutions quality given by heuristics.