SchedulingProblemen

SchedulingProblemen is a term used in some German-language sources to denote scheduling problems in operations research. Scheduling problems are optimization problems that determine the start times of a collection of jobs subject to resource constraints, with the aim of improving objectives such as makespan, total completion time, or lateness. The typical data include processing times, machines or servers, release dates, due dates, and sometimes precedence relations among jobs. Constraints may reflect machine capacities, setup times, and maintenance windows.

Common variants include single-machine scheduling, parallel-machine scheduling (identical or uniform machines), flow shop problems (jobs passing through a fixed sequence of machines), job shop problems (each job has its own route), and open shop (order of machines is not fixed). Objectives vary: minimizing makespan, minimizing total completion time, minimizing maximum lateness or tardiness, minimizing the number of late jobs, or optimizing energy use and machine utilization.

Many scheduling problems are computationally hard. Even simple variants are often NP-hard; nevertheless, some special cases admit polynomial-time solutions. Notable results include Johnson’s rule for two-machine flow shops and simple priority rules such as shortest processing time (SPT) or earliest due date (EDD) for certain objectives on a single machine.

Solving approaches range from exact methods (integer programming, branch-and-bound) to heuristics (priority rules, greedy constructive methods) and metaheuristics (genetic algorithms, tabu search, simulated annealing). Hybrid approaches and online or dynamic scheduling address environments where data arrive over time. Applications span manufacturing, logistics, cloud computing, and healthcare.