流水作業(yè)生產(chǎn)線上工件的加工問題
頁數(shù) 18 字數(shù) 7484
摘要
作為經(jīng)典排序問題的推廣, 處理機的排序問題具有廣泛的實際背景.對于目標函數(shù)是極小化排序時間表長度的情況,可以采用多種的討論方式。
此文中根據(jù)所提的問題分別采用了各種不同的方法，對問題進行描述與解答，力求通過算法的多樣性對問題能夠得到最優(yōu)解或近似最優(yōu)解。
第一問為n/2排序問題，利用JOHNSON法則，最優(yōu)子結(jié)構(gòu)定理和遞歸算法給出一組最優(yōu)排序，在JOHNSON法則的基礎(chǔ)上可以用遺傳算法和模擬退火算法綜合利用，最終確定最優(yōu)的排序。
第二問對于當(dāng)m=3,m=4即機器數(shù)為3和4時，對機器數(shù)為3采用分支定界法、整數(shù)規(guī)劃法求解，對于機器數(shù)為4時，實際生產(chǎn)中的排序問題可以采用啟發(fā)式算法。對于此問題，在此采用了Palmer算法。同時也能用CDS法進行求解。
第三問m/n排序問題，確定給定的任意一個工件序，用遞歸算法，隨機產(chǎn)生一組順序S={S1,S2,……,Sn}集合,按順序S={S1,S2,……,Sn}列出加工矩陣，對于第一行第一列，只需把加工時間的數(shù)值作為完工時間標在加工時間的右上角，對于第一行元素，只需從左到右依次將前一列右上角的數(shù)字加上計算列的加工時間，將其結(jié)果填在計算列加工時間的右上角。對于從第2行到第m行，第一列的算法相同。只要把上一行右上角的數(shù)字和本行的加工時間相加，將結(jié)果填在本行加工時間的右上角；從第2列到第n列，則要從本行前一列右上角和本上一行的右上角數(shù)字取最大者，再和本列加工時間相加，將結(jié)果填在本列加工時間得右上角，這樣計算下去，最后一行的最后一列右上角數(shù)字即是Cmsn 。


關(guān)鍵字 JOHNSON法則，CDS法，最優(yōu)子結(jié)構(gòu)，遺傳算法，模擬退火算法 Gantt圖，遞歸算法 螞蟻算法 分支定界


參考文獻
1、生產(chǎn)計劃與控制 潘爾順 上海交通大學(xué)出版社 2003
2、數(shù)學(xué)模型 洪毅 林健良 陶志穗 高等教育出版社 2004
3、并行分布計算中的調(diào)度算法理論與設(shè)計 何炎祥 朱福喜 武漢大學(xué)出版社 2003
4、生產(chǎn)主管一日通 吳少平 廣東經(jīng)濟出版社 2004
5、Production and Operations Management (Manufacturing and Services) Richard B.Chase Nicholas J.aquilano F.Robert Jacobs McGraw-Hill