Hampus Karlberg

Task Scheduling Using Discrete particle Swarm Optimisation

Abstract

Optimising task allocation in networked systems helps in utilising available resources. When working with unstable and heterogeneous networks, task scheduling can be used optimise task completion time, energy efficiency and system reliability. The dynamic nature of networks also mean that the optimal schedule is subject to change over time. The heterogeneity and variability in network design also complicate translation of setups from one network to another. Discrete Particle Swarm Optimisation (DPSO) is a meta heuristic that can be used to find solutions to task scheduling. This thesis will explore how DPSO can be used to optimise job scheduling in an unstable network. The purpose is to find solutions for networks like the ones used on trains. This in turn is done to facilitate trajectory planning calculations. Through the use of an artificial neural network we estimate job scheduling costs. These costs are then used by our DPSO meta heuristic to explore a solution space of potential scheduling. Our results focus on the optimisation of batch sizes in relation to network reliability and latency. We simulate a series of unstable and heterogeneous networks and compare performances. The baseline comparison is the case where scheduling is done by evenly distributing jobs at fixed sizes. The performance of the different approaches is then analysed in relation to usability in a real life scenarios on vehicles. Our results show a noticeable increase in performance within a wide range of network set-ups. This is at the cost of long search times for the DPSO algorithm. We conclude that under the right circumstances, the method can be used to significantly speed up distributed calculations at the cost of requiring significant ahead of time calculations. We recommend future explorations into DPSO starting states to speed up convergence as well as benchmarks of real life performance.