分布估計算法求解矩形件排樣優(yōu)化問題

馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮(zhèn)江212003）

分布估計算法求解矩形件排樣優(yōu)化問題

馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮(zhèn)江212003）

矩形件排樣是一個平面二維優(yōu)化布局的問題，由于其眾多的約束條件和計算上的復雜性，在短時間內求其最優(yōu)解相當困難，屬于典型的NP完全問題。針對矩形件排樣問題，本文采取一種改進的最低水平線搜索算法，通過判斷排樣中產生的廢棄空閑區(qū)域的位置關系，對鄰接的空閑區(qū)域進行有效的合并，并結合分布估計算法求解矩形件排樣優(yōu)化問題。最后，通過模擬實驗，采用本文算法求解后矩形板材的利用率為93.75%，充分體現(xiàn)了本文算法的有效性。

優(yōu)化排樣；矩形件；分布估計算法；最低水平線搜索算法

矩形件排樣優(yōu)化的問題[1]是指將不同數(shù)量、大小不一的矩形件按照特定的順序，采取某種排布策略排放到矩形板材上（在本文中，假定矩形板材寬度一定，長度不限），同時滿足特定的約束條件，并且使得板材的利用率能夠最大化[2]。矩形件排樣優(yōu)化的問題廣泛存在于鈑金下料、造紙工業(yè)、玻璃切割、家具生產等現(xiàn)代制造、加工行業(yè)中。當前社會的發(fā)展對于資源的消耗日益增大，特別對于鋼材等工業(yè)原料的需求越來越大。提高原材料的利用率對于保護生態(tài)環(huán)境，提高企業(yè)的生產率進而獲得更大的經濟效益。然而，矩形件排樣優(yōu)化問題屬于NP完全問題，無法在短時間內求得最優(yōu)解。……