Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 | 7x 7x 7x 7x 7x 17x | /**
* Enumeration of the job-splitting options.
*/
export enum JobSplitting {
// Note that this is deliberately not a const enum. The TypeScript compiler inlines const enums, which means that the
// generated declaration file is *required* for compiling into valid JavaScript. However, the declaration file may not
// always be taken into consideration or even available. For example, the parcel bundler uses `transpileModule()` for
// TypeScript assets:
// https://github.com/parcel-bundler/parcel/blob/parcel-bundler%401.12.3/packages/core/parcel-bundler/src/assets/TypeScriptAsset.js#L46-L49
// However, `transpileModule()` is just a simple transform function:
// https://github.com/Microsoft/TypeScript/wiki/Using-the-Compiler-API#a-simple-transform-function
// It does not look at any imports at all:
// https://github.com/Microsoft/TypeScript/issues/5243
/**
* The job needs to be executed by a single machine en bloc (that is, with a single job fragment).
*/
NONE = 'none',
/**
* The job needs to be executed by a single machine but it allows preemption; that is, its execution may be
* interrupted by other jobs.
*/
PREEMPTION = 'preemption',
/**
* The job can be executed by multiple machines, and it also allows preemption.
*/
MULTIPLE_MACHINES = 'multi',
}
/**
* A job.
*/
export interface Job {
/**
* The processing requirement of a job (or, more succinctly, the job size).
*
* The actual *processing time* of a job (or job fragment) on a machine with speed `speed` is
* `Math.ceil(size / speed)`. This is the amount of time the machine is busy. In addition, a job may also have a
* delivery time. During that time, the machine is already available again and can process other jobs.
*
* If the job size is 0, the corresponding {@link ScheduledJob} will contain no {@link JobFragment} for *processing*
* this job. However, if {@link deliveryTime} is greater than 0, there would still be a job fragment for the delivery
* time (which starts at time 0).
*
* Jobs with both {@link size} and {@link deliveryTime} equal to 0 are explicitly allowed. They can be useful to
* specify a dependency between *sets* of jobs. For example, suppose `A` and `B` are disjoint sets of `n` and `m`
* jobs, respectively. Suppose each job in `B` depends on all jobs in `A`. However, instead of introducing `m * n`
* dependencies, it is easier to introduce a dummy job `c` with {@link size} and {@link deliveryTime} equal to 0 and
* with a dependency on each job in `A`. Moreover, each job in `B` depends on `c`. This way, only `m + n` dependencies
* are necessary to express the set-dependency.
*/
size: number;
/**
* Delivery time of a job, independent of the machine that it is scheduled on.
*
* During the delivery time of a job, a machine is available again to process other jobs. However, no dependents of
* this job can start before the delivery time has elapsed.
*
* In the computed {@link Schedule}, a separate {@link JobFragment} will be created to represent the delivery time. If
* {@link splitting} is {@link JobSplitting.MULTIPLE_MACHINES}, then this job fragment will be assigned to the machine
* specified by {@link preAssignment} (or simply the first machine if that field is `undefined`).
*
* The default is no delivery time; that is, 0.
*/
deliveryTime?: number;
/**
* Whether the job allows preemption or may be processed concurrently by more than one machine at a time.
*
* The default is {@link JobSplitting.PREEMPTION}.
*/
splitting?: JobSplitting;
/**
* Indices of the jobs that this job depends on.
*
* Dependencies are finish-to-start; that is, a job cannot start before all job dependencies are fully completed
* (including any delivery time they may have).
*
* The default is no dependencies; that is, the empty array.
*/
dependencies?: number[];
/**
* The earliest possible start time for this job.
*
* This constraint is in addition to {@link dependencies}.
*
* The default is none; that is, an earliest possible start time of 0.
*/
releaseTime?: number;
/**
* Index of the machine that this job must be assigned to.
*
* If both this is set and {@link splitting} is {@link JobSplitting.MULTIPLE_MACHINES}, then this field only
* determines what machine the delivery time (if any) will be assigned to.
*
* The default is no pre-assignment.
*/
preAssignment?: number;
}
/**
* An instance of the scheduling problem solved by this module.
*/
export interface SchedulingInstance {
/**
* The speeds of the machines available for processing jobs.
*
* The length of this array determines the number of machines available.
*/
machineSpeeds: number[];
/**
* The jobs that needs to be processed on one (or more) of the available machines.
*
* The dependency graph induced by {@link Job.dependencies} must be an acyclic graph.
*/
jobs: Job[];
/**
* The minimum processing requirement that a job fragment must have.
*
* The default is 0 (that is, there is no effective minimum).
*/
minFragmentSize?: number;
}
/**
* A job fragment is a an assignment of a job (or part of it) to a machine at a specific time.
*/
export interface JobFragment {
/**
* The machine that this job fragment is scheduled to be executed by.
*/
machine: number;
/**
* The wall clock start time for this job fragment.
*/
start: number;
/**
* The wall clock end time for this job fragment.
*/
end: number;
/**
* Whether this job fragment represents delivery time.
*
* If true, this job fragment does not prevent other jobs to be scheduled concurrently on the same machine. However,
* any dependent job can only execute once all processing of this job has been finished and the delivery time has
* elapsed.
*/
isWaiting: boolean;
}
/**
* A scheduled job consists of one or more job fragments.
*
* The job fragments are sorted by {@link JobFragment.end} and {@link JobFragment.machine} (in that order). Fragments on
* the same machine are guaranteed to not overlap. Moreover, if `a` and `b` are two consecutive job fragments on the
* same machine with `a.end === b.start`, then they differ in {@link JobFragment.isWaiting}.
*/
export type ScheduledJob = JobFragment[];
/**
* A schedule is an array of scheduled jobs.
*
* Machines are identified by their array index. For the result returned by {@link computeSchedule}(), there is a 1:1
* correspondence between the jobs in {@link Schedule} and in {@link SchedulingInstance.jobs} (given as argument).
*/
export type Schedule = ScheduledJob[];
/**
* Describes a failure while computing a schedule in {@link computeSchedule}().
*/
export type SchedulingFailure = string;
/**
* Returns whether the given value is a {@link SchedulingFailure}.
*/
export function isSchedulingFailure(value: any): value is SchedulingFailure {
return typeof value === 'string';
}
|