The balance of autonomous and centralized control in scheduling problems

The scheduling of processes in a network is a core logistic challenge with a multitude of applications in our complex industrialized world. Often, scheduling decisions are based on incomplete and unreliable information. Here, a simple rule of ’more information, better decisions’ may no longer hold and heuristics balancing global and local information, or centralized and autonomous control, may yield better performance. So far, only anecdotal evidence for the potential benefit of autonomous control in scheduling exists. Here, we explore this hypothesis within a minimal model derived from scheduling principles and the phenomenology of dynamical processes on graphs. In this model, centralized and autonomous control can be represented and quantitatively assessed, performance is well defined and problem complexity can be varied.