Skip to content

Benchmark catalogue

Every benchmark family, published suite, instance catalog, file format, and instance feature of DispatchAtlas, generated from the registries when this site is built. The benchmarks guide explains how to use them.

Families

A family generates one problem per seed from its parameters. Parameters not given keep the defaults listed here.

12 families are registered.

Family Problem class Summary
continuum-offloading continuum Independent requests issued by devices at Poisson arrival times, each run on its device or offloaded to an edge, fog, or cloud node at the price of uploading its input and returning its result.
continuum-pipeline continuum Periodic frames from device streams, each passing through a chain of stages whose data shrink stage by stage, so each stage is placed on the device or on an edge, fog, or cloud node.
continuum-workflow continuum Layered random or fork-join workflows submitted by devices, each task placed on its device or on an edge, fog, or cloud node, with data volumes set by a communication-to-computation ratio.
flexible-job-shop flexible-job-shop Jobs are chains of operations, each of which runs on one machine from its own random eligible set with machine-dependent times, as in Brandimarte (1993).
flow-shop flow-shop Jobs visit every machine in the same order, with integer processing times drawn uniformly as in Taillard (1993), optionally in one common job order on every machine.
hybrid-flow-shop hybrid-flow-shop Jobs visit a series of stages in order, each on one of the stage's identical or unrelated parallel machines.
job-shop job-shop Each job visits every machine once in its own random order, with processing times and routes drawn as in Taillard (1993).
multi-mode-rcpsp multi-mode-rcpsp Activities with precedence arcs choose among modes that trade duration against renewable-resource demand, on networks generated as in Kolisch, Sprecher and Drexl (1995).
open-shop open-shop Each job needs every machine once in any order and one machine at a time, with processing times drawn as in Taillard (1993).
parallel-machines parallel-machines Independent jobs each run on one of several unrelated machines, optionally with sequence-dependent setup times as in Vallada and Ruiz (2011), release dates, and due dates.
rcpsp rcpsp Activities with precedence arcs share renewable resources, generated with the network complexity, resource factor, and resource strength of Kolisch, Sprecher and Drexl (1995).
workflow workflow Layered random task graphs whose tasks each run on one of several unrelated processors, with communication costs paid between different processors, as generated for the HEFT experiments.

Edge-fog-cloud request offloading

Independent requests issued by devices at Poisson arrival times, each run on its device or offloaded to an edge, fog, or cloud node at the price of uploading its input and returning its result.

Parameter Default
applications 20
arrival_rate 4.0
work 1.0
input_data 1.0
output_data 0.1
due_factor 2.0
deadline_factor None
tiers 'device,edge,fog,cloud'
devices 4
edge_nodes 2
fog_nodes 1
cloud_nodes 1
objectives ('mean_response_time', 'energy', 'cost')
dispatchatlas benchmarks generate continuum-offloading --seed 1

Edge-fog-cloud stream pipelines

Periodic frames from device streams, each passing through a chain of stages whose data shrink stage by stage, so each stage is placed on the device or on an edge, fog, or cloud node.

Parameter Default
streams 4
frames 5
stages 3
period 1.0
work 0.5
input_data 2.0
reduction 0.5
due_factor 2.0
deadline_factor None
tiers 'device,edge,fog,cloud'
devices 4
edge_nodes 2
fog_nodes 1
cloud_nodes 1
objectives ('mean_response_time', 'energy', 'cost')
dispatchatlas benchmarks generate continuum-pipeline --seed 1

Edge-fog-cloud workflows

Layered random or fork-join workflows submitted by devices, each task placed on its device or on an edge, fog, or cloud node, with data volumes set by a communication-to-computation ratio.

Parameter Default
applications 4
tasks 10
structure 'layered'
shape 1.0
out_degree 2
work 1.0
ccr 1.0
pinned_fraction 0.0
arrival_rate 0.0
due_factor 2.0
deadline_factor None
tiers 'device,edge,fog,cloud'
devices 4
edge_nodes 2
fog_nodes 1
cloud_nodes 1
objectives ('makespan', 'energy', 'cost')
dispatchatlas benchmarks generate continuum-workflow --seed 1

Flexible job shop

Jobs are chains of operations, each of which runs on one machine from its own random eligible set with machine-dependent times, as in Brandimarte (1993).

Parameter Default
jobs 10
machines 6
min_operations 5
max_operations 7
flexibility 3
min_time 1
max_time 20
due_date_tightness None
weighted False
objectives ('makespan',)
dispatchatlas benchmarks generate flexible-job-shop --seed 1

Flow shop

