管加工中兩機(jī)器協(xié)調(diào)調(diào)度問(wèn)題第1頁(yè)，共28頁(yè)，2023年，2月20日，星期三基金項(xiàng)目國(guó)家杰出青年科學(xué)基金(70425003)；國(guó)家自然科學(xué)基金項(xiàng)目(70171030,60274049)；高等學(xué)校優(yōu)秀青年教師教學(xué)科研獎(jiǎng)勵(lì)計(jì)劃(教育司[2002]383).第2頁(yè)，共28頁(yè)，2023年，2月20日，星期三摘要

本文研究大型鋼鐵加工企業(yè)管加工廠生產(chǎn)作業(yè)中存在的一種工件分解類型的生產(chǎn)調(diào)度問(wèn)題，其特點(diǎn)為一個(gè)工件（母件）經(jīng)過(guò)切管機(jī)后被切成多個(gè)子件，母件和子件分別在兩個(gè)工序?qū)?yīng)的設(shè)備上（每個(gè)工序假設(shè)只有一個(gè)設(shè)備）進(jìn)行加工，文中考慮的機(jī)器環(huán)境是二機(jī)流水車間，目標(biāo)函數(shù)是所有工件最大完成時(shí)間最小。第3頁(yè)，共28頁(yè)，2023年，2月20日，星期三摘要傳統(tǒng)生產(chǎn)調(diào)度都是工件裝配類型或者工件類型不變，本文研究的調(diào)度問(wèn)題與傳統(tǒng)問(wèn)題不同，屬于分解類型的調(diào)度，不僅需要確定母件在切管機(jī)上的排序，同時(shí)要考慮母件在切管機(jī)上切出各個(gè)子管的先后順序。第4頁(yè)，共28頁(yè)，2023年，2月20日，星期三摘要根據(jù)母件分解成子件的數(shù)目不同，把問(wèn)題分成為兩類：一類是所有母件分解成子件的數(shù)目相同；一類是母件分解成子件的數(shù)目任意。對(duì)于這兩類問(wèn)題又分別就下面的幾種情況進(jìn)行分析：子件同時(shí)產(chǎn)生；子件不同時(shí)產(chǎn)生、母件的加工不可中斷；母件加工可中斷、母件間的切換有一個(gè)常數(shù)時(shí)間。第5頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言本文研究的問(wèn)題描述如下：考慮工件分解型的調(diào)度問(wèn)題，機(jī)器環(huán)境是二機(jī)流水車間，一個(gè)工件(母件)在經(jīng)過(guò)第一臺(tái)機(jī)器時(shí)裂變出多個(gè)工件(子件)，考慮的目標(biāo)函數(shù)是所有工件的最大完成時(shí)間最小。調(diào)度需要確定每個(gè)工件(母件)在切管機(jī)上的加工順序，以及母件的每個(gè)子件產(chǎn)生的順序。第6頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言本文研究的問(wèn)題是以鋼鐵加工企業(yè)鋼管廠為背景，研究套管加工流程中切管機(jī)和下游機(jī)器的協(xié)調(diào)調(diào)度，如圖1所示。從上游工序產(chǎn)生出的毛管很長(zhǎng)，要經(jīng)過(guò)切管機(jī)把毛管切成適當(dāng)長(zhǎng)度的子管，然后繼續(xù)在下游的機(jī)器上進(jìn)行倒棱、接箍擰緊、通徑、涂漆等工序，最后形成成品套管。第7頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言圖１：管加工廠流程切管機(jī)熱處理中間庫(kù)成品庫(kù)套管加工第8頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言鋼鐵企業(yè)使用的都是大型設(shè)備，提高設(shè)備的利用率是關(guān)鍵的指標(biāo)，因此本文研究的調(diào)度問(wèn)題以求工件最大完成時(shí)間最小化作為目標(biāo)函數(shù)。第9頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言文中研究的工件是分解類型的，工件數(shù)目經(jīng)過(guò)切管機(jī)后發(fā)生變化，并且母件每產(chǎn)生出一個(gè)子件都可以開(kāi)始在下游的機(jī)器上加工，而不用等其所有子件全部產(chǎn)生在開(kāi)始在第二臺(tái)機(jī)器上加工，因此問(wèn)題與傳統(tǒng)的二機(jī)流水問(wèn)題不同，不能直接由Johnson規(guī)則得到最優(yōu)解。第10頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言在以往的文獻(xiàn)中，有許多研究的是流水車間環(huán)境下求最大完成時(shí)間最小問(wèn)題，調(diào)度的類型都是工件類型不變，在此對(duì)其進(jìn)行簡(jiǎn)單的綜述。Sung

