Normal view MARC view

Production planning by mixed integer programming

Author: Pochet, Yves ; Wolsey, Laurence A. Series: Springer series in operations research and financial engineering Publisher: Springer, 2006.Language: EnglishDescription: 499 p. : Graphs ; 24 cm.ISBN: 0387299599Type of document: BookBibliography/Index: Includes bibliographical references and index
Tags: No tags from this library for this title. Log in to add tags.
Item type Current location Collection Call number Status Date due Barcode Item holds
Book Europe Campus
Main Collection
Print TS160 .P63 2006
(Browse shelf)
001213200
Available 001213200
Total holds: 0

Includes bibliographical references and index

Digitized

Production Planning by Mixed Integrer Programming Contents Part I Production Planning and MIP Introduction........................................................................................................ 3 1 The Modeling and Optimization Approach ................................................... 1.1 A Tiny Planning Model ........................................................................ 1.1.1 Problem Description .............................................................. 1.1.2 Some Solutions....................................................................... 1.1.3 A First Model ............................................................................ 1.1.4 Optimizing the Model............................................................... 1.2 A Production Planning Example ........................................................ 1.2.1 Problem Description .............................................................. 1.2.2 Modeling.................................................................................... 1.2.3 Mathematical Formulation..................................................... 1.2.4 Implementation ..................................................................... 1.2.5 Optimization Results ............................................................. Exercises .................................................................................................. Notes............................................................................................................. 2 Production Planning Models and Systems .................................................. 2.1 Some Production Planning Models..................................................... 2.2 The MRP Planning Model..................................................................... 2.2.1 The Planning Model and Its Inputs........................................ 2.2.2 The Planning Process: Single Item Decomposition ................ 2.2.3 Limitations of MRP and the Optimization Answer.................. 2.3 Advanced Planning Systems ............................................................. 2.3.1 Supply Chain Planning ......................................................... 2.3.2 Advanced Planning Systems and the Supply Chain Planning Matrix ................................................................... 2.4 Some Supply Chain Planning Problems ........................................... 2.4.1 Strategic Network Design Problems........................................ 7 9 9 10 11 15 16 16 21 25 26 30 33 36 39 41 46 47 55 62 66 66 68 71 71 2.4.2 Supply Chain Master Planning Problems............................. 72 Notes........................................................................................................... 74 3 Mixed Integer Programming Algorithms..................................................... 77 3.1 Mixed Integer Linear Programs ........................................................ 78 3.2 Running Time of Algorithms............................................................. 81 3.2.1 Performance of an Algorithm ................................................ 81 3.2.2 The Size of a Formulation ..................................................... 84 3.3 Branch-and-Bound Algorithm......................................................... 85 3.3.1 The Enumeration Principle .................................................. 85 3.3.2 The Branch-and-Bound Algorithm....................................... 88 3.3.3 Node Selection and Branching Rules ................................... 91 3.3.4 Solution Quality and Duality Gap ....................................... 92 3.4 Reformulation................................................................................... 93 3.4.1 The Quality of a Formulation ............................................... 93 3.4.2 Valid Inequalities.................................................................. 95 3.4.3 A Priori Reformulation........................................................... 97 3.4.4 A Priori and Extended Reformulation................................. 100 3.5 Branch-and-Cut Algorithm ........................................................... 101 3.5.1 Separation Algorithm .......................................................... 101 3.5.2 Cutting Plane Algorithm....................................................... 102 3.5.3 Branch-and-Cut Algorithm .................................................104 3.6 Primal Heuristics - Finding Feasible Solutions ............................. 107 3.6.1 Construction Heuristics ................................................... 108 3.6.2 Improvement Heuristics .................................................... 111 Notes.......................................................................................................... 113 4 Classification and Reformulation.............................................................. 115 4.1 Using Reformulations for Lot-Sizing Models................................... 117 4.1.1 Using A Priori Extended Reformulations ........................... 118 4.1.2 Using Cutting Planes .......................................................... 121 4.1.3 Using Approximate Reformulations .................................... 125 4.2 The Decomposition Approach for Complex Models ........................ 126 4.3 Model Classification ........................................................................ 128 4.3.1 Single-Item Classification..................................................... 129 4.3.2 Description of the Field PROB .................................................. 130 4.3.3 Description of the Field CAP....................................................... 130 4.3.4 Mathematical Formulations for PROB-CAP ............................ 131 4.3.5 Description of the Field VAR.......................................................... 134 4.3.6 Mathematical Formulations for PROB-CAP-VAR .................. 136 4.3.7 The Classification PROB-CAP-VAR............................................. 139 4.4 Reformulation Results: What and Where....................................... 140 4.4.1 Results for PROB-[U, CC] ............................................................. 141 4.4.2 Results for Backlogging Models PROB-[U, CC]-B.................... 142 4.4.3 Results for Start-Up Cost Models PROB-[U, CC]-SC ............ 142 4.4.4 The Reformulation Procedure..............................................143 4.5 A Production Planning Example: Reformulation and Solution .....145 Exercises .............................................................................................. 153 Notes.......................................................................................................... 153 5 Reformulations in Practice ....................................................................... 155 5.1 Extended Reformulations................................................................156 5.1.1 The Classical Approach for WW-U................................................156 5.1.2 The Black-Box Approach for WW-U ............................................ 157 5.1.3 The Classical Approach for LS-U ................................................. 159 5.1.4 The Black-Box Approach for LS-U ............................................... 160 5.2 Cut Separation............................................................................. 161 5.2.1 The Classical Approach for LS-U ................................................. 161 5.2.2 The Black-Box Approach for LS-U ............................................... 161 5.3 Heuristics in LS­LIB......................................................................... 162 5.3.1 Calling a Construction Heuristic ........................................ 162 5.3.2 Calling an Improvement Heuristic ...................................... 163 5.4 LS­LIB Procedures ........................................................................... 164 5.4.1 Reformulations ­ XForm ...................................................... 164 5.4.2 Cutting Plane Separation ­ XCut ....................................... 165 5.4.3 Heuristics ­ XHeur ..............................................................165 5.5 Two Practice Cases...........................................................................167 5.5.1 Consumer Goods Production Line: Problem Description .. 167 67 5.5.2 Cleaning Liquids Bottling Line: Problem Description . . . .....168 5.6 The Consumer Goods Production Line Case .................................169 5.6.1 Initial Classification ............................................................ 169 5.6.2 Initial Formulation ............................................................. 169 5.6.3 Reformulation and Algorithms ........................................... 170 5.6.4 Results............................................................................... 171 5.6.5 Sensitivity Analysis.............................................................. 172 5.7 The Cleaning Liquids Bottling Line Case ....................................... 173 5.7.1 Initial Classification ............................................................ 173 5.7.2 Initial Formulation ............................................................. 173 5.7.3 Reformulation and Algorithms ........................................... 174 5.7.4 Results............................................................................... 174 5.7.5 Sensitivity Analysis.............................................................. 175 5.7.6 Heuristics .......................................................................... 176 Exercises ............................................................................................... 177 Notes.......................................................................................................... 180 Part II Basic Polyhedral Combinatorics for Production Planning and MIP 6 Mixed Integer Programming Algorithms and Decomposition Approaches ...................................................................185 6.1 Polyhedra, Formulations, Optimization, and Separation .............. 186 6.1.1 Formulations of an Integer Program .................................. 186 6.1.2 Valid Inequality Representation of Polyhedra .....................187 6.1.3 Extreme Point Representation of Polyhedra........................189 6.1.4 Cutting Planes and the Separation Problem ...................... 190 6.1.5 Extended Formulations ......................................................191 6.1.6 Optimization and Separation: Polynomial Equivalence ..... 192 6.1.7 Optimization and Separation for Polynomially Solvable Problems............................................................... 193 6.2 Decomposition and Reformulation ................................................ 195 6.2.1 Decomposition of a Multi-Item Lot-Sizing Problem . . . ..... 196 6.3 Decomposition Algorithms...............................................................197 6.3.1 Decomposition Algorithms I: Valid Inequalities and Separation........................................................................ 197 6.3.2 Decomposition Algorithms II: Lagrangian Relaxation and Column Generation...................................................198 6.3.3 Decomposition Algorithms III: Hybrid Algorithms . . . ....... 201 6.4 Convex Hull Proofs........................................................................... 203 Exercises ............................................................................................... 204 Notes.......................................................................................................... 205 7 Single-Item Uncapacitated Lot-Sizing....................................................... 207 7.1 The Uncapacitated Lot-Sizing Problem (LS-U) .......................................207 7.2 Structure of Optimal Solutions of LS-U .................................................. 209 7.3 A Dynamic Programming Algorithm for LS-U ....................................... 212 7.4 Linear Programming Reformulations of LS-U ....................................... 217 7.4.1 Valid Inequalities for LS-U ............................................................. 217 7.4.2 Extended Formulations for LS-U...................................................221 7.5 Wagner-Whitin Costs...................................................................... 224 7.6 Partial Formulations ..................................................................... 226 7.7 Some Convex Hull Proofs................................................................. 228 Exercises ............................................................................................... 231 Notes.......................................................................................................... 233 8 Basic MIP and Fixed Cost Flow Models......................................................235 8.1 A Two-Variable Basic Mixed Integer Set ......................................... 237 8.1.1 Valid Inequalities and Formulations................................... 237 8.1.2 Optimal Solutions ...............................................................239 8.2 The MIP Set........................................................................................ 240 8.3 The Mixing Set ................................................................................. 241 8.3.1 Extreme Points ................................................................... 242 8.3.2 Valid Inequalities.................................................................242 8.3.3 Separation of the Mixing Inequalities .................................244 8.3.4 An Extended Formulation for conv(XkMIX)...................................... 245 8.3.5 Application of the Mixing Reformulation ............................ 247 8.4 Reformulation Approaches for More General Mixing Sets ............ 247 8.5 The Continuous Mixing Set............................................................ 249 8.6 Divisible Capacity Mixing Sets ........................................................ 253 8.6.1 The Two-Capacity Mixing Set .............................................. 253 8.6.2 The Divisible Mixing Set .......................................................253 8.7 The Continuous Integer Knapsack Set and the Gomory Mixed Integer Set ........................................................................... 255 8.8 The Continuous 0-1 Knapsack Set................................................257 8.9 The Binary Single-Node Flow Set ....................................................260 8.10 Some Convex Hull Proofs............................................................... 263 Exercises ............................................................................................... 264 Notes.......................................................................................................... 269 Part III Single-Item Lot-Sizing 9 Lot-Sizing with Capacities ........................................................................ 273 9.1 Complexity ........................................................................................274 9.2 Regeneration Intervals ................................................................... 274 9.3 Discrete Lot-Sizing with Constant Capacities ................................276 9.3.1 Valid Inequalities for DLS-CC.....................................................276 9.3.2 Optimization for DLS-CC ............................................................ 276 9.3.3 Parametric Optimization for DLS-CC........................................277 9.4 Discrete Lot-Sizing with Initial Stock and Constant Capacities ... 279 9.4.1 Valid Inequalities for DLSI-CC.................................................... 280 9.4.2 Extended Formulation for DLSI-CC ..........................................280 9.5 Lot-Sizing with Wagner­Whitin Costs and Constant Capacities....281 9.5.1 Optimization for WW-CC ............................................................. 281 9.5.2 Valid Inequalities for WW-CC..................................................... 283 9.5.3 Extended Formulations for WW-CC.......................................... 284 9.6 Lot-Sizing with Constant Capacities ............................................. 284 9.6.1 Optimization: An Algorithm for LS-CC..................................... 284 9.6.2 Valid Inequalities for LS-CC .......................................................287 9.6.3 Extended Formulation for LS-CC.............................................. 288 9.6.4 Resume of Results...............................................................289 9.7 Lot-Sizing with Varying Capacities ................................................. 290 9.7.1 Valid Inequalities for WW-C ...........................................................290 9.7.2 Simple Valid Inequalities for LS-C ........................................... 292 9.7.3 Submodular Inequalities for LS-C ............................................294 9.7.4 Lifted (1, S) Inequalities for DLSI-C............................................ 298 Exercises ............................................................................................... 300 Notes.......................................................................................................... 301 10 Backlogging and Start-Ups ....................................................................... 303 10.1 Backlogging .................................................................................... 304 10.2 Backlogging: The Uncapacitated Case.......................................... 304 10.2.1 Extreme Points and Optimization .................................... 304 10.2.2 Tight Formulations and Inequalities for LS-U-B ..................306 10.2.3 Tight Formulations and Inequalities for WW-U-B................. 308 10.3 Backlogging: The Constant Capacity Case................................... 311 10.3.1 Discrete Lot-Sizing with Backlogging DLS-CC-B .................311 10.3.2 Discrete Lot-Sizing with Initial Stocks and Backlogging DLSI-CC-B .............................................................315 10.3.3 Lot-Sizing with Wagner--Whitin Costs and Backlogging WW-CC-B .............................................................. 316 10.3.4 Lot-Sizing with Backlogging LS-CC-B.....................................318 10.3.5 Resume of Results............................................................. 319 10.4 Start-Up Costs: The Uncapacitated Case .................................... 319 10.4.1 A Dynamic Programming Algorithm for LS-U-SC . . . ........ 320 10.4.2 Tight Formulations and Inequalities for LS-U-SC ...............321 10.4.3 Wagner--Whitin Costs WW-U-SC............................................ 323 10.5 Start-Up Costs: The Capacitated Case ........................................ 323 10.5.1 The Discrete Lot-Sizing Problem DLS-CC-SC....................... 323 10.5.2 Capacitated Lot-Sizing with Start-Up Costs LS-C-SC ........326 10.5.3 Resume of Results............................................................. 329 10.6 Backlogging and Start-Ups WW-U-B, SC .......................................... 330 Exercises ............................................................................................... 331 Notes.......................................................................................................... 333 11 Single-Item Variants.................................................................................335 11.1 Sales or Variable Demand (SL) ................................................................. 336 11.1.1 The Uncapacitated Case: Sales and Arbitrary Demands . 337 11.1.2 The Uncapacitated Case: Sales and Nonnegative Demands.......................................................................... 338 11.2 Lower Bounds on Production (LB) ............................................................ 339 11.2.1 A Wagner--Whitin Relaxation WW-CC-LB ............................ 339 11.2.2 A Wagner--Whitin Relaxation with Backlogging WW-CC-B, LB................................................................................ 340 11.3 Lower Bounds on Production in a Set-Up Sequence ...................340 11.3.1 Almost Full Capacity Production (AFC)................................... 340 11.3.2 Minimum Production Level per Set-Up Sequence (MR) ..... 340 11.4 Restricted Length Set-Up Sequences (RLS)..........................................341 11.4.1 Varying Length Sequences................................................. 341 11.4.2 Constant Length Sequences..............................................342 11.5 Piecewise Concave Production Costs (CP)............................................344 11.6 Production Time Windows (TW P)........................................................... 345 11.6.1 An Algorithm for WW-U-TWP and Extended Formulation for WW-CC-TWP.................................................... 346 11.6.2 Indistinguishable Time Windows LS-C-TW P(I) and an Equivalent Problem....................................................... 348 11.6.3 A Dynamic Programming Algorithm for LS-U-TWP(I) 349 11.6.4 A Tight Extended Formulation for LS-U-TWP(I).....................350 11.7 Upper Bounds on Stocks (SUB)............................................................... 351 11.7.1 Equivalence to LS-CAP-TWP(I) ....................................................351 11.7.2 Valid Inequalities for LS-U-SUB............................................... 351 11.7.3 Valid Inequalities for WW-CC-SUB and WW-CC-B, SUB............................................................................ 352 11.8 Safety Stocks or Piecewise Convex Storage Costs (SS) .................. 353 11.8.1 Mixing Set Relaxations for LS-CC-SS.................................... 354 11.9 A Model with Backlogging, Sales Markets, and Concave Production Costs.......................................................................... 356 11.10 Stochastic Lot-Sizing on a Tree.................................................. 358 11.10.1 Mixing Set Relaxations with Constant Capacities ......... 359 11.10.2 Valid Inequalities for LS-CC-TREE....................................... 361 Exercises ............................................................................................... 361 Notes..........................................................................................................363 Part IV Multi-Item Lot-Sizing 12 Multi-Item Single-Level Problems ...........................................................369 12.1 Joint Resource Classification.......................................................371 12.1.1 Production Mode Classification ........................................ 371 12.1.2 Production Quantity Classification .................................. 372 12.2 Production Mode Models: One Set-Up ......................................... 374 12.2.1 Single Set-Up Constraint: M1. .......................................................................... 374 12.2.2 Start-Ups and Changeovers M1-{SC, SQ} ............................. 376 12.3 Production Modes: Two or More Set-Ups..................................... 378 12.3.1 Two Set-Ups: M2 .............................................................................379 12.3.2 Any Number of Set-Ups...................................................... 380 12.4 Production Quantity Constraints PQ ...............................................383 12.4.1 Product Resource Constraints PC and PC-SU .................... 383 12.5 Family Set-Ups: PC-FAM ........................................................................386 Exercises ............................................................................................... 388 Notes..........................................................................................................391 13 Multi-Level Lot-Sizing Problems............................................................... 395 13.1 Production in Series ML-S..........................................................................397 13.1.1 Optimization for ML-S/LS-U ................................................. 398 13.1.2 The Echelon Stock Reformulation for ML-S..........................400 13.1.3 Multi-Commodity Reformulations: Uncapacitated Case .402 13.1.4 Valid Inequalities for ML-S/LS-U..........................................403 13.1.5 Nested Solutions ............................................................. 405 13.2 Assembly Systems ....................................................................... 406 13.2.1 Nested Solutions ............................................................. 407 13.2.2 Lead-Times and Echelon Stocks ..................................... 407 13.3 General Systems ......................................................................... 409 13.4 Production and Distribution ...................................................... 411 13.4.1 Production Center and Sales Area Aggregation...............412 13.4.2 Sales Area Aggregation .....................................................414 Exercises ............................................................................................... 415 Notes.......................................................................................................... 416 Part V Problem Solving 14 Test Problems............................................................................................421 14.1 Making and Packing .................................................................... 422 14.1.1 Problem Description ........................................................ 422 14.1.2 Classification ................................................................... 426 14.1.3 Initial Formulation ......................................................... 427 14.1.4 Reformulations and Algorithms ...................................... 431 14.1.5 Analysis of Capacity and Customer Service Level............434 14.2 Storage Rack Production ............................................................. 436 14.2.1 Problem Description ........................................................ 436 14.2.2 Classification ................................................................... 439 14.2.3 Initial Formulation ......................................................... 440 14.2.4 Improving the Initial Formulation .................................. 443 14.2.5 Choosing the Appropriate Extended Reformulations . . . 444 14.2.6 Results with Extended Reformulations .......................... 445 14.2.7 Results with Primal Heuristics .......................................446 14.3 Insulating Board Extrusion ....................................................... 448 14.3.1 Problem Description ........................................................ 448 14.3.2 Classification ................................................................... 451 14.3.3 Initial Formulation ......................................................... 452 14.3.4 Improving the Initial Formulation .................................. 455 14.3.5 Results with Reformulations ...........................................459 14.3.6 The Multi-Period Planning and Scheduling Extension ... 460 14.4 Pigment Sequencing .................................................................... 466 14.4.1 Initial Formulation ......................................................... 466 14.4.2 Classification ................................................................... 466 14.4.3 Reformulations.................................................................. 467 14.4.4 Computational Results with Reformulations ................... 467 14.4.5 Modeling Periods with No Production ............................... 468 14.5 Process Manufacturing ............................................................... 470 14.5.1 Classification .....................................................................470 14.5.2 Initial Formulation ...........................................................471 14.5.3 Reformulation ................................................................... 472 14.5.4 Computational Results..................................................... 473 14.6 Powder Production .......................................................................473 14.6.1 Classification .....................................................................474 14.6.2 Initial Formulation ...........................................................474 14.6.3 Testing the Initial Formulation and Reformulations ........475 14.6.4 Finding Lower Bounds for Powder Production .................477 14.6.5 Finding Upper Bounds for Powder Production ................ 477 Exercises ............................................................................................... 478 Making and Packing ..................................................................... 478 Storage Rack Production ............................................................. 479 Insulating Board Extrusion .........................................................479 Process Manufacturing ................................................................480 Notes.......................................................................................................... 480 References...................................................................................................... 483 Index...................................................................................................................493

There are no comments for this item.

Log in to your account to post a comment.
Koha 18.11 - INSEAD Catalogue
Home | Contact Us | What's Koha?