Scheduling as a multi-dimensional placement problem

This paper describes research in developing an algorithm for a constraint-satisfaction problem (CSP) which solves certain classes of scheduling problems by formulating them as multi-dimensional placement problems. The test domain is check-in counter scheduling at an international airport. In this airport the counters are managed and allocated centrally by the local aviation authority. This scheduling problem is complicated by the fact that the resource requirement is stochastic - passenger arrival is a non-stationary probability distribution; the resources are not uniform - the physical location and available free space for queuing are different for different counters; and the resources to be allocated have other associated resources with their own sets of constraints - counters have associated baggage belts that have different capacity constraints. The approach presented combines simulation techniques with constraint-based reasoning to handle the stochastic nature of the problem. Scheduling requirements are modelled as multi-dimensional objects. The CSP algorithm presented here treats scheduling as a process of kneading and moulding these multi-dimensional objects into unallocated free space until a place is found for each of these objects. The constraints of the problem define how much the shape can be moulded. Copyright © 1996 Elsevier Science Ltd.