# zbMATH — the first resource for mathematics

Reducing the solution space of optimal task scheduling. (English) Zbl 1348.90312
Summary: Many scheduling problems are tackled by heuristics due to their NP-hard nature. Task scheduling with communication delays $$(P|\prec, c_{ij}| C_{\max})$$ is no exception. Nevertheless, it can be of significant advantage to have optimal schedules, e.g. for time critical systems or as a baseline to evaluate heuristics. A promising approach to optimal task scheduling with communication delays for small problems is the use of exhaustive search techniques such as $$A^\ast$$. $$A^\ast$$ is a best first search algorithm guided by a cost function. While good cost functions reduce the search space, early results have shown that problem specific pruning techniques are paramount. This paper proposes two novel pruning techniques that significantly reduce the search space for $$P|\prec, c_{ij}| C_{\max}$$. The pruning techniques Fixed Task Order and Equivalent Schedules are carefully investigated based on observations made with simple graph structures such as fork, join and fork-join, yet they are generally applicable. An extensive experimental evaluation of computing more than two thousand schedules demonstrates the efficiency of the novel pruning techniques in significantly reducing the solution space.

##### MSC:
 90B35 Deterministic scheduling theory in operations research 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 90C59 Approximation methods and heuristics in mathematical programming
Hypertool
Full Text: