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.
- Id:
continuum-offloading; implemented byContinuumOffloading - Problem class: continuum
- Objectives:
mean_response_time,energy,cost - Sources: Mao et al. (2017); Gupta et al. (2017); Fan et al. (2007)
| 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') |
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.
- Id:
continuum-pipeline; implemented byContinuumPipeline - Problem class: continuum
- Objectives:
mean_response_time,energy,cost - Sources: Kang et al. (2017); Gupta et al. (2017); Fan et al. (2007)
| 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') |
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.
- Id:
continuum-workflow; implemented byContinuumWorkflow - Problem class: continuum
- Objectives:
makespan,energy,cost - Sources: Topcuoglu et al. (2002); Gupta et al. (2017); Fan et al. (2007)
| 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') |
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).
- Id:
flexible-job-shop; implemented byFlexibleJobShop - Problem class: flexible-job-shop
- Objectives:
makespan - Sources: Brandimarte (1993); Singer and Pinedo (1998)
| 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',) |
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.
- Id:
flow-shop; implemented byFlowShop - Problem class: flow-shop
- Objectives:
makespan - Sources: Taillard (1993); Singer and Pinedo (1998)
| Parameter | Default |
|---|---|
jobs |
20 |
machines |
5 |
min_time |
1 |
max_time |
99 |
permutation |
True |
due_date_tightness |
None |
weighted |
False |
objectives |
('makespan',) |
Hybrid flow shop¶
Jobs visit a series of stages in order, each on one of the stage's identical or unrelated parallel machines.
- Id:
hybrid-flow-shop; implemented byHybridFlowShop - Problem class: hybrid-flow-shop
- Objectives:
makespan - Sources: Ruiz and Vázquez-Rodríguez (2010); Taillard (1993); Singer and Pinedo (1998)
| 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',) |
Job shop¶
Each job visits every machine once in its own random order, with processing times and routes drawn as in Taillard (1993).
- Id:
job-shop; implemented byJobShop - Problem class: job-shop
- Objectives:
makespan - Sources: Taillard (1993); Singer and Pinedo (1998)
| Parameter | Default |
|---|---|
jobs |
10 |
machines |
10 |
min_time |
1 |
max_time |
99 |
due_date_tightness |
None |
weighted |
False |
objectives |
('makespan',) |
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).
- Id:
multi-mode-rcpsp; implemented byMultiModeRcpsp - Problem class: multi-mode-rcpsp
- Objectives:
makespan - Sources: Kolisch et al. (1995); Kolisch and Sprecher (1997)
| 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',) |
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).
- Id:
open-shop; implemented byOpenShop - Problem class: open-shop
- Objectives:
makespan - Sources: Taillard (1993); Gonzalez and Sahni (1976)
| Parameter | Default |
|---|---|
jobs |
5 |
machines |
5 |
min_time |
1 |
max_time |
99 |
objectives |
('makespan',) |
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.
- Id:
parallel-machines; implemented byParallelMachines - Problem class: parallel-machines
- Objectives:
makespan - Sources: Vallada and Ruiz (2011); Crauwels et al. (1998)
| 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',) |
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).
- Id:
rcpsp; implemented byRcpsp - Problem class: rcpsp
- Objectives:
makespan - Sources: Kolisch et al. (1995); Kolisch and Sprecher (1997)
| 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',) |
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.
- Id:
workflow; implemented byRandomTaskGraph - Problem class: workflow
- Objectives:
makespan - Sources: Topcuoglu et al. (2002)
| Parameter | Default |
|---|---|
tasks |
20 |
shape |
1.0 |
out_degree |
2 |
ccr |
1.0 |
heterogeneity |
0.5 |
processors |
4 |
mean_duration |
10.0 |
objectives |
('makespan',) |
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.
- Id:
taillard-flow-shop; instancesta001tota120 - Source: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/flowshop2.txt
- Sources: Taillard (1993); Beasley (1990)
Taillard job shops¶
80 instances from 15 jobs x 15 machines to 100 x 20, generated exactly from the published seeds.
- Id:
taillard-job-shop; instancesta01tota80 - Source: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop2.txt
- Sources: Taillard (1993); Beasley (1990)
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.
- Id:
taillard-open-shop; instancestai4x4-1totai20x20-10 - Source: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/openshop.txt
- Bounds: published for 60 instances, 39 of them proven optimal
- Sources: Taillard (1993); Beasley (1990)
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.
- Id:
orlib-job-shop; instancesabz5toyn4 - Source: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt
- Files to download: jobshop1.txt
- Sources: Beasley (1990); Adams et al. (1988); Fisher and Thompson (1963); Lawrence (1984); Applegate and Cook (1991); Storer et al. (1992); Yamada and Nakano (1992)
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.
- Id:
orlib-flow-shop; instancescar1toreC41 - Source: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/flowshop1.txt
- Files to download: flowshop1.txt
- Sources: Beasley (1990); Carlier (1978); Heller (1960); Reeves (1995)
Brandimarte flexible job shops¶
The Mk01-Mk10 instances in the FJSPLib format of Mastrolilli and Gambardella, with machines numbered from 1.
- Id:
brandimarte; instancesmk01tomk10 - Source: https://people.idsia.ch/~monaldo/fjsp.html
- Files to download: TextData.zip from the page, extracted (Mk01.fjs to Mk10.fjs)
- Sources: Brandimarte (1993); Mastrolilli and Gambardella (2000)
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.
- Id:
psplib-j30; instancesj301_1toj3048_10 - Source: https://www.om-db.wi.tum.de/psplib/getdata.php?mode=sm
- Files to download: j30.sm.zip, extracted (files j301_1.sm to j3048_10.sm)
- Sources: Kolisch and Sprecher (1997); Kolisch et al. (1995)
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.
- Id:
psplib-j60; instancesj601_1toj6048_10 - Source: https://www.om-db.wi.tum.de/psplib/getdata.php?mode=sm
- Files to download: j60.sm.zip, extracted (files j601_1.sm to j6048_10.sm)
- Sources: Kolisch and Sprecher (1997); Kolisch et al. (1995)
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.
- Id:
psplib-j90; instancesj901_1toj9048_10 - Source: https://www.om-db.wi.tum.de/psplib/getdata.php?mode=sm
- Files to download: j90.sm.zip, extracted (files j901_1.sm to j9048_10.sm)
- Sources: Kolisch and Sprecher (1997); Kolisch et al. (1995)
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.
- Id:
psplib-j120; instancesj1201_1toj12060_10 - Source: https://www.om-db.wi.tum.de/psplib/getdata.php?mode=sm
- Files to download: j120.sm.zip, extracted (files j1201_1.sm to j12060_10.sm)
- Sources: Kolisch and Sprecher (1997); Kolisch et al. (1995)
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. |