|M.Sc Student||Cohen Tamar|
|Subject||Complexity Results for Periodic Decision Problems|
|Department||Department of Industrial Engineering and Management||Supervisor||Dr. Liron Yedidsion|
|Full Thesis text|
Many inventory models are aimed at minimizing ordering and holding costs while satisfying demand. The Joint Replenishment Problem (JRP) deals with the prospect of saving resources through coordinated replenishments in order to achieve substantial cost savings. In the JRP it is required to schedule the replenishment times of numerous commodities in order to supply a constant demand per commodity. Each commodity incurs fixed ordering costs every time it is replenished and linear holding costs proportional to the amount of the commodity held in storage. Linking all commodities, a joint ordering cost is incurred whenever one or more commodities are ordered. The objective of JRP is to minimize the sum of ordering and holding costs. It is a natural extension of the classical economic lot-sizing model that considers the optimal trade-off between ordering costs and holding costs for a single commodity. With multiple commodities, JRP adds the possibility of saving resources via coordinated replenishments, a common phenomenon in supply chain management. In this research we answer a long-standing open question regarding the computational complexity the periodic JRP. This problem received a lot of attention over the years and many heuristic and approximation algorithms were suggested. However, in spite of the vast effort, the complexity of the problem remained unresolved. In this paper, we provide a proof that the problem is indeed strongly NP-hard.