Harvest Processing Line
FLOW SHOP SCHEDULING
Approximately 10% of global grain harvest is lost to post-harvest handling delays and quality degradation (FAO, 2019). Each harvest cycle requires deciding the order in which grain lots pass through cutting, transport, cleaning, and drying stages. This is the Permutation Flow Shop Problem (Fm|prmu|Cmax) — one of the foundational NP-hard problems in scheduling theory.
Where This Decision Fits
Agricultural operational chain — the highlighted step is what this page optimizes
The Problem
From grain fields to optimization theory
You have a set of grain lots that must each pass through the same sequence of processing stages — cutting, transport, cleaning, and drying. The constraint is that each stage can only handle one lot at a time, and every lot must visit stages in the same fixed order. The question is: in what order should the lots be processed to finish all of them as quickly as possible?
This is the Permutation Flow Shop Problem (Fm|prmu|Cmax): n jobs on m machines in the same order. NP-hard for m ≥ 3.
| Agriculture Domain | Flow Shop Model | |
|---|---|---|
| Grain lot | Job | |
| Processing stage | Machine | |
| Stage duration (hours) | Processing time pij | |
| Finish all lots ASAP | Minimize Cmax |
Try It Yourself
Edit processing times, add/remove lots, and find the best sequence through the harvest line
Processing Times (hours)
6 Lots · 4 Stages · Click any cell to edit| Lot Name | Cutting | Transport | Cleaning | Storage |
|---|
The Algorithm
NEH Constructive Heuristic for Flow Shop
Sort by Total Processing Time
Order jobs in decreasing total processing time across all machines. Jobs with more work are placed first.
Initialize with First Job
Start the partial sequence with the job having the largest total processing time.
Insert Each Job at Best Position
For each remaining job, try inserting it at every possible position in the current sequence. Keep the position that minimizes makespan.
Return Final Sequence
After all jobs are inserted, the resulting permutation is the NEH solution. Complexity: O(n² · m).
Real-World Complexity
Factors beyond the basic flow shop model
Weather Dependence
Cutting times vary with moisture content, which changes with weather conditions.
Transport Variability
Field distance and road conditions create variable transport times.
Storage Capacity
Limited silo space creates blocking constraints between cleaning and storage.
Setup Times
Switching between grain types requires equipment cleaning, adding setup times.
Quality Degradation
Grain quality degrades over time, making no-wait constraints desirable.
Crew Coordination
Different stages need different crews, adding resource constraints.
References
Key literature on flow shop scheduling