Assessing the level of centralisation in scheduling decisions: The role of hybrid approaches

Decentralised scheduling has been recently advocated as a promising alternative to overcome the difficulties of scheduling jobs in today’s complex and uncertain manufacturing scenarios using the traditional (i.e. centralised) approach consisting of developing a global schedule under the assumption that all necessary data are available and known in advance. In the decentralised approach, machines in the shop floor interact among them to negotiate the jobs to be processed according to a weighted combination of indicators that reflect the current shop floor status. While earlier works have shown the potential advantages of this approach as compared to the centralised one, often these studies are too specific to obtain more generalisable conclusions, since they focus on a single illustrative case study with a small number of jobs/machines, and conduct a limited comparison of both approaches. Furthermore, while its ability to capture current shop floor conditions makes decentralised scheduling more adaptative and flexible than its centralised counterpart, its local (myopic) nature results in a low performance under certain conditions. Therefore, another aspect worth of investigation is to study if a combination of both approaches could ideally result in a more efficient hybrid scheduling mechanism for a wider range of scenarios. Our paper aims at studying these two aspects. First, we compare the performance of centralised and decentralised approaches in a set of medium-sized job shop instances with different levels of processing times variability, and with the objective of minimising the makespan. Each approach is compared under their best conditions, i.e. the optimal deterministic solution for the centralised approach and the best weights for the decentralised one. Second, we propose a hybrid approach that uses the centralised solution as an additional indicator in the decentralised approach. The extensive computational experience carried out shows that the decentralised approach outperforms the centralised one for the scenarios with some degree of variability and that the proposed hybrid approach exhibits the best overall performance, being able to combine the advantages of both centralised and decentralised methods. The sensitivity of the decentralised and hybrid approaches to the coefficients that weight the different indicators is also investigated.