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:
PLUGIN_GROUP
module-attribute
¶
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 |
name |
str
|
Human-readable name. |
problem_class |
str
|
The scheduling problem class, for example
|
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.
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 |
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. |
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.
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 groupsj0,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 examplej03-m2. Operationpof 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.objectivesexpects.
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 |
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. |
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 |
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. |
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. |
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 |
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. |
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 |
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. |
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]]
|
|
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]
|
|
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]]
|
|
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]]]
|
|
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]]
|
|
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. |
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
¶
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 |
release_span |
float
|
Release dates are uniform integers in
|
tardiness_factor |
float | None
|
Tardiness factor |
due_date_range |
float
|
Relative range |
weighted |
bool
|
Draw weights uniform in |
objectives |
tuple[str, ...]
|
Objectives the problems declare, primary first. |
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]]
|
|
required |
setups
|
Sequence[Sequence[Sequence[float]]] | None
|
|
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. |
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 ofJactivities hasceil(NC * (J + 2))arcs, the smallest count that reachesNC, of which theSarcs from the source to the start activities and theFarcs from the finish activities to the sink stay implicit. The PSPLIB J30 networks have exactly these counts: 42, 52, and 62 explicit arcs forNC1.5, 1.8, and 2.1. - Resource factor
RF: the average share of theKresources an activity requests. - Resource strength
RS: each capacity isK_min + round(RS * (K_max - K_min)), whereK_minis the smallest capacity that lets every activity run andK_maxis the peak demand of the earliest-start schedule that ignores resources. WithRS = 1that schedule is feasible.
Network. Activities are indexed in a precedence-feasible order and arcs run from lower to higher indices. As in ProGen:
- The first
Sactivities are the start activities and the lastFthe finish activities. Start activities get no predecessor and finish activities no successor. - Every other activity, in increasing order, gets one predecessor drawn uniformly from the earlier non-finish activities.
- Every non-finish activity still without a successor gets one drawn uniformly from the later non-start activities.
- 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 |
resources |
int
|
Number of renewable resources |
network_complexity |
float
|
|
resource_factor |
float
|
|
resource_strength |
float
|
|
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 |
finish_activities |
int
|
Number |
max_degree |
int
|
Most predecessors, and most successors, of an activity. |
objectives |
tuple[str, ...]
|
Objectives the problems declare, primary first. |
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 |
resources |
int
|
Number of renewable resources |
network_complexity |
float
|
|
resource_factor |
float
|
|
resource_strength |
float
|
|
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 |
finish_activities |
int
|
Number |
max_degree |
int
|
Most predecessors, and most successors, of an activity. |
objectives |
tuple[str, ...]
|
Objectives the problems declare, primary first. |
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]]
|
|
required |
arcs
|
Iterable[tuple[int, int]]
|
Precedence arcs |
required |
capacities
|
Sequence[float]
|
Capacity of each renewable resource |
required |
activity_ids
|
Sequence[str] | None
|
Task id of each activity. Defaults to |
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:
- The height,
ceil(U(0, 2 sqrt(v) / shape))levels, so its mean issqrt(v) / shape. - One width per level from
U(0, 2 shape sqrt(v)), meanshape * sqrt(v). The paper does not say how the widths are made to add up tov; here they are rescaled, largest remainder first, so they sum to exactlyvwith at least one task per level. - For every task outside the last level, an out-degree from
randint(1, 2 out_degree - 1), meanout_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. - For every task, a mean duration
w_ifromU(0, 2 mean_duration), and for every processor a duration fromU(w_i (1 - heterogeneity / 2), w_i (1 + heterogeneity / 2)). - For every edge, a raw weight from
U(0, 2). The weights are scaled so the mean communication cost isccrtimes 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
¶
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 |
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, |
shape |
float
|
Shape parameter |
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 |
processors |
int
|
Number of unrelated processors. |
mean_duration |
float
|
Expected mean duration over tasks and processors,
|
objectives |
tuple[str, ...]
|
Objectives the problems declare, primary first. The graphs have no due dates, so due-date objectives are refused. |
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. |
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
¶
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
module-attribute
¶
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 |
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
¶
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 that have at least one node, in the order nodes are listed.
resource
¶
resource(node: str) -> Resource
Return the node with id node.
Raises:
| Type | Description |
|---|---|
ConfigError
|
If the platform has no such node. |
transfer_time
¶
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
¶
Return the seconds node node needs for work work units.
That is work / speed, rounded to microseconds.
modes
¶
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 |
None
|
links
|
Iterable[Link]
|
Links replacing the |
()
|
Returns:
| Type | Description |
|---|---|
Platform
|
The platform. |
Raises:
| Type | Description |
|---|---|
ConfigError
|
If a count is negative, or |
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 / speedrounded 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_timeare 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: |
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], ...]
|
|
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 |
weight |
float
|
Importance of the application in weighted objectives. |
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
|
deadline_factor
|
float | None
|
Hard deadline of each sink, as a multiple of the
same response time. |
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_factoranddeadline_factor: due date and optional hard deadline of each application, as multiples of its contention-free response time counted from its release (seeresponse_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
¶
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
|
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. |
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
|
|
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 |
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 |
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. |
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
|
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. |
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.
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 machinei, then jobj, all from the time seed. - Job shop and open shop:
d[i][j]for jobj, then operationi, all from the time seed; then each job's machinesM[i][j] = iare shuffled by swappingM[i][j]withM[unif(machine seed, i, m)][j]fori = 1..m. Operationiof jobjruns on machineM[i][j]ford[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 |
problem_class |
str
|
|
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; |
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
¶
Advance Taillard's generator once and draw an integer in [low, high].
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
seed
|
int
|
Current state, in |
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
¶
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
|
|
required |
instance
|
str | int
|
Name, such as |
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.sourceinto 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 |
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 |
name |
str
|
Human-readable name. |
problem_class |
str
|
Problem class of every instance, as in
|
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 |
bounds |
Mapping[str, Bound]
|
Bounds published with the instances, keyed by instance name. |
notes |
str
|
Further facts about the suite. |
generated
property
¶
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.
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:
orlib-job-shop: OR-Library job shops, read byread_orlib_job_shop().orlib-flow-shop: OR-Library flow shops, read byread_orlib_flow_shop().fjs: FJSPLib flexible job shops (.fjs), read byread_fjs().psplib: PSPLIB projects (.sm,.mm), read byread_psplib().
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
¶
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 |
None
|
**options
|
Any
|
Keyword arguments of the reader, such as |
{}
|
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 a multi-instance OR-Library file into one text per instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
text
|
str
|
Contents of a file such as |
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 |
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 |
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 |
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 |
Raises:
| Type | Description |
|---|---|
SerializationError
|
If the text is malformed or lacks the instance. |
ConfigError
|
If |
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 |
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 |
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 |
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 |
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 |
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 |
Problem
|
Its metadata records the |
Problem
|
or |
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 / speedseconds 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_unitto 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.5or1.6that has noexecutionsection. 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.0or1e6. - 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[]withname(the task's identity),parentsandchildren(task names),runtimeInSeconds, andfiles[]entries withname,sizeInBytes, andlink("input"or"output").1.5and1.6:workflow.specification.tasks[]withid,parents,children,inputFiles, andoutputFiles;workflow.specification.files[]withidandsizeInBytes; andworkflow.execution.tasks[]withidandruntimeInSeconds.
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
¶
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 |
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 |
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
|
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 |
ConfigError
|
If an objective is unknown, repeated, or needs due
dates, |
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
runtimeis taken as its work, so it runsruntime / speedseconds on one core of the chosen node. - Every
parentlisted in achildelement becomes a dependency that carries the bytes of the files the parent writes and the child reads, divided bybytes_per_unitto 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 namespaceDAX_NAMESPACEor in none. Itsnameandversion, when present, are kept in the problem's metadata. - Every
jobunder the root:id(the task's id),runtimein seconds, andnameandnamespace, kept in the task's metadata astransformationandnamespace. - Every
usesunder a job:file,link, andsizein bytes. The linkinputmarks a file the job reads,outputone it writes,inoutone it reads and writes, andnoneone it does neither with. - Every
childunder the root and everyparentunder 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
¶
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 |
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 |
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 |
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, |
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 runwork / speedseconds 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.
M1is task 1 and depends on nothing,R4_2is task 4 and depends on task 2, andM5_3_4is 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 orMergeTask, 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 ofstatuses."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": withwork="core_seconds", theinstance_numorplan_cpuof 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": withwork="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 thanmin_tasksor more thanmax_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_timeseconds."core_seconds"multiplies the span byinstance_numand byplan_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, wherelatestis the latestend_timeamong 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
¶
The task statuses of the trace.
WORK_RULES
module-attribute
¶
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
¶
Decode the dependency code of a task name of the Alibaba 2018 trace.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
name
|
str
|
The |
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 |
tuple[int, tuple[int, ...]] | None
|
of an independent task. |
tuple[int, tuple[int, ...]] | None
|
|
Raises:
| Type | Description |
|---|---|
ConfigError
|
If |
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 |
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 |
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 |
('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
|
work
|
str
|
How the work of a task is derived, one of |
'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
|
None
|
Returns:
| Type | Description |
|---|---|
None
|
A generator of one problem per job that is read, in the order of the |
None
|
source. Its |
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 |
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
¶
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. |
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. |
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
|
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, |
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 |
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 |
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 |
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 |
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 |