A hybrid Tabu sample-sort simulated annealing approach for solving distributed scheduling problem

Abstract

The distributed scheduling problem has been considered as the allocation of a task to various machines in such a way that these machines are situated in different factories and these factories are geographically distributed. Therefore distributed scheduling has fulfilled various objectives, such as allocation of task to the factories and machines in such a manner that it can utilise the maximum resources. The objective of this paper is to minimise the makespan in each factory by considering the transportation time between the factories. In this paper, to address such a problem of scheduling in distributed manufacturing environment, a novel algorithm has been developed. The proposed algorithm gleans the ideas both from Tabu search and sample sort simulated annealing. A new algorithm known as hybrid Tabu sample-sort simulated annealing (HTSSA) has been developed and it has been tested on the numerical example. To reveal the supremacy of the proposed algorithm over simple SSA and Tabu search, more computational experiments have also been performed on 10 randomly generated datasets.

Keywords:

• Tabu-search
• sample sort simulated annealing (SSA)
• distributed scheduling
• makespan

Acknowledgements

The work described in this paper was substantially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative region, China (Project No. PolyU 510311). The authors also would like to thank The Hong Kong Polytechnic University Research Committee for financial and technical support.