Dissertation/Thesis Abstract

A Novel Solution Approach to Capacitated Lot-Sizing Problems with Setup Times and Setup Carry-Over
by Karagul, Hakan Fatih, Ph.D., North Carolina State University, 2012, 155; 3538539
Abstract (Summary)

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.

Indexing (document details)
Advisor: Hodgson, Thom J., Warsing, Donald P.
Commitee: King, Russell E., Uzsoy, Reha
School: North Carolina State University
Department: Industrial Engineering
School Location: United States -- North Carolina
Source: DAI-B 74/07(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Management, Industrial engineering, Operations research
Keywords: Capacitated lot-sizing, Mixed integer programming, Production planning, Setup carry-Over, Setup times
Publication Number: 3538539
ISBN: 978-1-303-01564-9
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest