Sequence Playground · Documentation

← Back to the playground

1 The shop floor

The Sample Sheet Metal Works makes sheet-metal parts for control cabinets and machine building. Every job (a batch of identical parts) passes three stations in a fixed order: laser cutting → bending → powder coating. The plant runs two shifts, so about 960 minutes per day.

The jobs belong to five product families. Within a family, sheet thickness, bending tool and colour are the same:

FamilyProductSheetBending toolColour
AControl cabinet door1.5 mmS1RAL 7035 light grey
BDevice housing1.0 mmS2RAL 9016 traffic white
CCable duct1.25 mmS2RAL 5010 gentian blue
DMachine console3.0 mmS3RAL 7016 anthracite grey
EFront panel2.0 mmS1RAL 9005 jet black

When a station switches from one family to another, it has to be set up:

  • Laser cutting: sheet thickness and cutting parameters change. This is quick, 5 to 18 minutes.
  • Bending: a different tool set is mounted. Between families that share a tool (A and E, B and C) this takes only 10 minutes; the heavy set S3 for D takes up to 35.
  • Powder coating: the booth is cleaned for the colour change. Light to dark takes 15 to 20 minutes; dark to light needs thorough cleaning, up to 60 minutes.

Powder coating is therefore the bottleneck: it has the longest processing times and the most expensive changeovers. The colour changes are also asymmetric. Whether white runs before black or the other way round makes a big difference.

The colours in the app's Gantt charts are only there to tell the families apart and remain distinguishable with colour vision deficiencies. They do not match the families' RAL colours.

2 The problem

The question for production control is: in which order should the jobs be processed? The sequence decides how often and how long the stations are set up, when the jobs are finished and whether the due dates hold.

Two goals often conflict:

  • Little setup: jobs of the same family are grouped, which shortens the total duration (makespan).
  • Meeting due dates: urgent jobs go first, even if that means more changeovers.

With n jobs there are n! possible sequences. For 12 jobs that is already 479,001,600; for 20 jobs about 2.4 · 1018. Trying them all is practically impossible. That is why planners use priority rules (fast and easy to follow) and metaheuristics such as simulated annealing (more thorough, but with no guarantee of the optimum).

The app looks at two cases:

  • Single machine: only the bottleneck, powder coating. This is the classic single-machine problem with sequence-dependent setup times.
  • Line: all three stations. All jobs pass the stations in the same order and are processed in the same sequence on every station. Technical term: permutation flow shop.

3 Data model

All times are whole minutes. The schedule starts at t = 0.

ObjectAttributesMeaning
Job jNumber, family, processing time pj,m per machine, due date djA batch that passes all stations
FamilyLetter, name, detailsJobs of the same family need no changeover between them
Machine mName, setup time matrixStation in the line; the order of the list is the station order

Setup times

Each machine has a setup time matrix sm(from, to). The row is the family of the previous job, the column the family of the next one. The matrix is asymmetric: s(A, B) and s(B, A) may differ. The diagonal is 0, because there is no setup within a family.

The additional row “empty” describes the initial state at the start of the shift, i.e. the setup time before the very first job.

Due-date pressure (random generator)

For a given seed, the generator always creates the same jobs. This makes results repeatable and comparable. Families and processing times are drawn uniformly, the processing times within the ranges from the master data.

The due-date pressure τ slider (0 to 1) controls how tight the due dates are. First the workload L of the most heavily loaded machine is estimated: the sum of its processing times plus one average setup per job. Each due date is then drawn uniformly from

dj ∈ [ L · (1 − τ − R/2) , L · (1 − τ + R/2) ] with R = 0.6

and rounded to 10 minutes. No due date lies before the job's own processing time. This scheme is common in the literature for test instances of tardiness problems.

  • τ = 0: the due dates lie around the total workload. Almost any sequence meets them.
  • τ ≈ 0.4: some jobs are urgent. The sequence decides about tardiness. This is the most interesting range for comparisons.
  • τ = 1: almost all due dates are very early. Tardiness cannot be avoided.

4 From sequence to schedule

Each method only returns a sequence of jobs. From it, the app computes the schedule using fixed rules.

Single machine

The jobs run back to back without gaps. Before each job there is a setup if the family changes:

Startj = Endprev + s(familyprev, familyj) Endj = Startj + pj

Line

A station can only start a job once it has finished its own setup and the job has left the previous station. The setup starts as soon as the station is free, even if the job is still running on the previous station:

Startj,m = max( Endprev,m + sm(familyprev, familyj) , Endj,m−1 )

This creates waiting times: a station is idle because the next job is not yet finished upstream. The completion time Cj is the end on the last station.

05101520 Time in min Machine 1 Machine 2 1 3 2 4 1 3 2 4
Line mini example, sequence 1 → 3 → 2 → 4. Machine 2 sets up right away (0–2), but then waits until t = 4 for job 1. Before job 2 it has finished its setup at t = 12, but has to wait until t = 13 for machine 1 to hand the job over. Job 2 is only completed at t = 18; its due date was 16: late (red).

5 KPIs

For all KPIs, lower is better. In the app's comparison table, the best value per column has a green outline.

KPIDefinitionWhat it tells you
MakespanC of the last jobWhen is everything done? Short = capacity well used
Total setupSum of all setups across all machinesHow much time is lost to changeovers and cleaning?
Σ tardinessΣ Tj with Tj = max(0, Cj − dj)How far are due dates exceeded in total? Finishing early does not count
Late jobsNumber of jobs with Tj > 0How many customers are waiting?
Setup shareTotal setup / (makespan × number of machines) in %What share of the available machine time is spent on setup?

The KPIs often point in different directions. A method with the shortest makespan can have many late jobs, and vice versa. Which KPI matters is a business decision, not a mathematical one.

6 Methods

All methods work on the same data and return a sequence. On the line, SPT and Nearest Neighbour use the sum of processing or setup times across all machines. The examples refer to the single-machine mini example.

FIFO – First In, First Out

Rule: process jobs in the order they arrived. In the app this is the order of the job table.

Example: 1 → 2 → 3 → 4 → 5. The families alternate all the time (A, B, A, B, A), so there is a setup before every job.

StrengthsSimple, fair, needs no calculation. A good baseline.
WeaknessesIgnores setup times and due dates completely.

SPT – Shortest Processing Time

Rule: the job with the shortest processing time first. On a tie, the smaller job number wins.

Example: 5 (2 min) → 2 (3) → 3 (4) → 1 (5) → 4 (6).

StrengthsWithout setup times it minimises the mean flow time; many jobs finish early.
WeaknessesLong jobs wait; due dates and setup times play no role.

EDD – Earliest Due Date

Rule: the job with the earliest due date first. On a tie, the smaller job number wins.

Example: 1 (due 10) → 2 (12) → 4 (20) → 5 (25) → 3 (30).

StrengthsWithout setup times it minimises the maximum tardiness; usually good for total tardiness.
WeaknessesIgnores setup times; with many family changes this costs capacity.

Nearest Neighbour – smallest setup next

Rule: starting from the “empty” state, always pick the job with the smallest setup time. On a tie, the earlier due date wins, then the smaller number. The method comes from the travelling salesman problem: the families are the “cities”, the setup times the “distances”.

Example: empty → A costs 2, empty → B costs 3, so an A job comes first (1, earliest due date). Then 5 and 3 (both A) without setup, then one change A → B and 2, 4. Result 1 → 5 → 3 → 2 → 4 with only two setups.

StrengthsGroups families, little setup time, often a short makespan.
Weaknesses“Greedy”: good first steps can force expensive changes later. Due dates only count on a tie.

Simulated Annealing

Idea: the method imitates the slow cooling of metal. At a high temperature the atoms can still rearrange freely; as the metal cools they settle into a low-energy, stable structure. Translated to scheduling: at first, even worse solutions are accepted, so the method does not get stuck in the first local optimum it finds. As the temperature drops, it becomes more and more selective.

s  ← random start sequence              T ← start temperature
repeat N times (iterations):
    s' ← neighbour of s                  (swap: exchange two jobs
                                          or insert: move one job)
    Δ  ← f(s') − f(s)                     (f = objective value, lower is better)
    if Δ ≤ 0 or random number < e^(−Δ / T):  s ← s'
    remember the best sequence found so far
    T  ← T · cooling rate
result: best sequence found

Probability of accepting a deterioration of Δ = 20:

Temperature T1002051
e−20/T82%37%1.8%≈ 0%

Objective (selectable in the app):

  • Makespan: finish everything as early as possible
  • Σ tardiness: meet the due dates as well as possible
  • Weighted: f = α · makespan + (1 − α) · Σ tardiness α weights the trade-off explicitly. α = 1 is pure makespan, α = 0 pure tardiness.

Parameters (sliders in the app):

  • Start temperature: how generously the method accepts worse solutions at first. A sensible value is in the range of typical differences Δ.
  • Cooling rate: factor per iteration, for example 0.998. Closer to 1 means cooling more slowly and searching longer.
  • Iterations: number of neighbourhood steps. The app shows the resulting end temperature = start temperature · cooling rateiterations.
  • Seed: controls the start sequence and the random moves. The same seed gives the same run.

Convergence curve: the light blue line shows the objective value of the current solution. At high temperature it jumps a lot. The dark blue line shows the best value found so far and can only go down. The dashed line is the best priority rule for the same objective.

Simulated annealing does not guarantee the optimum. Depending on parameters and seed, it can even do worse than a simple rule. That is exactly what you can try out in the app.

7 Mini examples to check by hand

Both examples are built into the app and can be loaded with the buttons in the header. All values can be checked by hand.

Single machine: 5 jobs, 2 families

JobFamilyProcessing timeDue date
1A510
2B312
3A430
4B620
5A225

Setup times: empty → A 2, empty → B 3, A → B 4, B → A 6.

FIFO step by step:

JobSetupSetup timeStartEnd CDue dTardiness T
1 (A)empty → A227100
2 (B)A → B41114122
3 (A)B → A62024300
4 (B)A → B428342014
5 (A)B → A640422517

Makespan 42, total setup 22, Σ tardiness 33, three late jobs, setup share 22 / 42 = 52.4%.

010203040 Machine 1 1 2 3 4 5
FIFO in the mini example: five setups (grey) take up more than half of the time, three jobs are late (red).

All methods compared (green = best value):

MethodSequenceMakespanSetupΣ tardinessLateSetup share
FIFO1-2-3-4-5422233352.4%
SPT5-2-3-1-4361632244.4%
EDD1-2-4-5-332127337.5%
Nearest Neighbour1-5-3-2-426614223.1%

Nearest Neighbour reaches the optimal makespan: 20 min of processing plus at least 2 + 4 min of setup. EDD, on the other hand, has the lowest tardiness. This is the trade-off in miniature.

Line: 4 jobs, 2 families, 2 machines

JobFamilyp on machine 1p on machine 2Due date
1A3412
2B2516
3A4228
4B3324

Setup times machine 1: empty → A 1, empty → B 2, A → B 3, B → A 2. Machine 2: empty → A 2, empty → B 1, A → B 2, B → A 4.

MethodSequenceMakespanSetupΣ tardinessLateSetup share
FIFO1-2-3-426192136.5%
SPT3-4-1-2291923232.8%
EDD1-2-4-324140029.2%
Nearest Neighbour1-3-2-42182119.0%

Here the setup share refers to two machines: 8 / (21 · 2) = 19.0%. The Nearest Neighbour schedule is shown as a Gantt chart in the section From sequence to schedule.

8 Using the app

Header

  • Mode: “Single machine” looks only at the bottleneck machine, “Line” at all machines. For the mini examples, the matching mode is fixed.
  • Methods: switch on and off with the checkboxes. Only selected methods appear in the table and the Gantt charts.
  • Reset: discards all changes and reloads master-data.js.
  • Save master data: downloads the current state as a file (see Your own scenario).
  • Mini examples: load the examples from section 7.

Left column: data

  • Jobs: change values directly in the table, add jobs with “+ Job” and delete them with ✕. Invalid entries are marked red and not applied.
  • Generator: choose seed, count and due-date pressure, then “Generate jobs”. Machines and setup times stay as they are.
  • Product families and setup times: names and setup times can be edited. Every change is recalculated immediately.

Right column: results

  • Overview: load per machine. The machine with the highest load is marked; it is usually the bottleneck.
  • Method comparison: the KPIs per method; the best value per column has a green outline.
  • Simulated Annealing: set the objective and parameters. “Start animation” replays the run in about five seconds; meanwhile the table and Gantt charts show the best solution found so far.
  • Gantt charts: one chart per method on a shared time axis, one row per machine. Setup is grey, late jobs have a red outline. Hovering with the mouse shows the job data.

Changes in the app only last until the page is reloaded. To keep a scenario, use “Save master data”.

9 Your own scenario

The demo scenario lives in the file master-data.js in the same folder as the app. You can edit it in any text editor, or put it together in the app and download it with “Save master data”. The downloaded file replaces the old one in the folder; after reloading, the app starts with the new state. If you download several times, the browser may add a number to the file name, for example master-data(1).js. In that case, rename the file.

Structure, shortened:

window.MASTER_DATA = {
  "scenario": { "name": "Sample Sheet Metal Works", "description": "…" },
  "homeLink": { "url": "/", "label": "Back to the website" },  (optional)
  "families": [ { "id": "A", "name": "Control cabinet door", "details": "…" }, … ],
  "machines": [
    { "id": "laser", "name": "Laser cutter",
      "setup": { "empty": { "A": 10, … }, "A": { "A": 0, "B": 8, … }, … } }, …
  ],
  "singleMachine": "coating",
  "jobs": [ { "id": 1, "family": "A", "processingTimes": { "laser": 35, … }, "dueDate": 300 }, … ],
  "generator": { "seed": 42, "jobCount": 12, "dueDatePressure": 0.4,
                 "processingTimeRanges": { "laser": { "min": 20, "max": 50 }, … } }
};
  • 2 to 8 families and 1 to 5 machines. The order of the machines is the station order of the line.
  • singleMachine sets which machine the “Single machine” mode shows.
  • Each setup matrix needs one row per family plus empty, each with one value per family. The diagonal is 0.
  • All times are whole minutes.

On start, the app checks the file. If there is an error, it shows the affected place, for example machines[2].setup.C.C: diagonal must be 0. The mini examples still work in that case.

Why .js and not .json? Browsers do not let a page opened by double-click load JSON files. A script file, on the other hand, works everywhere, even offline. The content is still written in JSON notation.

10 Limits of the model

The model is deliberately simple, so the effect of the sequence stays visible. In practice, further factors come into play:

  • All jobs are available from t = 0. Material that arrives later is not modelled.
  • No disruptions: there are no machine breakdowns, scrap or varying times. All times are fixed.
  • No shift boundaries or breaks: time runs continuously.
  • Unlimited buffers between the stations of the line. A job can wait for any length of time.
  • One sequence for all stations (permutation flow shop). Overtaking between stations is not possible, nor are different routes (job shop) or parallel machines.
  • Batches are not split: a job only moves to the next station once it is complete; there is no overlapping production.
  • Unweighted tardiness: every customer and every minute counts the same.
  • Unlimited setup staff: all stations can be set up at the same time.

11 Ideas for teaching

  1. Start with the mini example: work through FIFO on the board and compare with the app. Then ask: which sequence would you choose?
  2. Make the trade-off visible: compare EDD and Nearest Neighbour in the demo scenario. Which KPI matters more to the plant, and who decides that?
  3. Experience asymmetry: in powder coating, lower the “dark → light” setup times to the level of “light → dark”. How much do the results change?
  4. Vary the due-date pressure: with the same seed, generate τ = 0, 0.4 and 1. From which point do the methods differ in tardiness?
  5. Understand the bottleneck: switch between “Single machine” and “Line”. Why is the makespan longer on the line, even though the same jobs run?
  6. Explore the SA parameters: compare start temperature 1 with 500, and cooling rate 0.990 with 0.9995. When does the method get stuck, and when does it search randomly for too long?
  7. Randomness and repeatability: try several SA seeds. How much does the result vary? What does that mean for use in practice?
  8. Discuss the weighting: move α from 0 to 1 and watch how the SA solution moves between “little setup” and “meeting due dates”.