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


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


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