管加工中兩機(jī)器協(xié)調(diào)調(diào)度問題

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

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

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

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

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

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