Theory of scheduling

See also: Scheduling

The theory of scheduling is a branch of the Operations research which is interested in calculation of optimal dates of execution of tasks. For that, it is very often necessary to assign at the same time the essential resources to the execution of these tasks. A problem of scheduling can be regarded as a subproblem of Planification in which it is a question of deciding operational execution of the planned tasks.

Definition

A problem of scheduling consists in organizing in time the realization of tasks, taking into account temporal constraints (times, forced sequence) and constraints relating to the availability of the necessary resources.

In production (manufacturing, goods, of service), one can present it as a problem where it is necessary to carry out the release and the control of the advance of a whole of orders through the various centers composing the system.

A scheduling constitutes a solution with the problem of scheduling. It is defined by the planning of execution of the tasks (“order” and “calendar”) and of allowance of the resources and aims at satisfying one or more objectives. A scheduling is very often represented by a Bar chart.

Tasks

A task is an elementary entity localized in the time by a start date and/or of end, whose realization requires one duration, and who consumes a means according to a certain intensity.

According to the problems, the tasks can be carried out per pieces, or must be carried out without interruption; one speaks then respectively about problems préemptifs and not préemptifs. When the tasks are subjected to no constraint of coherence, they are known as independent.

Several tasks can constitute an activity and several activities can define a process.

Resources

The resource is average a technique or human intended to be used for the realization of a task and available in limited quantity, its capacity.

Several types of resources are to be distinguished. A resource is renewable so after being allocated with one or more tasks, it is again available in same quantity (the men, the machines, the equipment in general); the quantity of resource usable at every moment is limited. In the contrary case, it is consumable (raw materials, budget); total consumption (or office plurality) during time is limited. A resource is doubly forced when its instantaneous use and its total consumption are both limited (the money is an good example).

That it is renewable or consumable, the availability of a resource can vary during time. Its curve of availability is in general known a priori, except whenever it depends on the placement of certain generating tasks.

One in addition distinguishes mainly in the case of renewable resources the disjunctive resources which can carry out only one task at the same time (machine tool, robot manipulator) and the cumulative resources which can be used by several tasks simultaneously but of limited number (team of workmen, work station).

Constraints

The constraints express restrictions on the values which the variables of decision can take simultaneously. One distinguishes:

  • of the temporal constraints
    • allocated time constraints, exits generally of requirements of management and relating to the deadlines of the tasks (delivery periods, availability of the provisioning) or to the total duration of a project;
    • constraints of technological, or forced coherence ranges, which describe relations of a relative nature between the various tasks;
  • of the constraints of resources
    • operational requirements of resources which express the nature and the quantity of the means used by the tasks, as well as the characteristics of use of these means;
    • constraints of availability of the resources which specify the nature and the quantity of the means available during time. All these constraints can be formalized on the basis of distance between beginnings of tasks or potentials.

Objectives

In the resolution of a problem of scheduling, one can choose between two great types of strategies, aiming respectively to the optimality of the solutions, or more simply at their admissibility.

The approach by optimization supposes that the solutions candidates with a problem can be ordered in a rational way according to one or more numerical criteria of evaluation, built on the basis of indicator of performances. One will thus seek to minimize or maximize such criteria. One notes for example those

  • related to the Temps:
    • the total time of execution or the average time of completion of a whole of tasks
    • the stock of work-in-progress of treatment
    • various delays (maximum, means, nap, number, etc) or advances compared to the fixed deadlines;
  • related to the resources:
    • total or balanced quantity essential resources to construct a whole of tasks
    • the load of each resource;
    • related to an energy or a flow;
    • related to the costs of launching, production, transport, etc, but also with the incomes, the returns of investments.

Traditional problems

References

  • Joseph Y-T. Leung, Handbook off Scheduling: Algorithms, Models, and Performance Analysis , Chapman & Hall/CRC Computer & Information Science Series, 2004.

  • J. Carlier and pH. Christian woman, Problems of scheduling: modeling, complexity, algorithms , Masson, Paris, 1988.

  • P. Esquirol and P. Lopez, '' scheduling '', Economica, Paris, 1999.

  • Philippe Baptist, Emmanuel Néron, Francis Deaf, Model and algorithms in scheduling , Ellipses, Paris, 2004.

  • List of books

  • Gustave Gotheil, " Theory of the scheduling of the pélec" , Technosup, Rennes, 2006

External bonds

  • ordonnancement.org

  • (eng) Scheduling of the Production Portal

Random links:Embres-and-Castelmaure | In family (album) | Polyphony DIGITAL | The Council of orientation of public finances | 1905 (spectacle)