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 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.
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:
The classic scheduling problem is as follows:
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.
Inlike the two previous problems, the transportation problem is a maximization.
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 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.