Scheduling as ``the allocation of limited resources to tasks over time'' ([15]) has for a long time been one of the main research topics of Operations Research.
The basic structure of scheduling problems is as follows. There are a number of jobs given, each comprising a set of tasks. Every task needs a certain amount of processing time on a fixed machine. The solution to a scheduling problem consists in assigning a starting time to every task. The quality of a schedule is measured by an objective. In addition several restrictions must be kept by the solution, such as the technologically fixed sequence of the tasks within a job, the maximum workload of a machine etc.
Many different models have been developed in Operations Research but only few have found their way into industrial application. There are at least two important reasons for this:
The first reason is detailed by [15] (ch. 12.1); he states the following differences as important requirements from real manufacturing environments which are not covered by the somewhat simplified OR-models:
In addition to these differences from our experience the following demands are stated as equally important:
Most of the mathematical models suggested in the literature abstract from these problems. They state exactly one distribution to be valid for the processing time of all tasks; they use only one criterion as objective; any task needs at most or exactly one machine and no other resources; most models do not allow alternative machines, and time is simply seen as continuous.
Moreover, in OR-models the sequences in which resources are needed within a job differ very much between jobs. There are OR-problem instances where one job is processed in exactly the opposite order than another one, whereas in real productions most orders follow similar sequences due to technological conditions.
The fact that in most real productions some resources are highly utilized and thus form bottlenecks led to the production planning method OPT ([11]). In most OR-problems the resource utilizations are very similar.
These abstractions and the fact that it is not easy for practitioners to express their experience and knowledge in mathematical terms and models make them hardly applicable to real world scheduling problems.