Saturday, March 8, 2008

Planning and Scheduling

Some most important discussions in the class were:

Planning and scheduling are separate problems as such but go hand-in-hand. A scheduled plan is one which has the plan and a schedule for that plan with time and resource constraints.

Scheduling can be:
-called as a special case of planning with resource constraints
-called as an allocation problem that allocates resources to time points and resources

A planner solves the problem and a plan serves as an input to the scheduler. This input is similar to a disjunctive temporal network which can have either unary or multi capacity resources which are nothing but unary or n-ary mutual exclusions.

Even when the resources are available before or while planning, we would want to go in a hierarchical fashion, ignore the resources and produce a plan and leave the rest to a scheduler for computational reasons.

Planning and Scheduling can be considered as two ends of a spectrum with maximum and minimum level of choices respectively. There are a number of interesting problems in-between these two points in the spectrum.

A scheduling problem can be modeled as a CSP.
Start point representation and PCP representations for CSP were discussed.
PCPs do perform well as it converts the the disjunctive temporal constraint problem into simple temporal problems that are really much more feasible when compared to the start point representation.
One problem with PCP representation is they do not scale very well for multi resource constraints.

No comments: