A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

详细信息    查看全文

• 作者：Kejun Zhao ; Xiwen Lu ; Manzhan Gu
• 关键词：Multi ; agent scheduling ; Identical machines ; Makespan ; Approximation algorithm ; Performance ratio vector
• 刊名：Journal of Scheduling
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：19
• 期：1
• 页码：21-31
• 全文大小：500 KB
• 参考文献：Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problem with two competing agents. Operations Research, 52, 229–242.CrossRef
  Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.CrossRef
  Agnetis, A., Pascale, G., & Pacciarelli, D. (2009). A Lagrangian approach to single-machine scheduling problems with two competing agents. Journal of Scheduling, 12, 401–415.CrossRef
  Agnetis, A., Billaut, J. C., Gawiejnowicz, S., Pacciarelli, D., & Soukhal, A. (2014). Multiagent scheduling—models and algorithms, Springer, Berlin. ISBN 978-3-642-41879-2.
  Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281.CrossRef
  Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609.CrossRef
  Fan, B. Q., Cheng, T. C. E., Li, S. S., & Feng, Q. (2013). Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 16, 261–271.CrossRef
  Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, 416–429.CrossRef
  Lee, K., Choi, B.-C., Leung, J. Y.-T., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109, 913–917.CrossRef
  Leung, J. Y.-T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.CrossRef
  Li, S., & Yuan, J. J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15, 629–640.CrossRef
  Pinedo, M. L. (2010). Scheduling (4th ed.). Berlin: Springer.
  Saule, E., & Trystram, D. (2009). Multi-users scheduling in parallel systems. In Proceedings of IEEE International Parallel and Distributed Processing Symposium 2009, Washington, DC, 1C9.
  
• 作者单位：Kejun Zhao (1)
  Xiwen Lu (1)
  Manzhan Gu (2)
  
  1. Department of Mathematics, School of Science, East China University of Science and Technology, Shanghai, 200237, China
  2. School of Mathematics, Shanghai University of Finance and Economics, Shanghai, 200433, China
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Calculus of Variations and Optimal Control
  Optimization
  Artificial Intelligence and Robotics
  Production and Logistics
  
• 出版者：Springer Netherlands
• ISSN：1099-1425

文摘

This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent’s objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than \(i+\frac{1}{6}\) for the ith \((i=1,2,\ldots ,g)\) completed agent. Moreover, we show that the performance ratio is tight. Keywords Multi-agent scheduling Identical machines Makespan Approximation algorithm Performance ratio vector