Jobs visit every machine in the same order, with integer processing times drawn uniformly as in Taillard (1993), optionally in one common job order on every machine.

Parameter Default
jobs 20
machines 5
min_time 1
max_time 99
permutation True
due_date_tightness None
weighted False
objectives ('makespan',)
dispatchatlas benchmarks generate flow-shop --seed 1

Hybrid flow shop

Jobs visit a series of stages in order, each on one of the stage's identical or unrelated parallel machines.

Parameter Default
jobs 20
stages 5
min_machines 1
max_machines 3
unrelated False
min_time 1
max_time 99
due_date_tightness None
weighted False
objectives ('makespan',)
dispatchatlas benchmarks generate hybrid-flow-shop --seed 1

Job shop

Each job visits every machine once in its own random order, with processing times and routes drawn as in Taillard (1993).

Parameter Default
jobs 10
machines 10
min_time 1
max_time 99
due_date_tightness None
weighted False
objectives ('makespan',)
dispatchatlas benchmarks generate job-shop --seed 1

Multi-mode resource-constrained project

Activities with precedence arcs choose among modes that trade duration against renewable-resource demand, on networks generated as in Kolisch, Sprecher and Drexl (1995).

Parameter Default
activities 20
resources 2
network_complexity 1.5
resource_factor 0.5
resource_strength 0.5
min_modes 2
max_modes 3
min_duration 1
max_duration 10
min_demand 1
max_demand 10
start_activities 3
finish_activities 3
max_degree 3
objectives ('makespan',)
dispatchatlas benchmarks generate multi-mode-rcpsp --seed 1

Open shop

Each job needs every machine once in any order and one machine at a time, with processing times drawn as in Taillard (1993).

Parameter Default
jobs 5
machines 5
min_time 1
max_time 99
objectives ('makespan',)
dispatchatlas benchmarks generate open-shop --seed 1

Unrelated parallel machines

Independent jobs each run on one of several unrelated machines, optionally with sequence-dependent setup times as in Vallada and Ruiz (2011), release dates, and due dates.

Parameter Default
jobs 20
machines 5
min_time 1
max_time 99
max_setup 0
release_span 0.0
tardiness_factor None
due_date_range 0.6
weighted False
objectives ('makespan',)
dispatchatlas benchmarks generate parallel-machines --seed 1

Resource-constrained project

Activities with precedence arcs share renewable resources, generated with the network complexity, resource factor, and resource strength of Kolisch, Sprecher and Drexl (1995).

Parameter Default
activities 30
resources 4
network_complexity 1.5
resource_factor 0.5
resource_strength 0.5
min_duration 1
max_duration 10
min_demand 1
max_demand 10
start_activities 3
finish_activities 3
max_degree 3
objectives ('makespan',)
dispatchatlas benchmarks generate rcpsp --seed 1

Random task graphs on heterogeneous processors

Layered random task graphs whose tasks each run on one of several unrelated processors, with communication costs paid between different processors, as generated for the HEFT experiments.

Parameter Default
tasks 20
shape 1.0
out_degree 2
ccr 1.0
heterogeneity 0.5
processors 4
mean_duration 10.0
objectives ('makespan',)
dispatchatlas benchmarks generate workflow --seed 1

Published suites

10 suites are registered.

Suite Problem class Instances Loads
taillard-flow-shop flow-shop 120 offline, from the published seeds
taillard-job-shop job-shop 80 offline, from the published seeds
taillard-open-shop open-shop 60 offline, from the published seeds
orlib-job-shop job-shop 82 from downloaded files
orlib-flow-shop flow-shop 31 from downloaded files
brandimarte flexible-job-shop 10 from downloaded files
psplib-j30 rcpsp 480 from downloaded files
psplib-j60 rcpsp 480 from downloaded files
psplib-j90 rcpsp 480 from downloaded files
psplib-j120 rcpsp 600 from downloaded files

Taillard permutation flow shops

120 instances from 20 jobs x 5 machines to 500 x 20, generated exactly from the published seeds.

dispatchatlas suites load taillard-flow-shop ta001

Taillard job shops

80 instances from 15 jobs x 15 machines to 100 x 20, generated exactly from the published seeds.

dispatchatlas suites load taillard-job-shop ta01

Taillard open shops

60 instances from 4 jobs x 4 machines to 20 x 20, generated exactly from the published seeds. The bounds are those listed with the seeds.

dispatchatlas suites load taillard-open-shop tai4x4-1

OR-Library job shops

82 classic job shops in one file: abz5-9, ft06, ft10, ft20, la01-40, orb01-10, swv01-20, and yn1-4.

