An asymptotically optimum approach to some group formation problems: Parallel machine and order point scheduling

This paper poses the NP-hard stones problem, which is to allocate a number of stones of bounded weights, to heaps, when the objective is to equalize, as near as possible, the heap weights. To address this problem, the stones heuristic is presented. A bound is developed for the range of heap weights from the heuristic, which implies asymptotic optimality. Levels of approximation for finite problems are also developed. The heuristic may be used in general to allocate items to groups in a way that minimizes the range of some item-dependent characteristic of the groups. To demonstrate the heuristic it is applied to some parallel machine scheduling problems, and then, in the context of large scale warehouse management, it is applied to the order point scheduling problem in discrete time.