和Kim[2]研究的二機(jī)流水車間求最大完成時(shí)間問(wèn)題，允許工件有動(dòng)態(tài)的到達(dá)時(shí)間；Lin

和Cheng[3]研究的二機(jī)流水車間求最大完成時(shí)間是批調(diào)度問(wèn)題；Allahverdi[4]論文考慮的流水車間問(wèn)題，目標(biāo)函數(shù)是最大完成時(shí)間與平均流水時(shí)間的加權(quán)求和。

第11頁(yè)，共28頁(yè)，2023年，2月20日，星期三引言還有一些文獻(xiàn)研究流水車間裝配類型的調(diào)度問(wèn)題：Koulamas和Kyparisis[5]研究三機(jī)流水裝配車間問(wèn)題,目標(biāo)函數(shù)是最大完成時(shí)間,還有Yang[6]，Yakoyama和masao[7]研究的也是裝配工件的調(diào)度問(wèn)題。Lee[8]考慮具有裝配類型特征的分解工件調(diào)度問(wèn)題，目標(biāo)函數(shù)是多個(gè)費(fèi)用和最小，給出問(wèn)題的啟發(fā)式算法，并分析界。第12頁(yè)，共28頁(yè)，2023年，2月20日，星期三協(xié)調(diào)問(wèn)題首先給出這一部分考慮的協(xié)調(diào)問(wèn)題都要用到的一條性質(zhì)。性質(zhì)1：對(duì)于文中提出的問(wèn)題，如果可以得到最小值，總是可以通過(guò)使所有工件在兩機(jī)器上的加工順序相同得到。由性質(zhì)1，文中研究的問(wèn)題總是認(rèn)為所有子件在二臺(tái)機(jī)器上加工順序相同。第13頁(yè)，共28頁(yè)，2023年，2月20日，星期三協(xié)調(diào)問(wèn)題引理：如果問(wèn)題有最優(yōu)解，總是可以通過(guò)使第一個(gè)機(jī)器上沒(méi)有閑置時(shí)間而得到。證明：如果問(wèn)題的最優(yōu)解中，工件在機(jī)器一上的加工有閑置，移動(dòng)工件，使機(jī)器一上的加工沒(méi)有閑置，問(wèn)題的目標(biāo)函數(shù)值不會(huì)增大。由引理，我們?cè)谙旅娴亩ɡ碜C明中認(rèn)為工件在第一個(gè)機(jī)器上沒(méi)有閑置時(shí)間。即工件在第一臺(tái)機(jī)器上的加工是連續(xù)的。第14頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同

