Task Scheduling
With Precedence And Resource Constraints

Task Scheduling is implemented to illustrate the use of the framework for more complex domains.

Definitions

• A task has associated with it a task length and resource requirements.

  • The task length is assumed to be known and accurate.

  • The task length of a task j can be written TaskLength(j).

  • The resource requirement is an integral number of resources needed to finish the job. All of these resources must be applied to the task simultaneously. (If a task could be assigned to some resources now and others later, it would have been divided into two tasks in the first place.)

  • There is no notion of priority to a task.

• A resource is a unit which executes a task.

  • A resource may execute a single task at a time, or be idle.

  • A task executing on a resource can not be preempted.

  • All resources are identical.

  • A task may require multiple resources to be completed, and must be assigned to all needed resources simultaneously.

  • There is no limit to how many time steps a resource can be used.

• A precedence constraint is a pair (ja, jb) of tasks, where ja must be completed before jb can begin.

  • We represent the set of precedence constraints as a directed acyclic graph (DAG) where each node is a task, and there is an edge from node na to nb iff there is a precedence constraint between the corresponding tasks of the form (ja, jb).

  • In the DAG, a successor of task ja is a task jb such that there is a path from ja to jb. If the path is of length 1, then jb is a direct successor of ja.

  • The DAG must be acyclic. Constraints that form such a DAG are said to be consistent.

• A project is a set of tasks and consistent precedence constraints on these tasks.

• A schedule for a project on a set of resources consists of, for each task in the project, a start time of execution on any available resource. A schedule must be constraint preserving. That is, all of the following must be true:

  • At any time step with n idle resources, no more than m tasks are scheduled to start, where sum( ResourceRequirement(m), m) < n

  • Precedence constraints are satisfied. That is, for any two tasks ja with start time sa and jb with start time sb, if there is a constraint (ja, jb), then sa+TaskLength(ja) <= sb.

Problem Statement

Given a project and a finite number of resources, form a schedule that is near-optimal in total execution time.

The term "near-optimal" is used because optimality is not guaranteed, but the generated schedule should be considerably better than a randomly generated schedule.

Back to CBR page
sbogaert@cs.indiana.edu