A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations

This paper presents a state-space search approach for parallel processor scheduling problems with arbitrary precedence relations. The tasks to be scheduled are non-preemptive and have different dependence structures. The objective is to minimize the makespan and this problem has been identified as an NP-complete problem. As a result, the optimal solution to this problem is intractable and heuristic approaches are justified. In our approach, we will adopt the following strategies: (1) a state-space representation scheme is applied for the problem formulation, (2) A* and Best-First search techniques are presented and the possible variations of these two approaches are discussed, and (3) different bounding strategies and heuristics for A* and Best-First searches are explored. Efficiency and solution quality of each bound and heuristic are evaluated by experimental examples. To solve the problem in practical sizes, the EST/CP heuristic is developed and experimental results show that the heuristic is very encouraging and outperforms conventional methods. In summary, the state-space search approach provides a promising paradigm for parallel processor scheduling problems.