Skip to content

Latest commit

 

History

History
148 lines (112 loc) · 12.6 KB

README.md

File metadata and controls

148 lines (112 loc) · 12.6 KB
Raw

Algorithm for project planning. More precisely, list scheduling with support for machines running at different speeds, optional preemption, optional splitting of jobs across machines, release dates, and delivery times.

Status

Build Status Coverage Status Language grade: JavaScript npm

Overview

  • Transforms input of the following form

    {
  "machineSpeeds": [40, 8, 15],
  "jobs": [
    {"size": 240, "preAssignment": 1, "releaseTime": 40, "splitting": "none"},
    {"size": 640, "preAssignment": 1, "splitting": "preemption"},
    {"size": 3200, "splitting": "multi", "dependencies": [3]},
    {"size": 3200, "deliveryTime": 20, "splitting": "multi", "preAssignment": 2}
  ],
  "minFragmentSize": 320
}

    into a project plan that could be visualized as follows:

    Project Plan

  • See the interactive demo for experimenting with the algorithm, including visualizing its output as shown above.

  • No dependencies.

  • Written in TypeScript, but easily usable from JavaScript.

  • Tests have full code coverage.

License

Apache License 2.0

Releases and Usage

Published releases include TypeScript type declarations and are available as either UMD or ECMAScript 2015 (aka ES6) modules.

Node.js

Install with npm install @fschopp/project-planning-js or yarn add @fschopp/project-planning-js. Use the package as follows (example is in TypeScript, but ES6 JavaScript essentially reads the same, minus the types):

import {
  computeSchedule,
  Schedule,
  SchedulingFailure,
  SchedulingInstance,
} from '@fschopp/project-planning-js';
const instance: SchedulingInstance = {
  machineSpeeds: [ /* ... */ ],
  jobs: [ /* ... */ ]
};
const schedule: Schedule | SchedulingFailure = computeSchedule(instance);

Browser

Include the minified sources from the jsDelivr CDN:

<script src="https://cdn.jsdelivr.net/npm/@fschopp/project-planning-js@.../dist/index.min.js"
  integrity="..." crossorigin="anonymous"></script>

Of course, the two occurrences of ... need to be replaced by the current version and its corresponding subresource integrity (SRI) hash. Then, in a subsequent script:

let instance = { /* as above */ };
let schedule = ProjectPlanningJs.computeSchedule(instance);

Due to cross-origin restrictions for web workers, method computeScheduleAsync(), which runs the algorithm asynchronously in a separate thread, requires serving project-planning-js from the same domain as your website. If the script is served from the CDN, the asynchronous method will not work!

See JSFiddle for an example.

Project Documentation

Build

  • See the git history to find out the versions of the following development dependencies that were in use at the time of writing.
  • The source code is exclusively written in TypeScript. The TypeScript compiler compiles the source code into ECMAScript 2015 (aka ES6) modules, with a target of ECMAScript 2017. Its output is not yet ready for distribution because newer ECMAScript language features may not yet be widely supported by web browsers or Node.js. Additionally, the output by the TypeScript compiler still contains assertions. Creating the distribution therefore relies on another compilation step with Babel. Additionally, we also create a minified build.
  • We use Rollup for creating the distribution; that is, the final compilation and assembly. The distribution exists in 3 different forms:
    1. A single-file UMD module (at dist/index.js) that is “capable of working everywhere, be it in the client, on the server or elsewhere.” This is what the main property in the package.json file references.
    2. Same as the previous, but minified.
    3. An ES6 module with the same file layout as in the source tree. The only further transformation on the output from the TypeScript compiler is stripping of assertions. The ES6 distribution resides under dist/es6. This is what the module property in the package.json file references.
  • Rollup invokes Babel indirectly, through the rollup-plugin-babel.
  • Unfortunately, rollup-plugin-babel does not pick up the src/main/.babelrc.js file. This leads to a little bit of redundant configuration in rollup.config.js.
  • Parcel, which is used during development and for bundling the demo site, does consider the src/main/.babelrc.js file, however. (It does not care about the Rollup configuration.) It uses Babel to transpile ES6 JavaScript by default, without any (additional) configuration.
  • Both rollup-plugin-babel and Parcel consider the browserslist field in file package.json: rollup-plugin-babel delegates entirely to package @babel/preset-env (which then is mindful of that setting), and Parcel looks for the field, too.
  • The distribution has source maps that link the final JavaScript to its TypeScript sources. The configuration ensures that source maps of consecutive transformations are correctly merged.

