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

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

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

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

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

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

6、j1＝Pj2……Pjm；所以我們?cè)谧龌蛩惴ㄇ蠼鈺r(shí)會(huì)先將工件j在每一機(jī)臺(tái)的加工時(shí)間求取平均，再以基因算法架構(gòu)求解。當(dāng)問題以此方法架構(gòu)時(shí)就如同平行機(jī)臺(tái)問題，有利于簡(jiǎn)化我們?cè)诮?gòu)基算法的程序。以下為我們?cè)诮?gòu)算法時(shí)所需用到的目標(biāo)值。MinC＝minmax[??njjtjx1)()1(…??njjtjkx1)()(…??njjtjmx1)()(]WhereC＝max[??njjtjx1)()1(…??njjtjkx1)()(…??njjtjm

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