Scheduling

Scheduling is the process of assigning tasks to a set of resources. It is an important concept in many areas such as computing and production processes.

In mathematical terms, a scheduling problem is often solved as an optimization problem, with the objective of maximizing a measure of schedule quality. For example, an airline might wish to minimize the number of airport gates required for its aircraft in order to reduce its operating costs.

Scheduling is important in modern production and chemical industries, where it can have a major impact on the productivity of a process. Common objectives in this type of scheduling are to minimize the makespan (duration) of production or to maximize total profit for a given set of customer demands. Modern computerised scheduling tools greatly outperform the manual (heuristic) scheduling methods commonly employed in the industry.

Companies use backward and forward scheduling to plan their human and material resources. Backward scheduling is planning the tasks from the due date to detemine the start date and forward scheduling is planning the tasks from the start date to determine the shipping date or the due date.

It is a key concept in multitasking and multiprocessing operating system design, and in real-time operating system design. It refers to the way processes are assigned priorities in a priority queue. This assignment is carried out by software known as a scheduler.

In general-purpose operating systems, the goal of the scheduler is to balance processor loads, and prevent any one process from either monopolizing the processor or being starved for resources. In real-time environments, such as devices for automatic control in industry (for example robotics), the scheduler also must ensure that processes can meet deadlines; this is crucial for keeping the system stable.

Many scheduling problems are NP-hard and finding efficient ways of solving larger scheduling problems is an active research area. Common mathematical techniques used to solve scheduling problems are Mixed Integer Linear Programming, Logical programming and Constraint programming.

Common scheduling practices

• Round-robin scheduling (RR)
• Shortest job next (SJN)
• Shortest remaining time (SRT)
• Weighted round-robin scheduling
• Rate-monotonic scheduling (RMS)
• Deadline-monotonic scheduling (DMS)
• Earliest deadline first scheduling (EDF)
• Two-level scheduling
• FIFO
• LIFO
• Fair-share scheduling
• Least slack time scheduling (LST)
• Multilevel Feedback Queue
• 'Take' scheduling
• Gang scheduling
• Least-connection scheduling
• Weighted least-connection scheduling
• Shortest expected delay scheduling
• Never queue scheduling
• List scheduling
• Genetic Anticipatory
• Lottery Scheduling
• Critical Path Method of Scheduling

Disk arm scheduling

• Shortest seek first
• Elevator algorithm

See also

• Automated planning and scheduling
• cyclic executive
• Fixed priority scheduling (FPS)
• Dynamic priority scheduling
• Response time analysis (RTA)