Determination of replenishment dates for restricted-storage, static demand, cyclic replenishment schedule (Q2482372)

The authors consider the so called Warehouse Replenishment Scheduling Problem with Restricted Storage space (WRSPRS). There are \(N\) products in a warehouse with restricted storage space. Each product \(i, i=1,2,...,N\), is cyclically replenished after a fixed replenishment cycle \(T_i\) which is an integer multiple of some basic period. The demand rate \(d_i\) of each product \(i\) is known and is constant. (Therefore, the replenishment quantity \(q_i=d_iT_i\) of product \(i, i=1,2,...,N\), is constant too.) The warehouse space \(s_i\) is required for a unit of product \(i, i=1,2,...,N\). A replenishment schedule is defined by a vector \(X=(x_1, x_2,...,x_N)\), where \(x_i\) is the earliest scheduled replenishment time point of product \(i\). The authors define \(S_t(X)\) as the total warehouse-space requirement at time \(t\) due to the replenishment schedule \(X\). The objective is to determine a vector \(X^*=(x_1^*, x_2^*,...,x_N^*)\) so as to minimize the maximum warehouse-space requirement \(S_{\max}(X)=\max_t\{S_t(X)\}(0\leq t<\infty)\) . The mathematical model for the WRSPRS was formulated by \textit{N. N. Murthy, W. C. Benton} and \textit{P. A. Rubin} [Eur. J. Oper. Res. 150, No.2, 304--319 (2003; Zbl 1137.90320)] In the paper under consideration a new heuristic for solving the WRSPRS is proposed. The framework of this new heuristic is the following. At first the authors obtain an initial replenishment schedule by using an ``initial schedule procedure''. Then they conduct a local search to improve the best-on-hand solution. Two subroutines are used in this local search. The first routine has a feature, similar to the simulated annealing approach (see, for example, the paper by \textit{D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon} [Oper. Res. 37, No.6, 865--892 (1989; Zbl 0698.90065)]). Namely, in this routine the authors use a Boltzmann function to prevent the search being trapped in a local solution. The second routine reschedules a pair of randomly chosen products \(i\) and \(j\), and is used for further improvement. The computational experiments undertaken by the authors show that the proposed heuristic obtains solutions very close to the global optimum within a reasonable running time and significantly outperforms a heuristic by \textit{N. N. Murthy, W. C. Benton} and \textit{P. A. Rubin} [Eur. J. Oper. Res. 150, No. 2, 304--319 (2003; Zbl 1137.90320)].