Optimal Production Planning for PCB Assembly

Optimal Production Planning for PCB Assembly
اسم المؤلف
William Ho and Ping Ji
التاريخ
30 مارس 2023
المشاهدات
296
التقييم
(لا توجد تقييمات)
Loading...

Optimal Production Planning for PCB Assembly
With 41 Figures
William Ho and Ping Ji
Contents
1 Introduction 1
1.1 PCB Assembly Process 1
1.2 Assembly Equipment . 2
1.3 PCB Assembly Problems . 3
1.4 Scope of This Book 4
2 Optimization Techniques . 7
2.1 Introduction 7
2.2 Mathematical Programming . 7
2.2.1 Linear Programming . 8
2.2.2 Integer Linear Programming . 8
2.2.3 Nonlinear Programming 10
2.3 Exact Algorithms 10
2.3.1 Algorithms for Linear Programming 11
2.3.1.1 The Simplex Algorithm . 11
2.3.1.2 The Interior Point Algorithm . 11
2.3.2 Algorithms for Integer Linear Programming 11
2.3.2.1 The Branch-and-Bound Algorithm 11
2.3.2.2 The Cutting Plane Algorithm 12
2.3.3 Algorithms for Nonlinear Programming . 12
2.3.3.1 The Generalized Benders Algorithm . 12
2.3.3.2 The Branch-and-Reduce Algorithm 13
2.4 Metaheuristics 13
2.4.1 Simulated Annealing . 14
2.4.2 Tabu Search 15
2.4.3 Genetic Algorithms . 15
2.5 Commercial Packages 16
2.5.1 BARON 17
2.5.2 CPLEX 17
2.5.3 Others 17
2.6 Summary 17viii Contents
3 The Sequential Pick-and-Place (PAP) Machine . 19
3.1 Introduction 19
3.2 Literature Review . 20
3.2.1 The Component Sequencing Problem . 20
3.2.2 The Integrated Problem . 20
3.3 Operating Sequence 22
3.4 Notation 23
3.5 Mathematical Models . 24
3.5.1 A Component Sequencing Model . 24
3.5.2 A Feeder Arrangement Model 26
3.5.3 Integrated Mathematical Models 27
3.5.4 Iterative Approach vs. Integrated Approach . 33
3.5.5 Computational Analysis 35
3.5.5.1 Computing Complexity . 35
3.5.5.2 Computational Time 37
3.6 Genetic Algorithms 37
3.6.1 Encoding . 40
3.6.2 Improved Heuristics 41
3.6.2.1 Nearest Neighbor Heuristic . 41
3.6.2.2 2-Opt Local Search Heuristic 41
3.6.2.3 Iterated Swap Procedure 41
3.6.3 Evaluation . 42
3.6.4 Selection 42
3.6.5 Genetic Operations 43
3.6.5.1 The Modified Order Crossover . 44
3.6.5.2 The Heuristic Mutation 44
3.6.5.3 The Inversion Mutation . 45
3.6.6 Performance Analysis . 45
3.6.6.1 Comparison to Other Approaches . 46
3.6.6.2 Effect of Population Size . 47
3.6.6.3 Comparison to Optimal Solution . 48
3.6.6.4 Integrated Problem with Feeder Duplication . 48
3.7 Summary 50
4 The Concurrent Chip Shooter (CS) Machine . 53
4.1 Introduction 53
4.2 Literature Review . 54
4.2.1 The Component Sequencing Problem . 54
4.2.2 The Feeder Arrangement Problem 54
4.2.3 The Integrated Problem . 54
4.3 Operating Sequence . 56
4.4 Notation 64
4.5 Mathematical Models . 65
4.5.1 A Component Sequencing Model . 65
4.5.2 A Feeder Arrangement Model 67
4.5.3 Integrated Mathematical Models 69
4.5.4 Iterative Approach vs. Integrated Approach . 74Contents ix
4.5.5 Computational Analysis 77
4.5.5.1 Computing Complexity . 77
4.5.5.2 Computational Time 77
4.6 Genetic Algorithms 78
4.6.1 Evaluation . 78
4.6.2 Performance Analysis . 79
4.6.2.1 Comparison to Other Approaches . 79
4.6.2.2 Effect of Population Size . 80
4.6.2.3 Comparison to Optimal Solution . 81
4.6.2.4 Integrated Problem with Feeder Duplication . 82
4.7 Summary 83
5 The Line Assignment and the Component Allocation Problems 85
5.1 Introduction 85
5.2 The Line Assignment Problem . 86
5.2.1 A Mathematical Model . 87
5.2.2 A Genetic Algorithm . 89
5.2.2.1 Initialization 91
5.2.2.2 Evaluation 92
5.2.2.3 Selection 92
5.2.2.4 Crossover Operator 92
5.2.2.5 Mutation Operator . 93
5.2.3 A Numerical Example . 93
5.3 The Component Allocation Problem 98
5.3.1 A Mathematical Model . 100
5.3.2 A Genetic Algorithm . 101
5.3.2.1 Initialization 101
5.3.2.2 Evaluation 102
5.3.3 A Numerical Example . 102
5.4 Summary 107
6 A Prototype of the Printed Circuit Board Assembly Planning System
(PCBAPS) 109
6.1 The PCBAPS Framework . 109
6.2 A Guide to Using the PCBAPS 109
6.3 Graphical User Interfaces . 110
6.4 Summary 112
References 115
Index 119
Index
A
Algorithms, branch-and-bound (B&B)
algorithm 11
branch-and-reduce algorithm 12
cutting plane algorithm 12
generalized benders algorithm 12
genetic algorithms (GAs) 14, 15,
37, 78, 89
hybrid genetic algorithm (HGA) 39
interior point algorithm 11
Lagrangian relaxation algorithm 99
pivot and probe algorithm (PAPA)
89
simplex algorithm 11
stepping stone algorithm 89
Assembly heads 54
B
BARON 16
Board sequencing heuristic (BSH) 54
Branch-and-bound (B&B) algorithm
11
Branch-and-reduce algorithm 12
C
Chebyshev metric 75
Chip shooter (CS) machine 2
Chromosome, two-link representation
40
Clock sequence 20
Component allocation problems 86,
98, 100
crossover operator 92
genetic algorithm 89, 101
mutation operator 93
Component placement system (CPS)
54
Component sequencing 20
Computational time 37
Concurrent chip shooter (CS) machine
53
feeder arrangement model 67
feeders duplication 82
genetic algorithms 78
integrated approach 74
iterative approach 74
population size 80
CPLEX 16
Crossover operator 43, 92
Cutting plane algorithm 12
D
Data input interface 111
DICOPT 17
E
Encoding 40
Exploitation (intensification) 43
Exploration (diversification) 43120 Index
F
Feeder arrangement model 26, 67
Feeders duplication 48, 82
G
Generalized benders algorithm 12
Generalized transportation problem
(GTP) 87, 88
Genetic algorithms (GAs) 14, 15, 37,
78, 89
hybrid (HGA) 39
parameters input interface 112
Genetic local search (GLS) 16
Genetic operations 42
Global optimum 13
Graphical user interfaces 110
Greedy random adaptive search
procedures (GRASP) 98
H
Heuristics 13
2-opt local search 41
board sequencing heuristic (BSH)
54
meta-heuristics 13
nearest neighbor heuristic (NNH)
39, 41
Hybrid genetic algorithm (HGA) 39
flowchart 38
I
Implicit enumeration 11
Integer linear programming model,
PCB 86
Integer programming (IP) 8
Integrated approach 33, 74
Integrated circuits (ICs) 1
Interior point algorithm 11
Inversion mutation 45
Iterated swap procedure (ISP) 39, 41
Iterative approach 33, 74
L
Lagrangian relaxation algorithm 99
Line assignment 86
Linear programming (LP) 8
Lin-Kernighan (LK) 16
Local optimum 13
M
Machine input interface 111
Meta-heuristics 13
Minimax type integer linear
programming model 99
Minimax type objective function 69
Mixed integer linear programming
(MIP) models 11
Mixed integer nonlinear programming
(MINLP) model 12
Mutation operator 93
N
Nearest neighbor heuristic (NNH) 39,
41
Neighborhood technique 44
Non-convex relaxation 13
Nonlinear programming (NLP) 10
NP-complete 37, 99, 101
P
PCB assembly planning system 86
Pick-and-place (PAP) machine 2
Pick-up location (PUL) 57
Pivot and probe algorithm (PAPA) 89
Placement head 19
assembly sequence 22
Plated-through-hole (PTH)
technology 1
Population diversity 44
Population size 46, 80
Printed circuit board (PCB) 1
Printed circuit board assembly
planning system (PCBAPS) 109
Problem input interface 110Index 121
Q
Quadratic assignment problem (QAP)
10, 12, 26
R
Roulette wheel selection operation 42
S
Sequential pick-and-place (PAP)
machine 19
component sequencing 20
encoding 40
feeder arrangement model 26
feeders duplication 48
genetic algorithms 37
genetic operations 42
integrated approach 33
inversion mutation 43
iterated swap procedure 39
iterative approach 33
nearest neighbor heuristic 41
population size 46
Simplex algorithm 11
Simulated annealing (SA) 14
Stepping stone algorithm 89
Strategic partitioning 11
Surface mount technology (SMT) 1
T
Tabu search (TS) 14, 15
Traveling salesman problem (TSP) 3
Tree search 11

تحميل

يجب عليك التسجيل في الموقع لكي تتمكن من التحميل
تسجيل | تسجيل الدخول

التعليقات

اترك تعليقاً