Planning and scheduling problem
Automated planning and scheduling is about carrying out strategies or sequences of actions. Modern planning, even within AI, has increasingly reflected the integration of theory and high-performance algorithmic techniques from operations research since at least the 1950s.
Introduction to planning issues
Planning is the organization of the achievement of objectives in a specific area, with different means, and over a period / hierarchy. The result of this problem is a “plan” answering in detail the questions of the type QQOQCC: who, what, where, when, how and how much.
The assignment problem is linked to many other problems of operations research (reduction of problems in the 21 Karp problems for example). We will see here two sub-problems frequently encountered in assignment problems.
The scheduling problem is a task scheduling problem in which one has to decide the order in which the tasks should be executed. This problem is Np-hard given the variety and the complexity of its constraints.
The different methods presented in this course make it possible to clearly and quickly show the data related to the realization of a plan, such as:
- times, deadlines
- means, or resources
- the costs.
The classic scheduling problem is as follows:
This problem is to best assign tasks to agents. Each agent can perform a single task for a given cost and each task must be performed by a single agent. The assignments (that is to say the agent-task pairs) all have a defined cost, the aim being to minimize the total cost of the assignments in order to carry out all the tasks. This problem is solved in polynomial time.
Like the two previous problems, the transport problem is a maximization. The transport problem is one of the subclasses of problems of linear programming where the objective is to transport various quantities of a single homogeneous product which are initially stored at various origins, to different destinations such that the total transport is minimal.
If the sum of the sources is equal to the sum of the demands, the problem is said to be balanced, in this case the constraints become equalities. Otherwise, we create a virtual demand point (dummy) corresponding to the excess supply and with a zero transport cost.
The transport problem is often represented as a bipartite graph with a flow problem (coupling). We will show here other variants to solve this problem.