Flow Shop Scheduling Algorithms
Design and Performance Analysis
- 1st Edition - January 1, 2027
- Latest edition
- Authors: Danyu Bai, Tao Ren, Xinyue Wang
- Language: English
Flow Shop Scheduling Algorithms: Design and Performance Analysis is an in-depth exploration of flow shop scheduling models, critically important in discrete manufacturing and pr… Read more
Description
Description
Flow Shop Scheduling Algorithms: Design and Performance Analysis is an in-depth exploration of flow shop scheduling models, critically important in discrete manufacturing and process industries. The book presents a blend of exact algorithms, such as branch and bound, and approximate methods, including intelligent optimization techniques, to tackle the NP-hard problems (a class of complex computational problems that are at least as hard as the hardest problems in the NP class) inherent in flow shop scheduling. It offers readers a means to achieve optimal or near-optimal solutions for a range of scheduling problems, from small to medium scale, with a focus on scenarios involving release dates and other complex constraints. The book includes many algorithmic designs, performance analyses, and numerical experiments that validate the efficacy of the proposed methods
Key features
Key features
- Offers detailed designs of both exact and approximate algorithms, providing readers with a comprehensive set of tools to address small to large-scale flow shop scheduling problems
- Includes an in-depth analysis of the performance of the proposed algorithms, ensuring readers understand not just how to apply these methods, but also their limitations and potential for optimization
- Bridges the gap between theory and practice by discussing the application of these algorithms in real-world industrial settings, making it a valuable resource for professionals in the field
- Is enriched with extensive numerical experiments that validate the proposed methods, offering readers tangible evidence of the algorithms' effectiveness
Readership
Readership
Academics and researchers specializing in the fields of operations research, systems engineering, applied mathematics, and industrial engineering; postgraduate students and advanced undergraduate students specializing in the fields of operations management, systems optimization, and industrial management
Table of contents
Table of contents
1. Introduction
1.1 Symbols and Definitions of Scheduling Problems
1.2 Methods for Solving Scheduling Problems
1.3 Scheduling Algorithms and Performance Analysis Methods
1.3.1 Scheduling Algorithms
1.3.2 Main Methods for Evaluating Algorithm Performance
1.4 Current Research Status of Related Scheduling Problems
1.4.1 Current Status of Asymptotic Analysis Research
1.4.2 Current Research Status of Flow shop Scheduling Problems
1.5 Main Content of This Book References
2. Flow shop Scheduling with Release Dates
2.1 Introduction
2.2 Problem Description and Mathematical Model
2.3 Branch and Bound Algorithm
2.3.1 Pruning Rules
2.3.2 Lower Bound of the Branch and Bound Algorithm
2.3.3 Algorithm Procedure
2.4 Performance Analysis of Upper and Lower Bounds for Nonlinear Objective Problems
2.4.1 Convergence Analysis of the Lower Bound
2.4.2 Worst-Case Performance Analysis of the Initial Upper Bound
2.5 Hybrid Discrete Differential Evolution Algorithm
2.6 Numerical Experiments
2.6.1 Branch and Bound Algorithm
2.6.2 Discrete Differential Evolution Algorithm
2.6.3 Lower Bound Performance Tests
2.6.4 Industrial Data Testing
2.7 Summary of This Chapter References Appendix A A.1 Genetic Algorithm A.2 Particle Swarm Optimization Algorithm A.3 Orthogonal Experiment on the Maximum Completion Time Problem A.4 Orthogonal Experiment on the Maximum Delivery Time Problem A.5 Orthogonal Experiment on the k-th Power of Completion Time Problem
3. Flow shop Scheduling with Processor Blocking
3.1 Introduction
3.2 Problem Description and Mathematical Model
3.3 Branch and Bound Algorithm
3.3.1 Pruning Rules
3.3.2 Lower Bound of the Branch and Bound Algorithm
3.3.3 Algorithm Procedure
3.4 Hybrid Discrete Differential Evolution Algorithm
3.5 Numerical Experiments
3.5.1 Branch and Bound Algorithm
3.5.2 Hybrid Discrete Differential Evolution Algorithm
3.6 Summary of This Chapter References Appendix B B.1 Delivery Date Parameter Setting B.2 Orthogonal Experiment of the HDDE Algorithm
4. Flow shop Scheduling with Learning Effect
4.1 Introduction
4.2 Problem Description and Mathematical Model
4.2.1 Mathematical Model
4.2.2 Learning Effect Function
4.3 Asymptotic Performance Analysis of Heuristic Algorithms
4.3.1 SPTAF Heuristic and Its Asymptotic Optimality
4.3.2 SPTAA Heuristic and Its Asymptotic Optimality
4.3.3 EDDA Heuristic and Its Asymptotic Optimality
4.4 Branch and Bound Algorithm
4.4.1 Lower Bound of the Branch and Bound Algorithm
4.4.2 Pruning Rules
4.4.3 Algorithm Procedure
4.5 Intelligent Optimization Algorithms
4.5.1 Discrete Differential Evolution Algorithm
4.5.2 Particle Swarm Optimization Algorithm
4.5.3 Artificial Bee Colony Algorithm
4.6 Numerical Experiments
4.6.1 Branch and Bound Algorithm
4.6.2 Numerical Experiments of Intelligent Optimization Algorithms
4.6.3 Numerical Experiments of Heuristic Algorithms
4.7 Summary of This Chapter References Appendix C C.1 Single-Machine Learning Effect Scheduling Model with Release Dates C.2 Performance Analysis of the Lower Bound
5. Bi-Agent Flow shop Scheduling Problems
5.1 Introduction
5.2 Problem Description and Mathematical Model
5.3 Heuristic Algorithms
5.3.1 DA Heuristic and Its Asymptotic Optimality
5.3.2 Performance Analysis Based on the DA Lower Bound
5.3.3 ADA Heuristic and Its Asymptotic Optimality
5.3.4 Performance Analysis Based on the ADA Lower Bound
5.4 Branch and Bound Algorithm
5.4.1 Pruning Rules
5.4.2 Lower Bound of the Branch and Bound Algorithm
5.4.3 Algorithm Procedure
5.5 Discrete Artificial Bee Colony Algorithm
5.6 Numerical Experiments
5.6.1 Branch and Bound Algorithm
5.6.2 Discrete Artificial Bee Colony Algorithm
5.6.3 Numerical Experiments of Heuristics
5.7 Summary of This Chapter References Appendix D D.1 Theoretical Results of Single-Machine Bi-Agent Scheduling D.2 Parameter Setting of the DABC Algorithm
6. Bi-Agent Blocking Flow shop and Its Extension Problems
6.1 Introduction
6.2 Problem Description and Mathematical Model
6.2.1 Bi-Agent Blocking Flow shop Scheduling Problem
6.2.2 Extension Problems
6.3 Branch and Bound Algorithm
6.3.1 Pruning Rules
6.3.2 Lower Bound of the Branch and Bound Algorithm
6.3.3 Initial Upper Bound
6.3.4 Algorithm Procedure
6.4 Hybrid Particle Swarm Optimization Algorithm
6.5 Numerical Experiments
6.5.1 Hybrid Particle Swarm Optimization Algorithm
6.5.2 Branch and Bound Algorithm
6.5.3 Extension Problem Numerical Experiment
6.6 Summary of This Chapter References Appendix E E.1 Orthogonal Experiment of the DABC Algorithm E.2 Orthogonal Experiment of the HPSO Algorithm
7. Hybrid Flow shop Scheduling with Learning Effect
7.1 Introduction
7.2 Problem Introduction
7.2.1 Problem Description and Mathematical Model
7.2.2 Learning Effect Function
7.3 Branch and Bound Algorithm
7.3.1 Framework Design
7.3.2 Pruning Rules
7.3.3 Algorithm Procedure
7.4 Bi-Population Discrete Differential Evolution Algorithm
7.5 GSPTA Heuristic Algorithm and Problem Lower Bound
7.5.1 GSPTA Heuristic Algorithm
7.5.2 Problem Lower Bound
7.6 Numerical Experiments
7.6.1 Branch and Bound Algorithm
7.6.2 Bi-Population Discrete Differential Evolution Algorithm
7.6.3 Heuristic Algorithm References Index
1.1 Symbols and Definitions of Scheduling Problems
1.2 Methods for Solving Scheduling Problems
1.3 Scheduling Algorithms and Performance Analysis Methods
1.3.1 Scheduling Algorithms
1.3.2 Main Methods for Evaluating Algorithm Performance
1.4 Current Research Status of Related Scheduling Problems
1.4.1 Current Status of Asymptotic Analysis Research
1.4.2 Current Research Status of Flow shop Scheduling Problems
1.5 Main Content of This Book References
2. Flow shop Scheduling with Release Dates
2.1 Introduction
2.2 Problem Description and Mathematical Model
2.3 Branch and Bound Algorithm
2.3.1 Pruning Rules
2.3.2 Lower Bound of the Branch and Bound Algorithm
2.3.3 Algorithm Procedure
2.4 Performance Analysis of Upper and Lower Bounds for Nonlinear Objective Problems
2.4.1 Convergence Analysis of the Lower Bound
2.4.2 Worst-Case Performance Analysis of the Initial Upper Bound
2.5 Hybrid Discrete Differential Evolution Algorithm
2.6 Numerical Experiments
2.6.1 Branch and Bound Algorithm
2.6.2 Discrete Differential Evolution Algorithm
2.6.3 Lower Bound Performance Tests
2.6.4 Industrial Data Testing
2.7 Summary of This Chapter References Appendix A A.1 Genetic Algorithm A.2 Particle Swarm Optimization Algorithm A.3 Orthogonal Experiment on the Maximum Completion Time Problem A.4 Orthogonal Experiment on the Maximum Delivery Time Problem A.5 Orthogonal Experiment on the k-th Power of Completion Time Problem
3. Flow shop Scheduling with Processor Blocking
3.1 Introduction
3.2 Problem Description and Mathematical Model
3.3 Branch and Bound Algorithm
3.3.1 Pruning Rules
3.3.2 Lower Bound of the Branch and Bound Algorithm
3.3.3 Algorithm Procedure
3.4 Hybrid Discrete Differential Evolution Algorithm
3.5 Numerical Experiments
3.5.1 Branch and Bound Algorithm
3.5.2 Hybrid Discrete Differential Evolution Algorithm
3.6 Summary of This Chapter References Appendix B B.1 Delivery Date Parameter Setting B.2 Orthogonal Experiment of the HDDE Algorithm
4. Flow shop Scheduling with Learning Effect
4.1 Introduction
4.2 Problem Description and Mathematical Model
4.2.1 Mathematical Model
4.2.2 Learning Effect Function
4.3 Asymptotic Performance Analysis of Heuristic Algorithms
4.3.1 SPTAF Heuristic and Its Asymptotic Optimality
4.3.2 SPTAA Heuristic and Its Asymptotic Optimality
4.3.3 EDDA Heuristic and Its Asymptotic Optimality
4.4 Branch and Bound Algorithm
4.4.1 Lower Bound of the Branch and Bound Algorithm
4.4.2 Pruning Rules
4.4.3 Algorithm Procedure
4.5 Intelligent Optimization Algorithms
4.5.1 Discrete Differential Evolution Algorithm
4.5.2 Particle Swarm Optimization Algorithm
4.5.3 Artificial Bee Colony Algorithm
4.6 Numerical Experiments
4.6.1 Branch and Bound Algorithm
4.6.2 Numerical Experiments of Intelligent Optimization Algorithms
4.6.3 Numerical Experiments of Heuristic Algorithms
4.7 Summary of This Chapter References Appendix C C.1 Single-Machine Learning Effect Scheduling Model with Release Dates C.2 Performance Analysis of the Lower Bound
5. Bi-Agent Flow shop Scheduling Problems
5.1 Introduction
5.2 Problem Description and Mathematical Model
5.3 Heuristic Algorithms
5.3.1 DA Heuristic and Its Asymptotic Optimality
5.3.2 Performance Analysis Based on the DA Lower Bound
5.3.3 ADA Heuristic and Its Asymptotic Optimality
5.3.4 Performance Analysis Based on the ADA Lower Bound
5.4 Branch and Bound Algorithm
5.4.1 Pruning Rules
5.4.2 Lower Bound of the Branch and Bound Algorithm
5.4.3 Algorithm Procedure
5.5 Discrete Artificial Bee Colony Algorithm
5.6 Numerical Experiments
5.6.1 Branch and Bound Algorithm
5.6.2 Discrete Artificial Bee Colony Algorithm
5.6.3 Numerical Experiments of Heuristics
5.7 Summary of This Chapter References Appendix D D.1 Theoretical Results of Single-Machine Bi-Agent Scheduling D.2 Parameter Setting of the DABC Algorithm
6. Bi-Agent Blocking Flow shop and Its Extension Problems
6.1 Introduction
6.2 Problem Description and Mathematical Model
6.2.1 Bi-Agent Blocking Flow shop Scheduling Problem
6.2.2 Extension Problems
6.3 Branch and Bound Algorithm
6.3.1 Pruning Rules
6.3.2 Lower Bound of the Branch and Bound Algorithm
6.3.3 Initial Upper Bound
6.3.4 Algorithm Procedure
6.4 Hybrid Particle Swarm Optimization Algorithm
6.5 Numerical Experiments
6.5.1 Hybrid Particle Swarm Optimization Algorithm
6.5.2 Branch and Bound Algorithm
6.5.3 Extension Problem Numerical Experiment
6.6 Summary of This Chapter References Appendix E E.1 Orthogonal Experiment of the DABC Algorithm E.2 Orthogonal Experiment of the HPSO Algorithm
7. Hybrid Flow shop Scheduling with Learning Effect
7.1 Introduction
7.2 Problem Introduction
7.2.1 Problem Description and Mathematical Model
7.2.2 Learning Effect Function
7.3 Branch and Bound Algorithm
7.3.1 Framework Design
7.3.2 Pruning Rules
7.3.3 Algorithm Procedure
7.4 Bi-Population Discrete Differential Evolution Algorithm
7.5 GSPTA Heuristic Algorithm and Problem Lower Bound
7.5.1 GSPTA Heuristic Algorithm
7.5.2 Problem Lower Bound
7.6 Numerical Experiments
7.6.1 Branch and Bound Algorithm
7.6.2 Bi-Population Discrete Differential Evolution Algorithm
7.6.3 Heuristic Algorithm References Index
Product details
Product details
- Edition: 1
- Latest edition
- Published: January 1, 2027
- Language: English
About the authors
About the authors
DB
Danyu Bai
Professor Danyu Bai is based at the School of Maritime Economics and Management and is the Director of Department of Logistics and Supply Chain Management, Dalian Maritime University, Dalian, China. He serves as the vice president of the Scheduling Sub-Society of the Operations Research Society of China. He has authored two academic books and more than 50 refereed papers. In 2023, he received the second prize of the Innovation Technology Award at the Chinese Society of Simulation Science and Technology Awards
Affiliations and expertise
Director of Department of Logistics and Supply Chain Management, Dalian Maritime University, Dalian, ChinaTR
Tao Ren
Professor Tao Ren is a Professor at the Software College at Northeastern University, China. His main research interests include the study of artificial intelligence algorithms and their applications in cutting-edge fields, such as image processing based on machine learning, seismic monitoring, multi-agent games, and intelligent optimization
Affiliations and expertise
Professor, Software College, Northeastern University, ChinaXW
Xinyue Wang
Dr Xinyue Wang is an Associate Research Fellow at the Software College of Northeastern University. Dr Wang obtained her Ph.D. degree in Mathematics and Computer Science from Université Paris-Saclay, France. Her main research interests include computer science, systems engineering, scheduling optimization, algorithm design, and theoretical analysis
Affiliations and expertise
Associate Research Fellow, Software College of Northeastern University, China