Scheduling can be viewed either as a constraint satisfaction problem or as a constrained optimization problem. When we think of scheduling as a constraint satisfaction problem, our aim is to find a schedule that satisfies the constraints, whatever they may be. When we think of scheduling as an optimization problem, our aim is to find a schedule that is optimal or close to optimal with respect to a given optimization criterion. The optimization criteria usually relate to time, capacity, and sequence: typically the makespan, tardiness, peak capacity, or transition cost.
-
The makespan is the amount of time that elapses between the beginning of the first activity and the end of the last activity (i.e., the total amount of time needed to finish the project).
-
The tardiness may relate to minimizing the "lateness" of any number of activities. In some problems, the criterion is to minimize average tardiness of activities so that most of the activities are not "too" late. In other problems, the criterion is to minimize the maximal tardiness so that even the most delayed activity is not too greatly overdue.
-
The peak capacity of a resource is the greatest amount of the resource that is used over time.
-
The transition cost of an activity is the cost incurred to switch from processing one activity to processing the next.
PREVIOUS
NEXT