Algorithm Description

Overview

This module implements a generalized list scheduling algorithm, a notion first formalized by Graham (1966). The algorithm is given a priority list of jobs, and “at each step the available job with the highest ranking [...] is assigned to the first machine that becomes available” (Graham et al., 1979).

Our extensions are very common in the literature; see Lawler et al. (1993).

  1. Machines are uniform (also called related). That is, each machine has a speed si so that the processing time of a job on a particular machine is inversely proportional to that machine’s speed.
  2. Each job may optionally be interrupted (known as preemption).
  3. Each job may optionally be processed by more than one machine at a time, as long as the processing requirement of each job fragment is not less than a given threshold. (If a job allows splitting across machines, this also includes allowing preemption.)
  4. There is a release date rj for each job; that is, an earliest start time.
  5. There is a delivery time qj for each job that must elapse between the end of the job’s processing and the start of any dependent job.
  6. As part of the input, each job may already be assigned to a particular machine.

In the three-field notation for theoretical scheduling problems introduced by Graham et al. (1979), this algorithm is applicable to a superset of Q│prec,rj,qj│γ. The reasons for “superset” are:

  • Item 2 allows preemption as a job-specific option (as opposed to preemption being allowed or disallowed for all jobs).
  • Items 3 and 6 above.

A typical optimization goal is γ = Cmax; that is, minimizing the maximum completion time, also known as the makespan. However, the list scheduling algorithm is obviously independent of the optimization goal (it is the approximation ratio that is not!).

Details and Runtime

  • List scheduling is a greedy algorithm.
  • Let m be the number of machines, and n the number of jobs. The algorithm repeats the following steps for each job:
    • Among all remaining available jobs, determine the one that came first on the input list. This requires extracting the minimum from a heap and takes time O(log n).
    • Scheduling a single job takes time O(n + m):
      • If the job can be split across machines, fill the gaps following the release time. At any time a machine becomes available or unavailable, update the current total speed. The number of gaps on all machines (or equivalently, the number of update steps) is O(n).
      • If the job cannot be split across multiple machines, find the machine which would allow the earliest completion of the job. In aggregate, for all machines, this again may require iterating over O(n) gaps.
  • The total worst-case runtime is thus O(n2 + n · m). However, assuming that only few gaps will arise in the schedule (for instance, because there are few dependencies, most jobs have no release times, or there are frequently splittable jobs that will fill up the gaps), the run time should be closer to O(n · (m + log n)).
  • In any case, the runtime should rarely be a problem for any scheduling task that one would reasonably want to solve in a web browser.

Approximation Guarantees

  • Even the most simple discrete scheduling problems are NP-hard. This includes, for instance, minimizing the makespan on two identical machines (P2││Cmax in short).
  • Worse, in particular when precedence constraints are added, the theoretical understanding of scheduling problems is still limited. For instance, no constant-factor approximation algorithm is known at all for makespan minimization on uniform machines (Q│prec│Cmax), and this of course also applies to list scheduling. See Chekuri and Bender (2001).
  • In practice, however, list scheduling is known to perform quite well for natural scheduling problems.
  • On identical machines (all speeds are the same), the list scheduling algorithm performs reasonably well even with precedence constraints. The approximation ratio for makespan minimization in this case (P│prec│Cmax) is 2 – (1 / m). See Graham (1966).
  • Liu and Liu (1974) showed that the approximation guarantee for list scheduling on uniform machines becomes much worse: 1 + max si / min si – max si / ∑ si.

References