Minimum concave cost production system: A further generalization of multi-echelon model (Q1114584)

The author considers a concave minimization problem associated with a series production system in which raw material is processed in m consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during period i \((i=1,...,n)\) are known in advance. The problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave. The origin of this model is the classical economic lot size problem of \textit{M. H. Wagner} and \textit{T. M. Whitin} [Manage. Sci. 5, 89-96 (1958)] and was extensively studied by \textit{W. I. Zangwill} [Manage. Sci. 15, 506-527 (1969; Zbl 0172.446)]. This model is very important from the theoretical as well as the practical point of view and this is one of the very rare instances in which a polynomial time algorithm has been constructed for concave minimization problems. This paper extends the model to the situation in which a time lag is associated with processing at each facility. An efficient \(0(n^ 4m)\) algorithm for this class of problems is presented.