A polynomial time algorithm to the economic lot sizing problem with constant capacity and piecewise linear concave costs
| Autor: | Jinwen Ou |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
021103 operations research Applied Mathematics 0211 other engineering and technologies ComputerApplications_COMPUTERSINOTHERSYSTEMS 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research Range minimum query Data structure 01 natural sciences Inventory cost Industrial and Manufacturing Engineering Economic lot sizing Piecewise linear function Dynamic programming 010201 computation theory & mathematics Constant (mathematics) Algorithm Time complexity Computer Science::Databases Software Mathematics |
| Zdroj: | Operations Research Letters. 45:493-497 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/j.orl.2017.07.010 |
| Popis: | It is well-known that the classical economic lot-sizing problem with constant capacity and general concave ordering/inventory cost functions can be solved in O ( T 4 ) time (Florian and Klein, 1971). We show that the problem can be solved in O ( m T 3 ) time when the ordering cost functions are piecewise linear concave and have m line segments with different slopes in a time period in average. Our algorithm makes use of the data structure of range minimum query (RMQ). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect