A Dynamic Programming Algorithm for SingleItem Capacitated Economic Lot Sizing with Startup Costs, Piecewise Linear Production Costs and Piecewise Linear Holding Costs
Lutz Tautenhahn (1997, 1999, 2001)
C++ Sourcecode is available at http://www.lutanho.net/plt/lotsize.zip (bugfixed 20050704)
Data:  
I   number of periods  
x_{i}^{min}   min. feassible production quantity in period i  (i = 1...I)  
x_{i}^{max}   max. feassible production quantity in period i  (i = 1...I)  
y_{i}^{min}   min. feassible inventory quantity in period i  (i = 1...I1)  
y_{i}^{max}   max. feassible inventory quantity in period i  (i = 1...I1)  
y_{0}   inventory quantity at the end of period 0  
y_{I}   inventory quantity at the end of period I  
J_{i}   number of production intervals in period i  (i = 1...I)  
K_{i}   number of inventory intervals in period i  (i = 1...I)  
x_{i}^{j}   upper border of production interval j in period i  (i = 1...I, j = 0...J_{i})  
y_{i}^{k}   upper border of inventory interval k in period i  (i = 1...I, k = 0...K_{i})  
a_{i}   startup costs in period i  (i = 1...I)  
s_{i}^{j}   fix production costs in period i in interval j  (i = 1...I, j = 1...J_{i})  
c_{i}^{j}   variable production costs in period i in interval j  (i = 1...I, j = 1...J_{i})  
t_{i}^{k}   fix inventory costs in period i in interval k  (i = 1...I, k = 1...K_{i})  
h_{i}^{k}   variable inventory costs in period i in interval k  (i = 1...I, k = 1...K_{i})  
d_{i}   demand in period i  (i = 1...I)  
u_{0}   binary production variable in period 0  
Variables:  
u_{i}   binary production variable in period i  (i = 1...I)  
x_{i}   production quantity in period i  (i = 1...I)  
y_{i}   inventory quantity at the end of period i  (i = 1...I 1) 
A field is an invalid field (no field) if:
pl (integer) predecessor left pr (integer) predecessor right le (integer) left ri (integer) right hl (integer) height left dh (integer) derivative of height
ri < le orIn order to operate with the property * of a field f, the notation f .* is used (f .pl, f.pr, ...).
hl < 0 or
hl + (rile) * dh < 0
F^{n} = {f^{1}, ..., f^{n}}A set F^{n} is sorted, if and only if:
A set F^{n} is wellformed , if and only if:
f^{i}.le < f^{i+1}.le + 1 or (for all i = 1...n1) (left sorted) f^{i}.ri < f^{i+1}.ri + 1 or (for all i = 1...n1) (right sorted) ( f^{i}.le< f^{i+1}.le + 1 and f^{i}.ri< f^{i+1}.ri + 1 ) (for all i = 1...n1) (both side sorted)
f^{i}.ri + 1 = f^{i+1}.le (for all i = 1...n1)In this way a wellformed fieldset can represent a piecewise linear total cost function or any other piecewise linear function.
F_{*}^{1} = p_{*}(f, d)Meaning:
3. 1. 2 ProductionTransformation of a fieldset F^{n} by a field d
p_{d0} production quantity = 0 for an entire inventory interval; without setup costs; no startup costs in this period; startup costs in the next period possible p_{dl} production quantity = left border of the production interval for an entire inventory interval; with setup costs; startup costs in this period possible, in the next period impossible p_{dr} production quantity = right border of the production interval for an entire inventory interval; with setup costs; startup costs in this period possible, in the next period impossible p_{fl} inventory quantity = left border of the inventory interval for an entire production interval; with setup costs; startup costs in this period possible, in the next period impossible p_{fl} inventory quantity = right border of the inventory interval for an entire production interval; with setup costs; startup costs in this period possible, in the next period impossible
F_{*}^{n} = { f_{*}^{1}, ..., f_{*}^{n} }= P_{*} (F^{n}, d) = { p_{*} ( f^{1} , d), ..., p_{*} ( f^{n} , d) }Meaning:
If F^{n} is the representation of a total cost function in a certain period and d is the representation of the appropriate production cost function (linear plus setup costs) in this period then the resulting fieldsets include the representation of all possible extremal production transformations. So the optimum production transformation can be represented by at least one of these resulting fieldsets for each inventory level.
F_{m}^{k} = m(f, d) (k = 1, 2 or 3)Meaning:
If f is the representation of a possible total cost function in the interval [f.le, f.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] then the resulting fieldset is the representation of the minimum total costs of both in the interval [f.le, f.ri].3. 2. 2 MinimumInterference of a wellformed fieldset F^{n} with a field g
F_{M}^{k} = {m(f^{1}, g), ..., m(f^{n}, g)} = M ( F^{n} , g) = M ({f^{1}, ..., f^{n}}, g) (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] then the resulting fieldset is the representation of the minimum total costs of both in the interval [f^{1}.le, f^{n}.ri].3. 2. 3 MinimumInterference of a wellformed fieldset F^{n} with a (not necessarily sorted) fieldset G^{o}
F_{1}^{n(1)} = M (F^{n} ,g^{1})and
F_{i+1}^{n(i+1)} = M (F_{i}^{n(i)} ,g^{i+1}) for i = 1...o1In general:
F_{MM}^{k} = MM (F^{n} ,G^{o}) = F_{o}^{n(o)} (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and G^{o} is the representation of o other possible total cost functions in the intervals [g^{1}.le, g^{1}.ri], ..., [g^{o}.le, g^{o}.ri] then the resulting fieldset is the representation of the minimum total costs of all in the interval [f^{1}.le, f^{n}.ri].
F_{l}^{k} = l(f, d) (k = 1, 2, 3 or 4)Meaning:
If f is the representation of a possible total cost function in the interval [f.le, f.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] and f.le2<d.ri holds then the resulting fieldset is the representation of the minimum total costs of both in the interval [Min{f.le, d.le}, f.ri] else in the interval [f.le, f.ri].3. 3. 2 LeftInterference of a wellformed fieldset F^{n} with a field g
F_{L}^{k} = { l(f^{1}, g), m(f^{2}, g), ..., m(f^{n}, g)} = L ( F^{n} , g) = L ({f^{1}, ..., f^{n}}, g) (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] and f^{1}.le2<d.ri holds then the resulting fieldset is the representation of the minimum total costs of both in the interval [Min{ f^{1}.le, d.le}, f^{n}.ri] else in the interval [f^{1}.le, f^{n}.ri].3. 3. 3 LeftInterference of a wellformed fieldset F^{n} with a sorted fieldset G^{o}
F_{1}^{n(1)} = L (F^{n} ,g^{o})and
F_{i+1}^{n(i+1)} = L (F_{i}^{n(i)} ,g^{oi}) for i = 1...o1In general:
F_{LL}^{k} = LL (F^{n} ,G^{o}) = F_{o}^{n(o)} (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and G^{o} is the representation of o other possible total cost function in o intervals on [g^{1}.le, g^{o}.ri] and f^{1}.le2< g^{o}.ri holds then the resulting fieldset is the representation of the minimum total costs of all in the interval [Min{ f^{1}.le, g^{1}.le}, f^{n}.ri] else in the interval [f^{1}.le, f^{n}.ri].
F_{r}^{k} = r(f, d) (k = 1, 2, 3 or 4)Meaning:
If f is the representation of a possible total cost function in the interval [f.le, f.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] and f.ri+2>d.le holds then the resulting fieldset is the representation of the minimum total costs of both in the interval [f.le, Max{f.ri, d.ri}] else in the interval [f.le, f.ri].3. 4. 2 RightInterference of a wellformed fieldset F^{n} with a field g
F_{R}^{k} = {m(f^{1}, g), ..., m(f^{n1}, g) ), r(f^{n}, g)} = R ( F^{n} , g) = R ({f^{1}, ..., f^{n}}, g) (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and d is the representation of another possible total cost function in the interval [d.le, d.ri] and f^{n}.ri+2>d.le holds then the resulting fieldset is the representation of the minimum total costs of both in the interval [ f^{1}.le, Max{f^{n}.ri, d.ri}] else in the interval [f^{1}.le, f^{n}.ri].3. 4. 3 RightInterference of a wellformed fieldset F^{n} with a sorted fieldset G^{o}
F_{1}^{n(1)} = R (F^{n} ,g^{1})and
F_{i+1}^{n(i+1)} = R (F_{i}^{n(i)} ,g^{i+1}) for i = 1...o1In general:
F_{RR}^{k} = RR (F^{n} ,G^{o}) = F_{o}^{n(o)} (k>n1)Meaning:
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] and G^{o} is the representation of o other possible total cost function in o intervals on [g^{1}.le, g^{o}.ri] and f^{n}.ri+2> g^{1}.le holds then the resulting fieldset is the representation of the minimum total costs of all in the interval [f^{1}.le, Max{f^{n}.ri, g^{n}.ri}] else in the interval [f^{1}.le, f^{n}.ri].
F_{s}^{k} = s (f, Inf, Sup) (k = 0 or 1)Meaning:
If f is the representation of a possible total cost function in the interval [f.le, f.ri] then the resulting fieldset is the representation in the interval [Max{ f.le, Inf}, Min{f.ri, Sup}].3. 5. 2 Section of a wellformed fieldset F^{n} on the interval [Inf, Sup]
Meaning:
F_{S}^{k} = S (F^{n}, Inf, Sup) = {s(f^{1}, Inf, Sup), ..., s(f^{Inf}, Inf, Sup), ..., s(f^{Sup}, Inf , Sup), ..., s(f^{n}, Inf, Sup)} = {s(f^{Inf}, Inf, Sup), ..., s(f^{Sup}, Inf, Sup)} = {s(f^{Inf}, Inf, Sup), f^{Inf+1}, ..., f^{Sup1}, s(f^{Sup}, Inf, Sup)} = {f_{S}^{1}, ..., f_{S}^{k}} (k<n+1)
If F^{n} is the representation of a possible total cost function in the interval [f^{1}.le, f^{n}.ri] then the resulting fieldset is the representation in the interval [Max{ f^{1}.le, Inf}, Min{f^{n}.ri, Sup}].
F_{c}^{k} = c (f^{1}, f^{2}) (k = 1 or 2)Meaning:
If f^{1} is the representation of a possible total cost function in the interval [f^{1}.le, f^{1}.ri] and f^{2} is the representation of another possible total cost function in the interval [f^{2}.le, f^{2}.ri] and f^{1}.ri+1=f^{2}.le holds and the two fields can be consolidated (i.e. the fields ‘fit’ together) then the resulting fieldset consists of only one field that is the representation of both in the interval [f^{1}.le, f^{2}.ri] else the resulting fieldset consists of the two fields f^{1} and f^{2}. In this way it is possible to reduce data without any loss of information.3. 6. 2 Consolidation of a wellformed fieldset F^{n} at position i
F_{C}^{k} = C (F^{n}, i) = {f^{1}, ..., c(f^{i}, f^{i+1}), ..., f^{n}} (k = n1 or n)Meaning:
If F^{n} is the representation of a possible total cost function then the resulting fieldset is the representation of the same cost function with a Consolidation of the fields f^{i} and f^{i+1}. In this way it is possible to reduce data without any loss of information.3. 6. 3 Total Consolidation of a wellformed fieldset F^{n}
F_{1}^{n(1)} = C (F^{n}, n1)and
F_{i+1}^{n(i+1)} = C (F^{n(i)}, n(i+1)) for i = 1 ... n2In general:
F_{CC}^{k} = CC (F^{n}) = F_{n1}^{n(n1)} (k<n+1)Meaning:
If F^{n} is the representation of a possible total cost function then the resulting fieldset is the representation of the same cost function with a minimum number of fields. In this way it is possible to reduce data without any loss of information.
F_{h}^{k} = h (f, g) (k = 1, 2 or 3)Meaning:
If f is the representation of a total cost function without holding costs in the interval [f.le, f.ri] and g is the representation of a linear holding cost function in the interval [g.le, g.ri] then the resulting fieldset is the representation of the same total cost function in the interval [f.le, f.ri] with additional holding costs in the interval [g.le, g.ri].3. 7. 2 Linear HoldingTransformation of a wellformed fieldset F^{n} by a field g
F_{H}^{k} = H (F^{n}, g) = {h(f^{1}, g), ..., h(f^{n}, g)}= {f_{H}^{1}, ..., f_{H}^{k}} (n1<k<n+3)Meaning:
If F^{n} is the representation of a total cost function without holding costs in the interval [f^{1}.le, f^{n}.ri] and g is the representation of a linear holding cost function in the interval [g.le, g.ri] then the resulting fieldset is the representation of the same total cost function in the interval interval [f^{1}.le, f^{n}.ri] with additional holding costs in the interval [g.le, g.ri].3. 7. 3 Piecewise Linear HoldingTransformation of a wellformed fieldset F^{n} by a wellformed fieldset G^{o}
F_{1}^{n(1)} = H (F^{n} ,g^{1})and
F_{i+1}^{n(i+1)} = H (F_{i}^{n(i)} ,g^{i+1}) for i = 1...o1In general:
F_{HH}^{k} = HH (F^{n} ,G^{o}) = F_{o}^{n(o)} (k>n1)Meaning:
If F^{n} is the representation of a total cost function without holding costs in the interval [f^{1}.le, f^{n}.ri] and G^{o} is the representation of a piecewise linear holding cost function in the interval [g^{1}.le, g^{o}.ri] then the resulting fieldset is the representation of the same total cost function in the interval [f^{1}.le, f^{n}.ri] with additional holding costs in the interval [g^{1}.le, g^{o}.ri].
if d.pl=0: F_{op}^{m} = S ( P_{d0} ( F^{n}, d ), Inf, Sup) (production quantity=0)if d.le<d.ri:
if d.pl>0: F_{op}^{m} = S ( P_{dl} ( F^{n}, d ), Inf, Sup) (production quantity>0)
In general:
if d.pl=0: F_{*}^{n} = P_{*} ( F^{n}, d) (for * = d0, dr, fl, fr) F_{op}^{m} = CC (S (RR (RR ( F_{d0}^{n}, F_{fl}^{n} ), LL ( F_{dr}^{n}, F_{fr}^{n} ) ), Inf, Sup) ) if d.pl>0: F_{*}^{n} = P_{*} ( F^{n}, d) (for * = dl, dr, fl, fr) F_{op}^{m} = CC (S (RR (RR ( F_{dl}^{n}, F_{fl}^{n} ), LL ( F_{dr}^{n}, F_{fr}^{n} ) ), Inf, Sup) )
F_{op}^{m} = op (F^{n}, d, Inf, Sup) = {f_{op}^{1}, ..., f_{op}^{m}}Meaning:
If F^{n} is the representation of an optimum total cost function in a certain period, d is the representation of the appropriate production cost function in the next period and [Inf, Sup] is feasible inventory interval in the next period then the resulting fieldset is the representation of an optimum total cost function without holding costs in the next period. The appropriate model has no startup costs (o), linear production costs + setup costs (p) and no holding costs, resulting in the notation op.3. 8. 2 OptimumTransformation opt of a wellformed set F^{n} by a field d and a field g
F_{opt}^{m} = H ( op ( F^{n}, d, g.le, g.ri ), g )In general:
F_{opt}^{m} = opt (F^{n}, d, g) = {f_{opt}^{1}, ..., f_{opt}^{m}}Meaning:
If F^{n} is the representation of an optimum total cost function in a certain period, d is the representation of the appropriate production cost function in the next period and g is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldset is the representation of an optimum total cost function in the next period. The appropriate model has no startup costs (o), linear production costs + setup costs (p) and linear holding costs (t), resulting in the notation opt.3. 8. 3 OptimumTransformation oPt of a wellformed fieldset F^{n} by a wellformed fieldset D^{k} and a field g
F_{1}^{n(1)} = op (F^{n}, d^{1}, g.le, g.ri)and
F_{i+1}^{n(i+1)} = CC (RR (F_{i}^{n(i)}, op (F^{n}, d^{i+1}, g.le, g.ri) ) ) (for i = 1 ... k1)and
F_{oPt}^{m} = H ( F_{k}^{n(k)} , g )In general:
F_{oPt}^{m} = oPt (F^{n}, D^{k}, g) = {f_{oPt}^{1}, ..., f_{oPt}^{m}}Meaning:
If F^{n} is the representation of an optimum total cost function in a certain period, D^{k} is the representation of the appropriate production cost function in the next period and g is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldset is the representation of an optimum total cost function in the next period. The appropriate model has no startup costs (o), piecewise linear production costs + setup costs (P) and linear holding costs (t), resulting in the notation oPt.3. 8. 4 OptimumTransformation opT of a wellformed fieldset F^{n} by a field d and a wellformed fieldset G^{o}
F_{1}^{n(1)} = op (F^{n}, d, g^{1}.le, g^{o}.ri)and
F_{opT}^{m} = CC (HH (F_{1}^{n(1)}, G^{o}))In general:
F_{opT}^{m} = opT (F^{n}, d, G^{o}) = {f_{opT}^{1}, ..., f_{opT}^{m}}Meaning:
If F^{n} is the representation of an optimum total cost function in a certain period, d is the representation of the appropriate production cost function in the next period and G^{o} is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldset is the representation of an optimum total cost function in the next period. The appropriate model has no startup costs (o), linear production costs + setup costs (p) and piecewise linear holding costs (T), resulting in the notation opT.3. 8. 5 OptimumTransformation oPT of a wellformed fieldset F^{n} by a wellformed fieldset D^{k} and a wellformed fieldset G^{o}
F_{1}^{n(1)} = op (F^{n}, d^{1}, g.le, g.ri)and
F_{i+1}^{n(i+1)} = CC (RR (F_{i}^{n(i)}, op (F^{n}, d^{i+1}, g.le, g.ri) ) ) (for i = 1 ... k1)and
F_{oPT}^{m} = CC (HH (F_{k}^{n(k)}, G^{o}))In general:
F_{oPT}^{m} = oPT (F^{n}, D^{k}, G^{o}) = {f_{oPT}^{1}, ..., f_{oPT}^{m}}Meaning:
If F^{n} is the representation of an optimum total cost function in a certain period, D^{k} is the representation of the appropriate production cost function in the next period and G^{o} is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldset is the representation of an optimum total cost function in the next period. The appropriate model has no startup costs (o), piecewise linear production costs + setup costs (P) and piecewise linear holding costs (T), resulting in the notation oPT.3. 8. 6 OptimumTransformation Opt of two wellformed sets E^{m} and F^{n} by an integer c, a field d and a field g
E_{Opt}^{p} = H (CC (S (MM (P_{d0} (F^{n}, d), P_{d0} (E^{m}, d)), g.le, g.ri)), g)if d.pl>0:
E_{Opt}^{p }= {}In general:
E_{Opt}^{p} = Opt_{E} (E^{m}, F^{n}, d, g) = {e_{Opt}^{1}, ..., e_{Opt}^{p}}In general:
d.pl = 1
F_{opt}^{n(1)} = opt (F^{n}, d, g)
d.hl = d.hl + c
F_{Opt}^{q} = CC (MM (F_{opt}^{n(1)}, opt (E^{m}, d, g)))
F_{Opt}^{q} = Opt_{F} (E^{m}, F^{n}, c, d, g) = {f_{Opt}^{1}, ..., f_{Opt}^{q}}Meaning:
If E^{m} is the representation of an optimum total cost function in a certain period with production quantity=0 and no setup costs, F^{n} is the representation with any production quantity and setup costs, c is the amount of the startup costs in the next period, d is the representation of the appropriate production cost function in the next period with no startup costs and g is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldsets are the representation of an optimum total cost function in the next period. The appropriate model has startup costs (O), linear production costs + setup costs (p) and linear holding costs (t), resulting in the notation Opt.3. 8. 7 OptimumTransformation OPt of two wellformed sets E^{m} and F^{n} by an integer c, a wellformed fieldset D^{k} and a field g
E_{OPt}^{p} = H (CC (S (MM (P_{d0} (F^{n}, d^{1}), P_{d0} (E^{m}, d^{1})), g.le, g.ri)), g)if d^{1}.pl>0:
E_{OPt}^{p }= {}In general:
E_{OPt}^{p} = OPt_{E} (E^{m}, F^{n}, D^{k}, g) = {e_{OPt}^{1}, ..., e_{OPt}^{p}}In general:
d^{1}.pl = 1
F_{1}^{n(1)} = op (F^{n}, d^{1}, g.le, g.ri)
F_{i+1}^{n(i+1)} = CC (RR (F_{i}^{n(i)}, op (F^{n}, d^{i+1}, g.le, g.ri) ) ) (for i = 1 ... k1)
d^{i}.hl = d^{i}.hl + c (for i = 1 ... k)
E_{1}^{m(1)} = op (E^{m}, d^{1}, g.le, g.ri)
E_{i+1}^{m(i+1)} = CC (RR (E_{i}^{m(i)}, op (E^{m}, d^{i+1}, g.le, g.ri) ) ) (for i = 1 ... k1)
F_{OPt}^{q} = H (CC (MM (F_{k}^{n(k)}, E_{k}^{m(k)}) ), g)
F_{OPt}^{q} = OPt_{F} (E^{m}, F^{n}, c, D^{k}, g) = {f_{OPt}^{1}, ..., f_{OPt}^{q}}Meaning:
If E^{m} is the representation of an optimum total cost function in a certain period with production quantity=0 and no setup costs, F^{n} is the representation with any production quantity and setup costs, c is the amount of the startup costs in the next period, D^{k} is the representation of the appropriate production cost function in the next period with no startup costs and g is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldsets are the representation of an optimum total cost function in the next period. The appropriate model has startup costs (O), piecewise linear production costs + setup costs (P) and linear holding costs (t), resulting in the notation OPt.3. 8. 8 OptimumTransformation OpT of two wellformed sets E^{m} and F^{n} by an integer c, a field d and a wellformed fieldset G^{o}
E_{1}^{m(1)} = CC (S (MM (P_{d0} (F^{n}, d), P_{d0} (E^{m}, d)), g^{1}.le, g^{o}.ri))if d.pl>0:
E_{OpT}^{p }= CC ( HH (E_{1}^{m(1)}, G^{o}))
E_{OpT}^{p }= {}In general:
E_{OpT}^{p} = OpT_{E} (E^{m}, F^{n}, d, G^{o}) = {e_{OpT}^{1}, ..., e_{OpT}^{p}}In general:
d.pl = 1
F_{opT}^{n(1)} = opT (F^{n}, d, G^{o})
d.hl = d.hl + c
F_{OpT}^{q} = CC (MM (F_{opT}^{n(1)}, opT (E^{m}, d, G^{o})))
F_{OpT}^{q} = OpT_{F} (E^{m}, F^{n}, c, d, G^{o}) = {f_{OpT}^{1}, ..., f_{OpT}^{q}}Meaning:
If E^{m} is the representation of an optimum total cost function in a certain period with production quantity=0 and no setup costs, F^{n} is the representation with any production quantity and setup costs, c is the amount of the startup costs in the next period, d is the representation of the appropriate production cost function in the next period with no startup costs and G^{o} is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldsets are the representation of an optimum total cost function in the next period. The appropriate model has startup costs (O), linear production costs + setup costs (p) and piecewise linear holding costs (T), resulting in the notation OpT.3. 8. 9 OptimumTransformation OPT of two wellformed sets E^{m} and F^{n} by an integer c, a wellformed fieldset D^{k} and a wellformed fieldset G^{o}
E_{1}^{m(1)} = CC (S (MM (P_{d0} (F^{n}, d^{1}), P_{d0} (E^{m}, d^{1})), g^{1}.le, g^{o}.ri))if d^{1}.pl>0:
E_{OPT}^{p }= CC ( HH (E_{1}^{m(1)}, G^{o}))
E_{OPT}^{p }= {}In general:
E_{OPT}^{p} = OPT_{E} (E^{m}, F^{n}, D^{k}, G^{o}) = {e_{OPT}^{1}, ..., e_{OPT}^{p}}In general:
d^{1}.pl = 1
F_{1}^{n(1)} = op (F^{n}, d^{1}, g^{1}.le, g^{o}.ri)
F_{i+1}^{n(i+1)} = CC (RR (F_{i}^{n(i)}, op (F^{n}, d^{i+1}, g^{1}.le, g^{o}.ri) ) ) (for i = 1 ... k1)
d^{i}.hl = d^{i}.hl + c (for i = 1 ... k)
E_{1}^{m(1)} = op (E^{m}, d^{1}, g^{1}.le, g^{o}.ri)
E_{i+1}^{m(i+1)} = CC (RR (E_{i}^{m(i)}, op (E^{m}, d^{i+1}, g^{1}.le, g^{o}.ri) ) ) (for i = 1 ... k1)
F_{OPT}^{q} = CC (HH (MM (F_{k}^{n(k)}, E_{k}^{m(k)}), G) )
F_{OPT}^{q} = OPT_{F} (E^{m}, F^{n}, c, D^{k}, G^{o}) = {f_{OPT}^{1}, ..., f_{OPT}^{q}}Meaning:
If E^{m} is the representation of an optimum total cost function in a certain period with production quantity=0 and no setup costs, F^{n} is the representation with any production quantity and setup costs, c is the amount of the startup costs in the next period, D^{k} is the representation of the appropriate production cost function in the next period with no startup costs and G^{o} is the representation of the appropriate holding cost function in the next period in the feasible inventory interval then the resulting fieldsets are the representation of an optimum total cost function in the next period. The appropriate model has startup costs (O), piecewise linear production costs + setup costs (P) and piecewise linear holding costs (T), resulting in the notation OPT.
f_{d0} = { pl = f.le pr = f.ri le = f.le + d.le ri = f.ri + d.le hl = f.hl dh = f.dh }
f_{dl} = { pl = f.le pr = f.ri le = f.le + d.le ri = f.ri + d.le hl = f.hl + d.hl dh = f.dh }
f_{dr} = { pl = f.le pr = f.ri le = f.le + d.ri ri = f.ri + d.ri hl = f.hl + d.hl + (d.rid.le)*d.dh dh = f.dh }
f_{fl} = { pl = f.le pr = f.le le = f.le + d.le ri = f.le + d.ri hl = f.hl + d.hl dh = d.dh }
f_{fr} = { pl = f.ri pr = f.ri le = f.ri + d.le ri = f.ri + d.ri hl = f.hl + (f.rif.le)*f.dh + d.hl dh = d.dh }
F_{*}^{1} = p_{*}(f, d) = { f_{*}^{1} } (* = d0, dl, dr, fl, fr)
There are 9 combinations, that can be distinguished by identity numbers (CaseId’s). Cases with f.le>f.ri or d.le>d.ri are impossible.
( 1, * ): d.le < f.le+1 ( 2, * ): f.le < d.le < f.ri+1 ( 3, * ): f.ri < d.le ( *, 1 ): d.ri < f.le ( *, 2 ): f.le1 < d.ri < f.ri ( *, 3 ): f.ri1 < d.ri
4. 2. 2 Calculation instruction for CaseId 1 and CaseId 9
Case CaseId Type of result ( 1, 1 ): 1 (= 1*1) F_{m}^{k} = F_{m}^{1} ( 2, 1 ): 0 not possible ( 3, 1 ): 0 not possible ( 1, 2 ): 2 (= 1*2) F_{m}^{k} = F_{m}^{1} or F_{m}^{2} or F_{m}^{3} ( 2, 2 ): 4 (= 2*2) F_{m}^{k} = F_{m}^{1} or F_{m}^{3} ( 3, 2 ): 0 not possible ( 1, 3 ): 3 (= 1*3) F_{m}^{k} = F_{m}^{1} or F_{m}^{2} ( 2, 3 ): 6 (= 2*3) F_{m}^{k} = F_{m}^{1} or F_{m}^{2} or F_{m}^{3} ( 3, 3 ): 9 (= 3*3) F_{m}^{k} = F_{m}^{1}
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} } = { f }4. 2. 3 Calculation instruction for CaseId 2
dl = f.hl  ( d.hl + ( f.le  d.le ) * d.dh )If ( dl>0 and dr<0 ) or ( dl<0 and dr >0 ) Calculation of the integer variable lr with
dr = ( f.hl + ( d.ri  f.le ) * f.dh )  ( d.hl + ( d.ri d.le ) * d.dh )
lr < ( dl * d.ri  dr * f.le ) / (dl  dr ) < lr + 1 or lr = ( dl * d.ri  dr * f.le ) / (dl  dr )SubCase 2.1: dl1<0 and dr1<0
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} } = { f }SubCase 2.2: dl+1>0 and dr+1>0
SubCase 2.3: dl>0 and dr<0
f_{m}^{1} = { pl = d.pl + ( f.le  d.le ) * sign ( d.pr  d.pl ) pr = d.pr le = f.le ri = d.ri hl = d.hl + ( f.le  d.le ) * d.dh dh = d.dh }
f_{m}^{2} = { pl = f.pl + ( d.ri + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = d.ri + 1 ri = f.ri hl = f.hl + ( d.ri + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
SubCase 2.4: dl<0 and dr>0
f_{m}^{1} = { pl = d.pl + ( f.le  d.le ) * sign ( d.pr  d.pl ) pr = d.pl + ( lr  d.le ) * sign ( d.pr  d.pl ) le = f.le ri = lr hl = d.hl + ( f.le  d.le ) * d.dh dh = d.dh }
f_{m}^{2} = { pl = f.pl + ( lr + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = lr + 1 ri = f.ri hl = f.hl + ( lr + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
4. 2. 4 Calculation instruction for CaseId 3
f_{m}^{1} = { pl = f.pl pr = f.pl + ( lr  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = lr hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl + ( lr + 1  d.le ) * sign ( d.pr  d.pl ) pr = d.pr le = lr + 1 ri = d.ri hl = d.hl + ( lr + 1  d.le ) * d.dh dh = d.dh }
f_{m}^{3} = { pl = f.pl + ( d.ri + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = d.ri + 1 ri = f.ri hl = f.hl + ( d.ri + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{3} = { f_{m}^{1}, f_{m}^{2} , f_{m}^{3} }
dl = f.hl  ( d.hl + ( f.le  d.le ) * d.dh )If ( dl>0 and dr<0 ) or ( dl<0 and dr >0 ) Calculation of the variable lr with
dr = ( f.hl + ( f.ri  f.le ) * f.dh )  ( d.hl + ( f.ri d.le ) * d.dh )
lr < ( dl * f.ri  dr * f.le ) / (dl  dr ) < lr + 1 orSubCase 3.1: dl1<0 and dr1<0
lr = ( dl * f.ri  dr * f.le ) / (dl  dr )
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} } = { f }SubCase 3.2: dl+1>0 and dr+1>0
SubCase 3.3: dl>0 and dr<0
f_{m}^{1} = { pl = d.pl + ( f.le  d.le ) * sign ( d.pr  d.pl ) pr = d.pl + ( f.ri  d.le ) * sign ( d.pr  d.pl ) le = f.le ri = f.ri hl = d.hl + ( f.le  d.le ) * d.dh dh = d.dh }
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} }
SubCase 3.4: dl<0 and dr>0
f_{m}^{1} = { pl = d.pl + ( f.le  d.le ) * sign ( d.pr  d.pl ) pr = d.pl + ( lr  d.le ) * sign ( d.pr  d.pl ) le = f.le ri = lr hl = d.hl + ( f.le  d.le ) * d.dh dh = d.dh }
f_{m}^{2} = { pl = f.pl + ( lr + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = lr + 1 ri = f.ri hl = f.hl + ( lr + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
4. 2. 5 Calculation instruction for CaseId 4
f_{m}^{1} = { pl = f.pl pr = f.pl + ( lr  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = lr hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl + ( lr + 1  d.le ) * sign ( d.pr  d.pl ) pr = d.pl + ( f.ri  d.le ) * sign ( d.pr  d.pl ) le = lr + 1 ri = f.ri hl = d.hl + ( lr + 1  d.le ) * d.dh dh = d.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
dl = ( f.hl + ( d.le  f.le ) * f.dh )  d.hlIf ( dl>0 and dr<0 ) or ( dl<0 and dr >0 ) Calculation of the variable lr with
dr = ( f.hl + ( d.ri  f.le ) * f.dh )  ( d.hl + ( d.ri d.le ) * d.dh )
lr < ( dl * d.ri  dr * d.le ) / (dl  dr ) < lr + 1 orSubCase 4.1: dl1<0 and dr1<0
lr = ( dl * d.ri  dr * d.le ) / (dl  dr )
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} } = { f }SubCase 4.2: dl+1>0 and dr+1>0
SubCase 4.3: dl>0 and dr<0
f_{m}^{1} = { pl = f.pl pr = f.pl + ( d.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = d.le  1 hl = f.hl dh = f.dh }
f_{m}^{2} = d
f_{m}^{3} = { pl = f.pl + ( d.ri + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = d.ri + 1 ri = f.ri hl = f.hl + ( d.ri + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{3} = { f_{m}^{1}, f_{m}^{2}, f_{m}^{3} }
SubCase 4.4: dl<0 and dr>0
f_{m}^{1} = { pl = f.pl pr = f.pl + ( d.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = d.le  1 hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl pr = d.pl + ( lr  d.le ) * sign ( d.pr  d.pl ) le = d.le ri = lr hl = d.hl dh = d.dh }
f_{m}^{3} = { pl = f.pl + ( lr + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = lr + 1 ri = f.ri hl = f.hl + ( lr + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{3} = { f_{m}^{1}, f_{m}^{2}, f_{m}^{3} }
4. 2. 6 Calculation instruction for CaseId 6
f_{m}^{1} = { pl = f.pl pr = f.pl + ( lr  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = lr hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl + ( lr +1  d.le ) * sign ( d.pr  d.pl ) pr = d.pr le = lr + 1 ri = d.ri hl = d.hl + ( lr +1  d.le ) * d.dh dh = d.dh }
f_{m}^{3} = { pl = f.pl + ( d.ri + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = d.ri + 1 ri = f.ri hl = f.hl + ( d.ri + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{3} = { f_{m}^{1}, f_{m}^{2}, f_{m}^{3} }
dl = ( f.hl + ( d.le  f.le ) * f.dh )  d.hl )If ( dl>0 and dr<0 ) or ( dl<0 and dr >0 ) Calculation of the integer variables lr with
dr = ( f.hl + ( f.ri  f.le ) * f.dh )  ( d.hl + ( f.ri d.le ) * d.dh )
lr < ( dl * f.ri  dr * d.le ) / (dl  dr ) < lr + 1 orSubCase 6.1: dl1<0 and dr1<0
lr = ( dl * f.ri  dr * d.le ) / (dl  dr )
F_{m}^{k} = m(f, d) = F_{m}^{1} = { f_{m}^{1} } = { f }SubCase 6.2: dl+1>0 and dr+1>0
SubCase 6.3: dl>0 and dr<0
f_{m}^{1} = { pl = f.pl pr = f.pl + ( d.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = d.le  1 hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl pr = d.pl + ( f.ri  d.le ) * sign (d.pr  d.pl ) le = d.le ri = f.ri hl = d.hl dh = d.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
SubCase 6.4: dl<0 and dr>0
f_{m}^{1} = { pl = f.pl pr = f.pl + ( d.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = d.le  1 hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl pr = d.pl + ( lr  d.le ) * sign ( d.pr  d.pl ) le = d.le ri = lr hl = d.hl dh = d.dh }
f_{m}^{3} = { pl = f.pl + ( lr + 1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = lr + 1 ri = f.ri hl = f.hl + ( lr + 1  f.le ) * f.dh dh = f.dh }
F_{m}^{k} = m(f, d) = F_{m}^{3} = { f_{m}^{1}, f_{m}^{2} , f_{m}^{3} }
f_{m}^{1} = { pl = f.pl pr = f.pl + ( lr  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = lr hl = f.hl dh = f.dh }
f_{m}^{2} = { pl = d.pl + ( lr + 1  d.le ) * sign ( d.pr  d.pl ) pr = d.pl + ( f.ri  d.le ) * sign ( d.pr  d.pl ) le = lr + 1 ri = f.ri hl = d.hl + ( lr + 1  d.le ) * d.dh dh = d.dh }
F_{m}^{k} = m(f, d) = F_{m}^{2} = { f_{m}^{1}, f_{m}^{2} }
Case else:
f_{l}^{1} = { pl = d.pl pr = d.pl + ( f.le 1  d.le ) * sign ( d.pr  d.pl ) le = d.le ri = f.le  1 hl = d.hl dh = d.dh }
F_{l}^{k} = l(f, d) = { f_{l}^{1}, m(f, d) }
F_{l}^{k} = l(f, d) = m(f, d)
Case else:
f_{r}^{k} = { pl = d.pl + ( f.ri + 1  d.le ) * sign ( d.pr  d.pl ) pr = d.pr le = f.ri+1 ri = d.ri hl = d.hl + ( f.ri + 1  d.le ) * d.dh dh = d.dh }
F_{r}^{k} = r(f, d) = { m(f, d), f_{r}^{k} }
F_{r}^{k} = r(f, d) = m(f, d)
There are 9 combinations, that can be distinguished by identity numbers (CaseId’s). Cases with f.le>f.ri or Inf>Sup are impossible.
( 1, * ): Inf < f.le+1 ( 2, * ): f.le < Inf < f.ri+1 ( 3, * ): f.ri < Inf ( *, 1 ): Sup < f.le ( *, 2 ): f.le1 < Sup < f.ri ( *, 3 ): f.ri1 < Sup
4. 5. 2 Calculation instruction for CaseId 2
Case CaseId Type of result ( 1, 1 ): 1 (= 1*1) F_{b}^{k} = F_{b}^{0} = {} ( 2, 1 ): 0 not possible ( 3, 1 ): 0 not possible ( 1, 2 ): 2 (= 1*2) F_{b}^{k} = F_{b}^{1} ( 2, 2 ): 4 (= 2*2) F_{b}^{k} = F_{b}^{1} ( 3, 2 ): 0 not possible ( 1, 3 ): 3 (= 1*3) F_{b}^{k} = F_{b}^{1} = { f_{b}^{1} } = { f } ( 2, 3 ): 6 (= 2*3) F_{b}^{k} = F_{b}^{1} ( 3, 3 ): 9 (= 3*3) F_{b}^{k} = F_{b}^{0} = {}
4. 5. 3 Calculation instruction for CaseId 4
f_{b}^{1} = { pl = f.pl pr = f.pl + ( Sup  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = Sup hl = f.hl dh = f.dh }
F_{b}^{k} = b(f, Inf, Sup) = F_{b}^{1} = { f_{b}^{1}}
4. 5. 4 Calculation instruction for CaseId 6
f_{b}^{1} = { pl = f.pl + ( Inf  f.le ) * sign ( f.pr  f.pl ) pr = f.pl + ( Sup  f.le ) * sign ( f.pr  f.pl ) le = Inf ri = Sup hl = f.hl + ( Inf  f.le ) * f.dh dh = f.dh }
F_{b}^{k} = b(f, Inf, Sup) = F_{b}^{1} = { f_{b}^{1}}
f_{b}^{1} = { pl = f.pl + ( Inf  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = Inf ri = f.ri hl = f.hl + ( Inf  f.le ) * f.dh dh = f.dh }
F_{b}^{k} = b(f, Inf, Sup) = F_{b}^{1} = { f_{b}^{1}}
SubCase1.1: (  f^{1}.hl + ( f^{2}.le  f^{1}.le ) * f^{1}.dh = f^{2}.hl and 
f^{1}.hl + ( f^{2}.ri  f^{1}.le ) * f^{1}.dh = f^{2}.hl + ( f^{2}.ri  f^{2}.le ) * f^{2}.dh and  
f^{1}.pl + ( f^{2}.le  f^{1}.le ) * sign ( f^{1}.pr  f^{1}.pl ) = f^{2}.pl and  
f^{1}.pl + ( f^{2}.ri  f^{1}.le ) * sign ( f^{1}.pr  f^{1}.pl ) = f^{2}.pr) 
f_{v}^{1} = { pl = f^{1}.pl pr = f^{2}.pr le = f^{1}.le ri = f^{2}.ri hl = f^{1}.hl dh = f^{1}.dh }
F_{v}^{k} = v (f^{1}, f^{2}) = F_{v}^{1} = { f_{v}^{1} }
SubCase1.2: (  f^{2}.hl  ( f^{2}.le  f^{1}.le ) * f^{2}.dh = f^{1}.hl and 
f^{2}.hl  ( f^{2}.le  f^{1}.ri ) * f^{2}.dh = f^{1}.hl + ( f^{1}.ri  f^{1}.le ) * f^{1}.dh and  
f^{2}.pl  ( f^{2}.le  f^{1}.le ) * sign ( f^{2}.pr  f^{2}.pl ) = f^{1}.pl and  
f^{2}.pl  ( f^{2}.le  f^{1}.ri ) * sign ( f^{2}.pr  f^{2}.pl ) = f^{1}.pr) 
SubCase 1.else and Case else:
f_{v}^{1} = { pl = f^{1}.pl pr = f^{2}.pr le = f^{1}.le ri = f^{2}.ri hl = f^{1}.hl dh = f^{2}.dh }
F_{v}^{k} = v (f^{1}, f^{2}) = F_{v}^{1} = { f_{v}^{1} }
F_{v}^{k} = v (f^{1}, f^{2}) = F_{v}^{2} = { f_{v}^{1}, f_{v}^{2} } = { f^{1}, f^{2} }
There are 9 combinations, that can be distinguished by identity numbers (CaseId’s). Cases with f.le>f.ri or g.le>g.ri are impossible.
( 1, * ): g.le < f.le+1 ( 2, * ): f.le < g.le < f.ri+1 ( 3, * ): f.ri < g.le ( *, 1 ): g.ri < f.le ( *, 2 ): f.le1 < g.ri < f.ri ( *, 3 ): f.ri1 < g.ri
4. 5. 2 Calculation instruction for CaseId 1 and CaseId 9
Case CaseId Type of result ( 1, 1 ): 1 (= 1*1) F_{h}^{k} = F_{h}^{1} = { f_{h}^{1} } = { f } ( 2, 1 ): 0 not possible ( 3, 1 ): 0 not possible ( 1, 2 ): 2 (= 1*2) F_{h}^{k} = F_{h}^{2} ( 2, 2 ): 4 (= 2*2) F_{h}^{k} = F_{b}^{3} ( 3, 2 ): 0 not possible ( 1, 3 ): 3 (= 1*3) F_{h}^{k} = F_{h}^{1} = { f_{h}^{1} } ( 2, 3 ): 6 (= 2*3) F_{h}^{k} = F_{h}^{2} ( 3, 3 ): 9 (= 3*3) F_{b}^{k} = F_{b}^{1} = { f_{h}^{1} } = { f }
F_{h}^{k} = h(f, g) = F_{h}^{1} = { f_{h}^{1}} = { f }4. 5. 3 Calculation instruction for CaseId 2
4. 5. 4 Calculation instruction for CaseId 3
f_{h}^{1} = { pl = f.pl pr = f.pl + ( g.ri  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = g.ri hl = f.hl + g.hl + ( f.le  g.le ) * g.dh dh = f.dh + g.dh}
f_{h}^{2} = { pl = f.pl + ( g.ri +1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = g.ri+1 ri = f.ri hl = f.hl + ( g.ri +1  f.le ) * f.dh dh = f.dh }
F_{h}^{k} = h(f, g) = F_{h}^{2} = { f_{h}^{1}, f_{h}^{2}}
4. 5. 5 Calculation instruction for CaseId 4
f_{h}^{1} = { pl = f.pl pr = f.pr le = f.le ri = f.ri hl = f.hl + g.hl + ( f.leg.le ) * g.dh dh = f.dh + g.dh }
F_{h}^{k} = h(f, g) = F_{h}^{1} = { f_{h}^{1}}
4. 5. 6 Calculation instruction for CaseId 6
f_{h}^{1} = { pl = f.pl pr = f.pl + ( g.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = g.le  1 hl = f.hl dh = f.dh }
f_{h}^{2} = { pl = f.pl + ( g.le  f.le ) * sign ( f.pr  f.pl ) pr = f.pl + ( g.ri  f.le ) * sign ( f.pr  f.pl ) le = g.le ri = g.ri hl = f.hl + ( g.le  f.le ) * f.dh + g.hl dh = f.dh + g.dh }
f_{h}^{3} = { pl = f.pl + ( g.ri +1  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = g.ri+1 ri = f.ri hl = f.hl + ( g.ri +1  f.le ) * f.dh dh = f.dh }
F_{h}^{k} = h(f, g) = F_{h}^{3} = { f_{h}^{1}, f_{h}^{2}, f_{h}^{3}}
f_{h}^{1} = { pl = f.pl pr = f.pl + ( g.le  1  f.le ) * sign ( f.pr  f.pl ) le = f.le ri = g.le  1 hl = f.hl dh = f.dh }
f_{h}^{2} = { pl = f.pl + ( g.le  f.le ) * sign ( f.pr  f.pl ) pr = f.pr le = g.le ri = f.ri hl = f.hl + ( g.le  f.le ) * f.dh + g.hl dh = f.dh + g.dh }
F_{h}^{k} = h(f, g) = F_{h}^{2} = { f_{h}^{1}, f_{h}^{2}}
Set  y_{I}^{Inf} = Max { y_{I}^{min}; y_{I} } 
For i = I1 down to 1 calculate  y_{i}^{Inf} = Max { y_{i+1}^{Inf} + d_{i+1}  x_{i+1}^{max} ; y_{i}^{min} } 
Set  y_{0}^{Inf} = Max { y_{1}^{Inf} + d_{1}  x_{1}^{max} ; y_{0} } 
For i = 1 up to I calculate  y_{i}^{Inf} = Max { y_{i1}^{Inf} + x_{i}^{min}  d_{i} ; y_{i}^{Inf} } 
Set  y_{0}^{Sup} = y_{0} 
For i = 1 up to I calculate  y_{i}^{Sup} = Min { y_{i1}^{Sup} + x_{i}^{max}  d_{i} ; y_{i}^{max} } 
Set  y_{I}^{Sup} = Min { y_{I}^{Sup}; y_{I} } 
For i = I1 down to 0 calculate  y_{i}^{Sup} = Min { y_{i+1}^{Sup} + d_{i+1}  x_{i+1}^{min}; y_{i}^{Sup} } 
Set  IsFeasibleSolution = true 
For i = 0 up to I do  If ( y_{i}^{Inf} > y_{i}^{Sup} ) then IsFeasibleSolution = false 
5. 2. 3 Calculation of the optimum total cost functions
f_{0}^{1} = { pl = y_{0} pr = y_{0} le = y_{0} ri = y_{0} hl = 0 dh = 0 }
if (model=opt or model=opT) then calculate field d withSubStep 2: Calculate the fieldset F_{i}^{n(i)}
d = { pl = sign(x_{i}^{min}) pr = 0 le = d_{i} + x_{i}^{min} ri = Min { x_{i}^{max}  d_{i} ; y_{i}^{Sup}  y_{i1}^{Inf} } hl = s_{i}^{1} + x_{i}^{min} * c_{i}^{1} dh = c_{i}^{1} }
if (model=oPt or model=oPT) then calculate fieldset D^{J(i)} = {d^{1}, ..., d^{J(i)}}with
d^{j} = { pl = sign(x_{i}^{j1}+1) pr = 0 le = d_{i} + x_{i}^{j1}+1 ri = x_{i}^{j}  d_{i} hl = s_{i}^{j} + (x_{i}^{j1} +1) * c_{i}^{j} dh = c_{i}^{j} }
if (model=opt or model=oPt) then calculate field g with
g = { pl = 0 pr = 0 le = y_{i}^{min} ri = y_{i}^{max} hl = t_{i}^{1} + y_{i}^{min} * h_{i}^{1} dh = h_{i}^{1} }
if (model=opT or model=oPT) then calculate fieldset G^{K(i)} = {g^{1}, ..., g^{K(i)}} with
g^{k} = { pl = 0 pr = 0 le = y_{i}^{k1}+1 ri = y_{i}^{k} hl = t_{i}^{k} + (y_{i}^{k1}+1)* h_{i}^{k} dh = h_{i}^{k} }
if model=opt: F_{i}^{n(i)} = opt ( F_{i1}^{n(i1)}, d, g )5. 2. 4 Calculation of the optimum production and inventory quantities
if model=oPt: F_{i}^{n(i)} = oPt ( F_{i1}^{n(i1)}, D^{J(i)}, g )
if model=opT: F_{i}^{n(i)} = opT ( F_{i1}^{n(i1)}, d, G^{K(i)} )
if model=oPT: F_{i}^{n(i)} = oPT ( F_{i1}^{n(i1)}, D^{J(i)}, G^{K(i)} )
Find f_{i}^{*} in F_{i}^{n(i)} = {f_{i}^{1}, ..., f_{i}^{*}, ..., f_{i}^{n(i)}}, so thatSubStep 2:
f_{i}^{*}.le1 < y_{i} < f_{i}^{*}.ri+1
Calculate y_{i1} = f_{i}^{*}.pl + ( y_{i}  f_{i}^{*}.le ) * sign ( f_{i}^{*}.pr  f_{i}^{*}.pl )Calculate the optimum production quantities and startups in the following way:
x_{i} = d_{i} + y_{i}  y_{i1}
u_{i} = sign( x_{i} )_{ }
Initialize the set F_{0}^{1} = {f_{0}^{1}} with
e_{0}^{1} = { pl = y_{0} pr = y_{0} le = y_{0} ri = y_{0} hl = 0 dh = 0 }
5. 3. 3 Calculation of the optimum total cost functions
f_{0}^{1} = { pl = y_{0} pr = y_{0} le = y_{0} ri = y_{0} hl = ( 1  u_{0} ) * a_{1} dh = 0 }
Set the integer c = a_{i}SubStep 1:
if (model=Opt or model=OpT) then calculate field d withSubStep 2: Calculate the fieldsets E_{i}^{m(i)} and F_{i}^{n(i)}
d = { pl = sign(x_{i}^{min}) pr = 0 le = d_{i} + x_{i}^{min} ri = Min { x_{i}^{max}  d_{i} ; y_{i}^{Sup}  y_{i1}^{Inf} } hl = s_{i}^{1} + x_{i}^{min} * c_{i}^{1} dh = c_{i}^{1} }
if (model=OPt or model=OPT) then calculate fieldset D^{J(i)} = {d^{1}, ..., d^{J(i)}}with
d^{j} = { pl = sign(x_{i}^{j1}+1) pr = 0 le = d_{i} + x_{i}^{j1}+1 ri = x_{i}^{j}  d_{i} hl = s_{i}^{j} + (x_{i}^{j1} +1) * c_{i}^{j} dh = c_{i}^{j} }
if (model=Opt or model=OPt) then calculate field g with
g = { pl = 0 pr = 0 le = y_{i}^{min} ri = y_{i}^{max} hl = t_{i}^{1} + y_{i}^{min} * h_{i}^{1} dh = h_{i}^{1} }
if (model=OpT or model=OPT) then calculate fieldset G^{K(i)} = {g^{1}, ..., g^{K(i)}}with
g^{k} = { pl = 0 pr = 0 le = y_{i}^{k1}+1 ri = y_{i}^{k} hl = t_{i}^{k} + (y_{i}^{k1}+1)* h_{i}^{k} dh = h_{i}^{k} }
5. 3. 4 Calculation of the optimum production and inventory quantities
if model=Opt: E_{i}^{m(i)} = Opt_{E} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, d, g ) F_{i}^{n(i)} = Opt_{F} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, c, d, g ) if model=OPt: E_{i}^{m(i)} = OPt_{E} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, D^{J(i)}, g ) F_{i}^{n(i)} = OPt_{F} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, c, D^{J(i)}, g ) if model=OpT: E_{i}^{m(i)} = OpT_{E} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, d, G^{K(i)} ) F_{i}^{n(i)} = OpT_{F} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, c, d, G^{K(i)} ) if model=OPT: E_{i}^{m(i)} = OPT_{E} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, D^{J(i)}, G^{K(i)} ) F_{i}^{n(i)} = OPT_{F} (E_{i1}^{m(i1)}, F_{i1}^{n(i1)}, c, D^{J(i)}, G^{K(i)} )
Set a = 0For i = I down to 1 calculate:
Find f_{i}^{*} in F_{i}^{n(i)} = {f_{i}^{1}, ..., f_{i}^{*}, ..., f_{i}^{n(i)}}, so thatCalculate the optimum production quantities in the following way:
f_{i}^{*}.le1 < y_{i} < f_{i}^{*}.ri+1
Try to find e_{i}^{*} in E_{i}^{m(i)} = {e_{i}^{1}, ..., e_{i}^{*}, ..., e_{i}^{n(i)}}, so that
e_{i}^{*}.le1 < y_{i} < e_{i}^{*}.ri+1
Set c = 1
If there is an e_{i}^{*} then calculate
c = a + (e_{i}^{*}.hl + (y_{i}  e_{i}^{*}.le) * e_{i}^{*}.dh)  (f_{i}^{*}.hl + (y_{i}  f_{i}^{*}.le) * f_{i}^{*}.dh)
If c<0 then calculate
y_{i1} = e_{i}^{*}.pl + ( y_{i}  e_{i}^{*}.le ) * sign ( e_{i}^{*}.pr  e_{i}^{*}.pl )
u_{i} = 0
Else calculate
y_{i1} = f_{i}^{*}.pl + ( y_{i}  f_{i}^{*}.le ) * sign ( f_{i}^{*}.pr  f_{i}^{*}.pl )
u_{i} = 1
Set a = a_{i} * u_{i}
x_{i} = d_{i} + y_{i}  y_{i1}
Problem Size I  Time [sec] using subproblems of  
Size I  Size I_sub  
73  0.05  0.12 
146  0.10  0.38 
219  0.15  0.83 

