Files in this item



application/pdf9411791.pdf (8MB)Restricted to U of Illinois
(no description provided)PDF


Title:Uncapacitated Lot-Sizing Problems With Setup Interactions
Author(s):Stowers, Curtis Louis
Doctoral Committee Chair(s):Palekar, Udatta
Department / Program:Mechanical and Industrial Engineering
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:1993
Description:189 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
Other Identifier(s):(UMI)AAI9411791
Date Available in IDEALS:2014-12-17
Date Deposited:1993

This item appears in the following Collection(s)

Item Statistics