針對(duì)作業(yè)車間調(diào)度問(wèn)題(Job shop scheduling problem,JSP),以優(yōu)化最大完工時(shí)間為目標(biāo),提出一種有效的多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)。鄰域結(jié)構(gòu)真正將JSP求解算法的盲目搜索變得更加科學(xué)有效,同時(shí)移動(dòng)多個(gè)工序是進(jìn)一步提升鄰域結(jié)構(gòu)性能的關(guān)鍵。針對(duì)交換兩個(gè)工序鄰域結(jié)構(gòu),從理論上剖析了如何進(jìn)行多工序聯(lián)動(dòng)能夠優(yōu)化最大完工時(shí)間。對(duì)已有多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)存在的不足進(jìn)行了分析,提出了科學(xué)有效的最多同時(shí)交換3對(duì)工序的多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)。在交換關(guān)鍵工序塊邊緣工序的同時(shí),根據(jù)最早開(kāi)完工時(shí)間查找前移工序的工件前序工序,對(duì)其進(jìn)行前移交換操作,根據(jù)最晚開(kāi)完工時(shí)間查找后移工序的工件后序工序,對(duì)其進(jìn)行后移交換操作。提出了更為寬泛的針對(duì)2個(gè)工序交換操作的可行解保障條件,在此基礎(chǔ)上,擴(kuò)展了同時(shí)交換2對(duì)工序和3對(duì)工序的可行解保障條件。對(duì)JSP基準(zhǔn)算例進(jìn)行測(cè)試,驗(yàn)證了所提鄰域結(jié)構(gòu)具有良好的性能,對(duì)于設(shè)計(jì)更為高效的JSP求解算法具有重要意義。

【文章頁(yè)數(shù)】：15 頁(yè)

【部分圖文】：

圖1ft06算例的一個(gè)調(diào)度解(Cmax=82)

圖1所示為ft06算例的一個(gè)調(diào)度解(Cmax=82)，為了便于分析研究，給出了最早開(kāi)完工時(shí)間甘特圖(便于查看工序頭長(zhǎng)度)和最晚開(kāi)完工時(shí)間甘特圖(便于查看工序尾長(zhǎng)度)，分別如圖1a和1b所示，每臺(tái)機(jī)器上工序的加工順序，以及對(duì)應(yīng)的最大完工時(shí)間Cmax完全相同。矩形框中的數(shù)字(4,2,....

圖2ft06算例CET鄰域結(jié)構(gòu)的一個(gè)鄰域解(交換工序7-26得到，Cmax=84)

在圖2所示的CET鄰域結(jié)構(gòu)操作交換工序7-26基礎(chǔ)上，再交換工序1-25和8-21，得到CET+2MT鄰域結(jié)構(gòu)操作鄰域解如圖3所示。可見(jiàn)，與CET鄰域結(jié)構(gòu)Cmax=84相比，CET+2MT鄰域結(jié)構(gòu)Cmax=83，在CET鄰域結(jié)構(gòu)的基礎(chǔ)上，能夠減小最大完工時(shí)間。但是，CET+2MT....

圖3ft06算例CET+2MT鄰域結(jié)構(gòu)的一個(gè)鄰域解(交換工序1-25,7-26,8-21得到，Cmax=83)

(7)如果JS[u"]=Φ，結(jié)束；否則，設(shè)置u"=JS[u"]，轉(zhuǎn)至步驟(6)。圖4ICET+2MT多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)示意圖

圖4ICET+2MT多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)示意圖

圖3ft06算例CET+2MT鄰域結(jié)構(gòu)的一個(gè)鄰域解(交換工序1-25,7-26,8-21得到，Cmax=83)在圖2所示的CET鄰域結(jié)構(gòu)操作交換工序7-26基礎(chǔ)上，再交換工序1-25和10-15，得到ICET+2MT鄰域結(jié)構(gòu)操作鄰域解如圖5所示。可見(jiàn)，與CET鄰域結(jié)構(gòu)Cmax=....

本文編號(hào)：3925010