Rescheduling Under Disruptions in Manufacturing Systems: Models and Algorithms (Uncertainty and Operations Research)

✍ Scribed by Dujuan Wang, Yunqiang Yin, Yaochu Jin

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 155
• Category: Library

✦ Synopsis

This book provides an introduction to the models, methods, and results of some rescheduling problems in the presence of unexpected disruption events, including job unavailability, arrival of new jobs, and machine breakdown. The occurrence of these unexpected disruptions may cause a change in the planned schedule, which may render the originally feasible schedule infeasible. Rescheduling, which involves adjusting the original schedule to account for a disruption, is necessary in order to minimize the effects of the disruption on the performance of the system. This involves a trade-off between finding a cost-effective new schedule and avoiding excessive changes to the original schedule.
This book views scheduling theory as practical theory, and it has made sure to emphasize the practical aspects of its topic coverage. Thus, this book considers some scenarios existing in most real-world environments, such as preventive machine maintenance, and deteriorating effect where the actual processing time of a job gets longer along with machine’s usage and age. To alleviate the effect of disruption events, some flexible strategies are adopted, including allocation extra resources to reduce job processing times or rejection the production of some jobs. For each considered scenario, depending on the model settings and on the disruption events, this book addresses the complexity, and the design of efficient exact or approximated algorithms. Especially when optimization methods and analytic tools fall short, this book stresses metaheuristics including improved elitist non-dominated sorting genetic algorithm and differential evolution algorithm. This book also provides extensive numerical studies to evaluate the performance of the proposed algorithms. The problem of rescheduling in the presence of unexpected disruption events is of great importance for the successful implementation of real-world scheduling systems. There is now an astounding body of knowledge in this field. This book is the first monograph on rescheduling. It aims at introducing the author's research achievements in rescheduling. It is written for researchers and Ph.D. students working in scheduling theory and other members of scientific community who are interested in recent scheduling models. Our goal is to enable the reader to know about some new achievements on this topic.

✦ Table of Contents

Preface
Contents
1 Introduction
1.1 Rescheduling
1.1.1 Job Characteristics
1.1.2 Machine Environments
1.1.3 Optimality Criteria
1.2 Complexity of Problems and Algorithms
1.2.1 The Classes mathcalP and mathcalNP
1.3 Bibliographic Remark
2 Rescheduling on Identical Parallel Machines in the Presence of Machine Breakdowns
2.1 Problem Formulation
2.2 Problem Analysis
2.3 Problem Pm, hm1 1| τ,[Bi, Fi]1leqileqm1|(sumj=1nCj,Δmax)
2.3.1 A Pseudo-Polynomial Time Algorithm for the Problem Pm, hm1 1| τ,[Bi, Fi]1leqileqm1|(sumj=1nCj,Δmax)
2.3.2 The Performance of Algorithm SMDP
2.4 Problem Pm, hm1 1| τ,[Bi, Fi]1leqileqm1|(sumj=1nCj,sumj=1nTj)
2.4.1 A Pseudo-Polynomial Time Algorithm for the Problem Pm, hm1 1 | τ,[Bi, Fi]1leqileqm1|(sumj=1nCj,sumj=1nTj)
2.4.2 A Two-Dimensional FPTAS for Finding a Pareto Optimal Solution
2.4.3 The Performance of Algorithms STDP and STAA
2.5 Summary
2.6 Bibliographic Remarks
3 Parallel-Machine Rescheduling with Job Rejection in the Presence of Job Unavailability
3.1 Problem Formulation and Formulation
3.1.1 Problem Formulation
3.1.2 Mixed Integer Linear Programming
3.2 Optimal Properties
3.3 A Pseudo-Polynomial Time Algorithm for the Problem with a Fixed Number of Machines
3.4 Column Generation Algorithm
3.4.1 The Master Problem
3.4.2 DE-Based Algorithm for the Master Problem Initialization
3.4.3 The Pricing Sub-problem
3.5 Branch-and-Price Algorithm
3.5.1 Fixing and Setting of Variables
3.5.2 Branching Strategy
3.5.3 Constructing a Feasible Integral Solution
3.5.4 Node Selection Strategy
3.5.5 Branch-and-Price Example
3.6 Computational Experiments
3.6.1 Data Sets
3.6.2 Analysis of Computational Results
3.6.3 Comparison with Alternative Solution Methods
3.6.4 Detailed Performance of the Branch-and-Price Algorithm
3.7 Summary
3.8 Bibliographic Remarks
4 Rescheduling with Controllable Processing Times and Job Rejection in the Presence of New Arrival Jobs and Deterioration Effect
4.1 Problem Formulation
4.2 Problem Analysis
4.3 A Directed Search Strategy for Dynamic Multi-objective Scheduling
4.3.1 Solution Representation
4.3.2 Population Re-initialization Mechanism (PRM)
4.3.3 Offspring Generation Mechanism (OGM)
4.3.4 Non-dominated Sorting Based Selection
4.4 Comparative Studies
4.4.1 Numerical Test Instances
4.4.2 Performance Indicators
4.4.3 Parameters Setting for Compared Algorithms
4.4.4 Results
4.5 Summary
4.6 Bibliographic Remarks
5 Rescheduling with Controllable Processing Times and Preventive Maintenance in the Presence of New Arrival Jobs and Deterioration Effect
5.1 Problem Formulation
5.2 Problem Analysis
5.3 An Improved NSGA-II for Integrating Preventive Maintenance and Rescheduling
5.3.1 NSGA-II/DE Algorithm
5.3.2 NSGA-II/DE + POSQ Algorithm
5.3.3 NSGA-II/DE + POSQ + AHS Algorithm
5.4 Comparative Studies
5.4.1 Parameter Setting
5.4.2 Performance Indicators of Pareto Fronts
5.4.3 Results
5.5 Summary
5.6 Bibliographic Remarks
6 A Knowledge-Based Evolutionary Proactive Scheduling Approach in the Presence of Machine Breakdown and Deterioration Effect
6.1 Problem Formulation
6.2 A Knowledge-Based Multi-objective Evolutionary Algorithm
6.2.1 Encoding Scheme
6.2.2 Main Evolutionary Operations
6.2.3 Support Vector Regression Model
6.2.4 Structural Property Based a Priori Domain Knowledge
6.3 Comparative Studies
6.3.1 Experimental Design
6.3.2 Parameters Tuning
6.3.3 Results
6.4 Summary
6.5 Bibliographic Remarks
Appendix References