Standard

A benders decomposition based heuristic for the hierarchical production planning problem. / Aardal, Karen; Larsson, Torbjörn.

In: European Journal of Operational Research, Vol. 45, No. 1, 1990, p. 4-14.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Aardal, Karen ; Larsson, Torbjörn. / A benders decomposition based heuristic for the hierarchical production planning problem. In: European Journal of Operational Research. 1990 ; Vol. 45, No. 1. pp. 4-14.

BibTeX

@article{2374346f60f149c8bb859c4eab1cec18,
title = "A benders decomposition based heuristic for the hierarchical production planning problem",
abstract = "In this paper a heuristic procedure for determining good feasible solutions to a multi-item dynamic production planning problem is described and evaluated. The problem, which is modelled as a mixed-integer linear program, has a hierarchical structure where production items are aggregated into families, and families into product types.A decomposition of the original problem creates a trivial subproblem providing feasible solutions on the type level, and a master problem which separates into one uncapacitated lot-sizing problem for each family. The latter problems can be solved by dynamic programming with very little computational effort. Besides the nice structure of both the sub- and master problem, the dual information from the subproblem can be given interesting economic interpretations. As distinguished from Hax and Meal's hierarchical framework for production planning and also they hybrid approach suggested by Graves in 1982, there exists a direct information flow from the family level problem to the type level problem in form of a production plan.The heuristic is essentially an application of Benders decomposition, the only difference being that the Benders cuts are relaxed using Lagrangean multipliers. A subgradient procedure is used to update the Lagrangean multipliers. One iteration of this heuristic requires less computational effort compared to Grave's algorithm. This is due to the fact that the Benders subproblem can be solved by inspection, while Graves' algorithm involves solving an LP-problem on the type level. For thirtysix medium-size test problems the average deviation from optimum is 2.34%, and the deviation ranges between 0.00% and 5.95%.",
keywords = "Hierarchical production planning, Benders decomposition, Lagrangean relaxation, subgradient optimization",
author = "Karen Aardal and Torbj{\"o}rn Larsson",
year = "1990",
doi = "10.1016/0377-2217(90)90151-Z",
language = "English",
volume = "45",
pages = "4--14",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

RIS

TY - JOUR

T1 - A benders decomposition based heuristic for the hierarchical production planning problem

AU - Aardal, Karen

AU - Larsson, Torbjörn

PY - 1990

Y1 - 1990

N2 - In this paper a heuristic procedure for determining good feasible solutions to a multi-item dynamic production planning problem is described and evaluated. The problem, which is modelled as a mixed-integer linear program, has a hierarchical structure where production items are aggregated into families, and families into product types.A decomposition of the original problem creates a trivial subproblem providing feasible solutions on the type level, and a master problem which separates into one uncapacitated lot-sizing problem for each family. The latter problems can be solved by dynamic programming with very little computational effort. Besides the nice structure of both the sub- and master problem, the dual information from the subproblem can be given interesting economic interpretations. As distinguished from Hax and Meal's hierarchical framework for production planning and also they hybrid approach suggested by Graves in 1982, there exists a direct information flow from the family level problem to the type level problem in form of a production plan.The heuristic is essentially an application of Benders decomposition, the only difference being that the Benders cuts are relaxed using Lagrangean multipliers. A subgradient procedure is used to update the Lagrangean multipliers. One iteration of this heuristic requires less computational effort compared to Grave's algorithm. This is due to the fact that the Benders subproblem can be solved by inspection, while Graves' algorithm involves solving an LP-problem on the type level. For thirtysix medium-size test problems the average deviation from optimum is 2.34%, and the deviation ranges between 0.00% and 5.95%.

AB - In this paper a heuristic procedure for determining good feasible solutions to a multi-item dynamic production planning problem is described and evaluated. The problem, which is modelled as a mixed-integer linear program, has a hierarchical structure where production items are aggregated into families, and families into product types.A decomposition of the original problem creates a trivial subproblem providing feasible solutions on the type level, and a master problem which separates into one uncapacitated lot-sizing problem for each family. The latter problems can be solved by dynamic programming with very little computational effort. Besides the nice structure of both the sub- and master problem, the dual information from the subproblem can be given interesting economic interpretations. As distinguished from Hax and Meal's hierarchical framework for production planning and also they hybrid approach suggested by Graves in 1982, there exists a direct information flow from the family level problem to the type level problem in form of a production plan.The heuristic is essentially an application of Benders decomposition, the only difference being that the Benders cuts are relaxed using Lagrangean multipliers. A subgradient procedure is used to update the Lagrangean multipliers. One iteration of this heuristic requires less computational effort compared to Grave's algorithm. This is due to the fact that the Benders subproblem can be solved by inspection, while Graves' algorithm involves solving an LP-problem on the type level. For thirtysix medium-size test problems the average deviation from optimum is 2.34%, and the deviation ranges between 0.00% and 5.95%.

KW - Hierarchical production planning

KW - Benders decomposition

KW - Lagrangean relaxation

KW - subgradient optimization

U2 - 10.1016/0377-2217(90)90151-Z

DO - 10.1016/0377-2217(90)90151-Z

M3 - Article

VL - 45

SP - 4

EP - 14

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -

ID: 47550987