Formulations and valid inequalities for Economic Lot Sizing Problems with Remanufacturing (ELSR)

  • Sharifah Aishah Binti Syed Ali

Student thesis: Doctoral Thesis


Nowadays, many manufacturers are beginning to establish remanufacturing facilities due to the stricter government regulations on end-of-life product treatment, and the increasing public awareness towards environmental issues. Remanufacturing offers a huge potential for employment, and provides profitable business opportunities. However, production planning activities are more complex for remanufacturing,as they incorporate greater uncertainties and greater risk associated with product returns and demands. These activities become even more intricate in hybrid remanufacturing and manufacturing systems. For this reason, we have investigated two variants of production planning of the hybrid remanufacturing and manufacturing systems, they are: i) Economic Lot Sizing Problem with Remanufacturing and Separate Setups (ELSRs) and ii) Economic Lot Sizing Problem with Remanufacturing and Joint Setups (ELSRj).In each period, the demands can be fulfilled by either remanufactured, or new products, or both. These problems have been proven to be N P-hard in general.Therefore, we study different approaches to tackle these problems.First, we propose several traditional methodologies to obtain better lowerf bounds for both problems, namely (ℓ, S) - like inequalities and reformulation techniques, such as facility location (FL) reformulation, multi-commodity (MC) reformulation, and shortest path (SP) reformulation. Both theoretical and computational comparisons of different lower bounding techniques are discussed. The results show that the reformulation techniques demonstrate better performance than other formulations for the separate setups case when the setup cost for remanufacturing is equivalent to the setup cost for manufacturing. For the joint setups case, our (ℓ; S) - like inequalities, which have the same lower bounds as the reformulation techniques, are the most efficient methods to quickly solve the problem.Motivated by the previous chapter, we further investigate the polyhedral structure of a simpler mixed integer set, arising from the feasible set of ELSRs and ELSRj problems, in order to derive several existing and new valid inequalities.These mixed integer sets are variants of the well-known single node fixed-charge network set, where two knapsack sets are considered simultaneously. Our main contributions for these problems rely upon on identifying the facet-defining conditions of the proposed inequalities, and discussing their separation problems. For each problem, comparisons of computational experiments between different traditional methodologies introduced earlier, and the proposed inequalities, are presented to test their effectiveness. The results indicate that the valid inequalities, with embedded (ℓ; S) - like inequalities for the separate setups case, have significantly improved the lower bounds in almost (all) instances tested, compared with other formulations when the setup cost for remanufacturing is, at most, the setup cost for manufacturing. As regards to the joint setups case, the results show that (ℓ; S) -like inequalities remain provide stronger lower bounds than the proposed inequalities for those randomly generated instances.
Date of Award12 Oct 2016
Original languageEnglish
Awarding Institution
  • University Of Strathclyde
SupervisorKerem Akartunali (Supervisor) & Robert van der Meer (Supervisor)

Cite this