Parallelized decomposition approaches for capacitated lot-sizing problems: application to the problem with constraints on ending inventories.
Saved in:
| Title: | Parallelized decomposition approaches for capacitated lot-sizing problems: application to the problem with constraints on ending inventories. |
|---|---|
| Authors: | Charles, Mehdi1,2 (AUTHOR) charles.mehdi@hotmail.com, Dauzère-Pérès, Stéphane1,3 (AUTHOR), Kedad-Sidhoum, Safia4 (AUTHOR), Mazhoud, Issam2 (AUTHOR) |
| Source: | International Journal of Production Research. Dec2025, Vol. 63 Issue 23, p9009-9029. 21p. |
| Subjects: | Decomposition method, Heuristic, Simulation methods & models, Production scheduling, Parallel algorithms, Dynamic programming, Inventory control, Relaxation methods (Mathematics) |
| Abstract: | This paper introduces an original parallelisation framework to design a new relax-and-fix heuristic, using strategies that do not rely on the classical chronological order, for capacitated lot-sizing problems. These decomposition approaches, never considered in the literature, are applied to solve a multi-item lot-sizing problem with constraints on ending inventories, setup times and lost sales. Another decomposition approach, a Lagrangian relaxation heuristic, is also proposed and parallelised. Moreover, to solve the relaxed problem in the Lagrangian relaxation heuristic, a polynomial dynamic programming algorithm is derived for an uncapacitated version of the single-item lot-sizing problem with ending inventory constraints. Computational experiments are conducted to analyze the efficiency of the different approaches, in particular of the new relax-and-fix strategies, and compare them to a linear programming standard solver. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 189849845 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Parallelized decomposition approaches for capacitated lot-sizing problems: application to the problem with constraints on ending inventories. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Charles%2C+Mehdi%22">Charles, Mehdi</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> charles.mehdi@hotmail.com</i><br /><searchLink fieldCode="AR" term="%22Dauzère-Pérès%2C+Stéphane%22">Dauzère-Pérès, Stéphane</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Kedad-Sidhoum%2C+Safia%22">Kedad-Sidhoum, Safia</searchLink><relatesTo>4</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Mazhoud%2C+Issam%22">Mazhoud, Issam</searchLink><relatesTo>2</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Production+Research%22">International Journal of Production Research</searchLink>. Dec2025, Vol. 63 Issue 23, p9009-9029. 21p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Decomposition+method%22">Decomposition method</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Simulation+methods+%26+models%22">Simulation methods & models</searchLink><br /><searchLink fieldCode="DE" term="%22Production+scheduling%22">Production scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+algorithms%22">Parallel algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Inventory+control%22">Inventory control</searchLink><br /><searchLink fieldCode="DE" term="%22Relaxation+methods+%28Mathematics%29%22">Relaxation methods (Mathematics)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: This paper introduces an original parallelisation framework to design a new relax-and-fix heuristic, using strategies that do not rely on the classical chronological order, for capacitated lot-sizing problems. These decomposition approaches, never considered in the literature, are applied to solve a multi-item lot-sizing problem with constraints on ending inventories, setup times and lost sales. Another decomposition approach, a Lagrangian relaxation heuristic, is also proposed and parallelised. Moreover, to solve the relaxed problem in the Lagrangian relaxation heuristic, a polynomial dynamic programming algorithm is derived for an uncapacitated version of the single-item lot-sizing problem with ending inventory constraints. Computational experiments are conducted to analyze the efficiency of the different approaches, in particular of the new relax-and-fix strategies, and compare them to a linear programming standard solver. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189849845 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1080/00207543.2025.2532140 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 9009 Subjects: – SubjectFull: Decomposition method Type: general – SubjectFull: Heuristic Type: general – SubjectFull: Simulation methods & models Type: general – SubjectFull: Production scheduling Type: general – SubjectFull: Parallel algorithms Type: general – SubjectFull: Dynamic programming Type: general – SubjectFull: Inventory control Type: general – SubjectFull: Relaxation methods (Mathematics) Type: general Titles: – TitleFull: Parallelized decomposition approaches for capacitated lot-sizing problems: application to the problem with constraints on ending inventories. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Charles, Mehdi – PersonEntity: Name: NameFull: Dauzère-Pérès, Stéphane – PersonEntity: Name: NameFull: Kedad-Sidhoum, Safia – PersonEntity: Name: NameFull: Mazhoud, Issam IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00207543 Numbering: – Type: volume Value: 63 – Type: issue Value: 23 Titles: – TitleFull: International Journal of Production Research Type: main |
| ResultId | 1 |
