A distributed look-ahead algorithm for scheduling interdependent tasks

Autonomous decentralized systems, which concurrently work on different types of jobs consisting of interdependent tasks (steps), are considered. A dynamic decentralized look-ahead scheduling algorithm and a cooperation protocol are proposed. The goal is to utilize information about the internal job structure concerning future service requirements and system state information for dynamically arranging schedules such that jobs can take advantage of inevitable waiting times of others. The algorithm is evaluated by simulations. Waiting time reductions in sample configurations of up to 75% for single job types at the expense of only slightly worse response times for other job types compared to systems not applying the algorithm demonstrate the algorithm´s success