首页技术支持联系方式 English 网站地图

公司介绍

新闻中心

PCB抄板


主营项目:	PCB抄板,PCB改板,PCB生产,IC解密,样机制作

·最新公告点击进入 >>

深科特PCB抄板、芯片解密、PCB生产企业-为您提供最专业的PCB抄板、芯片解密、PCB生产、样机制作服务，以超强的技术实力成为PCB抄板、芯片解密、PCB生产、IC解密行业界的领跑者。
任何样板，均可100%保证一次性克隆成功！

设计能力　　　　　

1		最高速信号：3.125G差分信号

2		最高设计层数：38层

3		最大Connections：18564

4		最大PIN数目：26756

5		最小过孔：8MIL(4MIL激光孔)

6		最小线宽：3MIL

7		最小线间距：4MIL

8		最小BGA PIN间距：0.5mm

9		一块PCB板最多BGA数目：30

10		最大的板面积：640mm*580mm

	PCB抄板

PCB改板

PCB抄板反向推理

·	PCB生产/批量生产

	SMT加工

	成功案例

　当前位置：首页 > PCB生产

PCB生产排程算法架构解析

日期:2009-3-27 10:37:26　

概述

PCB（Printed Circuit Board）厂为电子产业的基础，一般的电子产品大多数都含有PCB板在内部，如何大量的产出及缩短总完工时间，决定了工厂的利润来源。一般来说PCB工厂为了要使流程时间缩短，通常都会从机台的平衡（Balance）、技术的改良及机台的更新来着手，往往忽略了排程（Scheduling）在生产规划的重要性，而且PCB厂的工厂模式，属于非等效平行机台（Unrelated Parallel Machines）为复杂的求解模式，如果以工厂人员手动的排程方法需要花费较多的时间且其解也不一定较佳，本研究以基因算法（Genetic Algorithms）建构排程的求解模式，利用基因算法的优点来解决复杂的排程问题。

关键词：PCB工厂、PCB生产、PCB抄板、IC封装技术、不相关平行机台、基因算法

1. 导论

在整个制造规划和控制系统的架构中，由于排程连结了物料需求规划功能和生产现场的执行功能，而扮演了重要的角色。排程可以定义为在一段时间内，配置可用的资源来处理一群工作，以达到所设定的目标；而目标则可以订为满足交期或缩短闲置时间等。为了能有效地达成既定的目标，大量解决排程问题的方法不断的提出，但直到今天排程问题依然存在且持续被讨论着。

在1980年之前，解决排程问题的方法可划分成两大类[2]：一是最佳化问题，另一方面则是启发式法则。作业研究可以说是最佳化技术的典型代表；但是应用最佳化所发展出来的排程策略，往往会因为过多的假设而变得不切实际，无法实际地应用在真实的制造系统中。至于启发式法则典型的代表就是派工法则。启发式的优点是较简单且实用，缺点为具有高度的系统和准则的相依性；如Moreno和Ding[9]对于排程问题中零件的选取法，提出一套启发式的法则。Mukhopadhyay[10]则发展整合各启发式法的排程方法进行排程工作。

在1980 年代以后，人工智能与最佳化技术结合，促成最佳化搜寻技术的发展。模拟退火法（Simulated Annealing）[11]和遗传基因演算[11]等均是属于最佳化搜寻技术的领域。这类方法的特性在于能在广大的解答空间（Solution Space）中有效地搜寻到近似最佳解的答案；如Kim 和Lee[12]以分布式遗传基因算法为基础，衍生出一个零工型制造系统的排程方法，可以在合理的计算时间内找出最佳的排程解答；Murata 及Ishibuchi[d]则以遗传基因算法、塔布搜寻法（Tabu search）和模拟退火法来探讨流线型制造系统的排程问题，实验结果显示遗传算法的表现优于另外两者。

针对平行机器排程问题，总时程最小化、总流程时间最小化和总延迟时间最小化，均是属于NP-hard 问题的范围[13]。现有文献大多探讨相同机器或等率机器之排程问题，就问题复杂度而言，不相关机器之问题较相同或等率机器之问题更为困难。

由于IC封装技术不断提升，IC载板( ICSubstrate )需求量近年来成长迅速。在台湾既有半导体产业集聚的优势条件下，IC载板俨然成为印刷电路板厂及晶圆封装厂等各家厂商未来所积极投资发展的重点。IC载板的制程类似印刷电路板PCB ( PrintedCircuitBoard )的制程，以往与PCB相关的研究较偏重于PCB插件组装及制程技术，而少数探讨PCB裸板排程方面的研究亦仅止于考虑单一加工站生产限制条件的产能规划，对于印刷电路板厂的管理尤其在排程上的问题却很少有这方面的研究。结合PCB工厂的生产排程与基因算法，为了得到使多个订单能在最短的时间内完工，来换取接更多的订单，使得工厂的盈余增加。

