A Unifying Approximate Dynamic Programming Model for the Economic Lot Scheduling Problem

• 成果类型: Article
• 署名作者: Adelman, Daniel; Barz, Christiane
• 署名单位: University of Chicago; University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0607
• 发表日期: 2014
• 页码: 374-402
• 关键词: optimality equation; average optimality; feasibility; sizes; elsp

摘要

We formulate the well-known economic lot scheduling problem (ELSP) with sequence-dependent setup times and costs as a semi-Markov decision process. Using an affine approximation of the bias function, we obtain a semi-infinite linear program determining a lower bound for the minimum average cost rate. Under a very mild condition, we can reduce this problem to a relatively small convex quadratically constrained linear problem by exploiting the structure of the objective function and the state space. This problem is equivalent to the lower bound problem derived by Dobson [Dobson G (1992) The cyclic lot scheduling problem with sequence-dependent setups. Oper. Res. 40:736-749] and reduces to the well-known lower bound problem introduced in Bomberger [Bomberger EE (1966) A dynamic programming approach to a lot size scheduling problem. Management Sci. 12: 778-784] for sequence-dependent setups. We thus provide a framework that unifies previous work, and opens new paths for future research on tighter lower bounds and dynamic heuristics.