Scheduling
Scheduling ( German "schedule creation" ; and timing ; in Business Administration scheduling machine scheduling or rostering called) is an anglicized to create a sequence plan ( English schedule ), the processes limited resources to allocate ( allocation ).
General
The scheduling follows the summary planning of the upcoming tasks. The allocation to a pool of resources is later followed by loading for a single instance of this pool.
In Business Administration Scheduling sets usually determines which single job instances when are executed (in what order) and where production machines (in which assignment), that controls the production processes from the completion of the order planning ( english planning ) over the dispatching ( English dispatch ) in the Execution ( English processing ) with accompanying order control ( English control ) with observation of the status ( English monitoring ) and feedback of events ( English feedback ) up to the completion of all linked sub-processes of each individual order instance. In the production economy one speaks simply of machine occupancy planning.
In computer science in the area of operating systems, scheduling defines which processes are given when and how much processor time; in database technology , scheduling defines how parallel transactions must run without violating the consistency of the database (see also: Scheduler ).
criteria
A good scheduling method is characterized by the fact that it optimizes the following criteria:
- Throughput : As many processes as possible are processed in the shortest possible time.
- Efficiency : The available resources are used to the full as possible.
- Fairness : The resources are allocated fairly to the processes, which means that no process is permanently neglected. It also says the process avoiding the "starvation" ( starvation ) of processes.
- Transparency: The individual steps of the processes are clearly identified and separated in their sequence and in their allocation to resources.
- Adherence to deadlines: Processes that have to be completed by a certain date are planned in such a way that the deadline is met. While in business administration deadlines to be met precisely are called “ deadlines ” and approximate deadlines to be met are called “completion dates”, in computer science one speaks only of deadlines and instead differentiates between the following types of real-time requirements : “hard real time” keeps all deadlines precisely, “soft real time” keeps Deadlines are somewhat on and best effort (“as good as possible”) does not guarantee that the deadlines will be met.
- Easy and fast. For an implementation in high-speed switches, it is important to limit the complexity.
In addition to these general optimization criteria, other secondary conditions are occasionally required, for example:
- Dwell time. Processes should be ended as quickly as possible.
Preemptive and non-preemptive procedures
A distinction is made between preemptive (from English preemptive , 'anticipatory') procedures from non-preemptive or cooperative :
- A cooperative scheduling method transfers the required resources to a process and waits until the process releases these resources again or until it has been completely processed and thus releases the resources again.
- A pre- emptive procedure, on the other hand, can withdraw resources from the process before it is completed in order to allocate them to other processes in the meantime. The process is interrupted in its execution (it goes into the 'ready' state) and remains there until resources are reassigned to it by the scheduler.
Special terms in business administration
Business administration and computer science have different terminologies for the same subject matter. The following terms are used in business administration:
- Order ( English job ) is synonymous with "process" and describes the implementation of certain operations using machines. They are specified in more detail by the following data:
- Work steps ( English task ) are the technically operational contents of the work to be carried out in an order.
- Processing time ( English processing time ) is the time duration in which an order must be processed at a (certain) machine.
- Einlastzeit ( english release date ) is the date on which the order in the system arrives, so the time can be started at the earliest with the processing.
- Weight ( English weight ) is equivalent to the secondary criterion "dwell time" and designates a priority factor, which describes the urgency of a job compared to other tasks in the system.
- Completion date ( English due date ) refers to the point in time when an order should be processed. Here, only mandatory completion dates are referred to as English deadlines .
Jobs that are processed before the planned completion date as well as jobs that cannot meet it and are only finished later generate costs. These are known as "early costs" and "tardy costs". The order in which a job runs through several machines is known as the “route”.
When solving scheduling problems, various restrictions (“ constraints ”) must be taken into account. For example, resources (e.g. machines, fitters, processors, etc.) are used to carry out jobs that are only available to a limited extent.
A distinction is often made between hard constraints, which must be strictly observed, and soft constraints. The hard restrictions include the above example and all restrictions of a physical nature (for example set-up times ). Soft restrictions are those that are used to optimize the plans, but do not necessarily have to be adhered to. If necessary, it is possible to provide additional capacity in the form of overtime after the existing personnel capacities have been fully utilized.
Other typical restrictions are the completion dates specified by the planning, which, however, usually represent weaker restrictions than the resource-related or technical, as well as loading times that are intended to prevent production from starting even though the required materials are not yet available.
Scheduling problems
Scheduling problems are often defined by the system configuration, the given restrictions and the underlying objective. The various models are classified using an established system of criteria.
The simplest system configuration is the single machine model . There is only one machine on which jobs have to be scheduled. The model is found very often - if, for example, you have a system configuration with several machines, but in which there is a single bottleneck machine, so that the scheduling of the other machines must be based on the plan of the bottleneck, the problem at hand will affect the single machine Problem returned. Due to the low complexity, it is possible to achieve certain goals with certainty by means of simple priority rules.
The parallel machine model is a generalization of the single machine model. Several machines of the same type work in parallel. An incoming job can be processed by any of these machines.
Often, jobs have to go through different operations on different machines, so they have different paths. Such an environment is known as a job shop . Job shop problems occur, for example, in the semiconductor industry in wafer production; A hospital can also be seen as a typical example of a job shop: The patients are jobs that follow different paths and are treated at different locations in the hospital (registration, waiting room, doctor's room, X-ray room, ...).
If all jobs run through the same machines in the same order, that is, if their paths are identical, this is called a flow shop . A flow shop is therefore a special job shop.
Typical flow shops can be found, for example, in the metal manufacturing industry or in batch and flow production in food production.
Scheduling problems occur at many points in production processes and are in most cases very difficult to solve optimally, since they often fall into the class of NP-complete problems. In practice, however, good approximate solutions are often sufficient.
The single-machine early / tardy problem is a frequently occurring and practice-relevant problem . In a single-machine environment, a number of jobs should be scheduled on one machine so that the early costs and tardy costs that occur are as minimal as possible. The objective coincides with the objective of just-in-time production . This problem is NP-complete.
The mentioned scheduling problems can all be formulated as integer optimization problems . One tries to solve such problems mainly with so-called branch-and-bound methods or the Johnson algorithm .
See also:
Scheduling in computer science
The generation of a schedule is an important part of all computer systems in which several functions can compete for the same resources. In some cases, highly optimized schedulers are being developed for the various areas in which workflows are required. Accordingly, schedulers can be differentiated both on the basis of their mode of operation and on the basis of their special application area.
The following are examples of important areas of application for which highly optimized schedulers are developed:
- The process scheduler (German: process management / resource allocation / time planning ) is part of operating systems . He is responsible for the fair management of multiple processes running on a computer .
- The hard disk scheduler is responsible for the time management of write and read jobs from the operating system to the hard disk drive .
- In database management systems, a transaction scheduler manages the write and read accesses of the individual transactions to the data in order to avoid violations of the ACID principle for maintaining data consistency.
- When job scheduling (task scheduling) is about the correct control of jobs (batch jobs, program start etc.), which are usually larger IT environments in time and other interdependencies.
literature
- J. Blazewicz, KH Ecker, E. Pesch, G. Schmidt, J. Weglarz: Scheduling Computer and Manufacturing Processes. Springer, Berlin 2001, ISBN 3-540-41931-4 .
- Peter Brucker: Scheduling Algorithms. 5th edition. Springer, 2007, ISBN 978-3-540-69515-8 .
- R. Conway, W. Maxwell, L. Miller: Theory of Scheduling. Addison-Wesley, Reading 1967.
- Wolfgang Domschke, Armin Scholl, Stefan Voss: Production planning - process organizational aspects. Springer, Berlin 1993, ISBN 3-540-56585-X .
- Florian Jaehn, Erwin Pesch: Scheduling - Introduction to Scheduling. Springer, 2014, ISBN 978-3-642-54438-5 .
- PS Ow, TE Morton: The single machine early / tardy problem. In: Management Science. Vol. 35, No. 2, 1989, pp. 177-192.
- M. Pinedo: Scheduling: Theory, Algorithms and Systems. Prentice Hall, Englewood Cliffs, New Jersey 2008.
- M. Pinedo, X. Chao: Operations Scheduling with Applications in Manufacturing and Services. Irwin / McGraw-Hill, Boston 1999.
- G. Schmidt: process management. Springer, Berlin 2002, ISBN 3-540-43170-5 .
Individual evidence
- ↑ a b c Theodor Nebl: Introduction to the production economy . 2nd Edition. 1997, ISBN 3-486-24326-8 , p. 341 f.
- ^ Dietrich Adam: Production Management. 9th edition. 1998, ISBN 3-409-69117-0 , pp. 535f.
- ↑ Horst Seelbach: scheduling. In: Waldemar Wittmann / Werner Kern / Richard Köhler / Hans U. Küpper / Klaus von Wysocki: Concise dictionary of business administration. 5th edition, 1993, col. 1 f.
- ^ A b Hans Corsten: Production Management . 12th edition. 2009, ISBN 978-3-486-58751-7 , p. 510.
- ↑ Jörg Heuer: The multiprocessor scheduling problem with sequence-dependent set-up times. 2004, ISBN 3-8244-8253-3 , p. 9.
- ↑ Holger Luczak / Walter Eversheim (eds.): Production planning and control. 2nd Edition. 1999, ISBN 3-540-65559-X , p. 48.
- ↑ Dietrich Production Management . 9th edition. 1998, ISBN 3-409-69117-0 , p. 120.