In this study we propose a novel mixed integer linear programming (MILP) formulation to solve capacitated lot-sizing problems (CLSP) with setup times and setup carry over. We compare our novel formulation to two formulations in the literature by solving single- and multiple-machine instances with and without holding costs. We refer to one of these original formulations as the ¢wclassical formulation,¡ü and we call the other, which is modified from the classical formulation, the ¢wmodified formulation.¡ü Extensive computational tests show that our novel formulation consistently outperforms both the classical formulation and the modified formulation in terms of the computation time required to achieve an optimal or near-optimal solution and the resulting solution gap, which measures the difference between the best upper bound and the best lower bound in the branch and bound tree used to solve these mixed-integer-programming formulations. Our experiments also show that the modified formulation is superior to the classical formulation in terms of gap and computation time performance. We demonstrate that the main difference between the classical formulation and the modified formulation comes from the structure of their respective branch and bound trees. We also demonstrate that the LP relaxation of our novel formulation provides a tighter lower bound as compared to the modified formulation. For problems in which production lots must be allocated across m ≥ 2 parallel machines, the branch and bound solution process unfortunately results in larger upper bound-lower bound gaps, but the novel formulation continues to perform better than the classical and modified formulations. The solution to a relaxed, single-machine formulation of the parallel-machine problem that is based on our novel formulation, however, leads to a substantially tighter lower bound than those generated by the branch and bound solutions, and we use this to demonstrate that our time-restricted MIP solutions are actually quite good in terms of the upper bound (incumbent solution). This relaxed formulation also leads directly to a heuristic approach that can solve the parallel-machine problem in less than one minute, on average. This heuristic solves the problems in our experiments to within 1.4% of the single-machine formulation bound, on average, although the heuristic solution for some instances reflects a gap of 5% or higher.
|Advisor:||Hodgson, Thom J., Warsing, Donald P.|
|Commitee:||King, Russell E., Uzsoy, Reha|
|School:||North Carolina State University|
|School Location:||United States -- North Carolina|
|Source:||DAI-B 74/07(E), Dissertation Abstracts International|
|Subjects:||Management, Industrial engineering, Operations research|
|Keywords:||Capacitated lot-sizing, Mixed integer programming, Production planning, Setup carry-Over, Setup times|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be