pcb廠之生產(chǎn)排程以基因演算法架構(gòu)

1、PCBPCB廠之生產(chǎn)排程以基因算法架構(gòu)廠之生產(chǎn)排程以基因算法架構(gòu)SchedulingOfPCBFactyBuildingByGeicAlgithms曾文宏南臺科技大學工業(yè)管理研究所吳秉威南臺科技大學工業(yè)管理研究所摘要PCB（PrintedCircuitBoard）廠為電子產(chǎn)業(yè)的基礎，一般的電子產(chǎn)品大多數(shù)都含有PCB板在內(nèi)部，如何大量的產(chǎn)出及縮短總完工時間，決定了工廠的利潤來源。一般來說PCB工廠為了要使流程時間縮短，通常都會從機臺的平衡

2、（Balance）、技術(shù)的改良及機臺的更新來著手，往往忽略了排程（Scheduling）在生產(chǎn)規(guī)劃的重要性，而且PCB廠的工廠模式，屬于非等效平行機臺（UnrelatedParallelMachines）為復雜的求解模式，如果以工廠人員手動的排程方法需要花費較多的時間且其解也不一定較佳，本研究以基因算法（GeicAlgithms）建構(gòu)排程的求解模式，利用基因算法的優(yōu)點來解決復雜的排程問題。關鍵詞：關鍵詞：PCB工廠、不相關平行機臺、基因

3、算法1.導論導論在整個制造規(guī)劃和控制系統(tǒng)的架構(gòu)中，由于排程連結(jié)了物料需求規(guī)劃功能和生產(chǎn)現(xiàn)場的執(zhí)行功能，而扮演了重要的角色。排程可以定義為在一段時間內(nèi)，配置可用的資源來處理一群工作，以達到所設定的目標；而目標則可以訂為滿足交期或縮短閑置時間等。為了能有效地達成既定的目標，大量解決排程問題的方法不斷的提出，但直到今天排程問題依然存在且持續(xù)被討論著。在1980年之前，解決排程問題的方法可劃分成兩大類[2]：一是最佳化問題，另一方面則是啟發(fā)式法

4、則。作業(yè)研究可以說是最佳化技術(shù)的典型代表；但是應用最佳化所發(fā)展出來的排程策略，往往會因為過多的假設而變得不切實際，無法實際地應用在真實的制造系統(tǒng)中。至于啟發(fā)式法則典型的代表就是派工法則。啟發(fā)式的優(yōu)點是較簡單且實用，缺點為具有高度的系統(tǒng)和準則的相依性；如Meno和Ding[9]對于排程問題中零件的選取法，提出一套啟發(fā)式的法則。Mukhopadhyay[10]則發(fā)展整合各啟發(fā)式法的排程方法進行排程工作。在1980年代以后，人工智能與最佳化技

5、術(shù)結(jié)合，促成最佳化搜尋技術(shù)的發(fā)展。模擬退火法（SimulatedAnnealing）[11]和遺傳基因演算[11]等均是屬于最佳化搜尋技術(shù)的領域。這類方符號定義：Cmax：工作的總完工時間，ak：機器k的開始加工時間，rj：工作j的底達時間，xjk：工作j指定在機器k加工的百分比（10），pjk：工作j指定在機器k加工的單位處理時間，j：在工作j之后抵達之工作，包含工作j。在工廠中由于工件j在機器k的處理時間相差不多，也就是說Pjk＝P

6、j1＝Pj2……Pjm；所以我們在做基因算法求解時會先將工件j在每一機臺的加工時間求取平均，再以基因算法架構(gòu)求解。當問題以此方法架構(gòu)時就如同平行機臺問題，有利于簡化我們在建構(gòu)基算法的程序。以下為我們在建構(gòu)算法時所需用到的目標值。MinC＝minmax[??njjtjx1)()1(…??njjtjkx1)()(…??njjtjmx1)()(]WhereC＝max[??njjtjx1)()1(…??njjtjkx1)()(…??njjtjm

7、x1)()(]isthemakespanX(ij)t(j)＝jobj在machinei的加工時間t(j)＝jobj的加工時間X(ij)＝01i＝123……nj＝123……n3.基因算法基因算法基因算法中有一組解族群(Population)，就像生物的染色體一般。依照不同類型的問題，可藉由不同的編碼方式(Coding)去顯示不同的問題特性，而在由適合函數(shù)表現(xiàn)染色體解的好壞程度。透過基因算法中的復制(Reproduction)、交配(Cro