Skip to content

Benchmarks

Benchmark families, published suites, instance-file readers, catalogs, and instance features.

dispatchatlas.benchmarks

Benchmark families, published instance suites, and instance-file readers.

Generate a problem from a registered family:

from dispatchatlas.benchmarks import generate
problem = generate("job-shop", seed=1, jobs=10, machines=5)

Rebuild a published instance, or read one from a file:

from dispatchatlas.benchmarks import load_instance, taillard_flow_shop
ta001 = taillard_flow_shop("ta001")
ft06 = load_instance("ft06.txt", format="orlib-job-shop")

The submodules hold the rest: suites (reference suites and their known bounds), catalog (named instance sets written to disk with checksums), characterize (instance features), continuum (edge-fog-cloud platforms), and the readers that map published workloads onto such a platform: wfcommons (WfCommons workflow instances), pegasus (Pegasus DAX workflow files), and alibaba (the batch jobs of the Alibaba 2018 cluster trace).

dispatchatlas.benchmarks.registry

The benchmark-family registry and plugin discovery.

A benchmark family is a parameterised generator of problems. Each family is a dataclass whose fields are its parameters and whose generate(seed) method returns one Problem. Equal parameters and seed always give the same problem.

Families register like solvers. Installed packages can add families through the dispatchatlas.benchmarks entry-point group:

[project.entry-points."dispatchatlas.benchmarks"]
my_families = "my_package.families:register"

PLUGIN_GROUP module-attribute

PLUGIN_GROUP = 'dispatchatlas.benchmarks'

Entry-point group scanned for benchmark-family plugins.

BUILT_IN_MODULES module-attribute

BUILT_IN_MODULES: tuple[str, ...] = ('dispatchatlas.benchmarks.shop', 'dispatchatlas.benchmarks.machines', 'dispatchatlas.benchmarks.project', 'dispatchatlas.benchmarks.workflow', 'dispatchatlas.benchmarks.continuum')

Modules whose register(registry) function adds the built-in families.

FamilyInfo dataclass

FamilyInfo(id: str, name: str, problem_class: str, summary: str, references: tuple[str, ...] = (), objectives: tuple[str, ...] = ('makespan',), parameters: Mapping[str, Any] = dict())

Metadata describing a benchmark family.

Attributes:

Name Type Description
id str

Registry key in kebab case, for example "flow-shop".

name str

Human-readable name.

problem_class str

The scheduling problem class, for example "job-shop" or "continuum".

summary str

One sentence describing what the generated problems model.

references tuple[str, ...]

Bibliography keys, DOIs, or URLs of the sources the generator follows.

objectives tuple[str, ...]

Objectives the generated problems declare by default.

parameters Mapping[str, Any]

Default parameter values. Filled from the dataclass fields when registered.

Generator

Bases: Protocol

The interface of a benchmark family.

info property

info: FamilyInfo

Metadata of the family.

generate

generate(seed: int = 0) -> Problem

Return the problem for seed.

FamilyRegistry

FamilyRegistry()

A collection of benchmark families addressable by id.

register

register(factory: Any, info: FamilyInfo | None = None, *, replace_existing: bool = False) -> None

Add a family.

Parameters:

Name Type Description Default
factory Any

Callable building the generator from keyword parameters, usually the family's dataclass.

required
info FamilyInfo | None

The family's metadata. Defaults to factory.info.

None
replace_existing bool

Allow replacing a family with the same id.

False

Raises:

Type Description
ConfigError

If the id is taken, or no metadata is available.

create

create(family_id: str, **parameters: Any) -> Generator

Build a family's generator with the given parameter values.

Raises:

Type Description
ConfigError

If the id is unknown or a parameter is invalid.

generate

generate(family_id: str, seed: int = 0, **parameters: Any) -> Problem

Generate one problem of a family.

info

info(family_id: str) -> FamilyInfo

Return the metadata of a registered family.

infos

infos() -> tuple[FamilyInfo, ...]

Return the metadata of every family, sorted by id.

ids

ids() -> tuple[str, ...]

Return every registered id, sorted.

copy

copy() -> FamilyRegistry

Return an independent copy of this registry.

load_plugins

load_plugins(registry: FamilyRegistry, *, group: str = PLUGIN_GROUP) -> list[str]

Register the families published by installed plugins.

Returns:

Type Description
list[str]

Names of the entry points that loaded. A plugin that fails is skipped

list[str]

with a warning and registers none of its families.

default_registry

default_registry(*, plugins: bool = True) -> FamilyRegistry

Return a registry of the built-in families, plus plugins by default.

generate

generate(family_id: str, seed: int = 0, **parameters: Any) -> Problem

Generate one problem of a registered family.

Example

from dispatchatlas.benchmarks import generate problem = generate("job-shop", seed=1, jobs=6, machines=4)

dispatchatlas.benchmarks.shop

Classic shop-scheduling families and the builders that map shop data onto the model.

Five families generate the classic machine environments:

  • flow-shop: every job visits machines 0, 1, ..., m-1 in that order.
  • job-shop: every job visits every machine once, in its own order.
  • open-shop: every job needs every machine once, in any order.
  • flexible-job-shop: a job is a chain of operations, and each operation runs on one machine chosen from its own eligible set.
  • hybrid-flow-shop: jobs visit a series of stages in order, each on one of the stage's parallel machines.

Processing times follow Taillard (1993): independent integers drawn uniformly from [min_time, max_time], [1, 99] by default.

The builders (flow_shop_problem() and its siblings) turn plain matrices into problems. The families, the exact Taillard instances in dispatchatlas.benchmarks.taillard, and the file readers in dispatchatlas.benchmarks.formats all use them, so a shop instance has the same shape whatever its origin:

  • Machines are unary resources m0, m1, ... and jobs are task groups j0, j1, .... Indices are zero-padded to a common width, so ids sort in index order.
  • A flow-shop or open-shop operation is task <job>-<machine>, for example j03-m2. Operation p of a job in the other shops is task <job>-o<p>, or <job>-s<stage> in a hybrid flow shop.
  • Consecutive operations of a job are joined by finish-to-start dependencies.
  • An operation that may run on several machines has one mode per machine.
  • A job's due date sits on its final operation and its weight on every one of its operations, as dispatchatlas.core.objectives expects.

Due dates and weights, when requested, follow the job-shop weighted-tardiness benchmark of Singer and Pinedo (1998): job j is due at floor(f * P_j), where P_j is its total processing time and f the due-date tightness (1.3, 1.5, and 1.6 in that benchmark), and the first 20 % of the jobs weigh 4, the next 60 % weigh 2, and the rest weigh 1. An operation with several modes contributes its mean duration to P_j.

FlowShop dataclass

FlowShop(jobs: int = 20, machines: int = 5, min_time: int = 1, max_time: int = 99, permutation: bool = True, due_date_tightness: float | None = None, weighted: bool = False, objectives: tuple[str, ...] = ('makespan',))

Flow shops with Taillard's processing-time scheme.

Draws, in order: the processing times machine by machine and, within a machine, job by job, the order of Taillard's generator. Due dates and weights, when requested, are computed from the times without further draws.

Attributes:

Name Type Description
jobs int

Number of jobs.

machines int

Number of machines.

min_time int

Smallest processing time.

max_time int

Largest processing time.

permutation bool

Require one common job order on every machine.

due_date_tightness float | None

Factor f of the due dates floor(f * P_j), or None for no due dates.

weighted bool

Give jobs the weights 4, 2, and 1 of Singer and Pinedo (1998) instead of weight 1.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the flow shop for seed.

JobShop dataclass

JobShop(jobs: int = 10, machines: int = 10, min_time: int = 1, max_time: int = 99, due_date_tightness: float | None = None, weighted: bool = False, objectives: tuple[str, ...] = ('makespan',))

Job shops with Taillard's processing-time and routing scheme.

Draws, in order, as in Taillard's generator: every processing time, job by job and operation by operation; then each job's machine order, built by swapping position i with a uniformly drawn position i..m-1 for i = 0, ..., m-1.

Attributes:

Name Type Description
jobs int

Number of jobs.

machines int

Number of machines. Every job visits each machine once.

min_time int

Smallest processing time.

max_time int

Largest processing time.

due_date_tightness float | None

Factor f of the due dates floor(f * P_j), or None for no due dates.

weighted bool

Give jobs the weights 4, 2, and 1 of Singer and Pinedo (1998) instead of weight 1.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the job shop for seed.

OpenShop dataclass

OpenShop(jobs: int = 5, machines: int = 5, min_time: int = 1, max_time: int = 99, objectives: tuple[str, ...] = ('makespan',))

Open shops with Taillard's data scheme.

Draws, in order, as in Taillard's open-shop generator (the same procedure as his job shops): every processing time, job by job; then a random machine permutation per job that assigns the i-th time of a job to a machine.

Attributes:

Name Type Description
jobs int

Number of jobs.

machines int

Number of machines. Every job needs each machine once.

min_time int

Smallest processing time.

max_time int

Largest processing time.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the open shop for seed.

FlexibleJobShop dataclass

FlexibleJobShop(jobs: int = 10, machines: int = 6, min_operations: int = 5, max_operations: int = 7, flexibility: int = 3, min_time: int = 1, max_time: int = 20, due_date_tightness: float | None = None, weighted: bool = False, objectives: tuple[str, ...] = ('makespan',))

Flexible job shops in the style of Brandimarte (1993).

Draws, job by job: the number of operations, uniform in [min_operations, max_operations]; then per operation the number of eligible machines, uniform in [1, flexibility], the eligible machines as a uniform sample of that size, and one processing time per eligible machine, uniform in [min_time, max_time].

Attributes:

Name Type Description
jobs int

Number of jobs.

machines int

Number of machines.

min_operations int

Fewest operations of a job.

max_operations int

Most operations of a job.

flexibility int

Most machines eligible for one operation.

min_time int

Smallest processing time.

max_time int

Largest processing time.

due_date_tightness float | None

Factor f of the due dates floor(f * P_j), where an operation counts with its mean time over its machines, or None for no due dates.

weighted bool

Give jobs the weights 4, 2, and 1 of Singer and Pinedo (1998) instead of weight 1.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the flexible job shop for seed.

HybridFlowShop dataclass

HybridFlowShop(jobs: int = 20, stages: int = 5, min_machines: int = 1, max_machines: int = 3, unrelated: bool = False, min_time: int = 1, max_time: int = 99, due_date_tightness: float | None = None, weighted: bool = False, objectives: tuple[str, ...] = ('makespan',))

Hybrid flow shops with identical or unrelated parallel machines per stage.

Draws, in order: the number of machines of every stage, uniform in [min_machines, max_machines]; then job by job and stage by stage the processing time, one draw shared by the stage's machines when they are identical, or one draw per machine when they are unrelated.

Attributes:

Name Type Description
jobs int

Number of jobs.

stages int

Number of stages every job visits in order.

min_machines int

Fewest parallel machines of a stage.

max_machines int

Most parallel machines of a stage.

unrelated bool

Draw an independent processing time per machine instead of one time shared by the stage's identical machines.

min_time int

Smallest processing time.

max_time int

Largest processing time.

due_date_tightness float | None

Factor f of the due dates floor(f * P_j), where a stage counts with its mean time over its machines, or None for no due dates.

weighted bool

Give jobs the weights 4, 2, and 1 of Singer and Pinedo (1998) instead of weight 1.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the hybrid flow shop for seed.

flow_shop_problem