深圳市深科特集团成立于2000年，公司专业从事双面、四至三十八层PCB板、克隆（抄板）、PCB改板、原理图及BOM单制作、芯片解密、PCB生产、成品加工等工作。公司拥有多名曾从事PCB设计布线工作多年的工程师，对多层PCB板有极其详尽透彻的了解，对含有激光孔、盲孔、埋孔的高端PCB板结构及走线规则的理解更是胜人一筹。无论是元件密集，遍布微带线、等长线的电脑主板、高端显卡板、千兆网络设备基板，或是对高频处理要求苛刻，电磁兼容性控制严格的小灵通主板、手机主板、无线网卡及其他无线通讯设备，以及叠层多达30层，盲孔埋孔密布的工控主板，都能依据客户提供的一套完好样板（或样机）一次性克隆生产。PCB生产，建厂已近20年，具备三十层以上多层板、多级激光盲埋孔板生产能力，可大批量加工线宽线距3mil（0.075mm),孔径4mil(0.10mm)的高精密PCB板，产能达每月多层板50000平米以上。负责协调PCB生产事宜的工程技术人员都有从事PCB生产管理多年，可轻松处理PCB生产过程中各种工程问题，并严把工艺指令下达、成品PCB板验收关，有效避免客户不必要的成本投入和损失。

2. 问题描述

一般来说PCB工厂的厂房布置，皆为平行机台的样式，且每一条生产线在微调之后都可以生产任一产品，差别在每一条生产所需花费的时间不同，过去有人以数学规划的方式；再利用LINDO求解，但是只要问题数量大的话，在加上计算机设备不够强，求解时间往往需要很久。非相关平行机台总完工时间最小化排程问题可利用下列线性规划数学模式来表示[14]：

Cmax ：工作的总完工时间，

ak ：机器k的开始加工时间，

rj ：工作j的底达时间，

xjk ：工作j指定在机器k加工的百分比（1 or 0），

pjk ：工作j指定在机器k加工的单位处理时间，

j´：在工作j之后抵达之工作，包含工作j。

在工厂中由于工件j在机器k的处理时间相差不多，也就是说Pjk＝Pj1＝Pj2……Pjm；所以我们在做基因算法求解时会先将工件j在每一机台的加工时间求取平均，再以基因算法架构求解。当问题以此方法架构时就如同平行机台问题，有利于简化我们在建构基算法的程序。以下为我们在建构算法时所需用到的目标值。

3. 基因算法

基因算法中有一组解族群(Population)，就像生物的染色体一般。依照不同类型的问题，可藉由不同的编码方式(Coding)去显示不同的问题特性，而在由适合函数表现染色体解的好坏程度。透过基因算法中的复制(Reproduction)、交配(Crossover)、突变(Mutation)及淘汰的机制，染色体以世代的改进方式，直到达到终止的条件。以下将介绍基因算法的流程与实际编码的过程。

3.1编码方式(Coding)

在进行基因算法时，需将每一个可行解编成一个字符串，字符串必须要能表达出这个可行解的特性，编码的方式大概可分为两种：二进制与实数型。由于平行机台排程的特性，本研究采用实数型编码方式。

3.2复制(Reproduction)

复制的目的是为了找出取代较差父代的染色体，这个运算机制将会找出较佳的染色体，使其可以有较佳的机率保留下来。常用的复制方法有两种，一种是放回的随机抽样(轮盘法)如下，这是将染色体的适合度函数除以所有染色体的适合度函数值的总合，各染色体求出的值称为适合值比率，在依各适合值比率大小随机选取。另一种方法是不放回的随机抽样，是将各染色体的适合度函数除以此代所有染色体的适合度函数值的平均值，求出各染色体的适合值比率，此数值将会有整数值及小数值，整数值代表此染色体至少要被复制几次的部份，小数值利用轮盘法随机被选取要复制的机率。

3.3交配(Crossover)

交配的目的是为了让染色体之间互相交换有用的基因，使新染色体有机会产生组合更高的适合度，以达成不断演化的目的。对实数型编码来说，较常见的交配方法有以下几种。

3.3.1 PMX(Partially Matched Crossover)：

3.3.2 LOX(Linear Order Crossover)：

3.3.3 CX（Cycle Crossover）：

3.3.4 SX（Simple Crossover）：

本研究的编码方是以加工作业的顺序为染色体中的基因排序，因此为了保留下良好染色体中所表示的加工作业顺序，所以本研究采用LOX帮交配方法。

3.4突变(Mutation)

突变也是用来产生子代的一种方法，为了防止复制与交配过程中；忽略有机会在后来的世代找到好解的基因串。以下为常见的突变方式：

3.4.1 邻近两点变换

3.4.2随机两点变换

3.4.3随机三点变换

一般来说，交配率机率可以高，但突变率应低一点，否则有可能破坏找到的优良基因排序。

1. 验证

以下举三个例子验证所做的基因算法结果，交配率为0.92、突变率为0.05，第一个例子(Table1)为7工件3平行机台，得到的的结果(Table2)小优于LST，但与SA一样，第二个例子(Table3) 10工件3平行机台，最后出来的结果(Table4)GA与SA还是一样的，第三个例子(Table5) 30工件3平行机台，运算后的结果(Table6)为GA优于SA所得之演算结果，且GA对最佳解也比SA好，所以用GA来建构PCB厂生产排程是可行的方法。

