The capacitated multi-item lot sizing problem is a model which aims at scheduling production of several products over a finite number of periods, while minimizing production costs, holding inventory costs and setup costs subject to demand and capacity constraints. These costs may vary for each product and each period and are all linear. Our model includes setup times for each product. / We compare two approaches: a classic Lagrangean relaxation of the capacity constraints and a Lagrangean decomposition by variable splitting. In both cases, the Lagrangean multipliers are updated with an interior point cutting plane technique. The results show: (1) The superiority of the interior point method over the commonly used subgradient optimization in terms of accuracy at termination, number of iterations and ease of utilization. (2) The better quality of the bounds obtained by the Lagrangean decomposition by variable splitting over the Lagrangean relaxation.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.23429 |
| Date | January 1995 |
| Creators | Trouiller, Cyril |
| Contributors | Avis, D. (advisor), Goffin, J. L. (advisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 001486224, proquestno: MM12283, Theses scanned by UMI/ProQuest. |
Page generated in 0.0021 seconds