Multi-Processor Scheduling Problems in Planning

摘要

A natural feature of many planning problems is the allocation of a fixed set of reusable resources between tasks, where a resource cannot be assigned to two tasks concurrently. Planning to minimise the makespan of a solution is not a common feature of existing planners. Planners that handle resources directly rely on explicit identification of resources in the domain, and use conflict resolution to prune invalid resource allocations. This approach does not guide planners towards efficient allocations of resources. This paper describes how domain analysis can be used to recognise the occurrence of a common resource allocation sub-problem within planning domains. STAN4, a hybrid system that uses domain analysis to identify certain combinatorial sub-problems within planning problems, can recognize and solve this family of Multi-Processor Scheduling (MPS) problems efficiently. Data is presented showing that STAN4 finds high quality solutions to MPS instances beyond the capabilities of other planning systems.