Data structures¶

There are three different data structures, that a developer should be aware of. The first two are used for a problem representation, and the third one is used for a schedule.

Problem description¶

Problem description is represented as a JavaScript object. The purpose of this object is to describe a problem in a format that is easy enough to code for a developer. Problem descriptions are used in tests; they can also be returned by functions that generate random problems.

Flow-Shop¶

Before the problem is loaded, it can be presented as the following JavaScript object:

{
  type: 'standard',

  jobs: [
    { id: 1, times: [1, 2, 3], ready: 3 },
    { id: 2, times: [3, 0, 1] },
    { id: 3, times: [2, 2, 4] }
  ]
}

Things to note:

The type is set to “standard” - it means, that it’s a standard Flow-Shop class problem.
Each job has its identifier. The identifier should be a unique string describing the job. Before the problem is loaded, though, non-string identifiers are allowed. (They will be transformed to strings after the problem is loaded.)
Each job has its ready time. By default, the ready time is equal to zero.

Job Shop¶

Here’s an example of a Job Shop class problem:

{
  type: 'standard',

  jobs: [
    { id: 1, ready: 10, tasks: [
        { id: 1, time: 5,  machine: 1 },
        { id: 2, time: 10, machine: 2 }
      ] },
    { id: 2, tasks: [
        { id: 1, time: 10, machine: 1 },
        { id: 2, time: 15, machine: 3 }
      ] }
  ]
}

And here’s another example, of the same problem, yet in a different format:

{
  type: 'standard-string',

  jobs: [
    { id: 1, ready: 10, tasks: '1:1(5),2:2(10)' },
    { id: 2, tasks: '1:1(10),2:3(15)' }
  ]
}

Please note, that the type has a different value here. It cannot be of the same value, since a different format is used (and thus, a different problem loader is needed).

Loaded problem¶

The loaded problem is also represented as a JavaScript object. In fact, it can be the same object, that was used to problem description. Yet, the purpose of the loaded problem is different: it should be easy to process while problem solving. So, usually the loaded problems format is slightly different than the original one.

Flow-Shop¶

In the Flow-Shop case, there are two differences in comparison to the problem description format:

The job’s identifiers are strings.
All the ready times are specified (even when they have the default value of 0).

{
  type: 'standard',

  jobs: [
    { id: '1', times: [1, 2, 3], ready: 3 },
    { id: '2', times: [3, 0, 1], ready: 0 },
    { id: '3', times: [2, 2, 4], ready: 0 }
  ]
}

The tasks identifiers can be their jobs identifiers followed by the - character and the number of task counted from 1 (e.g. “1-1”, “1-2”, “1-3”).

Job Shop¶

After a standard, Job Shop class problem has been loaded, it should represented in the following format:

{
  type: 'standard',

  jobs: [
    { id: '1', ready: 10, tasks: [
        { id: '1', time: 5,  machine: 'm1' },
        { id: '2', time: 10, machine: 'm2' }
      ] },
    { id: '2', ready: 0, tasks: [
        { id: '1', time: 10, machine: 'm1' },
        { id: '2', time: 15, machine: 'm3' }
      ] }
  ]
}

Things to note:

The type of the problem is “standard”, no matter what the format of the source problem data was.
All the identifiers are strings. (Please also note the machines’ identifiers!)
The tasks identifiers should be unique, but it’s up to the user.

Schedule¶

Schedule is a collection (a JavaScript array) of scheduled tasks. Each task is identified by its identifier (which may differ for different classes of problems). For each task, its start time and its end time are also given.

Here is an example of empty schedule, with three resources:

{
  m1: [],

  m2: [],

  m3: []
}

And here we have an example of schedule with some tasks:

{
  m1: [
    { id: '1-1', start: 0, end: 10 },
    { id: '3-1', start: 10, end: 20 }
  ],

  m2: [],

  m3: []
}