flow_shop_problem(times: Sequence[Sequence[float]], *, problem_id: str = 'flow-shop', permutation: bool = True, due_dates: Sequence[float] | None = None, weights: Sequence[float] | None = None, objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build a flow shop from a job-by-machine processing-time matrix.

Parameters:

Name Type Description Default
times Sequence[Sequence[float]]

times[j][k] is the processing time of job j on machine k. Every job visits the machines in increasing index order.

required
problem_id str

Id of the problem.

'flow-shop'
permutation bool

Require every machine to process the jobs in one common order, as in the permutation flow shop.

True
due_dates Sequence[float] | None

Due date of each job, placed on its last operation.

None
weights Sequence[float] | None

Weight of each job, placed on all its operations.

None
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If the matrix is empty or ragged, or a per-job list has the wrong length.

job_shop_problem

job_shop_problem(routes: Sequence[Alternatives], *, machines: int | None = None, problem_id: str = 'job-shop', due_dates: Sequence[float] | None = None, weights: Sequence[float] | None = None, objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build a job shop from each job's route of machines and processing times.

Parameters:

Name Type Description Default
routes Sequence[Alternatives]

routes[j] lists the (machine index, processing time) of job j's operations in processing order. Machine indices start at 0.

required
machines int | None

Number of machines. Defaults to one more than the largest index in the routes.

None
problem_id str

Id of the problem.

'job-shop'
due_dates Sequence[float] | None

Due date of each job, placed on its last operation.

None
weights Sequence[float] | None

Weight of each job, placed on all its operations.

None
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If a job has no operation, a machine index is out of range, or a per-job list has the wrong length.

flexible_job_shop_problem

flexible_job_shop_problem(jobs: Sequence[Sequence[Alternatives]], *, machines: int | None = None, problem_id: str = 'flexible-job-shop', due_dates: Sequence[float] | None = None, weights: Sequence[float] | None = None, objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build a flexible job shop from each operation's machine alternatives.

Parameters:

Name Type Description Default
jobs Sequence[Sequence[Alternatives]]

jobs[j][p] lists the (machine index, processing time) options of operation p of job j. Each option becomes one mode. Machine indices start at 0.

required
machines int | None

Number of machines. Defaults to one more than the largest index used.

None
problem_id str

Id of the problem.

'flexible-job-shop'
due_dates Sequence[float] | None

Due date of each job, placed on its last operation.

None
weights Sequence[float] | None

Weight of each job, placed on all its operations.

None
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If a job or an operation is empty, a machine index is out of range, or a per-job list has the wrong length.

hybrid_flow_shop_problem

hybrid_flow_shop_problem(times: Sequence[Sequence[Sequence[float]]], *, problem_id: str = 'hybrid-flow-shop', due_dates: Sequence[float] | None = None, weights: Sequence[float] | None = None, objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build a hybrid flow shop from per-stage, per-machine processing times.

Machines are named s<stage>-m<k>. Each job has one operation per stage, with one mode per machine of the stage.

Parameters:

Name Type Description Default
times Sequence[Sequence[Sequence[float]]]

times[j][s][k] is the processing time of job j at stage s on the stage's machine k. Every job must list the same number of stages and, per stage, the same number of machines.

required
problem_id str

Id of the problem.

'hybrid-flow-shop'
due_dates Sequence[float] | None

Due date of each job, placed on its last operation.

None
weights Sequence[float] | None

Weight of each job, placed on all its operations.

None
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If the stage layout is empty or differs between jobs, or a per-job list has the wrong length.

open_shop_problem

open_shop_problem(times: Sequence[Sequence[float]], *, problem_id: str = 'open-shop', objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build an open shop from a job-by-machine processing-time matrix.

Each operation holds its machine and a unary resource job-<j> that stands for its job, so a job runs on at most one machine at a time while its operations may run in any order.

Parameters:

Name Type Description Default
times Sequence[Sequence[float]]

times[j][k] is the processing time of job j on machine k.

required
problem_id str

Id of the problem.

'open-shop'
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If the matrix is empty or ragged.

register

register(registry: FamilyRegistry) -> None

Add the shop families to registry.

dispatchatlas.benchmarks.machines

Unrelated parallel machines, with optional setups, release dates, and due dates.

Each job is a single operation that runs on exactly one of m machines, and its processing time depends on the machine. With sequence-dependent setups, a machine that finishes job a must wait S[k][a][b] before it can start job b; the first job on a machine needs no setup. This is the R|S_ijk|Cmax benchmark of Vallada and Ruiz (2011): processing times uniform in [1, 99] and setup times uniform in [1, 9], [1, 49], [1, 99], or [1, 124].

Due dates follow the tardiness-factor scheme of the OR-Library weighted-tardiness instances (Crauwels, Potts and Van Wassenhove 1998): an integer drawn uniformly from [P (1 - TF - RDD / 2), P (1 - TF + RDD / 2)], where TF is the tardiness factor and RDD the relative range of due dates. On one machine P is the total processing time; here it is the mean machine load, the sum over jobs of their mean processing time divided by m. Weights, when requested, are integers uniform in [1, 10] as in the same instances.

The problems use the conventions of dispatchatlas.benchmarks.shop: machines m0, m1, ... and jobs j0, j1, ... zero-padded to one width. Each job is a task with one mode per machine.

VALLADA_RUIZ_SETUPS module-attribute

VALLADA_RUIZ_SETUPS: tuple[int, ...] = (9, 49, 99, 124)

The largest setup time of each setup class of Vallada and Ruiz (2011).

ParallelMachines dataclass

ParallelMachines(jobs: int = 20, machines: int = 5, min_time: int = 1, max_time: int = 99, max_setup: int = 0, release_span: float = 0.0, tardiness_factor: float | None = None, due_date_range: float = 0.6, weighted: bool = False, objectives: tuple[str, ...] = ('makespan',))

Unrelated parallel machines in the style of Vallada and Ruiz (2011).

Draws, in order: the processing times job by job and machine by machine; the setup times machine by machine, then by preceding job and following job; the release dates; the due dates; the weights. Draws of an option that is switched off are skipped.

Attributes:

Name Type Description
jobs int

Number of jobs.

machines int

Number of machines.

min_time int

Smallest processing time.

max_time int

Largest processing time.

max_setup int

Largest setup time. Setups are uniform in [1, max_setup] for every machine and ordered pair of jobs. 0 means no setups. Vallada and Ruiz use 9, 49, 99, and 124.

release_span float

Release dates are uniform integers in [0, release_span * P], P being the mean machine load. 0 releases every job at time 0.

tardiness_factor float | None

Tardiness factor TF of the due dates, in [0, 1], or None for no due dates. A job's due date is its release date plus the drawn value, and never earlier than its release date.

due_date_range float

Relative range RDD of the due dates.

weighted bool

Draw weights uniform in [1, 10] instead of weight 1.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the parallel-machine problem for seed.

parallel_machine_problem

parallel_machine_problem(times: Sequence[Sequence[float]], *, setups: Sequence[Sequence[Sequence[float]]] | None = None, releases: Sequence[float] | None = None, due_dates: Sequence[float] | None = None, weights: Sequence[float] | None = None, problem_id: str = 'parallel-machines', objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build an unrelated parallel-machine problem.

Parameters:

Name Type Description Default
times Sequence[Sequence[float]]

times[j][k] is the processing time of job j on machine k.

required
setups Sequence[Sequence[Sequence[float]]] | None

setups[k][a][b] is the setup time machine k needs between job a and job b. Diagonal entries are ignored. No setup precedes the first job on a machine. The model forbids zero processing times on a machine with a non-zero setup time.

None
releases Sequence[float] | None

Release date of each job.

None
due_dates Sequence[float] | None

Due date of each job.

None
weights Sequence[float] | None

Weight of each job.

None
problem_id str

Id of the problem.

'parallel-machines'
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If the matrices are empty or ragged, a per-job list has the wrong length, or a job has a zero processing time on a machine with setup times.

register

register(registry: FamilyRegistry) -> None

Add the parallel-machine family to registry.

dispatchatlas.benchmarks.project

Resource-constrained project scheduling, single-mode and multi-mode.

Both families follow ProGen, the generator of Kolisch, Sprecher and Drexl (1995) that produced the PSPLIB instances (Kolisch and Sprecher 1997), and take its three parameters:

  • Network complexity NC: the average number of non-redundant arcs per node of the activity-on-node network, counting a dummy source and sink. A network of J activities has ceil(NC * (J + 2)) arcs, the smallest count that reaches NC, of which the S arcs from the source to the start activities and the F arcs from the finish activities to the sink stay implicit. The PSPLIB J30 networks have exactly these counts: 42, 52, and 62 explicit arcs for NC 1.5, 1.8, and 2.1.
  • Resource factor RF: the average share of the K resources an activity requests.
  • Resource strength RS: each capacity is K_min + round(RS * (K_max - K_min)), where K_min is the smallest capacity that lets every activity run and K_max is the peak demand of the earliest-start schedule that ignores resources. With RS = 1 that schedule is feasible.

Network. Activities are indexed in a precedence-feasible order and arcs run from lower to higher indices. As in ProGen:

  1. The first S activities are the start activities and the last F the finish activities. Start activities get no predecessor and finish activities no successor.
  2. Every other activity, in increasing order, gets one predecessor drawn uniformly from the earlier non-finish activities.
  3. Every non-finish activity still without a successor gets one drawn uniformly from the later non-start activities.
  4. Arcs drawn uniformly from the remaining admissible pairs are added until the network has its target number of arcs.

An arc is admissible when it is not redundant (no other path already leads from its tail to its head), makes no existing arc redundant, and leaves every activity at most max_degree predecessors and successors. A network that leaves an activity of step 3 without an admissible successor, or does not end with exactly the target number of arcs, is discarded and drawn again, up to 100 times. If no draw succeeds, the last one is kept, with the limits of step 3 relaxed for the activities that needed it.

Requests. As in ProGen, every activity first requests one resource drawn uniformly; then (activity, resource) pairs not yet requested are drawn uniformly, without replacement, until ceil(RF * J * K) pairs are requested.

Differences from ProGen. ProGen draws the numbers of start and finish activities from ranges, runs step 3 in increasing order, and accepts an arc count within a tolerance of the target. Here the numbers are fixed, step 3 runs from the last activity back to the first, which gives the late activities, with few later activities to choose from, the first choice and so fails far less often, and the arc count must match the target. ProGen lets the minimum and maximum number of requests per activity vary; here they are one and K. There are no dummy source and sink activities and no nonrenewable resources. MultiModeRcpsp lists its own differences.

Activities are tasks a1, a2, ... and resources r1, r2, ..., zero-padded to one width, following the PSPLIB numbering.

Rcpsp dataclass

Rcpsp(activities: int = 30, resources: int = 4, network_complexity: float = 1.5, resource_factor: float = 0.5, resource_strength: float = 0.5, min_duration: int = 1, max_duration: int = 10, min_demand: int = 1, max_demand: int = 10, start_activities: int = 3, finish_activities: int = 3, max_degree: int = 3, objectives: tuple[str, ...] = ('makespan',))

Single-mode projects with ProGen's network complexity, resource factor, and strength.

Draws, in order: the network (see the module description), the duration of every activity, the requests, and the demand of every request, activity by activity and resource by resource. Capacities follow from the drawn data, with K_min the largest demand on the resource.

Attributes:

Name Type Description
activities int

Number of activities J.

resources int

Number of renewable resources K.

network_complexity float

NC. PSPLIB uses 1.5, 1.8, and 2.1.

resource_factor float

RF in [0, 1]. PSPLIB uses 0.25, 0.5, 0.75, and 1.

resource_strength float

RS in [0, 1].

min_duration int

Shortest duration.

max_duration int

Longest duration.

min_demand int

Smallest demand of a request.

max_demand int

Largest demand of a request.

start_activities int

Number S of activities without predecessors.

finish_activities int

Number F of activities without successors.

max_degree int

Most predecessors, and most successors, of an activity.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the project for seed.

MultiModeRcpsp dataclass

MultiModeRcpsp(activities: int = 20, resources: int = 2, network_complexity: float = 1.5, resource_factor: float = 0.5, resource_strength: float = 0.5, min_modes: int = 2, max_modes: int = 3, min_duration: int = 1, max_duration: int = 10, min_demand: int = 1, max_demand: int = 10, start_activities: int = 3, finish_activities: int = 3, max_degree: int = 3, objectives: tuple[str, ...] = ('makespan',))

Multi-mode projects whose modes trade duration against resource demand.

The network, the requests, and the resource strength follow Rcpsp. An activity's modes all use the resources the activity requests and are listed from shortest to longest: durations strictly increase, the demand on one requested resource strictly decreases, and the demands on the others never increase, so no mode is at least as long and as demanding as another.

Draws, in order: the network; the number of modes and their distinct durations, activity by activity; the requests; then, activity by activity, the resource whose demand strictly decreases, and the demands of each requested resource in resource order, drawn distinct for that resource and freely for the others, and sorted from largest to smallest.

Unlike ProGen, whose modes may request different resources and whose demands may also stay constant as the duration grows, every mode here requests the same resources. K_min is the largest demand of any mode, because the model requires every mode to fit its resources. K_max is the peak of the earliest-start schedule with every activity in its shortest mode, which is also its most demanding one.

Attributes:

Name Type Description
activities int

Number of activities J.

resources int

Number of renewable resources K.

network_complexity float

NC.

resource_factor float

RF in (0, 1].

resource_strength float

RS in [0, 1].

min_modes int

Fewest modes of an activity.

max_modes int

Most modes of an activity.

min_duration int

Shortest duration.

max_duration int

Longest duration.

min_demand int

Smallest demand of a request.

max_demand int

Largest demand of a request.

start_activities int

Number S of activities without predecessors.

finish_activities int

Number F of activities without successors.

max_degree int

Most predecessors, and most successors, of an activity.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

generate

generate(seed: int = 0) -> Problem

Return the multi-mode project for seed.

project_problem

project_problem(modes: Sequence[Sequence[ModeData]], arcs: Iterable[tuple[int, int]], capacities: Sequence[float], *, activity_ids: Sequence[str] | None = None, problem_id: str = 'project', objectives: Sequence[str] = ('makespan',), family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build a project from activity modes, precedence arcs, and resource capacities.

Parameters:

Name Type Description Default
modes Sequence[Sequence[ModeData]]

modes[i] lists activity i's modes as (duration, demands), where demands[k] is the amount of resource k held while the activity runs.

required
arcs Iterable[tuple[int, int]]

Precedence arcs (i, j): activity j starts after i finishes.

required
capacities Sequence[float]

Capacity of each renewable resource r1, r2, ....

required
activity_ids Sequence[str] | None

Task id of each activity. Defaults to a1, a2, ...

None
problem_id str

Id of the problem.

'project'
objectives Sequence[str]

Objectives to optimise, primary first.

('makespan',)
family str | None

Id of the family that generated the data, if any.

None
metadata Mapping[str, Scalar] | None

Annotations stored on the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ModelError

If a demand vector or the id list has the wrong length, or an arc names an unknown activity.

register

register(registry: FamilyRegistry) -> None

Add the project-scheduling families to registry.

dispatchatlas.benchmarks.workflow

Random task graphs on heterogeneous processors.

The workflow family generates the weighted task graphs of Topcuoglu, Hariri and Wu (2002), the generator behind the HEFT and CPOP experiments. A graph has tasks tasks arranged in levels. Each task runs on any one of processors unrelated processors, with a processor-dependent duration, and each edge carries a communication cost that is paid only when its two tasks run on different processors.

The generator draws, in this order:

  1. The height, ceil(U(0, 2 sqrt(v) / shape)) levels, so its mean is sqrt(v) / shape.
  2. One width per level from U(0, 2 shape sqrt(v)), mean shape * sqrt(v). The paper does not say how the widths are made to add up to v; here they are rescaled, largest remainder first, so they sum to exactly v with at least one task per level.
  3. For every task outside the last level, an out-degree from randint(1, 2 out_degree - 1), mean out_degree, and that many distinct successors drawn uniformly from the next level, or the whole next level when it is narrower. The paper leaves the choice of successors open; joining consecutive levels only keeps the height equal to the length of the longest dependency chain. A task that still has no parent then receives one, drawn uniformly from the level above.
  4. For every task, a mean duration w_i from U(0, 2 mean_duration), and for every processor a duration from U(w_i (1 - heterogeneity / 2), w_i (1 + heterogeneity / 2)).
  5. For every edge, a raw weight from U(0, 2). The weights are scaled so the mean communication cost is ccr times the mean duration over all tasks and processors, so every graph has the communication-to-computation ratio of the paper, not only the average graph.

Durations and communication costs are rounded to six decimals.

Communication uses one network endpoint per processor: every pair of processors is joined by a link of bandwidth 1 and no latency, so the transfer time of an edge equals its communication cost, and it is zero on one processor.

The paper draws the average duration w_DAG at random. Here it is the mean_duration parameter, since it only scales the instance.

LayeredGraph dataclass

LayeredGraph(levels: tuple[int, ...], edges: tuple[tuple[int, int], ...])

A directed acyclic graph whose tasks are grouped into levels.

Tasks are numbered level by level, so every edge goes from a lower to a higher task number and the numbering is a topological order.

Attributes:

Name Type Description
levels tuple[int, ...]

Level of each task, starting at 0.

edges tuple[tuple[int, int], ...]

Sorted (before, after) pairs with before < after.

height property

height: int

Number of levels.

RandomTaskGraph dataclass

RandomTaskGraph(tasks: int = 20, shape: float = 1.0, out_degree: int = 2, ccr: float = 1.0, heterogeneity: float = 0.5, processors: int = 4, mean_duration: float = 10.0, objectives: tuple[str, ...] = ('makespan',))

Random task graphs on heterogeneous processors (Topcuoglu, Hariri and Wu 2002).

The draws follow the module description, in its order. The defaults of tasks, shape, out_degree, ccr, and heterogeneity come from the parameter sets of the paper; those of processors and mean_duration, which the paper does not fix, are illustrative.

Attributes:

Name Type Description
tasks int

Number of tasks, v in the paper.

shape float

Shape parameter alpha: above 1 gives wide graphs, below 1 long ones.

out_degree int

Mean number of successors of a task.

ccr float

Communication-to-computation ratio, the mean communication cost over the mean duration.

heterogeneity float

Range percentage beta of a task's durations across processors, between 0 (identical processors) and 2.

processors int

Number of unrelated processors.

mean_duration float

Expected mean duration over tasks and processors, w_DAG in the paper.

objectives tuple[str, ...]

Objectives the problems declare, primary first. The graphs have no due dates, so due-date objectives are refused.

generate

generate(seed: int = 0) -> Problem

Return the task graph for seed.

layered_graph

layered_graph(rng: Random, tasks: int, shape: float, out_degree: int) -> LayeredGraph

Draw the levels and edges of a random task graph.

Follows steps 1 to 3 of the module description: the height and level widths of Topcuoglu, Hariri and Wu (2002), and uniform out-degrees with mean out_degree towards the next level, completed so that every task below the first level has a parent in the level above. Edges join consecutive levels only, and there are at most 2 * out_degree * tasks of them, so the graph stays sparse as it grows.

Parameters:

Name Type Description Default
rng Random

Source of every random draw.

required
tasks int

Number of tasks, at least 1.

required
shape float

Shape parameter. Values above 1 give short, wide graphs with much parallelism; values below 1 give long, narrow ones.

required
out_degree int

Mean number of successors of a task, at least 1.

required

Returns:

Type Description
LayeredGraph

The levels and edges.

Raises:

Type Description
ValueError

If a parameter is out of range.

register

register(registry: FamilyRegistry) -> None

Add the workflow family to registry.

dispatchatlas.benchmarks.continuum

Scheduling across an edge-fog-cloud continuum.

Devices issue applications; compute nodes in the edge, fog, and cloud tiers, and the devices themselves, run their tasks; a network carries data between tiers. Placement is a decision: every compute task has one mode per node it may run on, with duration work / speed on one core of that node. Each application starts and ends on its device, through zero-duration source and sink tasks, so offloading pays upload and download transfers, and the response time of an application runs from its release to its sink. Because nodes and links carry power, price, latency, and bandwidth, the core objectives energy, cost, makespan, and mean_response_time all measure real consequences of placement.

Three families are registered:

  • continuum-offloading: independent requests at Poisson arrival times.
  • continuum-workflow: layered random or fork-join workflows.
  • continuum-pipeline: periodic frames through chains of stages.

The building blocks are public, so other workloads can use the same model:

from dispatchatlas.benchmarks.continuum import (
    Application,
    NodeSpec,
    build_problem,
    three_tier_platform,
)

fast_cloud = NodeSpec(cores=16, speed=6.0, idle_power=60.0, busy_power=300.0)
platform = three_tier_platform(devices=2, cloud=2, nodes={"cloud": fast_cloud})
request = Application(
    "a0", "device-0", release=0.0, work=(2.0,), upload=(1.5,), download=(0.1,)
)
problem = build_problem("one-request", platform, [request], due_factor=2.0)

dispatchatlas.benchmarks.continuum.platform

Compute nodes and network of an edge-fog-cloud continuum.

A Platform is a set of compute nodes, each a Resource whose capacity is its number of cores and whose tier names its layer, plus the Network whose links join the tiers. three_tier_platform() builds the usual layout: devices that issue work, then edge, fog, and cloud nodes of growing speed and distance.

Units: time in seconds; work in work units, the seconds one core of speed 1 needs; data in megabytes; bandwidth in megabytes per second; power in watts; energy in joules; cost in an abstract currency. Durations are rounded to microseconds, and the default link parameters keep transfer times of data given in kilobytes to microseconds too, so models in integer time, such as those of the exact solvers, represent them exactly.

The hardware in DEFAULT_NODES and the links in DEFAULT_LINKS are illustrative orders of magnitude chosen so that no tier is best on every objective. They are not measurements. Override them for any study that depends on their values.

TIERS module-attribute

TIERS: tuple[str, ...] = ('device', 'edge', 'fog', 'cloud')

The tiers of three_tier_platform(), nearest to the data first.

DEFAULT_NODES module-attribute

DEFAULT_NODES: Mapping[str, NodeSpec] = MappingProxyType({'device': NodeSpec(cores=1, speed=1.0, idle_power=0.5, busy_power=2.5, cost_rate=0.0), 'edge': NodeSpec(cores=2, speed=2.0, idle_power=4.0, busy_power=36.0, cost_rate=0.04), 'fog': NodeSpec(cores=8, speed=2.0, idle_power=12.0, busy_power=108.0, cost_rate=0.096), 'cloud': NodeSpec(cores=32, speed=3.0, idle_power=48.0, busy_power=432.0, cost_rate=0.288)})

Illustrative hardware per tier.

One work unit takes 1 s on a device, 0.5 s on an edge or fog node, and 1/3 s in the cloud. It spends 2 J of busy energy on a device, 8 J on the edge, 6 J in the fog, and 4 J in the cloud, and costs nothing on a device, 0.01 on the edge, 0.006 in the fog, and 0.003 in the cloud. Idle power is a ninth of full-load power on edge, fog, and cloud nodes and a fifth on a device. The edge is thus the closest fast tier, the fog has the same speed with more cores, and the cloud is the fastest and cheapest per unit of work but the farthest away.

DEFAULT_LINKS: tuple[Link, ...] = (_join('device', 'device', _ACCESS, _ACCESS), _ACCESS, _join('device', 'fog', _ACCESS, _METRO), _join('device', 'cloud', _ACCESS, _METRO, _WIDE_AREA), Link('edge', 'edge', bandwidth=25.0, latency=0.002, energy_per_unit=0.1), _METRO, _join('edge', 'cloud', _METRO, _WIDE_AREA), Link('fog', 'fog', bandwidth=125.0, latency=0.001, energy_per_unit=0.02), _WIDE_AREA, Link('cloud', 'cloud', bandwidth=1000.0, latency=0.0005, energy_per_unit=0.01))

Illustrative links between every pair of tiers, same-tier pairs included.

Three hops form a chain: wireless access from devices to the edge (12.5 MB/s, 5 ms, 0.5 J/MB), a metro network from the edge to the fog (25 MB/s, 5 ms, 0.1 J/MB), and a wide-area network from the fog to the cloud (5 MB/s, 40 ms, 0.2 J/MB, 0.002 per MB). A transfer between two tiers crosses every hop in between: it gets the narrowest bandwidth and pays the sum of the latencies, energies, and costs, so a device reaches the cloud at 5 MB/s after 50 ms. Nodes of one tier exchange data over a local network.

NodeSpec dataclass

NodeSpec(cores: int = 1, speed: float = 1.0, idle_power: float = 0.0, busy_power: float = 0.0, cost_rate: float = 0.0)

Hardware of one compute node.

A task holds one core while it runs, so a node runs up to cores tasks at once. Energy and cost follow the core model: a task on one of cores cores adds (busy_power - idle_power) / cores watts and costs cost_rate / cores per second.

Attributes:

Name Type Description
cores int

Number of cores, the node's resource capacity.

speed float

Work units one core completes per second. A task of work w runs for w / speed seconds.

idle_power float

Watts drawn while the node is on.

busy_power float

Watts drawn with every core busy.

cost_rate float

Currency per second with every core busy.

Platform dataclass

Platform(resources: tuple[Resource, ...], network: Network)

Compute nodes grouped into tiers, and the links between the tiers.

Each node is a resource with a tier. Its speed is read from its "speed" metadata entry, 1 when absent.

Attributes:

Name Type Description
resources tuple[Resource, ...]

The nodes.

network Network

Links between tiers. A transfer between two different nodes uses the link joining their tiers.

tiers property

tiers: tuple[str, ...]

Tiers that have at least one node, in the order nodes are listed.

nodes

nodes(tier: str) -> tuple[Resource, ...]

Return the nodes of tier, empty when it has none.

resource

resource(node: str) -> Resource

Return the node with id node.

Raises:

Type Description
ConfigError

If the platform has no such node.

speed

speed(node: str) -> float

Return the speed of node node, in work units per second per core.

transfer_time

transfer_time(data: float, source: str, target: str) -> float

Return the time to move data from node source to node target.

Zero for no data or one node, otherwise the transfer time of the link joining the two nodes' tiers, as the core model computes it.

Raises:

Type Description
ConfigError

If the network has no link between the two tiers.

duration

duration(work: float, node: str) -> float

Return the seconds node node needs for work work units.

That is work / speed, rounded to microseconds.

modes

modes(work: float, nodes: Sequence[Resource]) -> tuple[Mode, ...]

Return one mode per node for a task of work work units.

Each mode holds one core of its node for duration() seconds and is located on that node, so choosing a mode places the task.

three_tier_platform

three_tier_platform(*, devices: int = 4, edge: int = 2, fog: int = 1, cloud: int = 1, nodes: Mapping[str, NodeSpec] | None = None, links: Iterable[Link] = ()) -> Platform

Build a platform of devices and of edge, fog, and cloud nodes.

Nodes are named <tier>-<index>, for example edge-0. Devices get the resource kind "device", the other nodes "node", and every node records its speed in its "speed" metadata entry.

Parameters:

Name Type Description Default
devices int

Number of devices.

4
edge int

Number of edge nodes.

2
fog int

Number of fog nodes.

1
cloud int

Number of cloud nodes.

1
nodes Mapping[str, NodeSpec] | None

Hardware per tier replacing DEFAULT_NODES, for example {"cloud": NodeSpec(cores=32, speed=6.0)}.

None
links Iterable[Link]

Links replacing the DEFAULT_LINKS entry that joins the same pair of tiers.

()

Returns:

Type Description
Platform

The platform.

Raises:

Type Description
ConfigError

If a count is negative, or nodes or links name a tier outside TIERS.

dispatchatlas.benchmarks.continuum.applications

Applications that devices issue, and the problems they form on a platform.

An Application is the unit of work a device issues: a request made of one task, a chain of stages, or a whole workflow. build_problem() turns applications into a scheduling problem in which placement is a decision:

  • Every compute task gets one mode per eligible node, with duration work / speed rounded to microseconds and one core of that node, so choosing a mode places the task.
  • Every application gets a zero-duration source task and sink task located on its device. The source sends the input data to the entry tasks, the exit tasks send their results to the sink, and the network prices both transfers. Offloading therefore costs upload and download time, and the response time of the application runs from its release to its sink.
  • All tasks of an application share its release time, weight, and group, so completion-time objectives such as mean_response_time are computed per application.
  • The due date and the optional hard deadline sit on the sink, at the release plus a factor times the application's contention-free response time, rounded up to microseconds.

The contention-free response time is the sink's finish time when resources never make a task wait: each task starts once the data of its predecessors have arrived, and each dependency is priced at the predecessor's best node independently. For a chain, such as a request or a pipeline, this is exactly the best response time the application can have on its own. For a general workflow it is a lower bound on it.

Application dataclass

Application(name: str, device: str, release: float, work: tuple[float, ...], edges: tuple[tuple[int, int, float], ...] = (), upload: tuple[float, ...] = (), download: tuple[float, ...] = (), tiers: tuple[tuple[str, ...], ...] = (), weight: float = 1.0)

A request, pipeline, or workflow that a device issues.

Compute tasks are numbered from 0 in a topological order: every edge goes from a lower to a higher number.

Attributes:

Name Type Description
name str

Identifier of the application. It names the group of its tasks and prefixes their ids: <name>-source, <name>-t<k>, and <name>-sink.

device str

Id of the node that issues the application. Its source and sink tasks are located there.

release float

Time the application is issued.

work tuple[float, ...]

Work of each compute task, in work units.

edges tuple[tuple[int, int, float], ...]

(before, after, data) dependencies between compute tasks, with before < after and the data volume the first sends.

upload tuple[float, ...]

Data the device sends to each compute task. Empty means none. Tasks without predecessors always depend on the source, even without data.

download tuple[float, ...]

Data each compute task returns to the device. Empty means none. Tasks without successors always precede the sink.

tiers tuple[tuple[str, ...], ...]

Tiers each compute task may run on. The "device" tier stands for the issuing device only. Empty means every tier of TIERS for every task.

weight float

Importance of the application in weighted objectives.

entries

entries() -> tuple[int, ...]

Compute tasks that depend on the source.

exits

exits() -> tuple[int, ...]

Compute tasks that precede the sink.

eligible_nodes

eligible_nodes(platform: Platform, application: Application) -> list[tuple[Resource, ...]]

Return the nodes each compute task of application may run on.

Raises:

Type Description
ConfigError

If the device is unknown or a task has no eligible node.

response_bound

response_bound(platform: Platform, application: Application) -> float

Return the contention-free response time of application.

Dynamic programming over the compute tasks in index order: the finish time of task k on node n is its data-ready time on n plus work / speed(n), where the data of each predecessor arrive from the node that makes them arrive first. Durations are those of duration(). The result is the time, after the release, at which the last result reaches the device. Exact for chains, a lower bound for general workflows (see the module description).

build_problem

build_problem(problem_id: str, platform: Platform, applications: Sequence[Application], *, objectives: Sequence[str] = ('mean_response_time', 'energy', 'cost'), due_factor: float | None = None, deadline_factor: float | None = None, family: str | None = None, metadata: Mapping[str, Scalar] | None = None) -> Problem

Build the scheduling problem of applications on platform.

Tasks are listed application by application, each as its source, its compute tasks in index order, and its sink. See the module description for the modes, dependencies, and due dates this creates.

Parameters:

Name Type Description Default
problem_id str

Id of the problem.

required
platform Platform

Nodes and network the applications run on.

required
applications Sequence[Application]

The applications, with distinct names.

required
objectives Sequence[str]

Objectives of the problem, primary first.

('mean_response_time', 'energy', 'cost')
due_factor float | None

Due date of each sink as a multiple of the application's contention-free response time, counted from its release. None sets no due date.

None
deadline_factor float | None

Hard deadline of each sink, as a multiple of the same response time. None sets no deadline.

None
family str | None

Id of the generating family, if any.

None
metadata Mapping[str, Scalar] | None

Annotations of the problem.

None

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ConfigError

If a factor is below 1, two applications share a name, or an application refers to an unknown node or has a task without an eligible node.

dispatchatlas.benchmarks.continuum.families

The continuum benchmark families: offloading, workflows, and pipelines.

Each family draws applications with its own structure and builds the problem with build_problem() on a three_tier_platform() with the default hardware and links. All three share these parameters:

  • devices, edge_nodes, fog_nodes, cloud_nodes: node counts. Applications are assigned to devices in turn.
  • tiers: comma-separated tiers a compute task may run on, "device" meaning the issuing device itself.
  • due_factor and deadline_factor: due date and optional hard deadline of each application, as multiples of its contention-free response time counted from its release (see response_bound()).
  • objectives: objectives the problems declare, primary first.

Work and data volumes are drawn uniformly between half and one and a half times their means. Work and times are rounded to microseconds and data to kilobytes, which keeps every time value of the problems a decimal with at most six digits. Problems are named <family>-<size>-<seed> and record every parameter that is not None, plus the seed, in their metadata, as the other built-in families do. Parameter defaults are illustrative sizes for quick experiments, not calibrated to a measured workload.

STRUCTURES module-attribute

STRUCTURES: tuple[str, ...] = ('layered', 'fork-join')

Task-graph structures of ContinuumWorkflow.

ContinuumOffloading dataclass

ContinuumOffloading(applications: int = 20, arrival_rate: float = 4.0, work: float = 1.0, input_data: float = 1.0, output_data: float = 0.1, due_factor: float = 2.0, deadline_factor: float | None = None, tiers: str = 'device,edge,fog,cloud', devices: int = 4, edge_nodes: int = 2, fog_nodes: int = 1, cloud_nodes: int = 1, objectives: tuple[str, ...] = ('mean_response_time', 'energy', 'cost'))

Independent requests offloaded across an edge-fog-cloud continuum.

Devices issue requests at the arrival times of a Poisson process of rate arrival_rate. Each request is one compute task between a source and a sink on its device: the device uploads input_data, the task processes work on the device itself or on an edge, fog, or cloud node, and output_data returns to the device. Placing the task trades processing speed against transfer time, transfer energy, and money.

Per request the generator draws, in order: the time since the previous request, the work, the input volume, and the output volume.

Attributes:

Name Type Description
applications int

Number of requests.

arrival_rate float

Requests per second over all devices.

work float

Mean work of a request, in work units.

input_data float

Mean data a request uploads, in megabytes.

output_data float

Mean data a request returns, in megabytes.

due_factor float

Due date as a multiple of the best response time on an idle platform.

deadline_factor float | None

Hard deadline as a multiple of the same time, or None for none.

tiers str

Tiers a request may run on, comma-separated.

devices int

Number of devices.

edge_nodes int

Number of edge nodes.

fog_nodes int

Number of fog nodes.

cloud_nodes int

Number of cloud nodes.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

platform

platform() -> Platform

Return the platform the requests run on.

generate

generate(seed: int = 0) -> Problem

Return the problem for seed.

ContinuumWorkflow dataclass

ContinuumWorkflow(applications: int = 4, tasks: int = 10, structure: str = 'layered', shape: float = 1.0, out_degree: int = 2, work: float = 1.0, ccr: float = 1.0, pinned_fraction: float = 0.0, arrival_rate: float = 0.0, due_factor: float = 2.0, deadline_factor: float | None = None, tiers: str = 'device,edge,fog,cloud', devices: int = 4, edge_nodes: int = 2, fog_nodes: int = 1, cloud_nodes: int = 1, objectives: tuple[str, ...] = ('makespan', 'energy', 'cost'))

Workflows that devices submit to an edge-fog-cloud continuum.

Each application is a task graph: a layered random graph drawn as in Topcuoglu, Hariri and Wu (2002), or a fork-join graph in which one task forks parallel tasks that one task joins. The device uploads data to the tasks without predecessors and receives the results of the tasks without successors. Every dependency, uploads and results included, carries a data volume whose mean takes ccr * work seconds to cross the access link between devices and the edge, so ccr is the ratio between moving one dependency's data off a device and processing one task on it.

Per application the generator draws, in order: the time since the previous application (when arrival_rate is positive), the graph, the work of each task, the data of each edge, of each upload, and of each result, and the tasks pinned to the edge.

Attributes:

Name Type Description
applications int

Number of workflows.

tasks int

Compute tasks per workflow.

structure str

"layered" or "fork-join".

shape float

Shape parameter of layered graphs: above 1 gives wide graphs, below 1 long ones.

out_degree int

Mean number of successors of a task in layered graphs.

work float

Mean work of a task, in work units.

ccr float

Communication-to-computation ratio, as defined above.

pinned_fraction float

Share of each workflow's tasks, rounded to the nearest count, that run on edge nodes only, whatever tiers allows.

arrival_rate float

Workflows per second, or 0 to release all at time 0.

due_factor float

Due date as a multiple of the contention-free response time.

deadline_factor float | None

Hard deadline as a multiple of the contention-free response time, or None for none.

tiers str

Tiers a task may run on, comma-separated.

devices int

Number of devices.

edge_nodes int

Number of edge nodes.

fog_nodes int

Number of fog nodes.

cloud_nodes int

Number of cloud nodes.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

platform

platform() -> Platform

Return the platform the workflows run on.

generate

generate(seed: int = 0) -> Problem

Return the problem for seed.

ContinuumPipeline dataclass

ContinuumPipeline(streams: int = 4, frames: int = 5, stages: int = 3, period: float = 1.0, work: float = 0.5, input_data: float = 2.0, reduction: float = 0.5, due_factor: float = 2.0, deadline_factor: float | None = None, tiers: str = 'device,edge,fog,cloud', devices: int = 4, edge_nodes: int = 2, fog_nodes: int = 1, cloud_nodes: int = 1, objectives: tuple[str, ...] = ('mean_response_time', 'energy', 'cost'))

Periodic frames of device streams, each processed by a chain of stages.

Each stream belongs to a device and emits a frame every period seconds from a random phase. A frame is one application: the device uploads input_data, and stages compute tasks process it in turn, each passing on reduction times the data it received, until the last returns its output to the device. All frames of a stream share the same stage work and data volumes. Because the data shrink along the chain, early stages favour nodes near the device and late stages favour fast remote nodes, the trade-off of splitting inference between device and cloud studied by Kang et al. (2017).

Per stream the generator draws, in order: the phase, the work of each stage, and the frame size.

Attributes:

Name Type Description
streams int

Number of streams.

frames int

Frames per stream.

stages int

Compute stages per frame.

period float

Seconds between two frames of a stream.

work float

Mean work of a stage, in work units.

input_data float

Mean frame size, in megabytes.

reduction float

Ratio between the data a stage sends on and the data it received.

due_factor float

Due date as a multiple of the best response time on an idle platform.

deadline_factor float | None

Hard deadline as a multiple of the same time, or None for none.

tiers str

Tiers a stage may run on, comma-separated.

devices int

Number of devices.

edge_nodes int

Number of edge nodes.

fog_nodes int

Number of fog nodes.

cloud_nodes int

Number of cloud nodes.

objectives tuple[str, ...]

Objectives the problems declare, primary first.

platform

platform() -> Platform

Return the platform the streams run on.

generate

generate(seed: int = 0) -> Problem

Return the problem for seed.

fork_join_graph

fork_join_graph(tasks: int) -> LayeredGraph

Return a fork-join graph: one task forks tasks - 2 parallel tasks that one task joins.

With one or two tasks the graph is a single task or a chain of two.

register

register(registry: FamilyRegistry) -> None

Add the continuum families to registry.

dispatchatlas.benchmarks.taillard

Taillard's benchmark instances, regenerated exactly from the published seeds.

Taillard (1993) defined 120 permutation flow-shop instances (ta001 to ta120), 80 job-shop instances (ta01 to ta80), and 60 open-shop instances by a portable random number generator and one or two seeds per instance. This module implements that generator and carries the seed tables distributed with OR-Library (Beasley 1990) in flowshop2.txt, jobshop2.txt, and openshop.txt, so every instance is available offline and identical to the published data.

The generator unif is the Lehmer generator seed <- 16807 * seed mod (2^31 - 1), computed with Schrage's factorisation (b = 127773, c = 2836) so that no intermediate value leaves the 32-bit range, followed by low + floor(seed / (2^31 - 1) * (high - low + 1)). A processing time is unif(seed, 1, 99):

  • Flow shop: d[i][j] for machine i, then job j, all from the time seed.
  • Job shop and open shop: d[i][j] for job j, then operation i, all from the time seed; then each job's machines M[i][j] = i are shuffled by swapping M[i][j] with M[unif(machine seed, i, m)][j] for i = 1..m. Operation i of job j runs on machine M[i][j] for d[i][j]; in an open shop the operations may run in any order.

The open-shop table also records the bounds printed in openshop.txt: an upper bound, marked there with * when it is optimal, and a lower bound.

Instances are named ta001 to ta120 (flow shop), ta01 to ta80 (job shop), and tai<n>x<n>-<k> for the k-th open shop with n jobs and machines, for example tai4x4-1; open shops are also numbered 1 to 60 in file order. The problems follow the conventions of dispatchatlas.benchmarks.shop, so machine M = 1 is resource m0.

TaillardInstance dataclass

TaillardInstance(name: str, problem_class: str, jobs: int, machines: int, time_seed: int, machine_seed: int | None = None, upper_bound: int | None = None, lower_bound: int | None = None, optimal: bool = False, source: str = '')

The published definition of one Taillard instance.

Attributes:

Name Type Description
name str

Instance name, for example "ta001".

problem_class str

"flow-shop", "job-shop", or "open-shop".

jobs int

Number of jobs.

machines int

Number of machines.

time_seed int

Seed of the processing times.

machine_seed int | None

Seed of the machine orders; None for flow shops.

upper_bound int | None

Makespan of the best schedule listed with the seeds, if any.

lower_bound int | None

Makespan lower bound listed with the seeds, if any.

optimal bool

Whether the listed upper bound is marked optimal.

source str

URL of the OR-Library file that lists the seeds.

unif

unif(seed: int, low: int, high: int) -> tuple[int, int]

Advance Taillard's generator once and draw an integer in [low, high].

Parameters:

Name Type Description Default
seed int

Current state, in [1, 2^31 - 2].

required
low int

Smallest value to draw.

required
high int

Largest value to draw.

required

Returns:

Type Description
tuple[int, int]

The next state and the drawn value.

flow_shop_matrix

flow_shop_matrix(time_seed: int, jobs: int, machines: int) -> list[list[int]]

Return the processing times d[i][j] of machine i and job j.

This is Taillard's generate_flow_shop, with rows and columns as printed in the paper and in flowshop2.txt.

job_shop_matrices

job_shop_matrices(time_seed: int, machine_seed: int, jobs: int, machines: int) -> tuple[list[list[int]], list[list[int]]]

Return (d, M): operation i of job j runs on machine M[i][j] for d[i][j].

This is Taillard's generate_job_shop, with rows (operations) and columns (jobs) as printed in jobshop2.txt, and machines numbered from 1.

open_shop_matrices

open_shop_matrices(time_seed: int, machine_seed: int, jobs: int, machines: int) -> tuple[list[list[int]], list[list[int]]]

Return (d, M) of Taillard's generate_open_shop.

The procedure is the same as job_shop_matrices(): job j needs machine M[i][j] for d[i][j], in any order.

flow_shop_instances

flow_shop_instances() -> tuple[TaillardInstance, ...]

Return the 120 flow-shop instances ta001 to ta120 in order.

job_shop_instances

job_shop_instances() -> tuple[TaillardInstance, ...]

Return the 80 job-shop instances ta01 to ta80 in order.

open_shop_instances

open_shop_instances() -> tuple[TaillardInstance, ...]

Return the 60 open-shop instances tai4x4-1 to tai20x20-10 in order.

taillard_instance

taillard_instance(problem_class: str, instance: str | int) -> TaillardInstance

Return the definition of one instance.

Parameters:

Name Type Description Default
problem_class str

"flow-shop", "job-shop", or "open-shop".

required
instance str | int

Name, such as "ta001", "ta01", or "tai4x4-1", or the instance's number in its table, starting at 1.

required

Raises:

Type Description
ConfigError

If the class or the instance is unknown.

taillard_flow_shop

taillard_flow_shop(instance: str | int) -> Problem

Return a Taillard permutation flow shop, for example taillard_flow_shop("ta001").

Raises:

Type Description
ConfigError

If the instance is unknown.

taillard_job_shop

taillard_job_shop(instance: str | int) -> Problem

Return a Taillard job shop, for example taillard_job_shop("ta01").

Raises:

Type Description
ConfigError

If the instance is unknown.

taillard_open_shop

taillard_open_shop(instance: str | int) -> Problem

Return a Taillard open shop, for example taillard_open_shop("tai4x4-1").

The published bounds are recorded in the problem's metadata as upper_bound, lower_bound, and optimal.

Raises:

Type Description
ConfigError

If the instance is unknown.

dispatchatlas.benchmarks.suites

Published benchmark suites: their instances, sources, references, and loaders.

A Suite describes one published instance set. Two kinds exist:

  • Generated suites, Taillard's (1993) flow, job, and open shops, are rebuilt exactly from their published seeds by dispatchatlas.benchmarks.taillard, so they load offline.
  • File suites, the OR-Library job and flow shops, Brandimarte's flexible job shops, and the PSPLIB projects, are read from files that the user downloads from Suite.source into a directory. The library does not bundle these files.

Example:

from dispatchatlas.benchmarks import suites
ta001 = suites.load("taillard-flow-shop", "ta001")
ft06 = suites.load("orlib-job-shop", "ft06", directory="downloads/orlib")

Bound dataclass

Bound(lower: float | None = None, upper: float | None = None, optimal: bool = False, objective: str = 'makespan')

Published bounds on the optimal value of one instance.

Attributes:

Name Type Description
lower float | None

Lower bound, if published.

upper float | None

Value of the best published schedule, if any.

optimal bool

Whether upper is proven optimal.

objective str

Objective the bounds refer to.

Suite dataclass

Suite(id: str, name: str, problem_class: str, instances: tuple[str, ...], source: str, references: tuple[str, ...], loader: Loader, files: str | None = None, bounds: Mapping[str, Bound] = dict(), notes: str = '')

One published benchmark suite.

Attributes:

Name Type Description
id str

Registry key, for example "taillard-flow-shop".

name str

Human-readable name.

problem_class str

Problem class of every instance, as in problem_class.

instances tuple[str, ...]

Instance names, in the order of the source.

source str

URL of the published instances or of the seeds that generate them.

references tuple[str, ...]

Bibliography keys of the works that define the instances.

loader Loader

Builds an instance from its name and, for file suites, the directory that holds the downloaded files.

files str | None

What to download from source into the directory passed to load(). None for suites generated offline.

bounds Mapping[str, Bound]

Bounds published with the instances, keyed by instance name.

notes str

Further facts about the suite.

generated property

generated: bool

Whether the instances are generated offline rather than read from files.

load

load(instance: str, directory: str | Path | None = None) -> Problem

Return one instance of the suite.

Parameters:

Name Type Description Default
instance str

Instance name; case does not matter.

required
directory str | Path | None

Directory holding the downloaded files, searched recursively. Required for file suites, ignored otherwise.

None

Raises:

Type Description
ConfigError

If the instance is unknown, or a file suite gets no directory or cannot find the instance's file in it.

suites

suites() -> tuple[Suite, ...]

Return every suite: the generated ones first, then the file suites.

suite

suite(suite_id: str) -> Suite

Return the suite with the given id.

Raises:

Type Description
ConfigError

If no suite has that id.

load

load(suite_id: str, instance: str, directory: str | Path | None = None) -> Problem

Return one instance of a suite. See Suite.load().

dispatchatlas.benchmarks.formats

Readers for published instance-file formats.

Each reader turns the text of one instance into a Problem built with the same builders as the generated families, so a read instance and a generated one have the same shape. The formats, by name:

load_instance() reads a file with the reader its extension or the format argument selects; OR-Library files, usually .txt, need format:

from dispatchatlas.benchmarks.formats import load_instance
problem = load_instance("jobshop1.txt", format="orlib-job-shop", instance="ft06")

FORMATS module-attribute

FORMATS: Mapping[str, Callable[..., Problem]] = MappingProxyType({'orlib-job-shop': read_orlib_job_shop, 'orlib-flow-shop': read_orlib_flow_shop, 'fjs': read_fjs, 'psplib': read_psplib})

Readers by format name.

EXTENSIONS module-attribute

EXTENSIONS: Mapping[str, str] = MappingProxyType({'.fjs': 'fjs', '.sm': 'psplib', '.mm': 'psplib'})

Format name implied by a file extension. OR-Library files need an explicit format.

load_instance

load_instance(path: str | Path, format: str | None = None, **options: Any) -> Problem

Read one instance file.

Parameters:

Name Type Description Default
path str | Path

The file.

required
format str | None

A key of FORMATS. Defaults to the format its extension implies, see EXTENSIONS.

None
**options Any

Keyword arguments of the reader, such as instance for OR-Library files or ignore_nonrenewable for PSPLIB files. The problem id defaults to instance when given, else to the file name without its extension.

{}

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
ConfigError

If the format is unknown or cannot be inferred, or an option is not accepted by the reader.

SerializationError

If the file is malformed.

dispatchatlas.benchmarks.formats.orlib

The OR-Library text format of job-shop and flow-shop instances.

An instance is a size line n m followed by one line per job that lists the machine time pairs of its operations in processing order. OR-Library (Beasley 1990) numbers machines from 0; Taillard's generator program can also number them from 1, which first_machine=1 reads. Lines before the size line, such as a description or the # comments of the JSPLIB collection, are skipped. Processing times may be zero, as in orb07 and in Heller's flow shops.

The files jobshop1.txt (82 job shops) and flowshop1.txt (31 flow shops) hold many instances: each starts with a line instance <name> and a description line, and lines of + separate them. split_orlib() cuts such a file into single instances, and the readers do it themselves when given instance=.

split_orlib

split_orlib(text: str) -> dict[str, str]

Split a multi-instance OR-Library file into one text per instance.

Parameters:

Name Type Description Default
text str

Contents of a file such as jobshop1.txt or flowshop1.txt.

required

Returns:

Type Description
dict[str, str]

The instance texts keyed by instance name, in file order. Each text

dict[str, str]

holds the description line, the size line, and the job lines. Empty

dict[str, str]

when the text has no instance <name> lines.

Raises:

Type Description
SerializationError

If an instance name appears twice.

read_orlib_job_shop

read_orlib_job_shop(text: str, *, instance: str | None = None, problem_id: str | None = None, first_machine: int = 0) -> Problem

Read a job shop in the OR-Library format.

Parameters:

Name Type Description Default
text str

One instance, or a multi-instance file when instance is given.

required
instance str | None

Name of the instance to extract from a multi-instance file.

None
problem_id str | None

Id of the problem. Defaults to instance, else "orlib-job-shop".

None
first_machine int

Number of the first machine in the text, 0 or 1.

0

Returns:

Type Description
Problem

The job shop, built by job_shop_problem().

Raises:

Type Description
SerializationError

If the text is malformed or lacks the instance.

ConfigError

If first_machine is neither 0 nor 1.

read_orlib_flow_shop

read_orlib_flow_shop(text: str, *, instance: str | None = None, problem_id: str | None = None, first_machine: int = 0, permutation: bool = True) -> Problem

Read a flow shop in the OR-Library format.

Every job must visit the machines in increasing order, as in OR-Library's flowshop1.txt and the files of Taillard's generator.

Parameters:

Name Type Description Default
text str

One instance, or a multi-instance file when instance is given.

required
instance str | None

Name of the instance to extract from a multi-instance file.

None
problem_id str | None

Id of the problem. Defaults to instance, else "orlib-flow-shop".

None
first_machine int

Number of the first machine in the text, 0 or 1.

0
permutation bool

Require one common job order on every machine, as in the permutation flow-shop benchmarks.

True

Returns:

Type Description
Problem

The flow shop, built by flow_shop_problem().

Raises:

Type Description
SerializationError

If the text is malformed, lacks the instance, or describes jobs that do not visit the machines in order.

ConfigError

If first_machine is neither 0 nor 1.

dispatchatlas.benchmarks.formats.fjs

The FJSPLib .fjs format of flexible job-shop instances.

The format of the collection compiled by Mastrolilli and Gambardella (2000), which holds the instances of Brandimarte (1993) among others: a header line n m with an optional third number, the average number of machines per operation, which is ignored; then per job the number of operations and, per operation, the number k of machines that can run it followed by k machine time pairs. Machines are numbered from 1. Some mirrors number them from 0, which first_machine=0 reads. Blank lines are ignored.

read_fjs

read_fjs(text: str, *, problem_id: str = 'fjs', first_machine: int = 1) -> Problem

Read a flexible job shop in the .fjs format.

Every machine option of an operation becomes one mode.

Parameters:

Name Type Description Default
text str

The instance.

required
problem_id str

Id of the problem.

'fjs'
first_machine int

Number of the first machine in the text, 0 or 1.

1

Returns:

Type Description
Problem

The flexible job shop, built by

Problem

Raises:

Type Description
SerializationError

If the text is empty, truncated, or has trailing values, a count below 1, a machine out of range, or a negative processing time.

ConfigError

If first_machine is neither 0 nor 1.

dispatchatlas.benchmarks.formats.psplib

The PSPLIB format of single-mode (.sm) and multi-mode (.mm) projects.

PSPLIB (Kolisch and Sprecher 1997) files list the jobs with their modes, successors, durations, and requests, then the resource availabilities. Job 1 and the last job are a dummy source and sink with zero duration and no requests; the reader drops them, so J30 instances have 30 tasks. Tasks keep their PSPLIB job numbers (a02 to a31 in J30) and renewable resources their numbers (r1, r2, ...).

A mode that requests more of a renewable resource than is available can never run, and is dropped. The model has renewable resources only. A nonrenewable resource whose availability covers the largest request of every job's remaining modes cannot constrain a schedule and is dropped. One that can is refused, unless ignore_nonrenewable=True drops it too, which turns the instance into a relaxation of the published one. Doubly constrained resources are refused.

read_psplib

read_psplib(text: str, *, problem_id: str = 'psplib', ignore_nonrenewable: bool = False) -> Problem

Read a PSPLIB project in the .sm or .mm format.

Parameters:

Name Type Description Default
text str

The instance.

required
problem_id str

Id of the problem.

'psplib'
ignore_nonrenewable bool

Drop nonrenewable resources even when they constrain the choice of modes.

False

Returns:

Type Description
Problem

The project, built by project_problem().

Problem

Its metadata records the horizon of the file, and dropped_modes

Problem

or ignored_nonrenewable when the reader dropped anything.

Raises:

Type Description
SerializationError

If the text is malformed.

ModelError

If the instance needs a resource the model lacks, or a job has no mode that fits the renewable resources.

dispatchatlas.benchmarks.wfcommons

Reading WfCommons workflow instances onto a continuum platform.

WfCommons (Coleman et al. 2022) publishes executions of real scientific workflows in the WfFormat JSON format. read_wfcommons() maps one instance onto a Platform:

  • Every workflow task becomes a task with one mode per eligible node. Its recorded runtime is taken as its work, so it runs runtime / speed seconds on one core of the chosen node, whatever number of cores the execution records for it.
  • Every parent-child pair becomes a dependency that carries the bytes of the files the parent writes and the child reads, divided by bytes_per_unit to express them in the platform's data unit (megabytes by default). The network then prices the transfer whenever the two tasks run on different nodes. A file that several children read is carried by the dependency of each of them, a file that a task lists more than once counts once, and a pair that shares no file is a dependency without data.
  • All tasks form one group, the workflow, and are released at time 0.

A file is represented only where it passes from a task to one of the declared children of that task. Three kinds of file lie on no dependency and are left out, whatever their size: files that no task of the workflow writes (its inputs), files that no task reads (its results), and files that one task writes and another reads when the two are not declared parent and child. The machines, core counts, memory, and start times that an execution records are not read.

The reader consumes a few fields and checks each of them; anything missing or malformed raises SerializationError naming the field, and naming the file when the instance is read from one:

  • Runtimes are never invented: a task without a recorded runtime is refused, and so is an instance of schema 1.5 or 1.6 that has no execution section. Zero runtimes are accepted, as recorded measurements.
  • A file size is a non-negative whole number of bytes, written as a JSON integer or as a real number without a fractional part, such as 2048.0 or 1e6.
  • Task identifiers are kept as written. One that starts or ends with white space is refused, since the data model does not hold such an id.
  • A document that contradicts itself is refused: a task or an execution entry listed twice, an execution entry for a task that the specification does not list, a parent or child that is not a task, a file listed with two sizes, a task that depends on itself, or dependencies that form a cycle.
  • A runtime, a duration, or the bytes of a dependency that a floating-point number cannot hold are refused.
  • A file is UTF-8 text, with or without a byte-order mark. A file in which a JSON object repeats a key is refused.

Supported schemaVersion values and the fields read:

  • 1.4: workflow.tasks[] with name (the task's identity), parents and children (task names), runtimeInSeconds, and files[] entries with name, sizeInBytes, and link ("input" or "output").
  • 1.5 and 1.6: workflow.specification.tasks[] with id, parents, children, inputFiles, and outputFiles; workflow.specification.files[] with id and sizeInBytes; and workflow.execution.tasks[] with id and runtimeInSeconds.

The lists of parents, children, and files are optional in every version: a task without one has none. Dependencies are the union of the parents and children lists, each pair counted once, so a pair that only one of its two tasks declares is a dependency.

SCHEMA_VERSIONS module-attribute

SCHEMA_VERSIONS: tuple[str, ...] = ('1.4', '1.5', '1.6')

WfFormat schema versions read_wfcommons() reads.

read_wfcommons

read_wfcommons(source: Mapping[str, Any] | str | PathLike[str], platform: Platform, *, tiers: Sequence[str] | None = None, problem_id: str | None = None, objectives: str | Sequence[str] = ('makespan',), bytes_per_unit: float = 1000000.0) -> Problem

Read a WfCommons WfFormat instance as a problem on platform.

Parameters:

Name Type Description Default
source Mapping[str, Any] | str | PathLike[str]

The parsed JSON document, as a mapping, or the path of a JSON file. A string is always a path, never JSON text. The numbers of a mapping may be of any type registered with numbers, such as NumPy scalars.

required
platform Platform

Nodes and network the workflow runs on.

required
tiers Sequence[str] | None

Tiers whose nodes may run tasks, as a sequence of names other than a string, each tier once and each with a node. Defaults to every tier of the platform except "device".

None
problem_id str | None

Id of the problem, a non-empty string without surrounding spaces. Defaults to the file name without its extension when source is a path, and to the instance name when it is a mapping. In either default, characters outside letters, digits, ., _, and - are replaced by - and leading punctuation is dropped, so that the id starts with a letter or digit. A file name that leaves nothing gives way to the name, and a name that is absent or leaves nothing to "wfcommons". The name is kept in the metadata of the problem, under "name".

None
objectives str | Sequence[str]

One objective name or several, primary first. The problem has no due dates, so an objective that needs them is refused.

('makespan',)
bytes_per_unit float

Bytes per data unit of the platform's bandwidths.

1000000.0

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
SerializationError

If the document is not a supported WfFormat instance or its content is inconsistent. The message names the file when source is a path.

ConfigError

If an objective is unknown, repeated, or needs due dates, tiers is a string, repeats a tier, or names a tier without a node, a node has less than one core, bytes_per_unit is not a positive number, problem_id is not a non-empty string without surrounding spaces, platform is not a platform, or source is neither a mapping nor a path: it is neither a mapping, a string, nor an os.PathLike object, or its path is not text, holds a null character, or cannot be written in the encoding of file names.

OSError

If the file cannot be read.

dispatchatlas.benchmarks.pegasus

Reading Pegasus DAX workflow files onto a continuum platform.

The Pegasus workflow management system (Deelman et al. 2015) describes an abstract workflow in an XML document, the DAX. The synthetic scientific workflows of Bharathi et al. (2008) and Juve et al. (2013), which model Montage, CyberShake, Epigenomics, LIGO Inspiral, and SIPHT, are distributed in schema 2.1 of that format with two additions: a runtime on every job and a size on every file a job uses. read_pegasus_dax() maps one such file onto a Platform:

  • Every job becomes a task with one mode per eligible node. Its runtime is taken as its work, so it runs runtime / speed seconds on one core of the chosen node.
  • Every parent listed in a child element becomes a dependency that carries the bytes of the files the parent writes and the child reads, divided by bytes_per_unit to express them in the platform's data unit (megabytes by default). The network then prices the transfer whenever the two tasks run on different nodes.
  • All tasks form one group, the workflow, and are released at time 0.

The elements and attributes read:

  • The root adag, in the namespace DAX_NAMESPACE or in none. Its name and version, when present, are kept in the problem's metadata.
  • Every job under the root: id (the task's id), runtime in seconds, and name and namespace, kept in the task's metadata as transformation and namespace.
  • Every uses under a job: file, link, and size in bytes. The link input marks a file the job reads, output one it writes, inout one it reads and writes, and none one it does neither with.
  • Every child under the root and every parent under a child: ref, the id of a job.

Everything else is ignored: other elements, such as filename, argument, and profile; other attributes, such as version, level, and cores of a job, register, transfer, optional, and type of a file, and the counts of the root, which are not compared with the content. Every task holds one core, whatever cores says.

Sizes belong to one job's listing of a file, not to the file name: one name can be listed with different sizes by different jobs, and written by several jobs. The data of a dependency is therefore read on that dependency alone. For every file name the parent lists as written and the child lists as read, it takes the size the parent gives, or the size the child gives when the parent gives none; the sizes other jobs give for the same name play no part. A uses without a size is accepted, and only a file passed along a dependency with a size on neither end is refused. A job that lists one file twice with the same link must give it one size.

Only child elements create dependencies. A file that one job writes and another reads adds none by itself, and a dependency between two jobs that share no file carries no data. Each parent-child pair is counted once.

Runtimes and sizes are never invented or corrected. They are finite decimal numbers in ASCII digits, with an optional minus sign, fraction, and exponent, and may have the white space of XML around them. No other form is read, such as nan, inf, 1_000, a plus sign in front of the number, or digits outside ASCII. A job without a runtime, or with a negative one, is refused, as is a negative size. Zero runtimes are accepted. A runtime too large to give a finite duration on a node, and files too large to give a dependency a finite amount of data, are refused as well.

The file must be UTF-8 text, with or without a byte-order mark. A file that contains a NUL character is refused: XML allows none, a file in UTF-16 or UTF-32 has them, and the XML parser takes a NUL among the first two bytes of a document as the sign of UTF-16, whatever encoding it is told to use. The decoded text is then searched for a document type declaration (<!DOCTYPE) and for an entity declaration (<!ENTITY) anywhere, a comment included, and a document that has one is refused before the XML parser is given it, so the parser meets no declared entity to expand or fetch. The parser reads the same decoded text as UTF-8, whatever encoding the document declares, and its tree builder raises when the parser reports a document type declaration to it, so no problem is built from a declaration the search missed. Anything missing or malformed raises SerializationError naming the file and the element.

DAX_NAMESPACE module-attribute

DAX_NAMESPACE = 'http://pegasus.isi.edu/schema/DAX'

XML namespace of the DAX elements. Documents without a namespace are read too.

read_pegasus_dax

read_pegasus_dax(source: str | PathLike[str], platform: Platform, *, tiers: Sequence[str] | None = None, problem_id: str | None = None, objectives: str | Sequence[str] = ('makespan',), bytes_per_unit: float = 1000000.0) -> Problem

Read a Pegasus DAX workflow file as a problem on platform.

Parameters:

Name Type Description Default
source str | PathLike[str]

Path of the DAX file, as a string or an os.PathLike object.

required
platform Platform

Nodes and network the workflow runs on.

required
tiers Sequence[str] | None

Tiers whose nodes may run tasks, as a sequence of names other than a string, each tier once and each with a node. Defaults to every tier of the platform except "device".

None
problem_id str | None

Id of the problem, a non-empty string without surrounding spaces. Defaults to the file name without its extension, and to the name of the adag element when the file name leaves nothing. In either default, characters outside letters, digits, ., _, and - are replaced by - and leading punctuation is dropped, so that the id starts with a letter or digit. The file name comes first because many files can share one adag name. A name that is absent or leaves nothing gives way to "pegasus-dax".

None
objectives str | Sequence[str]

One objective name or several, primary first. The problem has no due dates, so an objective that needs them is refused.

('makespan',)
bytes_per_unit float

Bytes per data unit of the platform's bandwidths.

1000000.0

Returns:

Type Description
Problem

The problem.

Raises:

Type Description
SerializationError

If the file is not a DAX document the reader accepts, its content is inconsistent, or a runtime or the files of a dependency are too large for a finite duration or amount of data.

ConfigError

If an objective is unknown, repeated, or needs due dates, tiers is a string, repeats a tier, or names a tier without a node, a node has less than one core, bytes_per_unit is not a positive number, problem_id is not a non-empty string without surrounding spaces, platform is not a platform, or source is not a path: it is neither a string nor an os.PathLike object, or its path is not text, holds a null character, or cannot be written in the encoding of file names.

OSError

If the file cannot be read.

dispatchatlas.benchmarks.alibaba

Reading the batch jobs of the Alibaba 2018 cluster trace onto a continuum platform.

The Alibaba cluster trace cluster-trace-v2018 (Alibaba Group 2018) records eight days of a production cluster of about 4000 machines that runs online services and batch jobs side by side (Guo et al. 2019). Its table batch_task.csv has one row per task of a batch job, and the task names encode the dependencies inside each job; Tian, Zheng and Wang (2019) characterise the resulting graphs. iter_alibaba_batch() reads the table as a stream and yields one problem per job on a Platform:

  • Every task of the job becomes a task with one mode per eligible node. The task's work, chosen by work, makes it run work / speed seconds on one core of the chosen node.
  • Every dependency decoded from the task names becomes a dependency. The table records no data volumes, so every dependency carries edge_data, 0 by default. With a positive value, the network prices the transfer whenever the two tasks run on different nodes.
  • The tasks of a job form one group, named after the job, and are released at time 0. The job name is the problem's id.

Rows. The table is UTF-8 text without a header and without quoted fields. A byte-order mark at its start and Windows line endings are accepted. Each row has nine comma-separated fields, listed in COLUMNS: task_name, instance_num, job_name, task_type, status, start_time, end_time, plan_cpu (100 for one core), and plan_mem (memory normalised to the range 0 to 100). instance_num, start_time, and end_time are integers, written as at most 18 ASCII digits after an optional minus sign; the times count seconds from the start of the trace. plan_cpu and plan_mem are finite decimal numbers, written in ASCII digits with an optional minus sign, fraction, and exponent. A numeric field may be empty, which stands for a missing value: the trace leaves instance_num, plan_cpu, and plan_mem empty in some rows. Blank lines are ignored. Any other row that does not have nine fields, whose task or job name is empty or has surrounding spaces, or whose numeric field has another form, such as nan, inf, 1_000, a plus sign, spaces around the number, or digits outside ASCII, raises SerializationError naming the row.

A task name and a job name consist of printable ASCII characters other than the two quote characters, as they do in the trace. A name with a quote, a control character, or a character outside ASCII raises SerializationError naming the row. The reader does not interpret quoted fields, and a stray character in front of a task name would hide its dependency code: a byte-order mark inside the table, as where two files were joined, or one at its start that was decoded with another encoding than UTF-8. A file that is passed open must therefore be opened as UTF-8.

Jobs. The rows of one job are consecutive in the trace, and the reader relies on it. It holds the rows of one job at a time and closes the job at the first row that names another, so its memory does not grow with the number of jobs. In that memory it cannot check the assumption completely. It keeps the names of the last 1024 jobs and raises SerializationError when one of them returns, because the job would be read in pieces. A name that returns after more jobs than that is not noticed: each run of its rows is read as a job of its own, and the problems of the runs share an id. In a table whose jobs are consecutive, as they are in the trace, every job is read whole and the ids of the problems are distinct.

Task names. parse_alibaba_task_name() reads a name in one of four ways:

  • A dependency code is one or more letters, the task's number in its job, and then the numbers of the tasks it depends on, each after an underscore. M1 is task 1 and depends on nothing, R4_2 is task 4 and depends on task 2, and M5_3_4 is task 5 and depends on tasks 3 and 4. The letters say nothing about dependencies. A task may start once every task it depends on has finished.
  • A cut-off code is a code followed by an underscore, such as M5_3_, or a name of 50 characters or more that starts like a code, with letters and a digit. The trace keeps 50 characters of a name. A cut removes whole dependencies or the last digits of one, and a complete code of 50 characters cannot be told from a cut one, so the dependencies of neither can be recovered.
  • An unknown code is any other name that starts like a code, such as M2_1_Stg3, whose suffix the documentation of the trace does not define.
  • Any other name, such as task_ followed by random characters or MergeTask, belongs to an independent task, which depends on nothing.

Skipped jobs. The reader never completes a job with a value the trace does not record. A job is skipped whole, and on_skip is called with its name and a reason, when one of the following holds. The reason is the first that applies, in the order of SKIP_REASONS:

  • "status": the status of a task is not one of statuses.
  • "time": the start or end time of a task is missing or reversed. The trace writes 0 where it records no time: both times of most waiting tasks are 0, and so is the end time of many running tasks. A 0 cannot be told from the first second of the trace, so a time that is empty or not positive is missing. An end time before the start time is reversed. Equal times are accepted, as a recorded span of zero.
  • "demand": with work="core_seconds", the instance_num or plan_cpu of a task is empty or not positive.
  • "truncated-name": a task name is a cut-off code.
  • "unknown-name": a task name is an unknown code.
  • "duplicate-task": two tasks have the same name or the same number.
  • "missing-dependency": a task depends on a number that no task of the job has.
  • "cycle": the dependencies form a cycle, as when a task depends on itself.
  • "dependency-time": with work="after_dependencies", a task ends before a task it depends on ends, so the times of the two contradict the dependency.
  • "too-few-tasks" and "too-many-tasks": the job has fewer tasks than min_tasks or more than max_tasks.

Work. work chooses one of three ways, listed in WORK_RULES, to derive the work of a task from the times the trace records:

  • "duration", the default, takes the recorded span of the task, end_time - start_time seconds.
  • "core_seconds" multiplies the span by instance_num and by plan_cpu / 100: the core-seconds the instances of the task request when each of them runs for the whole span.
  • "after_dependencies" takes the part of the span that lies after the tasks the task depends on: end_time - max(start_time, latest) seconds, where latest is the latest end_time among the tasks it depends on. For a task that depends on nothing it is the span.

The span of a task is not its run time. The reader takes the times of each task as they are recorded, and the trace gives the two tasks of a dependency one start time in about four dependencies of five, although no instance of a task starts before every instance of the tasks it depends on has completed (Alibaba Group 2018). The span of a dependent task therefore contains the time it waited, and "duration" and "core_seconds" overstate its work. In about four of five jobs with dependencies of the trace, the spans along the longest path of dependencies add up to more than the time from the job's earliest start to its latest end, and at the median to twice that time.

"after_dependencies" leaves out the wait that the recorded times show. What remains is the longest the task can have run, an upper bound and not a measurement, because the table does not record when a task began to run. Under this rule the works along any path of dependencies add up to at most the time from the job's earliest start to its latest end. The times are whole seconds, so a task that ends in the second in which the last task it depends on ends has a work of zero: about a fifth of the tasks of the trace under this rule, against about a twentieth whose span is zero.

Metadata. Each task records its instance_num, plan_cpu, plan_mem, task_type, status, start_time, and end_time under those names, without the fields the trace leaves empty. Each problem records its source, the job name as job, the earliest start time of its tasks as arrival, and the work rule as work, so jobs can be filtered further or laid out on the time axis of the trace.

COLUMNS module-attribute

COLUMNS: tuple[str, ...] = ('task_name', 'instance_num', 'job_name', 'task_type', 'status', 'start_time', 'end_time', 'plan_cpu', 'plan_mem')

The fields of a row of batch_task.csv, in order.

STATUSES module-attribute

STATUSES: tuple[str, ...] = ('Terminated', 'Failed', 'Running', 'Waiting')

The task statuses of the trace.

WORK_RULES module-attribute

WORK_RULES: tuple[str, ...] = ('duration', 'core_seconds', 'after_dependencies')

The ways iter_alibaba_batch() derives the work of a task.

SKIP_REASONS module-attribute

SKIP_REASONS: tuple[str, ...] = ('status', 'time', 'demand', 'truncated-name', 'unknown-name', 'duplicate-task', 'missing-dependency', 'cycle', 'dependency-time', 'too-few-tasks', 'too-many-tasks')

The reasons iter_alibaba_batch() skips a job, first to apply first.

parse_alibaba_task_name

parse_alibaba_task_name(name: str) -> tuple[int, tuple[int, ...]] | None

Decode the dependency code of a task name of the Alibaba 2018 trace.

Parameters:

Name Type Description Default
name str

The task_name field of a row of batch_task.csv.

required

Returns:

Type Description
tuple[int, tuple[int, ...]] | None

The task's number in its job and the numbers of the tasks it depends

tuple[int, tuple[int, ...]] | None

on, in the order of the name and each once, or None for the name

tuple[int, tuple[int, ...]] | None

of an independent task. "J4_2_3" gives (4, (2, 3)) and

tuple[int, tuple[int, ...]] | None

"M1" gives (1, ()).

Raises:

Type Description
ConfigError

If name is not a string.

SerializationError

If the name is a cut-off code or an unknown code, as the module documentation defines them.

iter_alibaba_batch

iter_alibaba_batch(source: str | PathLike[str] | Iterable[str], platform: Platform, *, tiers: Sequence[str] | None = None, objectives: str | Sequence[str] = ('makespan',), statuses: Sequence[str] = ('Terminated',), min_tasks: int = 1, max_tasks: int | None = None, work: str = 'duration', edge_data: float = 0.0, on_skip: Callable[[str, str], None] | None = None) -> Generator[Problem, None, None]

Read the batch jobs of the Alibaba 2018 trace as problems on platform.

The arguments are checked when the function is called. The source is read while the returned generator is consumed: the reader takes rows until one names another job, then yields the finished job or reports it to on_skip before it reads further.

Parameters:

Name Type Description Default
source str | PathLike[str] | Iterable[str]

The path of batch_task.csv, or any iterable of its text lines, such as a file opened as UTF-8. A string is always a path. A path is opened when the first problem is asked for, and the file stays open until the generator is exhausted, raises, or is closed. An iterable is never closed by the reader.

required
platform Platform

Nodes and network the jobs run on.

required
tiers Sequence[str] | None

Tiers whose nodes may run tasks, as a sequence of names other than a string, each tier once and each with a node. Defaults to every tier of the platform except "device".

None
objectives str | Sequence[str]

One objective name or several, primary first. The problems have no due dates, so an objective that needs them is refused.

('makespan',)
statuses Sequence[str]

Statuses, of STATUSES, that the tasks of a job may have, as a sequence of names other than a string.

('Terminated',)
min_tasks int

Smallest number of tasks of a job that is read.

1
max_tasks int | None

Largest number of tasks of a job that is read, or None for no limit.

None
work str

How the work of a task is derived, one of WORK_RULES. "duration" takes the recorded span of the task and "core_seconds" the core-seconds its instances request over that span. The span of a task with dependencies includes the time it waited for them, so both overstate the work of such a task, about twofold along the longest path of a job with dependencies. "after_dependencies" takes only the part of the span after the tasks it depends on have ended, and skips a job whose times contradict a dependency. The module documentation defines the three rules.

'duration'
edge_data float

Data volume of every dependency, in the data unit of the platform's bandwidths.

0.0
on_skip Callable[[str, str], None] | None

Called with the job name and the reason, one of SKIP_REASONS, for every job that is skipped, in the order of the source. An exception it raises reaches the caller of the generator and ends the iteration: the jobs after it are not read.

None

Returns:

Type Description
None

A generator of one problem per job that is read, in the order of the

None

source. Its close method ends the iteration and closes the file of

None

a source that was given as a path.

Raises:

Type Description
ConfigError

If an argument is invalid: an unknown or repeated objective, status, or tier, an objective that needs due dates, a string given for tiers or statuses, a tier without a node, a node with less than one core, a task limit below 1, max_tasks below min_tasks, an unknown work rule, a negative edge_data, a positive edge_data on a platform whose network lacks a link between two eligible nodes, or a source that is neither a path nor an iterable of lines: bytes, an object that is not iterable, or a path that is not text, holds a null character, or cannot be written in the encoding of file names.

SerializationError

While iterating, if a row is malformed, a job name returns among the last 1024 jobs, the source is not UTF-8 text, a job that is otherwise read has a task whose core-seconds are too large for a floating-point number, or a job cannot be built on the platform.

OSError

While iterating, if the file cannot be read.

dispatchatlas.benchmarks.catalog

Named instance catalogs, and writing instance sets to disk reproducibly.

A Catalog is a declarative list of registered families, each with parameter values and an instance count. build_catalog() generates every instance, deriving each seed from one root seed with derive_seed() under the namespace <catalog>/<entry> and the instance index, so an instance never depends on the entries listed before it. The instance ids are <entry>-<index>.

Built-in catalogs:

  • smoke: two tiny instances of every built-in family, for fast checks.
  • continuum: the continuum families on a small, medium, and large platform, five instances each.
  • workflow: random task graphs over part of the design of Topcuoglu, Hariri and Wu (2002): 20, 60, and 100 tasks, communication-to-computation ratios 0.1, 1, and 10, and shapes 0.5, 1, and 2.

materialize() writes a set of problems to a directory as problems/<id>.json plus a manifest.json that records, for every file, its SHA-256 digest, its family, its parameters, and its seed. Nothing in either depends on the clock or the machine, so writing the same problems twice gives identical bytes. load_directory() reads the set back and, by default, checks every file against its digest.

MANIFEST_FORMAT module-attribute

MANIFEST_FORMAT = 'dispatchatlas.catalog'

Value of the format field of a manifest.

CatalogEntry dataclass

CatalogEntry(family: str, parameters: Mapping[str, Any] = dict(), instances: int = 1, name: str | None = None)

One family of a catalog, with its parameters and instance count.

Attributes:

Name Type Description
family str

Id of a registered benchmark family.

parameters Mapping[str, Any]

Parameter values passed to the family; the others keep their defaults.

instances int

Number of instances to generate.

name str | None

Name of the entry, unique in its catalog and used in instance ids and seed namespaces. Defaults to the family id.

label property

label: str

The entry's name, or its family id when it has none.

Catalog dataclass

Catalog(name: str, description: str, entries: tuple[CatalogEntry, ...])

A named, declarative set of benchmark instances.

Attributes:

Name Type Description
name str

Name of the catalog, used in seed namespaces.

description str

One sentence on what the catalog is for.

entries tuple[CatalogEntry, ...]

The families to generate, with parameters and counts.

families property

families: tuple[str, ...]

Ids of the families the catalog uses, sorted.

size property

size: int

Number of instances the catalog generates.

catalogs

catalogs() -> Mapping[str, Catalog]

Return the built-in catalogs keyed by name.

build_catalog

build_catalog(catalog: str | Catalog, *, seed: int = 0, registry: FamilyRegistry | None = None) -> list[Problem]

Generate every instance of a catalog.

Instance i of an entry uses the seed derive_seed(seed, "<catalog>/<entry>", i) and gets the id <entry>-<i>. Its metadata records that seed under seed, as the built-in families do; for a family that records none, it is added, at the price of validating the problem a second time.

Parameters:

Name Type Description Default
catalog str | Catalog

Name of a built-in catalog, or a catalog.

required
seed int

Root seed of the catalog.

0
registry FamilyRegistry | None

Registry to look families up in. Defaults to the default registry with plugins.

None

Returns:

Type Description
list[Problem]

The problems, entry by entry.

Raises:

Type Description
ConfigError

If the catalog, a family, or a parameter is unknown, or seed is not a non-negative integer.

materialize

materialize(problems: Iterable[Problem], directory: str | Path, *, overwrite: bool = False) -> Path

Write problems and their manifest to a directory.

Each problem goes to problems/<id>.json in the format of dumps_problem(). The manifest, manifest.json, lists every file with its SHA-256 digest, the problem's family, its seed (the metadata seed entry, null when absent), and its parameters: the rest of the problem metadata, which is where the built-in families record their parameters. All files are written atomically, with sorted keys where the format allows.

Parameters:

Name Type Description Default
problems Iterable[Problem]

The problems. Their ids must be distinct and consist of letters, digits, ., _, and -, starting with a letter or digit.

required
directory str | Path

Target directory. Created when missing.

required
overwrite bool

Allow a non-empty directory. The manifest is replaced and JSON files in problems/ that the new set does not contain are removed; other files are left alone.

False

Returns:

Type Description
Path

The directory.

Raises:

Type Description
SerializationError

If an id is unsafe or repeated, or the directory is not empty and overwrite is false.

load_directory

load_directory(directory: str | Path, *, verify: bool = True) -> list[Problem]

Read the problems a manifest lists, in manifest order.

Parameters:

Name Type Description Default
directory str | Path

A directory written by materialize().

required
verify bool

Check every file against the SHA-256 digest in the manifest.

True

Returns:

Type Description
list[Problem]

The problems.

Raises:

Type Description
SerializationError

If the manifest is missing or malformed, a file is missing, a digest does not match, or a file holds a problem with another id.

dispatchatlas.benchmarks.characterize

Descriptive features of problem instances.

features() summarises a problem as numbers that describe its size, structure, flexibility, resources, communication, and timing, so instance sets can be compared, stratified, and related to solver performance. Every feature is a deterministic function of the problem alone; DEFINITIONS states each one.

Conventions shared by the definitions:

  • A task's shortest and mean duration are taken over its modes.
  • Jobs are groups of tasks, and every ungrouped task is a job of its own, as in dispatchatlas.core.objectives. A job's release is the earliest release of its tasks.
  • The critical path is the longest dependency path when every task takes its shortest duration and every dependency its lag, ignoring transfers, releases, and resource limits.
  • The earliest finish of a task is its finish time in a relaxation without resource limits: every task starts at its release or once each predecessor's data have arrived, where each dependency is priced at the predecessor mode that delivers first (see earliest_finish_times()).
  • A ratio whose denominator is zero is reported as 0.

DEFINITIONS module-attribute

DEFINITIONS: Mapping[str, str] = MappingProxyType({'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.'})

The name and definition of every feature features() returns, in order.

features

features(problem: Problem) -> dict[str, float]

Return every feature of DEFINITIONS for problem.

Parameters:

Name Type Description Default
problem Problem

The problem to describe.

required

Returns:

Type Description
dict[str, float]

Feature values keyed by name, in the order of DEFINITIONS.

earliest_finish_times

earliest_finish_times(problem: Problem) -> tuple[float, ...]

Return each task's earliest finish time when resources never make it wait.

Dynamic programming in topological order over every task and mode. A task in a given mode starts at its release, or once every predecessor's data have arrived, whichever is later. The data of a predecessor arrive at its finish plus the dependency lag plus the transfer time to the mode's location, minimised over the predecessor's modes independently for each dependency. A task's earliest finish is the minimum over its modes. The result is a lower bound on the task's finish in any feasible schedule. When every task has at most one predecessor, it is also the earliest finish that some placement reaches when resources never make a task wait.

Parameters:

Name Type Description Default
problem Problem

The problem.

required

Returns:

Type Description
tuple[float, ...]

The earliest finish of each task, indexed like problem.tasks.