makespan

Makespan

This Rust library implements several solvers for task scheduling problems optimizing makespan.

Graham's notation

Definitions of scheduling problems in operations research commonly use Graham's notation a|b|c where

1. a defines machine environment (resources)
2. b denotes task/job characteristics
3. c specifies the objective function that is to be minimized (note that this library focuses on optimizing the makespan C_max)

Covered scheduling problems

The module structure of this library follows a structure of the general taxonomy of scheduling problems and as mentioned above focuses on minimizing the makespan (C_max).

General constraints:

• Each task can be processed by at most one resource at a time
• Each resource can process at most one task at a time

Single-processor

This class of scheduling problems considers single processing unit (resource).

Non-preemptive

This sub-class considers non-preemptive tasks and is covered by module sp. The list of problems and corresponding algorithms includes:

• 1||C_max: optimal, linear
• 1|prec|C_max: optimal, linear
• 1|r_j|C_max: optimal, log-linear
• 1|d'_j|C_max: EDF (optimal, log-linear)
• 1|r_j,d'_j|C_max: heuristic (log-linear), Bratley's BnB (optimal)
• 1|chains,r_j|C_max: special case with chains totally ordered (otpimal, linear)

Multi-processor

This class of scheduling problems considers multiple processing units (resources).

Non-preemptive

This sub-class considers non-preemptive tasks and is covered by module mp. The list of problems and corresponding algorithms includes:

• P||C_max: LPT (approx), BnB (optimal)

Preemptive

This sub-class considers preemptive tasks and is covered by module mp_pmtn. The list of problems and corresponding algorithms includes:

• P|pmtn|C_max: McNaughton (optimal)

Resources

• Complexity results
• The scheduling zoo
• CTU lecture slides

License and version

Current version: 0.3.0

License: MIT OR Apache-2.0