這一部分中，研究母件個(gè)數(shù)為，每個(gè)母件經(jīng)過(guò)切管機(jī)裂變出的子工件個(gè)數(shù)均為。首先考慮母件經(jīng)過(guò)切管機(jī)同時(shí)裂變出所有的子工件，這個(gè)問(wèn)題總可以看作是一般意義上的二機(jī)流水求最小完成時(shí)間問(wèn)題，母件在第兩臺(tái)機(jī)器上的處理時(shí)間為其所有子件的處理時(shí)間之和。按照求解問(wèn)題的Johnson規(guī)則求出問(wèn)題的最優(yōu)解。第15頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同接下來(lái)考慮母件裂變子工件有確定處理時(shí)間，母件在第一臺(tái)機(jī)器上的加工不可中斷問(wèn)題。就一些特殊的情況給出求解問(wèn)題的最優(yōu)算法。性質(zhì)2：當(dāng)，對(duì)所有的，都成立，要得最大完成時(shí)間最小，這時(shí)只要把滿足的母件安排在所有母件的最后位置加工，同時(shí)其中的第個(gè)子件安排在其所有子件的最后位置加工即可。其他母件、子件的順序任意。證明略。第16頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同性質(zhì)3：當(dāng),對(duì)所有的，都成立。這時(shí)要得最大完成時(shí)間到最小，只要把滿足的母件安排在所有母件的第一個(gè)位置加工，同時(shí)其第個(gè)子件安排在其所有子件的第一個(gè)位置加工即可。其他母件、子件的順序任意。證明略。第17頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同下面考慮在切管機(jī)在還沒(méi)有切出一個(gè)母件的所有子件時(shí)，可以改切另一個(gè)母件，求最大完成時(shí)間最小問(wèn)題。這里切管機(jī)上母件的切換有一個(gè)常數(shù)的切換時(shí)間。下面給出一個(gè)多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法。第18頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同設(shè)函數(shù)為第二臺(tái)機(jī)器加工了個(gè)子工件的完成時(shí)間，其中表示第二臺(tái)機(jī)器加工的最后一個(gè)子工件是由第個(gè)母件產(chǎn)生的。，為切管機(jī)上切換一個(gè)母件的時(shí)間，為已經(jīng)產(chǎn)生出至少一個(gè)子工件的母件集合，為沒(méi)有加工過(guò)的母件集合，為第一臺(tái)機(jī)器上產(chǎn)生了個(gè)子工件的完成時(shí)間，。，其中表示由第個(gè)母件產(chǎn)生，并且已經(jīng)加工完的子件集合，表示第個(gè)母件還未裂變出的子件集合。第19頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)相同初始值遞歸函數(shù)最優(yōu)解第20頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意首先考慮如果母件經(jīng)過(guò)切管機(jī)同時(shí)產(chǎn)生出所有的子工件，這個(gè)問(wèn)題仍然可以看作是一般意義上的二機(jī)流水問(wèn)題。這時(shí)按照求解問(wèn)題的Johnson規(guī)則求出問(wèn)題的最優(yōu)解。第21頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意接下來(lái)考慮如果每個(gè)子件的產(chǎn)生都有一個(gè)確定的時(shí)間，問(wèn)題是一般意義NP難的，問(wèn)題的證明是由最小平方和問(wèn)題歸約得到的。最小平方和問(wèn)題：有限集A,每個(gè)的大小,正整數(shù)和J。問(wèn)：A是否能劃分成K個(gè)不相交的集合，使得？定理1：對(duì)于母件每產(chǎn)生一個(gè)子工件都有一個(gè)確定的時(shí)間，母件加工不可中斷，母件產(chǎn)生子件個(gè)數(shù)任意，求最小的問(wèn)題是一般意義NP難問(wèn)題。第22頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意證明：構(gòu)造調(diào)度的例子如下，母管的個(gè)數(shù)為K，每個(gè)母管切出的子管個(gè)數(shù)分別為，第j個(gè)母管經(jīng)過(guò)第一臺(tái)機(jī)器切出的所有子工件的處理時(shí)間分別為0，，所有工件在第二臺(tái)機(jī)器上的處理時(shí)間只有第一個(gè)工件的處理時(shí)間為，其余工件的處理時(shí)間都為0，調(diào)度的門檻值設(shè)為J。第23頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意如果最小平方和問(wèn)題有解，可見(jiàn)目標(biāo)函數(shù)值不超過(guò)J。反過(guò)來(lái)如果門檻值不超過(guò)J，由于，可知必有。調(diào)度函數(shù)值即為工件在第二臺(tái)機(jī)器上處理時(shí)間之和。必有。問(wèn)題得證。第24頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意在切管機(jī)在還沒(méi)有切出一個(gè)母件的所有子件時(shí)，可以改切另一個(gè)母件，求最小問(wèn)題。這里切管機(jī)上母件的切換有一個(gè)常數(shù)的切換時(shí)間。母件個(gè)數(shù)為n個(gè)，設(shè)函數(shù)為第二臺(tái)機(jī)器加工了i個(gè)子工件的完成時(shí)間，、和的定義同上，N、t、、、、、的定義同上，為第k個(gè)工件裂變出的工件數(shù)，，定義這里給出一個(gè)母件產(chǎn)生任意多個(gè)子工件的擬多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法。第25頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意初始值遞歸函數(shù)最優(yōu)解第26頁(yè)，共28頁(yè)，2023年，2月20日，星期三母件分解子件個(gè)數(shù)任意定理：這個(gè)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜性為。證明：狀態(tài)變量有Ln個(gè)，循環(huán)所用的時(shí)間最大為第二項(xiàng)，不會(huì)超過(guò)，算法的時(shí)間復(fù)雜性為。第27頁(yè)，共28頁(yè)