Improving Makespan in Dynamic Task Allocation for Cloud Robotic Systems with Time Window Constraints

A scheduling method in a robotic network cloud system with minimal makespan is beneficiary in the sense that the system can complete all of its assigned tasks in the fastest way. Robotic network cloud systems can be translated into graphs, with nodes representing hardware with independent computational processing power and edges as data transmissions between nodes. Tasks time windows constraints are a natural way of ordering the tasks. The makespan is the maximum time duration from the time that a node starts to perform its first scheduled task to the time that all the nodes complete their final scheduled tasks. The load balancing scheduling ensures that the time windows from the time that the first node completes its final scheduled tasks to the time that all the other nodes complete their final scheduled tasks are as narrow as possible. We propose a new load balancing algorithm for task scheduling such that the makespan is minimal. We prove the correctness of the proposed algorithm and present simulations illustrating the obtained results.