Set partitioning and column generation heuristics for capacitated dynamic lotsizing
Some new algorithms to solve the multi-item single-level lotsizing problem with a single capacity constraint are presented. The problem can be stated as \((1)\quad \min \sum^{N}_{i=1}\sum^{T}_{t=1}s_ iY_{it}+h_ iI_{it}\quad \quad (CLSP)(2)\quad s.t.\quad I_{it- 1}+x_{it}-I_{it}=d_{it}\text{ for all } i,t,(3)\quad \sum^{N}_{i=1}a_ ix_{it}\leq C_ t\text{ for all } t,(4)\quad x_{it}\leq (\sum^{T}_{m=t}d_{it})Y_{it}\text{ for all } i,t,(5)\quad x_{it},\quad I_{it}\geq 0\text{ for all } i,t,(6)\quad Y_{it}\in \{0,1\}\text{ for all } i,t,\)where \(x_{it}\), \(Y_{it}\) are variables denoting production quantities, setups and inventories respectively, \(d_{it}\) denotes demand, \(s_ i\) and \(h_ i\) are the setup and holding cost, \(a_ i\) the capacity available in period t. The objective of the model is to minimize total setup and holding cost (1), without backlogs (2), and without violating the capacity constraint in any one period (3). Constraints (4) enforce a setup for item i in any period with positive production for that item. Most previous research efforts reported in the literature use the single item uncapacitated problem solutions as candidate plans. A different approach is proposed in which candidate plans are also generated by some well-known multi-item capacitated dynamic lotsizing heuristics. The LP relaxation of a set partitioning model is solved and rounded to obtain an integer solution. A number of heuristics are subsequently applied to improve upon this initial solution. Heuristics are also used to convert the possibly fractional solution from the column generation step to a feasible integer one. Computational experience shows that these methods perform best for problems with fewer periods than items, but are quite good on average.
- A Dual Ascent and Column Generation Heuristic for the Discrete Lotsizing and Scheduling Problem with Setup Times
- A column generation heuristic for a dynamic generalized assignment problem
- A combined heuristic approach to dynamic lot sizing problems
- Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
- Efficient heuristics for dynamic lot sizing
- An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
- Dynamic knapsack sets and capacitated lot-sizing
- Searching for optimal integer solutions to set partitioning problems using column generation
- A set partitioning heuristic for the generalized assignment problem
- A heuristic procedure for the capacitated lot sizing problem with setup carry-over
- A cyclical scheduling heuristic for lot sizing with capacity constraints
- A simple heuristic for the multi-item single level capacitated lotsizing problem
- An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
- An Efficient Algorithm for Multi-Item Scheduling
- Deterministic Production Planning: Algorithms and Complexity
- Dynamic version of the economic lot size model
- Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
- Strong Formulations for Multi-Item Capacitated Lot Sizing
- Lot sizing and scheduling -- survey and extensions
- Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions
- A new heuristic approach for the multi-item dynamic lot sizing problem
- Reformulations of the shortest route model for dynamic multi-item multi-level capacitated lotsizing
- Progress with single-item lot-sizing
- Parameter controlled instance generation for lot sizing problems
- An exact column-generation approach for the lot-type design problem
- A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing
- HOPS -- Hamming-Oriented Partition Search for production planning in the spinning industry
- Dynamic capacitated lot-sizing problems: a classification and review of solution approaches
- Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company
- Single item lot sizing problems
- Self-adaptive randomized constructive heuristics for the multi-item capacitated lot sizing problem
- All-integer column generation for set partitioning: basic principles and extensions
- Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems
- Hybrid methods for lot sizing on parallel machines
- Multi-Item Single-Level Capacitated Dynamic Lot-Sizing Heuristics: A General Review
- A Dual Ascent and Column Generation Heuristic for the Discrete Lotsizing and Scheduling Problem with Setup Times
- scientific article; zbMATH DE number 1342809 (Why is no real title available?)
- scientific article; zbMATH DE number 1560348 (Why is no real title available?)
- A primal-dual algorithm for the dynamic lotsizing problem with joint set-up costs
- Analytics branching and selection for the capacitated multi-item lot sizing problem with nonidentical machines
- A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs
- Multilevel capacitated lotsizing complexity and LP-based heuristics
- Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches
This page was built for publication: Set partitioning and column generation heuristics for capacitated dynamic lotsizing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922926)
