Uncapacitated Lot-Sizing Problems With Setup Interactions
Stowers, Curtis Louis
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/72551
Description
Title
Uncapacitated Lot-Sizing Problems With Setup Interactions
Author(s)
Stowers, Curtis Louis
Issue Date
1993
Doctoral Committee Chair(s)
Palekar, Udatta
Department of Study
Mechanical and Industrial Engineering
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Industrial
Operations Research
Abstract
Lot-sizing problems focus on determining a minimal total production cost schedule. These production costs are generally composed of three components: a variable production cost, an inventory holding cost, and a setup cost. The optimal solution balances the holding costs against the setup and variable costs. In most of the research in this area, product interaction is incorporated by considering the products to be in competition for fixed production capacities. However, there exist problems in which distinct products are more closely coupled.
This dissertation focuses on the effect of setup interactions on the uncapacitated lot-sizing problem (ULSP) with time varying demand patterns. We consider three major instances of setup interactions in the ULSP: the Joint Replenishment Problem (JRP), the Weak Interaction Problem (WIP), and the Strong Interaction Problem (SIP). For each of the problems computational complexity boundaries are established. The general instance of all three problems is shown to be NP-Complete. Membership in this computationally intractable class of problems, necessitates the development of strong bounding techniques and effective branching rules which can be incorporated into an exact solution procedure. Each problem is formulated as a linear integer program. Different formulations are presented which exploit various properties of the problems. Relationships between the formulations and the problems are demonstrated.
A dual ascent procedure is developed for the JRP. The procedure exploits the structure of a Lagrangean dual of the problem. Efficient schemes are employed to solve the resulting sub-problems and to determine ascent directions. Branching rules and penalties based on the problem structure are incorporated into an exact numerical procedure. Testing indicates that these bounds can be used to obtain up to a tenfold improvement in performance over a well-known commercial solver (IBM/OSL). For the WIP, bounding procedures and heuristics are presented which yield near optimal solutions with minimal computational effort. Finally, bounding schemes based on a Lagrangean decomposition that result in a WIP are presented for the SIP. This new bounding technique is incorporated into an enumerative solution procedure which reduces the computational effort required to solve the SIP by 50 to 95 percent.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
