Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Supply Chains and Production Planning . . . . . . . . . . . . . . . . . . 1
1.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Components of Supply Chain Management . . . . . . . . . . . . . . . . 4
1.4 Scope of this Book. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Optimization Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Variables, Data, Subscripts, and Math . . . . . . . . . . . . . . 9
2.2.2 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Objective Functions and Constraints . . . . . . . . . . . . . . . 11
2.3 Finding Solutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 A Few Words About Uncertainty . . . . . . . . . . . . . . . . . . . 15
2.3.3 Solvers and Model Structure . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Implementing the Models in this Book . . . . . . . . . . . . . . . . . . . . 17
3. Starting with an mrp Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 mrp Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 mrp Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 mrp Optimization Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.5 Discussion of mrp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5.1 Troubles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.2 Virtues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4. Extending to an MRP II Model . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 MRP II Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 MRP II Data and Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Discussion of MRP II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Changeover Modeling Considerations . . . . . . . . . . . . . . . . . . . . . 38
4.4.1 A Straightforward Modification . . . . . . . . . . . . . . . . . . . . 38
4.4.2 Production that Spans Time Buckets . . . . . . . . . . . . . . . 39
4.4.3 Parallel Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4.4 Sequence Dependent Changeovers . . . . . . . . . . . . . . . . . . 41
4.4.5 A Few Remarks About Changeovers . . . . . . . . . . . . . . . . 42
5. A Better Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1 A Cost Based Objective Function. . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.1 Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.2 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Overtime and Extra Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.1 A Simple Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.2 Complications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.3 Allowing Tardiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.1 A Simple Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3.2 Complications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4 Objective Function Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.5 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6. Extensions to the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1 Substitutes, Multiple Routings and Subcontractors . . . . . . . . . 59
6.2 Penalizing Changes to the Plan . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3 End-of-horizon Effects and Minimum Inventories . . . . . . . . . . . 64
6.4 Modeling Product Movement and Transport . . . . . . . . . . . . . . . 66
6.4.1 Simple Product Movement and Shipping . . . . . . . . . . . . 67
6.4.2 Expedited Shipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4.3 Fixed Costs and Consolidations . . . . . . . . . . . . . . . . . . . . 67
6.4.4 Transportation Discounts . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4.5 Discussion of Transportation Modeling . . . . . . . . . . . . . 70
6.5 Summarizing the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.6 Aggregation and Consolidation . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.6.1 Consolidating Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.6.2 Aggregating Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.6.3 Discussion of Disaggregation . . . . . . . . . . . . . . . . . . . . . . . 79
7. Implementation Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.1 AMPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.1.1 mrp Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.1.2 mrp Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.1.3 Results of Running mrp . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.1.4 MRPII Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.5 Data for MRPII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.1.6 SCPc Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1.7 Data for SCPc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.2 GAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.2.1 mrp and MRPII Models . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2.2 SCPc Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.3 Maximal MPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3.1 mrp Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.3.2 MRPII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.3.3 SCPc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.4 OPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.4.1 mrp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.4.2 MRPII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.4.3 SCPc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.5 Xpress-Mosel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.5.1 mrp Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.5.2 mrp Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.5.3 mrp Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.5.4 MRPII Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.5.5 SCPc Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8. Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.1 MIPs and Relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.2 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
8.3 Special Variable Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.3.1 Semi-continuous Variables . . . . . . . . . . . . . . . . . . . . . . . . 141
8.3.2 General Integer Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 142
8.3.3 Special Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.4 Heuristic Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.4.1 A Brief Primer on Heuristics . . . . . . . . . . . . . . . . . . . . . . . 146
8.4.2 Abstract Formulation and Solution Representation . . . 147
8.4.3 Example of an Embedded Problem . . . . . . . . . . . . . . . . . 149
8.4.4 Neighborhoods and Evaluation Functions . . . . . . . . . . . . 150
8.4.5 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.4.6 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.4.7 Genetic and Evolutionary Algorithms . . . . . . . . . . . . . . . 157
8.5 Constraint Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
9. Some Stochastic Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9.1 Lead Times and Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.1.1 The Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.1.2 Load Dependent Lead Times. . . . . . . . . . . . . . . . . . . . . . . 167
9.1.3 Solver Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9.1.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.1.5 Complications and Discussion . . . . . . . . . . . . . . . . . . . . . . 173
9.2 Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.2.1 The Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.2.2 A Multi-stage Probabilistic Model With Recourse . . . . 178
9.2.3 Progressive Hedging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9.2.4 A PH based Heuristic for SCPc . . . . . . . . . . . . . . . . . . . 184
10. Research Directions and References . . . . . . . . . . . . . . . . . . . . . . 187
10.1 Supply Chain Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
10.1.1 The Evolution of Logistics . . . . . . . . . . . . . . . . . . . . . . . . . 188
10.1.2 Closed Loop Supply Chains and Reverse Logistics . . . . 191
10.1.3 The Importance of Information Technology . . . . . . . . . . 191
10.1.4 Supply Contracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
10.2 mrp, MRP II and Beyond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
10.2.1 The Early Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
10.2.2 Supply Chain Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10.3 Production Planning and Scheduling . . . . . . . . . . . . . . . . . . . . . . 202
10.3.1 Lot Sizing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
10.3.2 Planning and Inventory Control . . . . . . . . . . . . . . . . . . . . 208
10.3.3 Machine Scheduling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.3.4 Aggregation and Part Families . . . . . . . . . . . . . . . . . . . . . 212
10.3.5 Load Dependent Lead Times . . . . . . . . . . . . . . . . . . . . . . 214
10.4 Transportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
10.5 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.5.1 Exact Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
10.5.2 Heuristic Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . 225
10.5.3 Progressive Hedging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
10.5.4 Simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10.6 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253