基于遺傳算法的矩形件分層排樣問題研究.pdf

1、基于遺傳算法的基于遺傳算法的矩形件矩形件分層分層排樣問題排樣問題研究研究ResearchftheProblemofRectangularLayerPackingBasedonHybridGeicAlgithm學科專業(yè)：工業(yè)工程研究生：翟鵬飛指導教師：陳衛(wèi)東教授天津大學管理與經(jīng)濟學部二零一二年十二月摘要矩形件優(yōu)化排樣是指在矩形板材上排放多種不同大小規(guī)格的矩形件，這些矩形件不能相互重疊，也不能超出邊界，而板材的利用率達到最大。這一問題廣泛存

2、在于玻璃、家具、鋼材等領域，直接關系著工廠的經(jīng)濟效益。而矩形件排樣問題是一個典型的NP完全問題，至今仍未找到更加合適的解決辦法。本文所涉及矩形件分層排樣問題則和以上矩形件排樣問題相反，在鋼結構加工、家具生產(chǎn)和地板鋪設等行業(yè)會遇到這樣一種問題，需要的目標零件規(guī)格較大，必須由多種不同規(guī)格的矩形板材進行拼接，這同樣是一個NP完全問題，解決這一問題對于諸多行業(yè)都有深遠的意義。針對本文所涉及矩形件分層排樣問題，本文改進BL算法和最低水平線算法設計

3、了分層最低水平線算法進行分層排樣，而選用遺傳算法進行作為全局搜索算法，設計了適應度函數(shù)和環(huán)形交叉算子以改善遺傳算法性能，通過遺傳算法進行全局搜索和分層最低水平線算法的排樣得到矩形件分層排樣問題的優(yōu)化解。本文采用Java進行模擬算法的實現(xiàn)，對工廠提供的實際數(shù)據(jù)進行模擬實驗，將實驗結果進行分析得出了該改進算法的有效性和合理性，突破性的解決了矩形件分層排樣的矩形板材拼接問題。由于矩形件分層排樣問題目前還沒有算法予以解決，因而本文所涉及的實驗結