A backward algorithm for multi-processor scheduling problem with unequal release dates

This paper considers the multi-processor scheduling problem with unequal release dates to minimize total completion times. This problem is proved to be NP-hard in the strong sense. Traditional forward algorithms base on the heuristic rule SPT (shortest processing time first) and ERD (earliest release date first) for the problem are analyzed. A backward algorithm BA is proposed to avoid the limitation of the traditional forward heuristics. A large set of randomly generated large-sized instances are made to test the accuracy of BA. The results and analysis of experiments are reported and discussed.