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 to optimise task completion time, energy efficiency and system reliability. The dynamic nature of networks also means that the optimal schedule is subject to change over time. The heterogeneity and variability in network design also complicate the translation of setups from one network to another. Discrete Particle Swarm Optimisation (DPSO) is a metaheuristic 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. The 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 completion time. 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 with regards to usability in 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.