|
 |
ISSN 1996-1065 [Online]
ISSN 1818-1139 [PRINT] |
|
|
Special Issue October 2008 |
| Title: |
Game Theoretic Multi-Agent Systems Scheduler for Parallel
Machines |
| Authors: |
Elisha T. O. Opiyo, Erick Ayienga, Katherine Getao, & William Okello-Odongo,
Bernard Manderick, & Ann Nowé |
| Published: |
© IJCIR Special Issue October 2008, PP. 21-27 |
| Language: | English |
Abstract:
This paper considers the scheduling of n independent jobs on m non-identical machines using the ideas
from game theory and multi-agent systems. The values of n and m are fixed at 30 and 6 respectively giving
a schedule space with a dimension of approximately 1023 schedules. The agents are used to represent the
jobs and they select machines on which the jobs should be processed, resulting into schedules. The
schedules that are generated are evaluated using the makespan which is the total time taken for all the jobs
to be processed. The makespan of the schedules that are generated vary when the agents that represent the
jobs change the way they make their selection decisions. The agent selection policies that are investigated
in this paper include pure random choice, potential game strategy and dispersion game strategy. The results
that are obtained show that the random choice strategy and the potential game strategy generate the
empirical best schedules by chance. The dispersion game strategy however is shown to converge very
quickly to a stable schedule type whose best makespan value is between 3.1 to 3.4 times larger than the
empirical best schedule. The main contributions in this paper include generating schedules in a concrete
schedule space using ideas from game theory and multi-agent systems and the results that are obtained..View full Article
| General Terms: |
Agents, Scheduling, Parallel Machines
Additional Key Words and Phrases: Game theory; grid computers
|
| Categories and Subject Descriptors: | [Artificial Intelligence Applications]:- Multi-Agent Systems; |
|
|
|
|
