An efficient optimal algorithm for the quantity discount problem in material requirement planning

An optimal algorithm based on branch-and-bound approach is presented in this paper to determine lot sizes for a single item in material requirement planning environments with deterministic time-phased demand and constant ordering cost with zero lead time, where all-units discounts are available from vendors and backlog is not permitted. On the basis of the proven properties of optimal order policy, a tree-search procedure is presented to construct the sequence of optimal orders. Some useful fathom rules have been proven, which make the algorithm very efficient. To compare the performance of this algorithm with the other existing optimal algorithms, an experimental design with various environments has been developed. Experimental results show that the performance of our optimal algorithm is much better than the performance of other existing optimal algorithms. Considering computational time as the performance measure, this algorithm is considered the best among the existing optimal algorithms for real problems with large dimensions (i.e. large number of periods and discount levels).