Table1 7工件3平行机台

工件平行机台1 平行机台2 平行机台3 平均

1 5 7 6 6

2 7 6 5 6

3 2 6 4 4

4 3 4 5 4

5 5 2 5 4

6 2 4 3 3

7 3 3 3 3

Table2 结果

LST SA GA

7个工件数 11 10 10

Table3 10工件3平行机台

工件平行机台1 平行机台2 平行机台3 平均

1 3 4 2 3

2 2 1 3 2

3 7 6 5 6

4 3 4 5 4

5 5 5 5 5

6 8 6 7 7

7 9 8 7 8

8 5 7 6 6

9 2 2 2 2

10 5 6 7 6

Table4 结果

SA GA

10个工件数 25 25

Table5 30工件3平行机台

工件平行机台1 平行机台2 平行机台3 平均

1 3 4 2 3

2 2 1 3 2

3 7 6 5 6

4 3 4 5 4

5 5 5 5 5

6 8 6 7 7

7 9 9 9 9

8 11 15 13 13

9 4 4 4 4

10 13 21 11 12

11 8 11 9 10

12 10 7 7 8

13 24 21 21 22

14 15 9 9 11

15 8 8 8 8

16 24 27 27 26

17 13 15 14 14

18 4 6 8 6

19 19 16 16 17

20 30 25 26 27

21 10 12 11 11

22 18 16 17 17

23 24 25 29 26

24 15 17 16 16

25 7 7 7 7

26 25 24 24 23

27 14 14 17 15

28 18 18 18 18

29 14 16 15 15

30 12 13 14 13

Table6 结果

30工件

平均 GA 42.3

SA 46

BEST GA 41

SA 44

５．参考数据

1. 林淳菁,”应用遗传算法求解不相关平行机台之排程问题”,朝阳科大工业工程与管理硕士论文,2000

2. 曾毓文,”运用系统仿真与遗传算法从事非相关平行机台之研究”,台北科大生产系统工程与管理研究所,2000

3. 张育仁,李庆恩,王立志, ”自我调适的动态排程系统-限制排程、模糊理论和遗传算法的应用”, 工业工程学刊, 第15 卷, 第六期, 1998.

4. L.P.Khoo, T.K.NG.”A Genetic algorithm-baseed planning system for PCB component placement”INT.J. Production Economics 54(1998)321-332

5. E. Guerra,J.R.Villalobos,”A three-dimensional automated visual inspection system for SMT assembly”Computer&Industrial Engineering 40(2001)175-190

6. Colin R. R. “A GENETIC ALGORITHM FOR FLOWSHOP SEQUENCING”, Computer Ops Res.Vol.22 No1,pp.5-13,1995

7. Liu M. ,Wu Cheng, ”A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines”, Artificial Intelligence in Engineering 13(1990)399-4-3

8. Nguyen V. H., Nagendra N. N., “The scheduling problem of PCBs for multiple non-identical parallel machine ”,EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 158 (2004)577-594

9. Moreno, A. A., and Ding, F., “Goal oriented heuristics for the FMSloading (and part type selection)problems”, Proceedings of the ThirdORSA/TIMS Conference on Flexible Manufacturing Systems, 105-110,1989

10. Mukhopadhyay, S. K., B. Maiti and S. Garg, “Heuristic solution tothe scheduling problems in flexible manufacturing systems”, InternationalJournal of Production Research, 29, 2003-2024, 1991.

11. Murata, T. and H., Ishibuchi, ”Performance evaluation of geneticalgorithms for flowshop scheduling problems”, IEEE InternationalConference on Robotics and Automation, 1, 812-817, 1994.

12. Kim, G. H. and C. S. G. Lee, “An evolutionary approach to thejob-shop scheduling problem”, Proceeding IEEE International Conference onRobotics and Automation, 1, 501-506, 1994.

13. Pinedo, M., “Scheduling: theory, algorithms, and systems”,Prentice-Hall, 1995.

14. Gursel , A. S. , Pico, F. and Santiago , A. , “Indentical machine scheduling to minimize the number of tardy jobs when lot-splitting is allowed,” IEEE1996.

15. Nobuo Sannomiya,Hitoshi Iima,”Application of Genetic Algorithm to Scheduling Problem in Manufacturing Processes”,IEEE 1996

深圳市深科特集团

关键字:	PCB抄板 PCB生产 IC解密样机制作芯片解密 pcb板 SMT加工

·上一篇文章： PCB生产-工厂参观

·下一篇文章：没有了

深科特集团——PCB抄板 PCB生产芯片解密 BOM清单制作原理图反推样机调试加工成品量产

业务部　电话：0755-83766239 83766142 82920849(负责PCB抄板,PCB生产,方案设计,IC解密,成品生产等业务)

空气净化机远大空气净化机陈克明面条巴马科养水家用净水壶