Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms

Buchbinder, Niv; Kimbrel, Tracy; Levi, Retsef; Makarychev, Konstantin; Sviridenko, Maxim
July 2013
Operations Research;Jul/Aug2013, Vol. 61 Issue 4, p1014
Academic Journal
In this paper, we study an online make-to-order variant of the classical joint replenishment problem (JRP) that has been studied extensively over the years and plays a fundamental role in broader planning issues, such as the management of supply chains. In contrast to the traditional approaches of the stochastic inventory theory, we study the problem using competitive analysis against a worst-case adversary. Our main result is a 3-competitive deterministic algorithm for the online version of the JRP. We also prove a lower bound of approximately 2.64 on the competitiveness of any deterministic online algorithm for the problem. Our algorithm is based on a novel primal-dual approach using a new linear programming relaxation of the offline JRP model. The primal-dual approach that we propose departs from previous primal-dual and online algorithms in rather significant ways. We believe that this approach can extend the range of problems to which online and primal-dual algorithms can be applied and analyzed.


Related Articles

  • Deterministic and Metaheuristic Solutions for Closed-loop Supply Chains with Continuous Price Decrease. Kamali, H. R.; Sadegheih, A.; Vahdat-Zad, M. A.; Khademi-Zare, H. // International Journal of Engineering (1025-2495);Dec2014, Vol. 27 Issue 12, p1905 

    In a global economy, an efficient supply chain as the main core competency empowers enterprises to provide products or services at a right time in a right quantity, and at a low cost. This paper is to plan a single-product, multi-echelon, multi-period closed-loop supply chain for high-tech...

  • Approximating Sparse Covering Integer Programs Online. Gupta, Anupam; Nagarajan, Viswanath // Mathematics of Operations Research;Nov2014, Vol. 39 Issue 4, p998 

    A covering integer program (CIP) is a mathematical program of the form min{cT x | Ax ≥ 1, 0 ≤ x ≤ u, x ∈ Zn}, where all entries in A, c, u are nonnegative. In the online setting, the constraints (i.e., the rows of the constraint matrix A) arrive over time, and the...

  • Online pricing for bundles of multiple items. Zhang, Yong; Chin, Francis; Ting, Hing-Fung // Journal of Global Optimization;Feb2014, Vol. 58 Issue 2, p377 

    Given a seller with $$k$$ types of items, $$m$$ of each, a sequence of users $$\{u_1, u_2,\ldots \}$$ arrive one by one. Each user is single-minded, i.e., each user is interested only in a particular bundle of items. The seller must set the price and assign some amount of bundles to each user...

  • A fuzzy goal programming approach to solve multi-objective supply chain network design problems. Kanani Nezhad, Amir Abbas; Roghanian, Emad; Azadi, Zahra // International Journal of Industrial Engineering Computations;Summer2013, Vol. 4 Issue 3, p315 

    The design of supply chain (SC) networks has attracted more attention in recent years according to business and environmental factors.in this paper a multi objective supply chain network design model aims to minimize network costs while satisfying the desired service level, is presented. A fuzzy...

  • Distributed Search Algorithm for Supplier Selection. FU Li-kun; QIAO Pei-li; ZHU Li-feng // Journal of Harbin University of Science & Technology;Aug2014, Vol. 19 Issue 4, p107 

    Specific to the fuzzy constraints of product procurement, this study establishes a linear programming model. Maximizing value of the procurement is treated as the objective function and the vendor of suppliers is the most optimal variable decision. Employing distributed search algorithm to solve...

  • A Deterministic Algorithm for Generating Optimal Three-Stage layouts of Homogenous Strip Pieces. Jun Ji; Fei-Fei Xing; Jun Du; Ning Shi; Yao-Dong Cui // Journal of Industrial Engineering & Management;2014, Vol. 7 Issue 5, p1167 

    Purpose: The time required by the algorithms for general layouts to solve the large-scale two-dimensional cutting problems may become unaffordable. So this paper presents an exact algorithm to solve above problems. Design/methodology/approach: The algorithm uses the dynamic programming algorithm...

  • ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Misener, Ruth; Floudas, Christodoulos // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p503 

    This manuscript introduces ANTIGONE, Algorithms for coNTinuous/Integer Global Optimization of Nonlinear Equations, a general mixed-integer nonlinear global optimization framework. ANTIGONE is the evolution of the Global Mixed-Integer Quadratic Optimizer, GloMIQO, to general nonconvex terms. The...

  • A Deterministic Global Optimization Algorithm. Hongwei Jiao; Lin Wang; Jianping Wang // Information Technology Journal;2013, Vol. 12 Issue 22, p6986 

    In this study, a deterministic global optimization algorithm is proposed for globally solving the Nonconvex Quadratic Programming (NQP). In this algorithm, by using the characteristic of the NQP, a new linearization approach is presented. By utilizing the approach, the linear programming...

  • The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. Kronqvist, Jan; Lundell, Andreas; Westerlund, Tapio // Journal of Global Optimization;Feb2016, Vol. 64 Issue 2, p249 

    A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics