Methods to learn abstract scheduling models

For practical reasons, most scheduling problems are an abstraction of the real problem being solved. For example, when you plan your day, you schedule the activities which are critical; that is you schedule the activities which are essential to the success of your day. So you may plan what time to leave the house to get to work, when to have meetings, how you share your vehicle with your spouse and so on. On the other hand, you probably do not consider the activities that are easy to arrange like brushing your teeth, going to the shops, making photocopies and other such tasks that can usually be accomplished whenever you have the time available. Scheduling all of these activities at once is often too complicated. Instead, a simpler schedule is produced by considering only the critical activities. However, if a schedule goes wrong, it is often because an activity turned out to be critical but was not scheduled. We typically learn which activities are critical by experience and create an abstract scheduling problem which includes all known critical activities. Instead of scheduling the non-critical activities we estimate their effects in the abstract scheduling problem. We are interested in automating this abstraction process for scheduling problems. In our approach, given a set of activities A to be scheduled¹, we choose a subset of activities, critical(A), and create a simplified scheduling model which approximates the other activities non-critical(A) instead of scheduling them. We then search this abstract model for a good, if not optimal solution. A solution is a partial order schedule for activities in critical(A). This abstract solution is then extended to a solution the entire problem by inserting the remaining activities non-critical(A) into the schedule. While the approach reduces complexity by solving the problem in two stages it does so at a price. There is a risk that the good abstract solution will not produce a good solution to the entire problem. We know that the optimal solution can be found if we schedule everything at once, e.g. critical(A)=A, however this has the worst complexity and is impractical in many cases as time does not allow a complete search. Instead, we wish to discover the minimal set of critical activities which still yields good or optimal full solutions in a reasonable amount of time. Our preliminary experiments have shown that by trying many different subsets of critical activities we are able to discover a good set critical(A). Even with all the overhead of exploring different abstract models, we are able to produce better quality solutions than scheduling the entire problem at once. Although our experiments are still underway, we have found that many quick repetitions of this abstract process perform well when the size of critical(A) is relatively small.