Autonomous scheduling with unbounded and bounded agents

Ch. Yadati, C. Witteveen, Yingqian Zhang, M. Wu, J.A. Poutré, La

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

Autonomous scheduling deals with the problem - how to enable agents to schedule a set of interdependent tasks in such a way that whatever schedule they choose for their tasks, the individual schedules always can be merged into a global feasible schedule? Unlike the traditional approaches to distributed scheduling we do not enforce a fixed schedule to every participating agent. Instead we guarantee flexibility by offering a set of schedules to choose from in such a way that every agent can choose its own schedule independently from the others. We show that in case of agents with unbounded concurrency, optimal make-span can be guaranteed. Whenever the agents have bounded concurrency optimality cannot be guaranteed, but we present an approximation algorithm that ensures a constant make-span ratio
Original languageEnglish
Title of host publicationMultiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings
EditorsR. Bergmann, G. Lindemann, S. Kirn, M. Pechoucek
Place of PublicationBerlin
PublisherSpringer
Pages195-206
ISBN (Print)978-3-540-87804-9
DOIs
Publication statusPublished - 2008
Eventconference; Multiagent system technologies : 6th German conference, MATES 2008; 2008-09-23; 2008-09-26 -
Duration: 23 Sep 200826 Sep 2008

Publication series

NameLecture Notes in Computer Science
Volume5244
ISSN (Print)0302-9743

Conference

Conferenceconference; Multiagent system technologies : 6th German conference, MATES 2008; 2008-09-23; 2008-09-26
Period23/09/0826/09/08
OtherMultiagent system technologies : 6th German conference, MATES 2008

Fingerprint

Schedule
Makespan
Concurrency
Approximation algorithms
Optimality
Guarantee

Cite this

Yadati, C., Witteveen, C., Zhang, Y., Wu, M., & Poutré, La, J. A. (2008). Autonomous scheduling with unbounded and bounded agents. In R. Bergmann, G. Lindemann, S. Kirn, & M. Pechoucek (Eds.), Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings (pp. 195-206). (Lecture Notes in Computer Science; Vol. 5244). Berlin: Springer. https://doi.org/10.1007/978-3-540-87805-6_18
Yadati, Ch. ; Witteveen, C. ; Zhang, Yingqian ; Wu, M. ; Poutré, La, J.A. / Autonomous scheduling with unbounded and bounded agents. Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings. editor / R. Bergmann ; G. Lindemann ; S. Kirn ; M. Pechoucek. Berlin : Springer, 2008. pp. 195-206 (Lecture Notes in Computer Science).
@inproceedings{08ce74d0da2a4479912fedca6e4f5a7c,
title = "Autonomous scheduling with unbounded and bounded agents",
abstract = "Autonomous scheduling deals with the problem - how to enable agents to schedule a set of interdependent tasks in such a way that whatever schedule they choose for their tasks, the individual schedules always can be merged into a global feasible schedule? Unlike the traditional approaches to distributed scheduling we do not enforce a fixed schedule to every participating agent. Instead we guarantee flexibility by offering a set of schedules to choose from in such a way that every agent can choose its own schedule independently from the others. We show that in case of agents with unbounded concurrency, optimal make-span can be guaranteed. Whenever the agents have bounded concurrency optimality cannot be guaranteed, but we present an approximation algorithm that ensures a constant make-span ratio",
author = "Ch. Yadati and C. Witteveen and Yingqian Zhang and M. Wu and {Poutr{\'e}, La}, J.A.",
year = "2008",
doi = "10.1007/978-3-540-87805-6_18",
language = "English",
isbn = "978-3-540-87804-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "195--206",
editor = "R. Bergmann and G. Lindemann and S. Kirn and M. Pechoucek",
booktitle = "Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings",
address = "Germany",

}

Yadati, C, Witteveen, C, Zhang, Y, Wu, M & Poutré, La, JA 2008, Autonomous scheduling with unbounded and bounded agents. in R Bergmann, G Lindemann, S Kirn & M Pechoucek (eds), Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings. Lecture Notes in Computer Science, vol. 5244, Springer, Berlin, pp. 195-206, conference; Multiagent system technologies : 6th German conference, MATES 2008; 2008-09-23; 2008-09-26, 23/09/08. https://doi.org/10.1007/978-3-540-87805-6_18

Autonomous scheduling with unbounded and bounded agents. / Yadati, Ch.; Witteveen, C.; Zhang, Yingqian; Wu, M.; Poutré, La, J.A.

Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings. ed. / R. Bergmann; G. Lindemann; S. Kirn; M. Pechoucek. Berlin : Springer, 2008. p. 195-206 (Lecture Notes in Computer Science; Vol. 5244).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Autonomous scheduling with unbounded and bounded agents

AU - Yadati, Ch.

AU - Witteveen, C.

AU - Zhang, Yingqian

AU - Wu, M.

AU - Poutré, La, J.A.

PY - 2008

Y1 - 2008

N2 - Autonomous scheduling deals with the problem - how to enable agents to schedule a set of interdependent tasks in such a way that whatever schedule they choose for their tasks, the individual schedules always can be merged into a global feasible schedule? Unlike the traditional approaches to distributed scheduling we do not enforce a fixed schedule to every participating agent. Instead we guarantee flexibility by offering a set of schedules to choose from in such a way that every agent can choose its own schedule independently from the others. We show that in case of agents with unbounded concurrency, optimal make-span can be guaranteed. Whenever the agents have bounded concurrency optimality cannot be guaranteed, but we present an approximation algorithm that ensures a constant make-span ratio

AB - Autonomous scheduling deals with the problem - how to enable agents to schedule a set of interdependent tasks in such a way that whatever schedule they choose for their tasks, the individual schedules always can be merged into a global feasible schedule? Unlike the traditional approaches to distributed scheduling we do not enforce a fixed schedule to every participating agent. Instead we guarantee flexibility by offering a set of schedules to choose from in such a way that every agent can choose its own schedule independently from the others. We show that in case of agents with unbounded concurrency, optimal make-span can be guaranteed. Whenever the agents have bounded concurrency optimality cannot be guaranteed, but we present an approximation algorithm that ensures a constant make-span ratio

U2 - 10.1007/978-3-540-87805-6_18

DO - 10.1007/978-3-540-87805-6_18

M3 - Conference contribution

SN - 978-3-540-87804-9

T3 - Lecture Notes in Computer Science

SP - 195

EP - 206

BT - Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings

A2 - Bergmann, R.

A2 - Lindemann, G.

A2 - Kirn, S.

A2 - Pechoucek, M.

PB - Springer

CY - Berlin

ER -

Yadati C, Witteveen C, Zhang Y, Wu M, Poutré, La JA. Autonomous scheduling with unbounded and bounded agents. In Bergmann R, Lindemann G, Kirn S, Pechoucek M, editors, Multiagent system technologies : 6th German conference, MATES 2008 : Kaiserslautern, Germany, September 23-26, 2008 : proceedings. Berlin: Springer. 2008. p. 195-206. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-87805-6_18