Abstract:
On a multiprocessor system, task parallelisation is used to speedup the overall execution time. The performance gains are however subject to efficient scheduling of tasks onto processors. An optimal schedule maximises the utilisation of each available processor and the overall task execution time is minimised. The associated task scheduling problem with communication delays, P|prec, cij |Cmax, is a well known NP-hard problem. We discuss the Iterative Deepening A* (IDA*) algorithm for the task scheduling problem which is memory limited and solves the scheduling problem optimally. IDA* limits the initial depth of the search tree to a number that is a lower bound on its schedule length and then uses iterative deepening to further expand its search space. When IDA* expands its search space through iterative deepening, it has to re-generate all the previous states in the earlier search space along with the new states produced. The contribution of this work is to provide a tighter initial lower bound on the schedule length to reduce the number of states that are required to be regenerated during iterative deepening. We propose an improved lower bound using constraint violations to eliminate infeasible lower bounds (destructive bounds). Further, the structure of specific graphs namely fork, join and fork-join are studied and methods to tighten their lower bound are proposed. The experimental results demonstrate a significant improvement to the lower bound over existing bounding techniques.