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.
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
| Family | No. | Orders | Fill |
|---|---|---|---|
| C | 1! |
| 80 % |
| Setup C → B: 40 min | |||
| B | 2! |
| 100 % |
| Setup B → A: 35 min | |||
| A | 3! |
| 95 % |
| Urgent orders done after 3 batches | |||
| A | 4 |
| 20 % |
| Setup A → B: 35 min | |||
| B | 5 |
| 90 % |
Shop rule
| Family | No. | Orders | Fill |
|---|---|---|---|
| A | 1! |
| 95 % |
| Setup A → B: 35 min | |||
| B | 2! |
| 80 % |
| Setup B → C: 40 min | |||
| C | 3! |
| 80 % |
| Urgent orders done after 3 batches | |||
| Setup C → B: 40 min | |||
| B | 4 |
| 85 % |
| 5 |
| 25 % | |
| Setup B → A: 35 min | |||
| A | 6 |
| 20 % |
- urgent order
- non-urgent order topping up an urgent batch
- batch fill