دانلود کتاب Production Planning by Mixed Integer Programming

This textbook provides a comprehensive modeling, reformulation and optimization approach for solving production planning and supply chain planning problems, covering topics from a basic introduction to planning systems, mixed integer programming (MIP) models and algorithms through the advanced description of mathematical results in polyhedral combinatorics required to solve these problems. Based on twenty years worth of research in which the authors have played a significant role, the book addresses real life industrial production planning problems (involving complex production structures with multiple production stages) using MIP modeling and reformulation approach. The book provides an introduction to MIP modeling and to planning systems, a unique collection of reformulation results, and an easy to use problem-solving library. This approach is demonstrated through a series of real life case studies, exercises and detailed illustrations. Review by Jakub Marecek (Computer Journal) The emphasis put on mixed integer rounding and mixing sets, heuristics in-built in general purpose integer programming solvers, as well as on decompositions and heuristics using integer programming should be praised... There is no doubt that this volume offers the present best introduction to integer programming formulations of lotsizing problems, encountered in production planning. (2007)Table of ContentsCoverProduction Planning by Mixed Integer ProgrammingISBN-10: 0387299599 ISBN-13: 9780387299594PrefaceCase Studies and Web SiteContentsPart I Production Planning and MIP Introduction 1 The Modeling and Optimization Approach 1.1 A Tiny Planning Model o 1.1.1 Problem Description o 1.1.2 Some Solutions o 1.1.3 A First Model o 1.1.4 Optimizing the Model 1.2 A Production Planning Example o 1.2.1 Problem Description GW and the Global Supply Chain Department o 1.2.2 Modeling o 1.2.3 Mathematical Formulation o 1.2.4 Implementation o 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 o 2.2.1 The Planning Model and Its Inputs o 2.2.2 The Planning Process: Single Item Decomposition o 2.2.3 Limitations of MRP and the Optimization Answer 2.3 Advanced Planning Systems o 2.3.1 Supply Chain Planning o 2.3.2 Advanced Planning Systems and the Supply Chain Planning Matrix 2.4 Some Supply Chain Planning Problems o 2.4.1 Strategic Network Design Problems o 2.4.2 Supply Chain Master Planning Problems Notes 3 Mixed Integer Programming Algorithms 3.1 Mixed Integer Linear Programs 3.2 Running Time of Algorithms o 3.2.1 Performance of an Algorithm o 3.2.2 The Size of a Formulation 3.3 Branch-and-Bound Algorithm o 3.3.1 The Enumeration Principle o 3.3.2 The Branch-and-Bound Algorithm o 3.3.3 Node Selection and Branching Rules o 3.3.4 Solution Quality and Duality Gap 3.4 Reformulation o 3.4.1 The Quality of a Formulation Good and Bad Formulations o 3.4.2 Valid Inequalities o 3.4.3 A Priori Reformulation o 3.4.4 A Priori and Extended Reformulation 3.5 Branch-and-Cut Algorithm o 3.5.1 Separation Algorithm o 3.5.2 Cutting Plane Algorithm o 3.5.3 Branch-and-Cut Algorithm 3.6 Primal Heuristics - Finding Feasible Solutions o 3.6.1 Construction Heuristics o 3.6.2 Improvement Heuristics Notes 4 Classi.cation and Reformulation Motivation Objective Contents 4.1 Using Reformulations for Lot-Sizing Models o 4.1.1 Using A Priori Extended Reformulations o 4.1.2 Using Cutting Planes o 4.1.3 Using Approximate Reformulations 4.2 The Decomposition Approach for Complex Models 4.3 Model Classi.cation o 4.3.1 Single-Item Classi.cation o 4.3.2 Description of the Field PROB o 4.3.3 Description of the Field CAP o 4.3.4 Mathematical Formulations for PROB-CAP o 4.3.5 Description of the Field VAR o 4.3.6 Mathematical Formulations for PROB-CAP-VAR Backlogging o 4.3.7 The Classi.cation PROB-CAP-VAR 4.4 Reformulation Results: What and Where o 4.4.1 Results for PROB-[U, CC] o 4.4.2 Results for Backlogging Models PROB-[U, CC]-B o 4.4.3 Results for Start-Up Cost Models PROB-[U, CC]-SC o 4.4.4 The Reformulation Procedure 4.5 A Production Planning Example: Reformulation and Solution Exercises Notes 5 Reformulations in Practice Motivation Objectives Content 5.1 Extended Reformulations o 5.1.1 The Classical Approach for WW-U o 5.1.2 The Black-Box Approach for WW-U o 5.1.3 The Classical Approach for LS-U o 5.1.4 The Black-Box Approach for LS-U 5.2 Cut Separation o 5.2.1 The Classical Approach for LS-U o 5.2.2 The Black-Box Approach for LS-U 5.3 Heuristics in LS-LIB o 5.3.1 Calling a Construction Heuristic o 5.3.2 Calling an Improvement Heuristic 5.4 LS-LIB Procedures o 5.4.1 Reformulations - XForm o 5.4.2 Cutting Plane Separation - XCut o 5.4.3 Heuristics - XHeur 5.5 Two Practice Cases o 5.5.1 Consumer Goods Production Line: Problem Description o 5.5.2 Cleaning Liquids Bottling Line: Problem Description 5.6 The Consumer Goods Production Line Case o 5.6.1 Initial Classi.cation o 5.6.2 Initial Formulation o 5.6.3 Reformulation and Algorithms o 5.6.4 Results o 5.6.5 Sensitivity Analysis 5.7 The Cleaning Liquids Bottling Line Case o 5.7.1 Initial Classi.cation o 5.7.2 Initial Formulation o 5.7.3 Reformulation and Algorithms o 5.7.4 Results o 5.7.5 Sensitivity Analysis o 5.7.6 Heuristics Exercises NotesPart II Basic Polyhedral Combinatorics for Production Planning and MIP 6 Mixed Integer Programming Algorithms and Decomposition Approaches 6.1 Polyhedra, Formulations, Optimization, and Separation o 6.1.1 Formulations of an Integer Program De.nition 6.2 The set of points P = x o 6.1.2 Valid Inequality Representation of Polyhedra o 6.1.3 Extreme Point Representation of Polyhedra o 6.1.4 Cutting Planes and the Separation Problem o 6.1.5 Extended Formulations o 6.1.6 Optimization and Separation: Polynomial Equivalence o 6.1.7 Optimization and Separation for Polynomially Solvable Problems 6.2 Decomposition and Reformulation o 6.2.1 Decomposition of a Multi-Item Lot-Sizing Problem 6.3 Decomposition Algorithms o 6.3.1 Decomposition Algorithms I: Valid Inequalities and Separation o 6.3.2 Decomposition Algorithms II: Lagrangian Relaxation and Column Generation o 6.3.3 Decomposition Algorithms III: Hybrid Algorithms 6.4 Convex Hull Proofs Exercises Notes 7 Single-Item Uncapacitated Lot-Sizing 7.1 The Uncapacitated Lot-Sizing Problem (LS-U) 7.2 Structure of Optimal Solutions of LS-U 7.3 A Dynamic Programming Algorithm for LS-U 7.4 Linear Programming Reformulations of LS-U o 7.4.1 Valid Inequalities for LS-U o 7.4.2 Extended Formulations for LS-U 7.5 Wagner-Whitin Costs 7.6 Partial Formulations 7.7 Some Convex Hull Proofs Exercises Notes 8 Basic MIP and Fixed Cost Flow Models 8.1 A Two-Variable Basic Mixed Integer Set o 8.1.1 Valid Inequalities and Formulations Proposition 8.1 i. Let f = b -b=0. The simple mixed integer rounding o 8.1.2 Optimal Solutions 8.2 The MIP Set 8.3 The Mixing Set o 8.3.1 Extreme Points Proposition 8.3 The extreme rays of conv(X MIX o 8.3.2 Valid Inequalities o 8.3.3 Separation of the Mixing Inequalities o 8.3.4 An Extended Formulation for conv(X MIX o 8.3.5 Application of the Mixing Reformulation 8.4 Reformulation Approaches for More General Mixing Sets 8.5 The Continuous Mixing Set 8.6 Divisible Capacity Mixing Sets o 8.6.1 The Two-Capacity Mixing Set o 8.6.2 The Divisible Mixing Set 8.7 The Continuous Integer Knapsack Set and the Gomory Mixed Integer Set 8.8 The Continuous 0-1 Knapsack Set 8.9 The Binary Single-Node Flow Set 8.10 Some Convex Hull Proofs Exercises NotesPart III Single-Item Lot-Sizing 9 Lot-Sizing with Capacities 9.1 Complexity 9.2 Regeneration Intervals 9.3 Discrete Lot-Sizing with Constant Capacities o 9.3.1 Valid Inequalities for DLS-CC o 9.3.2 Optimization for DLS-CC o 9.3.3 Parametric Optimization for DLS-CC 9.4 Discrete Lot-Sizing with Initial Stock and Constant Capacities o 9.4.1 Valid Inequalities for DLSI-CC o 9.4.2 Extended Formulation for DLSI-CC 9.5 Lot-Sizing with Wagner-Whitin Costs and Constant Capacities o 9.5.1 Optimization for WW-CC o 9.5.2 Valid Inequalities for WW-CC o 9.5.3 Extended Formulations for WW-CC 9.6 Lot-Sizing with Constant Capacities o 9.6.1 Optimization: An Algorithm for LS-CC o 9.6.2 Valid Inequalities for LS-CC o 9.6.3 Extended Formulation for LS-CC o 9.6.4 R�esum�e of Results 9.7 Lot-Sizing with Varying Capacities o 9.7.1 Valid Inequalities for WW-C o 9.7.2 Simple Valid Inequalities for LS-C o 9.7.3 Submodular Inequalities for LS-C o 9.7.4 Lifted (l, S) Inequalities for DLSI-C Valid Inequalities for DLSI-C Exercises Notes 10 Backlogging and Start-Ups 10.1 Backlogging 10.2 Backlogging: The Uncapacitated Case o 10.2.1 Extreme Points and Optimization o 10.2.2 Tight Formulations and Inequalities for LS-U-B Valid inequalities o 10.2.3 Tight Formulations and Inequalities for WW-U-B 10.3 Backlogging: The Constant Capacity Case o 10.3.1 Discrete Lot-Sizing with Backlogging DLS-CC-B o 10.3.2 Discrete Lot-Sizing with Initial Stocks and Backlogging o 10.3.3 Lot-Sizing with Wagner-Whitin Costs and Backlogging o 10.3.4 Lot-Sizing with Backlogging LS-CC-B The Optimization Problem o 10.3.5 R�esum�e of Results 10.4 Start-Up Costs: The Uncapacitated Case o 10.4.1 A Dynamic Programming Algorithm for LS-U-SC o 10.4.2 Tight Formulations and Inequalities for LS-U-SC Valid Inequalities and Convex Hull of X LS-U-SC 10.5 Start-Up Costs: The Capacitated Case o 10.5.1 The Discrete Lot-Sizing Problem DLS-CC-SC o 10.5.2 Capacitated Lot-Sizing with Start-Up Costs LS-C-SC Valid Inequalities o 10.5.3 R�esum�e of Results 10.6 Backlogging and Start-Ups WW-U-B, SC Exercises Notes 11 Single-Item Variants 11.1 Sales or Variable Demand (SL) o 11.1.1 The Uncapacitated Case: Sales and Arbitrary Demands o 11.1.2 The Uncapacitated Case: Sales and Nonnegative Demands 11.2 Lower Bounds on Production (LB) o 11.2.1 A Wagner-Whitin Relaxation WW-CC-LB o 11.2.2 A Wagner-Whitin Relaxation with Backlogging 11.3 Lower Bounds on Production in a Set-Up Sequence o 11.3.1 Almost Full Capacity Production (AF C) o 11.3.2 Minimum Production Level per Set-Up Sequence (MR) 11.4 Restricted Length Set-Up Sequences (RLS) o 11.4.1 Varying Length Sequences o 11.4.2 Constant Length Sequences 11.5 Piecewise Concave Production Costs (CP) 11.6 Production Time Windows (TWP) o 11.6.1 An Algorithm for WW-U-TWP and Extended Formulation for WW-CC-TWP o 11.6.2 Indistinguishable Time Windows LS-C-TWP(I)andan Equivalent Problem o 11.6.3 A Dynamic Programming Algorithm for LS-U-TWP(I) o 11.6.4 A Tight Extended Formulation for LS-U-TWP(I) 11.7 Upper Bounds on Stocks (SUB) o 11.7.1 Equivalence to LS-CAP-TWP(I) o 11.7.2 Valid Inequalities for LS-U-SUB o 11.7.3 Valid Inequalities for WW-CC-SUB and WW-CC-B, SUB 11.8 Safety Stocks or Piecewise Convex Storage Costs (SS) o 11.8.1 Mixing Set Relaxations for LS-CC-SS 11.9 A Model with Backlogging, Sales Markets, and Concave Production Costs 11.10 Stochastic Lot-Sizing on a Tree o 11.10.1 Mixing Set Relaxations with Constant Capacities o 11.10.2 Valid Inequalities for LS-CC-TREE Exercises NotesPart IV Multi-Item Lot-Sizing 12 Multi-Item Single-Level Problems 12.1 Joint Resource Classi.cation o 12.1.1 Production Mode Classi.cation o 12.1.2 Production Quantity Classi.cation 12.2 Production Mode Models: One Set-Up o 12.2.1 Single Set-Up Constraint: M1 o 12.2.2 Start-Ups and Changeovers M1-{SC, SQ} 12.3 Production Modes: Two or More Set-Ups o 12.3.1 Two Set-Ups: M2 o 12.3.2 Any Number of Set-Ups 12.4 Production Quantity Constraints PQ o 12.4.1 Product Resource Constraints PC and PC-SU 12.5 Family Set-Ups: PC-FAM Exercises Notes 13 Multi-Level Lot-Sizing Problems 13.1 Production in Series ML-S o 13.1.1 Optimization for ML-S/LS-U o 13.1.2 The Echelon Stock Reformulation for ML-S o 13.1.3 Multi-Commodity Reformulations: Uncapacitated Case o 13.1.4 Valid Inequalities for ML-S/LS-U o 13.1.5 Nested Solutions 13.2 Assembly Systems o 13.2.1 Nested Solutions o 13.2.2 Lead-Times and Echelon Stocks 13.3 General Systems 13.4 Production and Distribution o 13.4.1 Production Center and Sales Area Aggregation o 13.4.2 Sales Area Aggregation Exercises NotesPart V Problem Solving 14 Test Problems 14.1 Making and Packing o 14.1.1 Problem Description General Context o 14.1.2 Classi.cation o 14.1.3 Initial Formulation o 14.1.4 Reformulations and Algorithms o 14.1.5 Analysis of Capacity and Customer Service Level 14.2 Storage Rack Production o 14.2.1 Problem Description General Context o 14.2.2 Classi.cation o 14.2.3 Initial Formulation o 14.2.4 Improving the Initial Formulation o 14.2.5 Choosing the Appropriate Extended Reformulations o 14.2.6 Results with Extended Reformulations o 14.2.7 Results with Primal Heuristics 14.3 Insulating Board Extrusion o 14.3.1 Problem Description General Context o 14.3.2 Classi.cation o 14.3.3 Initial Formulation o 14.3.4 Improving the Initial Formulation o 14.3.5 Results with Reformulations o 14.3.6 The Multi-Period Planning and Scheduling Extension 14.4 Pigment Sequencing o 14.4.1 Initial Formulation o 14.4.2 Classi.cation o 14.4.3 Reformulations Reformulation of the Changeover Variables o 14.4.4 Computational Results with Reformulations o 14.4.5 Modeling Periods with No Production 14.5 Process Manufacturing o 14.5.1 Classi.cation o 14.5.2 Initial Formulation o 14.5.3 Reformulation o 14.5.4 Computational Results 14.6 Powder Production o 14.6.1 Classi.cation o 14.6.2 Initial Formulation o 14.6.3 Testing the Initial Formulation and Reformulations o 14.6.4 Finding Lower Bounds for Powder Production o 14.6.5 Finding Upper Bounds for Powder Production Exercises NotesReferencesIndex