本研究提出結合電腦模擬和遺傳演算法的方法，以優化表面黏著技術 (SMT) 組裝線中印刷電路板 (PCB) 的生產排程。由於訂單需要提前規劃才能按特定順序投入生產，此方法旨在提供一種優化排程的替代方案。

在這種方法中，電腦模擬會盡可能貼近現實地模擬實際的組裝線，以便獲得接近真實世界的結果。為此，模擬會考慮進入生產的訂單中的關鍵細節。這些關鍵細節通常是影響生產時間的變數，例如需要黏著的元件數量、需要焊接的針腳數量以及訂購批次的大小。透過模擬，可以得到訂單的完成時間。

然後，遺傳演算法會生成潛在的排程順序，並以模擬的完成時間作為其評分。接著，該方法將選擇完成時間最短的順序。

該方法通過一系列基於真實樣本的不同大小的順序進行評估。結果展示了模擬的完整範圍以及提供完整和最佳響應的速度。

This study proposes a computer simulation accompanied by a genetic algorithm for scheduling in a surface mount technology(SMT) assembly line for the manufacturing of printed circuit boards(PCB). As orders need to be planned ahead to enter production in a given sequence, this approach seeks to provide an alternative to optimize scheduling. 

In said approach, the computer simulation mimics the real assembly line in order to get results as close to reality as possible. To do so, the simulation takes into account key details of the orders entering production. The key details are usually the variables that affect the production time such as the number of components or the number of pins to be mounted on the boards as well as the size of the batch ordered. Through the simulation the completion time of the orders is obtained. The genetic algorithm, then, generates potential sequences which scores will be their simulated completion time. The proposed approach then will take the sequence with the smaller completion time. 

The approach is evaluated through a series of different size sequences based on real life samples. The results show the full scope of the simulation as well as the speed at which a complete and optimal response can be provided.

Contents
Chapter 1 Introduction	1
Section 1 Research Motivation	1
Section 2 Research Objectives	2
Chapter 2 Literature Review	5
Section 1 Surface Mount Technology	5
Section 2 Existing Methods Comparison	7
Section 3 Consensus	11
Section 4 Optimization: Genetic algorithm	13
Chapter 3 - Methodology	17
Section 1 Two Steps Approach	17
Section 2 Simulation	21
Example:	29
Example 1:	29
Example 2:	31
Section 3 Genetic Algorithm	34
Section 4 Simulation & GA Example	39
Chapter 4 Experiments	46
Experiment 1	46
Experiment 2	52
Experiment 3	55
Chapter 5 - Conclusion	59
References	60


Tables
Table 2-2.1 Two previous researches on smt scheduling optimization	7
Table 2-2.2 Shortcomings or disadvantages of mathematical model and heuristic method	10
Table 2-3.1 Advantages and disadvantages of computer simulation and mathematical model	12
Table 3-2.1 Matrix of the randomized similarity coefficient	28
Table 3-2.2 Matrix of similarity of coefficients of the sequence of 3	30
Table 4-1.1 Specifications of each order in the sequence of 5	46
Table 4-1.2 Matrix of the randomized similarity coefficients of sequence of 5	47
Table 4-2.1 Specifications of the 10 orders	53
Table 4-2.2 Matrix of the randomized similarity coefficient	53
Table 4-3.1 The specifications of each order in the sequence of 20 orders	56



