# Category: Optimal scheduling

Single-machine scheduling
Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which n
Uniform-machines scheduling
Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of o
YDS algorithm
YDS is a scheduling algorithm for dynamic speed scaling processors which minimizes the total energy consumption. It was named after and developed by Yao et al. There is both an online and an offline v
Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occ
Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job
Coffman–Graham algorithm
In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into
Identical-machines scheduling
Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m i
Modified due-date scheduling heuristic
The modified due-date (MDD) scheduling heuristic is a greedy heuristic used to solve the single machine total weighted tardiness problem (SMTWTP).
Interval scheduling
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing t
Job-shop scheduling
Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling.
Activity selection problem
The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marke
Flow-shop scheduling
Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2,
Truthful job scheduling
Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research. We have a project composed of several "jobs" (tasks). There are several workers. Each
Multifit algorithm
The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson. Its nove
Talent scheduling
Talent scheduling is an optimization problem in computer science and operations research, and it is also a problem in combinatorial optimization. Suppose we need to make films, and each film contains
Time-utility function
A Time/Utility Function (TUF), née Time/Value Function, specifies the application-specific utility that an action (e.g., computational task, mechanical movement) yields depending on its completion tim
Vehicle rescheduling problem
The vehicle rescheduling problem (VRSP) is a combinatorial optimization and integer programming problem seeking to service customers on a trip after change of schedule such as vehicle break down or ma
Nurse scheduling problem
The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the operations research problem of finding an optimal way to assign nurses to shifts, typically with a set of hard
Optimal job scheduling
Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs (also called processes or tasks) and a list of machines (also called pr
Lawler's algorithm
Lawler's algorithm is a powerful technique for solving a variety of constrained scheduling problems. particularly single-machine scheduling. The algorithm handles any precedence constraints. It schedu
Unrelated-machines scheduling
Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m differe
Open-shop scheduling
Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduli