Batching and scheduling

This demo covers a common problem in industry. The task is to group production orders of the same family into batches of fixed capacity and a duration of 100 min (oven loads, tanks), then to schedule them on a production line, one family at a time. Changing family takes setup time. To limit the risk of stock shortages, some orders are flagged as urgent, and any batch containing one is urgent and takes priority. Three objectives are minimized in order of priority: the number of urgent batches, the total number of batches, then the total setup time. My solver, written in C++, computes an optimal solution and compares it with a classic shop rule.

Solver:
exact methods, branch and bound and dynamic programming (Held-Karp).
Shop rule:
a greedy heuristic. Orders are assigned one at a time, from longest to shortest starting with the urgent ones, to the fullest batch of their family that can hold them, or else to a new batch. Families are then sequenced by nearest neighbour on setup time.

The time shown covers only the solver's computation, run on a single core of a shared virtual server.

Draw a random case

Result

Precomputed example Optimal result
  • Urgent batches 3 same as the shop rule Mean fill: 92 % instead of 85 %
  • Batches 5 −17 % instead of 6 Mean fill: 77 % instead of 64 %
  • Setup time 110min −27 % instead of 150 min
Batch-by-batch detail

Solver

FamilyNo.OrdersFill
C1
  • J03 45!
  • J09 35
80 %
Setup C → B: 40 min
B2
  • J07 35!
  • J08 40
  • J02 25
100 %
Setup B → A: 35 min
A3
  • J04 45!
  • J05 25!
  • J10 25
95 %
Urgent orders done after 3 batches
A4
  • J01 20
20 %
Setup A → B: 35 min
B5
  • J06 45
  • J11 45
90 %

Shop rule

FamilyNo.OrdersFill
A1
  • J04 45!
  • J05 25!
  • J10 25
95 %
Setup A → B: 35 min
B2
  • J07 35!
  • J06 45
80 %
Setup B → C: 40 min
C3
  • J03 45!
  • J09 35
80 %
Urgent orders done after 3 batches
Setup C → B: 40 min
B4
  • J11 45
  • J08 40
85 %
5
  • J02 25
25 %
Setup B → A: 35 min
A6
  • J01 20
20 %
  • urgent order
  • non-urgent order topping up an urgent batch
  • batch fill

Edit this case

Families and production orders
  • number
  • size in % of a batch
  • urgent
  • not urgent
Setup times

To switch from one family (row) to another (column), in minutes.

from ↓ to → A B C
A–
B35–
C6040–