Optimization Online


Lot Sizing with Piecewise Concave Production Costs

Esra Koca(ekoca***at***bilkent.edu.tr)
Hande Yaman(hyaman***at***bilkent.edu.tr)
M. Selim Akturk(akturk***at***bilkent.edu.tr)

Abstract: We study the lot-sizing problem with piecewise concave production costs and concave holding costs. This problem is a generalization of the lot-sizing problem with quantity discounts, minimum order quantities, capacities, overloading, subcontracting or a combination of these. We develop a dynamic programming (DP) algorithm to solve this problem and answer an open question in the literature: we show that the problem is polynomially solvable when the breakpoints of the production cost function are time invariant and the number of breakpoints is fixed. For the special cases with capacities and subcontracting, the time complexity of our DP algorithm is as good as the complexity of algorithms available in the literature. We report the results of a computational experiment where the DP is able to solve instances that are hard for a mixed-integer programming (MIP) solver. We enhance the MIP formulation with valid inequalities based on mixing sets and use a cut-and-branch algorithm to compute better bounds. We propose a state space reduction based heuristic algorithm for large instances and show that the solutions are of good quality by comparing them with the bounds obtained from the cut-and-branch.

Keywords: lot sizing; piecewise concave production cost; quantity discounts; subcontracting; dynamic programming

Category 1: Other Topics (Dynamic Programming )

Citation: Technical Report, Department of Industrial Engineering, Bilkent University, Bilkent 06800, Ankara, Turkey, February 2013.

Download: [PDF]

Entry Submitted: 02/14/2013
Entry Accepted: 02/20/2013
Entry Last Modified: 02/14/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society