HeadyZhuEconomicPartPeriodSolver
Heady and Zhu describe an improved implementation of Wagner-Whitin based on two ideas:
Reference:
R. B. Heady and Z. Zhu (1994).
An Improved Implementation of the Wagner-Whitin Algorithm.
Production and Operations Management, 3(1), 55-63.
DOI: https://doi.org/10.1111/j.1937-5956.1994.tb00109.x
The publisher abstract reports that, over their rigorous test conditions, their implementation was about twice as fast as the previously fastest algorithm, used about half the array storage, and exhibited execution time approximately linear in planning-horizon length. Those are empirical findings from the paper, not worst-case asymptotic guarantees.
The publicly accessible publisher record for Heady-Zhu exposes the abstract but not the complete algorithm text. ULSAlgorithms therefore does not claim that this class is a line-by-line reproduction of their original program.
For the exact fixed-cost Economic-Part-Period cutoff, the implementation also uses the explicit later primary exposition:
S. J. Sadjadi, M. B. Gh. Aryanezhad and H. A. Sadeghi (2009).
An Improved WAGNER-WHITIN Algorithm.
International Journal of Industrial Engineering & Production Research, 20(3), 117-123.
That paper explicitly derives the fixed-cost quantity
\[DPP = \frac{A}{H}, \]
and shows how it is used to stop Wagner-Whitin branch calculations.
This source distinction is intentional: Heady-Zhu is the historical origin for the combined Planning-Horizon / Economic-Part-Period implementation family, while Sadjadi et al. provide an openly accessible primary derivation used to make this implementation auditable.
The current solver deliberately implements the fixed-cost specialization.
It requires:
\[A_t = A, \qquad p_t = p, \qquad h_t = h \]
for all economically relevant periods.
The final holding-cost entry is not constrained because terminal inventory is zero and that coefficient is never charged.
HeadyZhuEconomicPartPeriodSolver.IsApplicable(problem) exposes the check. Solve throws NotSupportedException outside this domain rather than silently applying an unsafe cutoff.
Consider an order opened in period i that covers demand through period j.
Moving that setup one period earlier makes every unit already scheduled for periods i+1..j wait one additional period. The incremental holding cost is
\[h \sum_{k=i+1}^{j} d_k. \]
If
\[h \sum_{k=i+1}^{j} d_k > A, \]
then carrying those future units one additional period is more expensive than opening an additional setup.
Equivalently,
\[\sum_{k=i+1}^{j} d_k > \frac{A}{h}. \]
The candidate setup at i is then dominated by splitting the plan and opening another setup in i+1. Any still earlier setup carries at least as much future demand, so all remaining earlier candidates can also be discarded.
This yields a safe early termination of the backward predecessor scan.
For every positive-demand prefix, the solver records the latest optimal last setup period. Wagner and Whitin's Planning Horizon Theorem permits predecessor periods before that point to be excluded from subsequent prefix optimizations.
The lower candidate bound is therefore monotone nondecreasing.
Zero-demand prefix extensions do not advance this bound because no setup is created by the zero-cost transition.
Let m_t be the number of predecessor periods actually examined for prefix t.
The work is
\[O\left(\sum_t m_t\right). \]
Worst case:
\[m_t = O(t) \quad\Rightarrow\quad O(n^2). \]
When the Economic-Part-Period cutoff and planning-horizon bound keep each m_t small, observed work approaches linear growth.
The class therefore intentionally advertises O(n²) worst case rather than turning the empirical approximately-linear behavior reported in the literature into an unsupported complexity theorem.
Only two rented O(n) work arrays are required:
Regeneration-interval costs are accumulated in scalar variables during the backward scan; no triangular matrix is stored.
The test suite reproduces the 12-period fixed-cost example in the later primary exposition:
The exact optimum is cross-validated with the independent quadratic oracle. The resulting objective (excluding a constant zero production cost) is 501.2.
The v0.10.0 campaign adds:
| Solver | Distinguishing idea | Worst-case time |
|---|---|---|
| WagnerWhitinClassicalSolver | explicit classical DP matrix | O(n²) |
| WagnerWhitinEvansSolver | incremental low-storage recurrence | O(n²) |
| BahlTajPlanningHorizonSolver | Evans + planning-horizon pruning | O(n²), data dependent |
| HeadyZhuEconomicPartPeriodSolver | planning horizon + EPP cutoff | O(n²), data dependent |
| WagnerWhitinSolver | Wagelmans convex-envelope specialization | O(n) |
1.17.0 