Show simple item record

dc.contributor.supervisor Kinsner, Witold (Electrical and Computer Engineering) en_US
dc.contributor.author Schor, Dario
dc.date.accessioned 2013-08-02T18:58:16Z
dc.date.available 2013-08-02T18:58:16Z
dc.date.issued 2013-08-02
dc.identifier.uri http://hdl.handle.net/1993/22020
dc.description.abstract Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications. en_US
dc.rights info:eu-repo/semantics/openAccess
dc.subject scheduling en_US
dc.subject evolutionary algorithms en_US
dc.subject particle swarm optimization en_US
dc.subject swarm intelligence en_US
dc.subject real-time systems en_US
dc.subject small satellite en_US
dc.title A Study of Particle Swarm Optimization Trajectories for Real-Time Scheduling en_US
dc.type info:eu-repo/semantics/masterThesis
dc.type master thesis en_US
dc.degree.discipline Electrical and Computer Engineering en_US
dc.contributor.examiningcommittee Ferens, Ken (Electrical and Computer Engineering) Ferguson, Philip (Magellan Aerospace Winnipeg) Gumel, Abba (Mathematics) en_US
dc.degree.level Master of Science (M.Sc.) en_US
dc.description.note October 2013 en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

View Statistics