PCB厂之生产排程以基因算法架

PCB厂之生产排程以基因算法架构

Scheduling Of PCB Factory Building By Genetic Algorithms

曾文宏 南台科技大学工业管理研究所

吴秉威 南台科技大学工业管理研究所

摘要

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

关键词：PCB工厂、不相关平行机台、基因算法

1. 导论

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

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

在1980 年代以后，人工智能与最佳化技术结合，促成最佳化搜寻技术的发展。模拟退火法（Simulated Annealing）[11]和遗传基因演算[11]等均是属于最佳化搜寻技术的领域。这类方法的特性在于能在广大的解答空间（Solution Space）中有效地搜寻到近似最佳解的答案；如Kim 和