基本信息
- 項目名稱：
- 帶kick策略的TS算法在電子表面裝貼分配問題中的應用
- 小類：
- 信息技術
- 大類：
- 自然科學類學術論文
- 簡介：
- 作品研究帶有流水線調度和并行調度雙重性質的表面裝貼分配問題，其目標為最小化元器件的貼裝時間。針對該NP難問題，提出了改進型的禁忌搜索算法進行求解。在該算法中，將傳統(tǒng)的禁忌搜索算法融合了序優(yōu)化算法與分散型的kick移動策略。實驗結果表明，此算法能夠有效地搜索出問題的近優(yōu)解，縮短貼裝時間，提高電子組裝的生產效率。
- 詳細介紹：
- 貼裝設備是典型的高利用率設備，實現(xiàn)將元器件貼放在PCB板上。貼片設備一般是流水式的排列在電子組裝生產線中，其價格昂貴，設備維護費用高，一般中小企業(yè)不輕易引入，被認為是電子組裝生產線上的“瓶頸”機器。因此貼片機的貼裝效率直接影響著整個組裝生產線的效率。由于不同類型的貼片機可貼裝的元器件范圍、貼裝速度、貼裝質量上具有不同的特點，因此在貼裝工序中，PCB板和元器件的生產安排有較大的優(yōu)化空間，從而縮短生產完成時間，提高生產效率。 對PCB板和元器件的生產安排包括PCB板的生產順序安排和元器件在不同貼片機上的分配，我們統(tǒng)稱為電子表面貼裝分配問題。該問題是一個強NP難問題。作品利用改進型的禁忌搜索算法去解決該問題。禁忌搜索算法是近年來受到普遍關注的一種高效率的現(xiàn)代智能啟發(fā)式優(yōu)化技術，對解決NP難的組合優(yōu)化問題具有良好的效果。但傳統(tǒng)的禁忌搜索算法存在它本身的缺陷和不足，如對初始解依賴性。作品根據(jù)傳統(tǒng)禁忌搜索算法本身的不足和實際的表面貼裝問題對算法進行改進，融合序優(yōu)化的思想產生初始解和分散型kick移動策略協(xié)助算法跳出局部最優(yōu)解。利用序優(yōu)化的思想產生初始解，盡量彌補禁忌搜索算法對初始解的依賴性；引入分散型的kick移動策略，試圖加強禁忌搜索算法的全局搜索能力。 實驗結果表明，利用本文提出的改進型禁忌搜索算法去解決表面裝貼分配問題可取得良好的效果，其算法結果優(yōu)于多點下降算法和傳統(tǒng)的禁忌搜索算法。此優(yōu)化算法適用于多個貼片機同時工作的情況和各種不同的任務規(guī)模，具有很好的通用性。算法結果對提高電子組裝的生產效率和信息化優(yōu)化管理具有一定的應用價值和現(xiàn)實意義。
作品專業(yè)信息
撰寫目的和基本思路
- 1)撰寫目的: 在可接受的時間內尋找一個近優(yōu)的PCB排序和元器件分配方案，最大限度地縮短貼裝時間，達到提高生產效率的目的。 2)基本思路：采用基于禁忌搜索的智能優(yōu)化算法去解決該問題。在禁忌搜索算法的基礎上，融合序優(yōu)化算法產生初始解和分散型kick策略協(xié)助算法跳出局部最優(yōu)解，盡量彌補了禁忌搜索算法對初始解的依賴性，并試圖加強禁忌搜索算法的全局搜索能力。
科學性、先進性及獨特之處
- 作品所研究問題不是單純的流水線調度或并行調度問題，而是一個新型的帶有流水線調度和并行調度雙重特性的優(yōu)化問題。利用現(xiàn)代智能啟發(fā)式的禁忌搜索算法，并融合了序優(yōu)化思想產生初始解和分散型kick策略協(xié)助算法跳出局部最優(yōu)解，有效地解決此表面貼裝分配問題。所提出的優(yōu)化算法明顯優(yōu)于多點下降算法和傳統(tǒng)的禁忌搜索算法。
應用價值和現(xiàn)實意義
- 貼片機是電子組裝生產線中的關鍵設備，實現(xiàn)元器件在PCB等基板上的貼裝。作品研究元器件在多臺流水放置的貼片機上的分配優(yōu)化問題，對提高生產線效率，對生產線信息化優(yōu)化管理具有一定的實際價值。作品提出的優(yōu)化算法能在可接受的時間內有效地搜索出問題的滿意解，盡可能地縮短貼裝時間。此優(yōu)化算法適用于多臺貼片機流水線排列工作的情況，能解決稍大規(guī)模的電子表面貼裝分配實例，具有較好的通用性和靈活性。
學術論文摘要
- 電子表面貼裝分配問題是在電子組裝過程中出現(xiàn)的生產優(yōu)化問題，其任務是實現(xiàn)對PCB板的排序和元器件在不同貼片機上的分配。該問題具有流水式的并行機調度特點，為NP難問題。為更好地搜索出問題的好解，我們提出了一種改進型禁忌搜索算法，即在傳統(tǒng)禁忌搜索算法的基礎上融合了序優(yōu)化算法特點和分散型kick移動策略。序優(yōu)化算法的應用彌補了禁忌搜索算法對初始解具有較大的依賴性的不足；而分散型kick策略的引入則增強了禁忌搜索算法的全局搜索能力。實驗結果表明，利用本文提出的改進型禁忌搜索算法去解決所研究問題可取得良好的效果。
獲獎情況
- 1）作品獲EI和ISTP檢索，EI檢索號：20091412011861，ISTP檢索號：10416287。 2）作品論文的英文版本已被2008年在中國武漢舉辦的國際會議“IEEE亞太地區(qū)計算智能與工業(yè)應用研討會（IEEE PACIIA 2008）”接收，會議由美國電子和電氣工程師協(xié)會(IEEE)和美國電子和電氣工程協(xié)會工業(yè)電子分會支持 (IEEE IES)，武漢工程大學主辦。 3）第十屆省賽“挑戰(zhàn)杯”一等獎。
鑒定結果
- 在國內公開發(fā)表的中文文獻中，未見涉及“針對電子貼裝工序（具有流水式并行機調度特點）的分配問題，采用kick策略的禁忌搜索算法進行求優(yōu)”的文獻報道。
參考文獻
- 現(xiàn)有技術： 禁忌搜索算法；序優(yōu)化算法；kick移動策略。 １）禁忌搜索算法（TS）：TS的思想是利用存儲結構存儲搜索過程中的信息，在進一步的迭代搜索中盡量避開已搜索路徑，提高搜索的分散性。TS收斂速度快，局部搜索能力強，但對初始解有較強的依賴性。 ２）序優(yōu)化算法（OO）：OO算法通過從解空間中隨機抽取一定數(shù)量的可行解組成表征集合，從而將對解空間的操作轉移到表征集合上以實現(xiàn)優(yōu)化目標，是一種統(tǒng)計優(yōu)化方法。 ３）kick移動策略：kick策略是迭代局部搜索算法中跳出局部最優(yōu)解的搜索策略，當算法陷入局部最優(yōu)解時，對當前局部最優(yōu)解進行移動，產生新的不同于當前解的新解，從而開始新的搜索過程。 技術文獻檢索目錄見附件1。
同類課題研究水平概述
- 表面貼裝工序為電子組裝過程中的關鍵工序，是提高組裝生產線效率的突破點。關于表面貼裝生產優(yōu)化的研究都集中在對單個貼片機的優(yōu)化上，如上海交大對貼片機的貼裝頭路徑優(yōu)化研究[1]，而對生產線上多個貼片機之間的任務安排研究不多。在國外則有相對較多的研究成果，在算法上多采用啟發(fā)式、遺傳算法對問題進行求解，已取得了一些結果。但其研究多是將生產線中元器件的分配問題歸結為并行機調度問題，而忽略了當貼片機流水線排列對元器件分配的影響。 Ji等[2]對多臺不同貼片機上的PCB分配問題進行了研究。論文假設已知元器件類型在機器上的處理時間，由此建立了以最小化表面貼裝完成時間為目標的整數(shù)規(guī)劃模型，提出基于遺傳算法的啟發(fā)式算法進行求解。Ammons等[3]假定已知元器件類型在機器上的估計貼裝時間，建立了整數(shù)規(guī)劃模型，實現(xiàn)對元器件類型在機器上的分配，以最小化表面貼裝的完成時間；并提出了基于鏈處理的啟發(fā)式和基于線性規(guī)劃的分支定界求解。與此研究不同，Kodek 和Krisper[4]另外還考慮了機器的啟動時間，根據(jù)數(shù)學模型提出了問題的下界，構造了有效的分支定界算法搜索近優(yōu)解。Müller-Hannemann和Weihe[5]則研究如何將元器件分配在多工作站上，證明了該問題為NP難問題，提出有效的啟發(fā)式算法獲得問題的近優(yōu)解。 本作品的研究充分考慮了貼片機流水線放置的特性和元器件并行分配的特點，對電子表面貼裝的分配優(yōu)化問題進行研究。在算法研究方面，禁忌搜索算法的發(fā)展已經初步成熟，且其已經被國內外的學者們應用到各式各樣的優(yōu)化問題中去。但是，針對本文所研究的問題，禁忌搜索是否也能夠像其在其他問題中一樣發(fā)揮優(yōu)勢，是一個亟待探討的問題。且國內外的學者們都意識到，禁忌搜索算法本身并不是很完美的，其對初始解的依賴性、其局部搜索的局限性等。因此本作品在嘗試用禁忌搜索算法來解決所研究問題的同時也致力與對算法本身的改進。對算法的改進集中在改進初始解和局部搜索能力上面，將序優(yōu)化思想應用于產生初始解，將迭代局部搜索算法的kick策略融入禁忌搜索算法，提高全局搜索能力。 總的來說，目前關于電子表面貼裝分配問題的研究在國內研究不多，在國外的研究方法也比較單一，因此十分有必要采用新的搜索方法對其進行進一步的研究。 參考文獻見附件2。
