{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72551"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72551","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Uncapacitated Lot-Sizing Problems With Setup Interactions","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Stowers, Curtis Louis"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Palekar, Udatta"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T23:21:08Z","date_published":"2014-12-17T23:21:08Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Engineering, Industrial","Operations Research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9411791"],"render_values":[{"text":"(UMI)AAI9411791","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72551","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Palekar, Udatta"]},{"key":"dc:creator","label":"Author","values":["Stowers, Curtis Louis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T23:21:08Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Industrial","Operations Research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72551","(UMI)AAI9411791"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-17T23:21:08Z (GMT). No. of bitstreams: 1 9411791.pdf: 7687933 bytes, checksum: 26ba0aee1046d3b8b74630ccdb9d85e4 (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72719 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","189 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."]},{"key":"dc:title","label":"Title","values":["Uncapacitated Lot-Sizing Problems With Setup Interactions"]}]}],"canonical_facts":{"dc:contributor":["Palekar, Udatta"],"dc:creator":["Stowers, Curtis Louis"],"dc:date":["2014-12-17T23:21:08Z","10000-01-01","1993"],"dc:description":["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.","Made available in DSpace on 2014-12-17T23:21:08Z (GMT). No. of bitstreams: 1 9411791.pdf: 7687933 bytes, checksum: 26ba0aee1046d3b8b74630ccdb9d85e4 (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72719 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","189 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."],"dc:identifier":["http://hdl.handle.net/2142/72551","(UMI)AAI9411791"],"dc:subject":["Engineering, Industrial","Operations Research"],"dc:title":["Uncapacitated Lot-Sizing Problems With Setup Interactions"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}