dispatchatlas suites load orlib-job-shop abz5 --directory downloads

OR-Library flow shops

31 permutation flow shops in one file: car1-8, hel1-2, and the odd-numbered reC01-41; each even-numbered reC instance reverses the machine order of the preceding one.

dispatchatlas suites load orlib-flow-shop car1 --directory downloads

Brandimarte flexible job shops

The Mk01-Mk10 instances in the FJSPLib format of Mastrolilli and Gambardella, with machines numbered from 1.

dispatchatlas suites load brandimarte mk01 --directory downloads

PSPLIB J30 single-mode projects

48 ProGen parameter combinations with 10 instances each, 30 activities and 4 renewable resources. The source also lists optimal values, lower bounds, and best-known solutions.

dispatchatlas suites load psplib-j30 j301_1 --directory downloads

PSPLIB J60 single-mode projects

48 ProGen parameter combinations with 10 instances each, 60 activities and 4 renewable resources. The source also lists optimal values, lower bounds, and best-known solutions.

dispatchatlas suites load psplib-j60 j601_1 --directory downloads

PSPLIB J90 single-mode projects

48 ProGen parameter combinations with 10 instances each, 90 activities and 4 renewable resources. The source also lists optimal values, lower bounds, and best-known solutions.

dispatchatlas suites load psplib-j90 j901_1 --directory downloads

PSPLIB J120 single-mode projects

60 ProGen parameter combinations with 10 instances each, 120 activities and 4 renewable resources. The source also lists optimal values, lower bounds, and best-known solutions.

dispatchatlas suites load psplib-j120 j1201_1 --directory downloads

Catalogs

A catalog is a named list of family settings with an instance count each. dispatchatlas catalogs build NAME --output DIR writes its instances with a manifest of their digests.

Catalog Instances Families Description
smoke 24 continuum-offloading, continuum-pipeline, continuum-workflow, flexible-job-shop, flow-shop, hybrid-flow-shop, job-shop, multi-mode-rcpsp, open-shop, parallel-machines, rcpsp, workflow Two tiny instances of every built-in family, for fast checks.
continuum 60 continuum-offloading, continuum-pipeline, continuum-workflow The continuum families on small, medium, and large platforms.
workflow 54 workflow Random task graphs over part of the design of Topcuoglu, Hariri and Wu (2002).

File formats

load_instance and dispatchatlas solve --format read these formats. OR-Library files hold many instances; name one with instance.

Format Reader Implied by
orlib-job-shop read_orlib_job_shop the format argument
orlib-flow-shop read_orlib_flow_shop the format argument
fjs read_fjs .fjs
psplib read_psplib .sm, .mm

Instance features

dispatchatlas.benchmarks.features(problem) returns these numbers for any problem.

Feature Definition
tasks Number of tasks.
resources Number of resources.
dependencies Number of dependencies.
jobs Number of jobs: groups plus ungrouped tasks.
objectives Number of declared objectives.
dependency_density Dependencies divided by the tasks(tasks - 1) / 2 pairs.
depth Tasks on the longest chain of dependencies.
critical_path Length of the critical path.
total_work Sum of the tasks' shortest durations.
parallelism Total work divided by the critical path, the mean parallelism.
mean_duration Mean over tasks of their mean duration.
duration_cv Coefficient of variation of the tasks' mean durations.
mean_modes Mean number of modes per task, the flexibility.
mode_spread Mean over tasks with several modes of (longest - shortest) / longest duration, the heterogeneity of the alternatives.
pinned_share Share of tasks whose modes all lie at one network endpoint, so their location is fixed.
capacity_mean Mean resource capacity.
capacity_max Largest resource capacity.
unary_share Share of resources of capacity 1.
setup_share Share of resources with a non-zero setup time.
area_bound Sum over tasks of the smallest product, over modes, of duration and units held, divided by the total capacity: a lower bound on the length of any schedule.
ccr Communication-to-computation ratio: the mean over dependencies of their mean transfer time between modes on different resources, divided by the mean duration of the tasks whose mean duration is positive; 0 without a network.
data_share Share of dependencies that carry data; 0 without a network.
release_span Latest release minus earliest release.
release_spread Release span divided by the area bound; large values mean the work arrives thinly spread over time.
due_share Share of tasks with a due date.
due_tightness Mean over tasks with a due date of (due date - job release) / (earliest finish - job release), skipping tasks whose earliest finish is their job's release; 1 means no slack.
deadline_share Share of tasks with a hard deadline.
deadline_tightness Like due_tightness, for hard deadlines.