Linked e-resources
Details
Table of Contents
Preface; Contents; List of Algorithms; List of Figures; List of Tables; Abbreviations; 1 Introduction; References; 2 The Capacitated Planned Maintenance Problem; 2.1 Problem Definition and Motivation; 2.2 Known Maintenance Problems; 2.2.1 Periodic Maintenance; 2.2.2 Machine Scheduling with Periodic Maintenance; 2.2.3 Periodic Maintenance Inspection; 2.2.4 Aircraft Maintenance; 2.2.5 Other Maintenance Approaches; 2.3 The Mathematical Formulation; 2.3.1 Assumptions and Terminology; 2.3.2 Data Structure; References; 3 Known Concepts and Solution Techniques; 3.1 Computational Complexity.
3.2 Linear and Integer Programming3.2.1 The Simplex Algorithm; 3.2.2 The Primal-Dual Simplex Algorithm; 3.3 Dual Decomposition: Lagrangean Relaxation; 3.3.1 Column Generation; 3.3.2 Subgradient Optimization; 3.4 Primal Decomposition: Benders' Reformulation; 3.5 Local Search and Tabu Search; 3.5.1 Local Search; 3.5.2 Tabu Search; 3.6 The Knapsack Problem; 3.6.1 Valid Inequalities; 3.6.2 Lower and Upper Bounds; 3.6.3 An Exact Algorithm; References; 4 The Weighted Uncapacitated Planned Maintenance Problem; 4.1 The Mathematical Formulation; 4.2 Polyhedral Properties; 4.3 Computational Complexity.
4.4 The Single Weighted Uncapacitated Planned Maintenance Problem4.4.1 An Optimal Solution to the Primal Problem; 4.4.2 An Optimal Solution to the Corresponding Dual Problem of the LP Relaxation; 4.5 The Uncapacitated Planned Maintenance Problem; References; 5 Analyzing the Solvability of the Capacitated Planned Maintenance Problem; 5.1 Valid Inequalities and Polyhedral Properties; 5.2 Computational Complexity; 5.3 Lower Bounds; 5.3.1 Considered Lower Bounds; 5.3.2 Relative Strengths and Computational Complexity; 5.3.3 Transformations of the Lower Bounds; 5.3.3.1 Network Flow Problems.
5.3.3.2 Facility Location Problems5.3.4 Mathematical Formulations of the Lagrangean Duals; 5.3.4.1 Lagrangean Duals Z(P)+(Q)(R) and Z(P)(X)+(Q)(R) ; 5.3.4.2 Lagrangean Dual Z(P) ; 5.3.4.3 Lagrangean Dual Z(C) ; 5.3.4.4 Lagrangean Dual Z(P)/(C) ; 5.3.4.5 Lagrangean Dual Z(Y)(V) ; References; 6 Algorithms for the Capacitated Planned Maintenance Problem; 6.1 Three Construction Heuristics; 6.1.1 The First Fit Heuristic; 6.1.2 The Overlap Heuristic; 6.1.3 The Iterated Best-of-Three Heuristic; 6.2 Two Lagrangean Heuristics; 6.2.1 The Lagrangean Relaxation of the Capacity Constraint.
6.2.1.1 The LP Lower Bound6.2.1.2 The Dual Priority Rule Lower Bound; 6.2.1.3 The Combined Lower Bound; 6.2.1.4 The Primal-Dual Lower Bound; 6.2.1.5 The Shortest Path Lower Bound; 6.2.1.6 The Upper Bound Heuristic; 6.2.2 The Lagrangean Relaxation of the Period Covering Constraint; 6.2.3 The Lagrangean Heuristic for Both Relaxations; 6.2.3.1 Initial Lagrangean Multiplier; 6.2.3.2 A Lagrangean Heuristic; 6.3 A More Sophisticated Lagrangean Hybrid Heuristic; 6.3.1 A General Approach to Link Two Lagrangean Relaxations ; 6.3.2 The Lagrangean Hybrid Heuristic.
3.2 Linear and Integer Programming3.2.1 The Simplex Algorithm; 3.2.2 The Primal-Dual Simplex Algorithm; 3.3 Dual Decomposition: Lagrangean Relaxation; 3.3.1 Column Generation; 3.3.2 Subgradient Optimization; 3.4 Primal Decomposition: Benders' Reformulation; 3.5 Local Search and Tabu Search; 3.5.1 Local Search; 3.5.2 Tabu Search; 3.6 The Knapsack Problem; 3.6.1 Valid Inequalities; 3.6.2 Lower and Upper Bounds; 3.6.3 An Exact Algorithm; References; 4 The Weighted Uncapacitated Planned Maintenance Problem; 4.1 The Mathematical Formulation; 4.2 Polyhedral Properties; 4.3 Computational Complexity.
4.4 The Single Weighted Uncapacitated Planned Maintenance Problem4.4.1 An Optimal Solution to the Primal Problem; 4.4.2 An Optimal Solution to the Corresponding Dual Problem of the LP Relaxation; 4.5 The Uncapacitated Planned Maintenance Problem; References; 5 Analyzing the Solvability of the Capacitated Planned Maintenance Problem; 5.1 Valid Inequalities and Polyhedral Properties; 5.2 Computational Complexity; 5.3 Lower Bounds; 5.3.1 Considered Lower Bounds; 5.3.2 Relative Strengths and Computational Complexity; 5.3.3 Transformations of the Lower Bounds; 5.3.3.1 Network Flow Problems.
5.3.3.2 Facility Location Problems5.3.4 Mathematical Formulations of the Lagrangean Duals; 5.3.4.1 Lagrangean Duals Z(P)+(Q)(R) and Z(P)(X)+(Q)(R) ; 5.3.4.2 Lagrangean Dual Z(P) ; 5.3.4.3 Lagrangean Dual Z(C) ; 5.3.4.4 Lagrangean Dual Z(P)/(C) ; 5.3.4.5 Lagrangean Dual Z(Y)(V) ; References; 6 Algorithms for the Capacitated Planned Maintenance Problem; 6.1 Three Construction Heuristics; 6.1.1 The First Fit Heuristic; 6.1.2 The Overlap Heuristic; 6.1.3 The Iterated Best-of-Three Heuristic; 6.2 Two Lagrangean Heuristics; 6.2.1 The Lagrangean Relaxation of the Capacity Constraint.
6.2.1.1 The LP Lower Bound6.2.1.2 The Dual Priority Rule Lower Bound; 6.2.1.3 The Combined Lower Bound; 6.2.1.4 The Primal-Dual Lower Bound; 6.2.1.5 The Shortest Path Lower Bound; 6.2.1.6 The Upper Bound Heuristic; 6.2.2 The Lagrangean Relaxation of the Period Covering Constraint; 6.2.3 The Lagrangean Heuristic for Both Relaxations; 6.2.3.1 Initial Lagrangean Multiplier; 6.2.3.2 A Lagrangean Heuristic; 6.3 A More Sophisticated Lagrangean Hybrid Heuristic; 6.3.1 A General Approach to Link Two Lagrangean Relaxations ; 6.3.2 The Lagrangean Hybrid Heuristic.