A Novel exact algorithm for economic lot-sizing with piecewise linear production costs

2024/03/24 by Kleitos Papadopoulos, Papadopoulos, Kleitos
Business, Management and Accounting · #Supply Chain and Inventory Management

paper · pdf · doi:10.48550/arxiv.2403.16314

Abstract

In this paper, we study the single-item economic lot-sizing problem with production cost functions that are piecewise linear. The lot-sizing problem stands as a foundational cornerstone within the domain of lot-sizing problems. It is also applicable to a variety of important production planning problems which are special cases to it according to \citeou. The problem becomes intractable when m, the number of different breakpoints of the production-cost function is variable as the problem was proven NP-hard by \citeFlorian1980. For a fixed m an O(T^2m+3) time algorithm was given by \citeKoca2014 which was subsequently improved to O(T^m+2log(T)) time by \citeou where T is the number of periods in the planning horizon.\newline We introduce a more efficient O(T^m+2) time algorithm for this problem which improves upon the previous state-of-the-art algorithm by Ou and which is derived using several novel algorithmic techniques that may be of independent interest.

Related

• A global constraint for the capacitated single-item lot-sizing problem
• An O(nlog n) Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
• A physical model approach to order lot sizing
• A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme
• Lot sizing problem integrated with cutting stock problem in a paper industry: a multiobjective approach