nach oben

Journal of Scheduling

Erschienen in:

01.02.2016

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

verfasst von: Kejun Zhao, Xiwen Lu, Manzhan Gu

Erschienen in: Journal of Scheduling | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel A survey of offline algorithms for energy minimization under deadline constraints

Nächster Artikel MP or not MP: that is the question

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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.

Titel: A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines
verfasst von: Kejun Zhao
Xiwen Lu
Manzhan Gu
Publikationsdatum: 01.02.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2016
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0460-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Journal of Scheduling (2016)

A graph coloring approach to the deployment scheduling and unit assignment problem

A mixed integer programming approach to multi-skilled workforce scheduling

MP or not MP: that is the question

A genetic algorithm for the robust resource leveling problem

A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

Premium Partner