Consider the problem of minimizing the maximum storage requirement resulting from the once-per-cycle replenishment of several items. Demand is assumed to be known and constant, and no backlogging is permitted. By contrast with previous models, replenishment may take place only atkdiscrete points in time. We prove that this problem is binaryNP-hard for fixedk. Consequently, a natural heuristic based on the rounding of optimal continuous time solutions is described. This heuristic provides a worst case performance ratio of 1 +C/k/k, whereCis a numerical constant, and 1/2 C 2. A heuristic borrowed from multiprocessor scheduling provides a worst case performance ratio of 2. Extensive computational testing indicates that the solutions delivered by the heuristics are, on average, very close to optimal in value.
展开▼
