Automated planning and scheduling


Planning is the organization of achieving goals in a specific area, with different means, and over a duration / hierarchy. The result of this problem is a « plan » that responds in detail to WWWWHH questions: who, what, where, when, how, and how much.

The assignment problem (planning) answers the following questions, according to the conditions and information:

  • How to manage the logical sequence of tasks and distribute them over time?
  • How to analyze the requested workloads of resources or means if they are limited?
  • How to express a need for resources or means if they are not limited?
  • How to take into account constraints outside the project (sales order, supplier delivery, etc.)?
  • How to analyze the consequences of a gap between actual and planned events?
  • How to identify start dates at the latest, or end at the earliest, activities?
  • How to simulate optimistic, pessimistic, or most likely assumptions?
  • How to analyze the impact of a hazard or a risk if it turned into a problem?
  • How to prioritize tasks?

The assignment problem is related to many other problems of operational research (eg reduction of problems in Karp problems). Here we will see some sub-problems commonly encountered in assignment problems.

Sub-problem: scheduling

The scheduling problem is a task scheduling problem in which it is necessary to decide the order in the tasks will be executed. This problem is Np-difficult due to the variety and complexity of its constraints.

The different methods presented in this course make it possible to show clearly and quickly the data related to the realization of a plan, such as:

  • Times
  • resources
  • costs

The classic scheduling problem is as follows:

Let Ti be N tasks requiring a duration di begining at ti which is a variable. The problem is subject to two types of constraints: time constraints; resource constraints or cumulative. At any time, the sum of the consumptions on the machine k must be lower than its capacity.

Sub-problem: matching

This problem is to assign tasks to agents. Each agent performs a unique task for a given cost and each task is performed by a unique agent. Any matching (agent-task couple) have a defined cost, the goal is to minimize the total cost to complete all tasks. This problem is resolved in polynomial time.

Let S be the agents and T be the tasks, the problem is modeled by a bipartite graph G=((S,T),E), with c is the cost on each edge. The problem of assignment is to find a perfect matching F⊂E which minimize ∑e∈E c(e).

Subproblem: transportation

Inlike the two previous problems, the transportation problem is a maximization. The transportation problem is one of the subclasses of linear programming problems where the objective is to transport various quantities of a single homogeneous product that are initially stored at various origins, to different destinations in such a way that the total transportation is minimum.

Let ai be the quantity of the commodity available at the origin i; bj be the quantity of the commodity needed at destination j; cij be the transportation cost of one unit of a commodity from origin i to destination j; and xij be the quantity transported from origin i to the destination j.

The problem is as follows:


If the sum of the sources is equal to the sum of the requests, the problem is said to be balanced, in this case the constraints become equalities. In the opposite case, a virtual demand point (dummy) is created which corresponds to the excess supply and with a zero transport cost.


The graph is similar to a mathching problem with a flow on each edge.