An Exhaustive Approach to Release Time Aware Divisible Load Scheduling

An interesting optimization problem is examined where optimal load allocations depend on processor release times, but the timing of release times depends on the load allocation scenario used. This circular relationship between an optimal solution and release times causes system models whose timing relationships may not have an optimal solution. To obtain an optimal solution based on an assumed model and its arbitrary timing relationships, we propose an exhaustive search algorithm as a starting point into open ended research on this topic on algorithmic scalability and feasibility conditions. Through simulation, the behavior of the exhaustive search algorithm is investigated and load scheduling trends with arbitrary release times are verified. A bus network (homogeneous single-level tree network) with arbitrary processor release times is considered. For the scheduling strategy, a sequential distribution with a staggered start scheduling scenario to minimize total processing finish time is assumed.