en Optimal design Optimal design پژوهشي Research <font size="2">The purpose of this paper is to present a polynomial time algorithm which determines the lot sizes for purchase component in Material Requirement Planning (MRP) environments with deterministic time-phased demand with zero lead time. In this model, backlog is not permitted, the unit purchasing price is based on the all-units discount system and resale of the excess units is possible at the ordering time. The properties of an optimal order policy are argued and on the basis of them, a branch and bound algorithm is presented to construct an optimal sequence of order policies. In the proposed B&B algorithm, some useful fathoming rules have been proven to make the algorithm very efficient. By defining a rooted tree graph, it has been shown that the worst-case time complexity function of the presented algorithm is polynomial. Finally, some test problems which are randomly generated in various environments are solved to show the efficiency of the algorithm. </font> branch and bound; purchasing; all-units discount; resale; complexity theory; graph theory 183 202 http://ijoce.iust.ac.ir/browse.php?a_code=A-10-1-61&slc_lang=en&sid=1 S.H. Mirmohammadi 18003194753284600298 18003194753284600298 Yes Sh. Shadrokh 18003194753284600299 18003194753284600299 No K. Eshghi 18003194753284600300 18003194753284600300 No