An O(T super 3) algorithm for the economic lot-sizing problem with constant capacities
Article Abstract:
A dynamic programming algorithm was developed for solving the economic lot-sizing problem with constant capacities, linear holding costs and concave production costs in O(T super 3) time. Because the O(T super 3) algorithm was based on the standard dynamic programming approach, the minimum costs for all possible subplans of the production plan had to be estimated. Computation of these costs was not done in a straightforward manner, but applied the structural properties of optimal subplans for improved implementation. The algorithm proved to be superior to Florian and Klein's (1971) O(T super 4) algorithm for G/G/G/C by a factor of T. Findings reveal that the economic lot-sizing problem with constant capacities in O(T super 3) time can be solved when the production costs are concave and the holding costs are linear.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1996
User Contributions:
Comment about this article or add new information about this topic:
A lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem
Article Abstract:
A study was conducted to develop a lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem (GMAP). The problem included generalized assignment problems as a special case. A lagrangian dual ascent algorithm was developed for GMAP which promoted a number of advantages that can be combined to create a novel lagrangian dual search algorithm called Subgradient search with Embedded Dual Ascent for GMAP. An optimal multiplier adjustment technique was utilized by the dual ascent algorithm for GMAP. Results indicated the efficiency and robustness of the branch-and-bound algorithm for GMAPs and complex generalized assignment problems. However, the dual ascent search was not effective in lower bounding schemes for large and complex generalized assignment problems.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1998
User Contributions:
Comment about this article or add new information about this topic:
A min cost flow solution for dynamic assignment problems in networks with storage devices
Article Abstract:
A generalization of the classical mininum-cost flow problem is proposed to address the optimal allocation problems of material or goods. An optimal flow assignment approach for networks with storage devices is considered. The networks are comprised of arcs that link different types of nodes, including diversions, storage devices, junctions, and source and link. The original minimum-cost flow problem is restructured with respect to network flow theory. New arcs are included to achieve three objectives: to reflect the temporal dimension of the problem in addition to its natural spatial dimension, to take into account piecewise linear utility functions, and to find a solution to the overall problem using a revised version of the Busacker-Gowen minimum-cost flow algorithm.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1995
User Contributions:
Comment about this article or add new information about this topic:
- Abstracts: Stories from the front-line: how they construct the organization. Breaking silence: tactical choices women managers make in speaking up about gender-equity issues
- Abstracts: Not sure you want to continue paying on that life insurance policy?
- Abstracts: Supplementary reports. Economic indicators
- Abstracts: An examination of competing versions of the person-environment fit approach to stress. Changing identities in a changing workplace: Identification, identity enactment, self-verification, and telecommuting
- Abstracts: A comparative study on the structural relationships of manufacturing practices, lead time and productivity in Japan and Korea