Figures
fig. 2-1.1 Surface mount assembly line with two component placement stations	5
fig. 2-1.2 Printed circuit boards	6
fig. 2-1.3 Surface mount assembly line with named stations	7
fig. 2-2.1 The dual implementation of the mathematical model	9
fig. 2-2.2  Improvement heuristic search stratified structure	10
fig. 2-4.1 Taxonomy of optimization method 	14
fig. 2-4.2 Genetic algorithm diagram	16
fig. 3-1.1 Block diagram of the structure of the proposed approach	18
fig. 3-1.2 First part the approach: simulation	19
fig. 3-1.3 Result of the initial simulation	19
fig. 3-1.4 Second part of the approach: genetic algorithm	20
fig. 3-2.1 General structure of  a PCB assembly line	21
fig. 3-2.2 Flowchart of SMT simulation	22
fig. 3-2.3 Detailed representation of the buffer, tote box arrangement	23
fig. 3-2.4 transportation and set up involved in scheduling	25
fig. 3-2.5 Block diagram representing simulation code structure	27
fig. 3-2.6 Input of the simulation	29
fig. 3-2.7 Order entering production with day and time of product completion	30
fig. 3-2.8 order being completed, how many board have been produced and another order entering	30
fig. 3-2.9 last order of completion ready for dispatch	31
fig. 3-2.10 Score based on the makespan	31
fig. 3-2.11 Same orders but entering production in a different sequence	31
fig. 3-2.12 First order of sequence [2,1,0] entering production	32
fig. 3-2.13 First order completion and second order entering production	32
fig. 3-2.14 Second order completion and third order entering production	33
fig. 3-2.15 Third and last order completion	33
fig. 3-2.16 Score based on makespan of sequence [2,1,0]	33
fig. 3-2.17 Two scores based on makespan comparison	33
fig. 3-3.1 Individual selected for reproduction out of overall population	34
fig. 3-3.2 Cycle of genetic algorithm	35
fig. 3-3.3 Two parents and the randomly selected genes in parent 1	36
fig. 3-3.4 Mating between parents and the steps to get the chromosome of the offspring	37
fig. 3-3.5 Genetic algorithm code structure	38
fig. 3-4.1 input of the simulation	39
fig. 3-4.2 result from the makespan	39
fig. 3-4.3 original population randomly generated	40
fig. 3-4.4 individuals coupled with their fitness score	40
fig. 3-4.5 list of individuals selected for reproduction	41
fig. 3-4.6 sample of offspring after crossover or reproduction	42
fig. 3-4.7 Offsprings after mutation phase	43
fig. 3-4.8  initial generation of offspring coupled with their makespan based fitness score	43
fig. 3-4.9 individuals coupled with fitness score from generation 1,  2 and 3	44
fig. 3-4.10 Generation 1 fittest individual	44
fig. 3-4.11 Generation 2 fittest Individual	44
fig. 3-4.12 Generation 3 fittest individual	44
fig. 3-4.13 fittest individual coupled with fitness score	45
fig. 3-4.14 convergence of individuals towards a stable point in the genetic algorithm	45
fig. 4-1.1 specifications of each order in the sequence of 5	46
fig. 4-1.2 makespan  of the sequence	47
fig. 4-1.3 execution time for sequence of 5	47
fig. 4-1.4(1) fittest sequence coupled with fitness score of each generation	47
fig. 4-1.4(2) graph of the fittest individuals with fitness scores of each generation	48
fig. 4-1.5 fittest individual by GA	48
fig. 4-1.6 list of the 120 variations of the sequence coupled with their fitness score	48
fig. 4-1.6 list of the 120 variations of the sequence coupled with their fitness score	49
fig. 4-1.6 list of the 120 variations of the sequence coupled with their fitness score	50
fig. 4-1.6 list of the 120 variations of the sequence coupled with their fitness score	51
fig. 4-1.6 list of the 120 variations of the sequence coupled with their fitness score	52
fig. 4-1.7 fittest variation with fitness score	52
fig. 4-1.8 GA vs enumerating the variations one by one	52
fig. 4-2.1 specifications of the 10 orders	53
fig. 4-2.2 makespan related fitness score	53
fig. 4-2.3 computation time of sequence of 10 in GA	54
fig. 4-2.4(1) fittest sequence coupled with fitness score of each generation	54
fig. 4-2.4(2)  graph representing fittest individuals across the generations of sequrnce of 10	55
fig. 4-2.5 fittest sequence with fitness score	55
fig. 4-3.1 the specifications of each order in the sequence of 20 orders	56
fig. 4-3.2 fitness of the  sequence in the order shown above of the 20 orders	57
fig. 4-3.3 computation time of experiment 2	57
fig. 4-3.4(1) fittest sequence coupled with fitness score of each generation	57
fig. 4-3.4(2) graph representing fittest individuals across the generations of sequrnce of 20	58
fig. 4-3.5 fittest sequence with fitness score	58

1.	Ahmadi, J., Ahmadi, R., MAtsuo, H. and Tirupati, D. 1995. Component fixture positioning/sequencing for printed circuit board assembly with concurrent operations. Operations Research, 43: 444–457.
2.	Attea, B.A., Abbood, A., Hasan, A., Pizzuti, C., Al-Ani, M., Ozdemir, S., Al-Dabbagh, R. 2021. A Review of Heuristics and Metaheuristics for Community Detection in Complex Networks: Current Usage, Emerging Development and Future Directions. Swarm and Evolutionary Computation, 63(8):100885
3.	Balakrishnan, A. and Vanderbeck, F. 1999. A tactical planning model for mixed-model electronics assembly operations. Operations Research, 47: 395–409.
4.	Bard, J. F., Clayton, R. W. and Feo, T. A. 1994. Machine setup and component placement in printed circuit board assembly. International Journal of Flexible Manufacturing Systems, 6: 5–31.
5.	Ghosh, S. and Gagnon, R. J. 1989. A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems. International Journal of Production Research, 27: 637–670.
6.	Jain, A., Johnson, M.E. and Safai, F. 1996. Implementation of setup optimization on the shop floor. Operations Research, 44: 843–851.
7.	Kaczmarczyk, W., Sawik T., Schaller A. & Tirpak T. M., 2004. Optimal versus heuristic scheduling of surface mount technology lines. International Journal of Production Research 42(10):2083-2110
8.	Katoch, S., Chauhan, S.S. & Kumar, V. 2021 A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126.
9.	Kumar, R. and Li, H. 1995. Integer programming approach to printed circuit board assembly. IEEE Transactions on Computers and Packaging, Manufacturing Technology, B18: 720–727.
10.	Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., Rathnayake, T., Vig, S., Granger, B. E., Muller, R. P., Bonazzi, F., Gupta, H., Vats, S.,Johansson, F., Pedregosa, F., Curry, M. J., Terrel, A. R., Roučka, Š., Saboo, A., Fernando, I., Kulal, S., Cimrman, R. & Scopatz, A. 2017 Sympy: symbolic computing in Python. PeerJ Computer Science, 3:e103; DOI 10.7717/peerj- cs.103
11.	Prolejko, P., Assel Poland, 2020. ef238935a2_smt-machine.png
12.	Sawik, T. 1999. Production Planning and Scheduling in Flexible Assembly Systems, Berlin: Springer.
13.	Sawik, T. 2000a. Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers. Mathematical and Computer Modelling, 31: 39–52.
14.	Sawik, T. 2001. Mixed integer programming for scheduling surface mount technology lines. International journal of Production Research, 39: 3219–3235.
15.	Sawik, T. 2002 Balancing and scheduling of surface mount technology lines, International Journal of Production Research, 40:9, 1973-1991.
16.	Slowik, A., Kwasnicka, H. 2020 Evolutionary algorithms and their applications to engineering problems. Neural Comput & Applic 32, 12363–12379.
17.	Spekking, R., 2016. "© Raimond Spekking / CC BY-SA 4.0 (via Wikimedia Commons)". SEG_DVD_430_-_Printed_circuit_board-4276.jpg
18.	Tavvakoli-Moghaddam, R. and Daneshmand-Mehr, M., 2005. A computer simulation model for job shop scheduling problems minimizing makespan. Computers and Industrial Engineering, 48: 811-823.
19.	Technology Solutions (UK) Ltd, TSL-SMT-01.jpg