PCB厂之生产排程以基因算法架构
Scheduling Of PCB Factory Building By Genetic Algorithms
曾文宏 南台科技大学工业管理研究所
吴秉威 南台科技大学工业管理研究所
摘要
PCB(Printed Circuit Board)厂为电子产业的基础,一般的电子产品大多数都含有PCB板在内部,如何大量的产出及缩短总完工时间,决定了工厂的利润来源.一般来说PCB工厂为了要使流程时间缩短,通常都会从机台的平衡(Balance)、技术的改良及机台的更新来着手,往往忽略了排程(Scheduling)在生产规划的重要性,而且PCB厂的工厂模式,属于非等效平行机台(Unrelated Parallel Machines)为复杂的求解模式,如果以工厂人员手动的排程方法需要花费较多的时间且其解也不一定较佳,本研究以基因算法(Genetic Algorithms)建构排程的求解模式,利用基因算法的优点来解决复杂的排程问题.
关键词:PCB工厂、不相关平行机台、基因算法
导论
在整个制造规划和控制系统的架构中,由于排程连结了物料需求规划功能和生产现场的执行功能,而扮演了重要的角色.排程可以定义为在一段时间内,配置可用的资源来处理一群工作,以达到所设定的目标;而目标则可以订为满足交期或缩短闲置时间等.为了能有效地达成既定的目标,大量解决排程问题的方法不断的提出,但直到今天排程问题依然存在且持续被讨论着.
在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工厂的生产排程与基因算法,为了得到使多个订单能在最短的时间内完工,来换取接更多的订单,使得工厂的盈余增加.
问题描述
一般来说PCB工厂的厂房布置,皆为平行机台的样式,且每一条生产线在微调之后都可以生产任一产品,差别在每一条生产所需花费的时间不同,过去有人以数学规划的方式;再利用LINDO求解,但是只要问题数量大的话,在加上计算机设备不够强,求解时间往往需要很久.非相关平行机台总完工时间最小化排程问题可利用下列线性规划数学模式来表示[14]:
Minz=Cmax ,
s.t.
ak+ ≦ Cmax k ,
=1,j ,
rj+ ≦ Cmax j,k,
xjk ≧ 0 j,k ,
符号定义:
Cmax :工作的总完工时间,
ak :机器k的开始加工时间,

下一页