A hybrid polynomial-time algorithm for the dynamic quantity discount lot size model with resale

We propose an efficient optimal algorithm for determining the lot sizes for purchase component in Material Requirement Planning (MRP) environments with deterministic time-phased demand and zero lead time. In this model, backlog is not permitted, the unit purchasing price is based on the all-units discount system with single price break point and resale of the excess units is acceptable at the ordering time. The problem is divided into the sub-plans with specific properties by the dynamic programming (DP) method already presented. By modifying the main structure of the DP method, we present a branch-and-bound algorithm to obtain the optimal ordering policy for each sub-plans. Furthermore, we prove some useful fathoming rules to make the branch-and-bound algorithm very efficient. It has also been shown that the worst-case time complexity function of the presented algorithm is O(N(4)) where N is the number of periods in the planning horizon. Finally, we show the efficiency of the presented algorithm and its fathoming rules by solving some test problems which are randomly generated in various environments. (C) 2011 Elsevier Ltd. All rights reserved.