大葉大學圖書館 |

Mixed integer programming approaches to lot-sizing and asset replacement problems.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
書名/作者:	Mixed integer programming approaches to lot-sizing and asset replacement problems.
作者:	Buyuktahtakin, I. Esra.
面頁冊數:	136 p.
附註:	Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7832.
Contained By:	Dissertation Abstracts International70-12B.
標題:	Engineering, Industrial.
標題:	Operations Research.
ISBN:	9781109516364
摘要、提要註:	In this dissertation, we develop mixed integer programming approaches for solving capacitated lot-sizing and parallel asset replacement problems. For capacitated lot-sizing, we analyze the use of dynamic programming in mixed integer programming frameworks. Specifically, this research aims to make contributions to the polyhedral characterization of the capacitated lot-sizing problem by defining a new set of valid inequalities derived from the end-of stage solutions of a dynamic programming algorithm. The end-of-stage solutions of the dynamic program provide valid bounds on the partial objective function values of the problem. We then define the stage value function according to the state values for a given level of inventory in a given stage and approximate it by its convex envelope. These inequalities can then be lifted by investigating potential state information at future stages. We test several possible implementations of these inequalities on randomly generated instances and demonstrate that our approach is more efficient than other integer programming based algorithms.
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3385908

Mixed integer programming approaches to lot-sizing and asset replacement problems.
Buyuktahtakin, I. Esra.

Mixed integer programming approaches to lot-sizing and asset replacement problems. - 136 p.

Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7832.

Thesis (Ph.D.)--University of Florida, 2009.

In this dissertation, we develop mixed integer programming approaches for solving capacitated lot-sizing and parallel asset replacement problems. For capacitated lot-sizing, we analyze the use of dynamic programming in mixed integer programming frameworks. Specifically, this research aims to make contributions to the polyhedral characterization of the capacitated lot-sizing problem by defining a new set of valid inequalities derived from the end-of stage solutions of a dynamic programming algorithm. The end-of-stage solutions of the dynamic program provide valid bounds on the partial objective function values of the problem. We then define the stage value function according to the state values for a given level of inventory in a given stage and approximate it by its convex envelope. These inequalities can then be lifted by investigating potential state information at future stages. We test several possible implementations of these inequalities on randomly generated instances and demonstrate that our approach is more efficient than other integer programming based algorithms.

ISBN: 9781109516364Subjects--Topical Terms:

423093
Engineering, Industrial.

Mixed integer programming approaches to lot-sizing and asset replacement problems.
LDR:05682nam 2200325 4500 001 345057
005 20110620110223.5
008 110817s2009 ||||||||||||||||| ||eng d
020 $a 9781109516364
035 $a (UMI)AAI3385908
035 $a AAI3385908
040 $a UMI $c UMI
100 1 $a Buyuktahtakin, I. Esra. $3 423515
245 1 0 $a Mixed integer programming approaches to lot-sizing and asset replacement problems.
300 $a 136 p.
500 $a Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7832.
500 $a Advisers: Joseph C. Hartman; J. Cole Smith.
502 $a Thesis (Ph.D.)--University of Florida, 2009.
520 $a In this dissertation, we develop mixed integer programming approaches for solving capacitated lot-sizing and parallel asset replacement problems. For capacitated lot-sizing, we analyze the use of dynamic programming in mixed integer programming frameworks. Specifically, this research aims to make contributions to the polyhedral characterization of the capacitated lot-sizing problem by defining a new set of valid inequalities derived from the end-of stage solutions of a dynamic programming algorithm. The end-of-stage solutions of the dynamic program provide valid bounds on the partial objective function values of the problem. We then define the stage value function according to the state values for a given level of inventory in a given stage and approximate it by its convex envelope. These inequalities can then be lifted by investigating potential state information at future stages. We test several possible implementations of these inequalities on randomly generated instances and demonstrate that our approach is more efficient than other integer programming based algorithms.
520 $a We also consider a generalization of the capacitated lot-sizing problem called the multi-item capacitated lot-sizing problem (MCLSP). We study a mixed integer programming model for solving the MCLSP, which incorporates shared capacity on the production of items for each period throughout a planning horizon. We derive valid bounds on the partial objective function of the MCLSP formulation by solving the first t periods of the problem over a subset of all items, using dynamic programming and integer programming techniques. We then develop algorithms for strengthening these valid inequalities by employing lifting and back-lifting procedures. These inequalities can be utilized in a cutting-plane strategy, in which we perturb the partial objective function coefficients to identify violated inequalities for the MCLSP polytope. We test the effectiveness of the proposed valid inequalities on randomly generated instances, and demonstrate that they are promising for solving MCLSP instances.
520 $a Our study of the parallel replacement problem is motivated by similar characteristics between the parallel replacement problem and lot-sizing problem. The parallel replacement problem under economies of scale (PRES) determines minimum cost replacement schedules for each individual asset in a group of assets that operate in parallel and are economically interdependent as a result of economies of scale. Economies of scale are due to the presence of the fixed charge in any period in which an asset is purchased. Both the parallel replacement and the lot-sizing problems have periodic demands that must be satisfied throughout the planning horizon. In the lot-sizing problem, production or purchases are made by trading off a fixed charge (set-up cost) against inventory holding and production/purchase costs. In the parallel replacement problem under economies of scale, additional fixed charges are incurred if assets are not replaced simultaneously. We prove that PRES is NP-hard. We then derive cutting plane approaches for the integer programming formulation of PRES. These cutting planes are motivated by the optimal replacement strategies implied by the no-splitting rule in the literature, which states that an optimal solution exists such that assets of the same age in the same time period are kept or replaced as a group. As a result of the no-splitting rule and constant demand, a purchase is enforced by a salvage in any optimal solution. We model PRES such that flow conservation constraints require a purchase whenever an asset is salvaged. We then use this property to generate inequalities for strengthening the PRES formulation. In addition, our inequalities have some similar characteristics with the flow cover inequalities derived for capacitated fixed charge networks. We present a set of experiments to illustrate the computational efficiency of the inequalities with respect to solving the mixed integer programs in a cut-and-branch framework.
520 $a We also study the integer programming formulation of the PRES under technological change and deterioration. We provide optimal solution characteristics and insights about the economics of the problem. We propose cutting planes for strengthening the problem formulation and effective solution algorithms based on these cutting planes for the PRES under technological change. Finally, we present some computational results to illustrate the effectiveness of the proposed methods. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html)
590 $a School code: 0070.
650 4 $a Engineering, Industrial. $3 423093
650 4 $a Operations Research. $3 423094
690 $a 0546
690 $a 0796
710 2 $a University of Florida. $3 423388
773 0 $t Dissertation Abstracts International $g 70-12B.
790 1 0 $a Hartman, Joseph C., $e advisor
790 1 0 $a Smith, J. Cole, $e advisor
790 $a 0070
791 $a Ph.D.
792 $a 2009
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3385908