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

1、管加工中兩機(jī)器協(xié)調(diào)調(diào)度問題第1頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二基金項(xiàng)目國家杰出青年科學(xué)基金(70425003)；國家自然科學(xué)基金項(xiàng)目(70171030, 60274049)；高等學(xué)校優(yōu)秀青年教師教學(xué)科研獎(jiǎng)勵(lì)計(jì)劃(教育司2002383) .第2頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二摘 要 本文研究大型鋼鐵加工企業(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í)間

2、最小。第3頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二摘 要傳統(tǒng)生產(chǎn)調(diào)度都是工件裝配類型或者工件類型不變，本文研究的調(diào)度問題與傳統(tǒng)問題不同，屬于分解類型的調(diào)度，不僅需要確定母件在切管機(jī)上的排序，同時(shí)要考慮母件在切管機(jī)上切出各個(gè)子管的先后順序。第4頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二摘 要根據(jù)母件分解成子件的數(shù)目不同，把問題分成為兩類：一類是所有母件分解成子件的數(shù)目相同；一類是母件分解成子件的數(shù)目任意。對于這兩類問題又分別就下面的幾種情況進(jìn)行分析： 子件同時(shí)產(chǎn)生； 子件不同時(shí)產(chǎn)生、母件的加工不可中斷； 母件加工可中斷、母件間的切換有一個(gè)常數(shù) 時(shí)間。第5頁，共28頁

3、，2022年，5月20日，6點(diǎn)15分，星期二引言本文研究的問題描述如下：考慮工件分解型的調(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)生的順序。第6頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言本文研究的問題是以鋼鐵加工企業(yè)鋼管廠為背景，研究套管加工流程中切管機(jī)和下游機(jī)器的協(xié)調(diào)調(diào)度，如圖1所示。從上游工序產(chǎn)生出的毛管很長，要經(jīng)過切管機(jī)把毛管切成適當(dāng)長度的子管，然后繼續(xù)在下游的機(jī)器上進(jìn)行倒棱、接箍擰緊、通徑、涂漆等工序，最后

4、形成成品套管。第7頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言 圖：管加工廠流程切管機(jī) 熱處理 中間庫 成品庫 套管加工第8頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言鋼鐵企業(yè)使用的都是大型設(shè)備，提高設(shè)備的利用率是關(guān)鍵的指標(biāo)，因此本文研究的調(diào)度問題以求工件最大完成時(shí)間最小化作為目標(biāo)函數(shù)。 第9頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言文中研究的工件是分解類型的，工件數(shù)目經(jīng)過切管機(jī)后發(fā)生變化，并且母件每產(chǎn)生出一個(gè)子件都可以開始在下游的機(jī)器上加工，而不用等其所有子件全部產(chǎn)生在開始在第二臺(tái)機(jī)器上加工，因此問題與傳統(tǒng)的二機(jī)流水問題不同，不能直接由Joh

5、nson規(guī)則得到最優(yōu)解。第10頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言在以往的文獻(xiàn)中，有許多研究的是流水車間環(huán)境下求最大完成時(shí)間最小問題，調(diào)度的類型都是工件類型不變，在此對其進(jìn)行簡單的綜述。Sung 和 Kim2研究的二機(jī)流水車間求最大完成時(shí)間問題，允許工件有動(dòng)態(tài)的到達(dá)時(shí)間；Lin 和 Cheng3研究的二機(jī)流水車間求最大完成時(shí)間是批調(diào)度問題；Allahverdi4論文考慮的流水車間問題，目標(biāo)函數(shù)是最大完成時(shí)間與平均流水時(shí)間的加權(quán)求和。 第11頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二引言還有一些文獻(xiàn)研究流水車間裝配類型的調(diào)度問題：Koulamas 和 Kyp

6、arisis5研究三機(jī)流水裝配車間問題,目標(biāo)函數(shù)是最大完成時(shí)間,還有Yang6， Yakoyama和 masao7研究的也是裝配工件的調(diào)度問題。Lee8考慮具有裝配類型特征的分解工件調(diào)度問題，目標(biāo)函數(shù)是多個(gè)費(fèi)用和最小，給出問題的啟發(fā)式算法，并分析界。第12頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二協(xié)調(diào)問題首先給出這一部分考慮的協(xié)調(diào)問題都要用到的一條性質(zhì)。性質(zhì)1：對于文中提出的問題，如果可以得到最小值，總是可以通過使所有工件在兩機(jī)器上的加工順序相同得到。由性質(zhì)1，文中研究的問題總是認(rèn)為所有子件在二臺(tái)機(jī)器上加工順序相同。第13頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二協(xié)

7、調(diào)問題引理：如果問題有最優(yōu)解，總是可以通過使第一個(gè)機(jī)器上沒有閑置時(shí)間而得到。證明：如果問題的最優(yōu)解中，工件在機(jī)器一上的加工有閑置，移動(dòng)工件，使機(jī)器一上的加工沒有閑置，問題的目標(biāo)函數(shù)值不會(huì)增大。由引理，我們在下面的定理證明中認(rèn)為工件在第一個(gè)機(jī)器上沒有閑置時(shí)間。即工件在第一臺(tái)機(jī)器上的加工是連續(xù)的。第14頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同 這一部分中，研究母件個(gè)數(shù)為 ，每個(gè)母件經(jīng)過切管機(jī)裂變出的子工件個(gè)數(shù)均為 。首先考慮母件經(jīng)過切管機(jī)同時(shí)裂變出所有的子工件，這個(gè)問題總可以看作是一般意義上的二機(jī)流水求最小完成時(shí)間問題，母件在第兩臺(tái)機(jī)器上的處理時(shí)間為其所有子件的

8、處理時(shí)間之和。按照求解問題的Johnson規(guī)則求出問題的最優(yōu)解。第15頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同接下來考慮母件裂變子工件有確定處理時(shí)間，母件在第一臺(tái)機(jī)器上的加工不可中斷問題。就一些特殊的情況給出求解問題的最優(yōu)算法。性質(zhì)2：當(dāng) ，對所有的， 都成立，要得最大完成時(shí)間最小，這時(shí)只要把滿足 的母件 安排在所有母件的最后位置加工，同時(shí)其中的第 個(gè)子件安排在其所有子件的最后位置加工即可。其他母件、子件的順序任意。證明略。 第16頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同性質(zhì)3：當(dāng) ,對所有的 ， 都成立。這時(shí)要得最大完成

9、時(shí)間到最小，只要把滿足 的母件 安排在所有母件的第一個(gè)位置加工，同時(shí)其第 個(gè)子件安排在其所有子件的第一個(gè)位置加工即可。其他母件、子件的順序任意。證明略。 第17頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同下面考慮在切管機(jī)在還沒有切出一個(gè)母件的所有子件時(shí)，可以改切另一個(gè)母件，求最大完成時(shí)間最小問題。這里切管機(jī)上母件的切換有一個(gè)常數(shù)的切換時(shí)間。下面給出一個(gè)多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法。第18頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同設(shè)函數(shù) 為第二臺(tái)機(jī)器加工了 個(gè)子工件的完成時(shí)間，其中 表示第二臺(tái)機(jī)器加工的最后一個(gè)子工件是由第 個(gè)母件產(chǎn)生的

10、。 ， 為切管機(jī)上切換一個(gè)母件的時(shí)間， 為已經(jīng)產(chǎn)生出至少一個(gè)子工件的母件集合， 為沒有加工過的母件集合， 為第一臺(tái)機(jī)器上產(chǎn)生了 個(gè)子工件的完成時(shí)間， 。 ，其中 表示由第 個(gè)母件產(chǎn)生，并且已經(jīng)加工完的子件集合， 表示第 個(gè)母件還未裂變出的子件集合。 第19頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)相同初始值遞歸函數(shù)最優(yōu)解第20頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意首先考慮如果母件經(jīng)過切管機(jī)同時(shí)產(chǎn)生出所有的子工件，這個(gè)問題仍然可以看作是一般意義上的 二機(jī)流水問題。這時(shí)按照求解問題的Johnson規(guī)則求出問題的最優(yōu)解。第21頁，共

11、28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意接下來考慮如果每個(gè)子件的產(chǎn)生都有一個(gè)確定的時(shí)間，問題是一般意義NP難的，問題的證明是由最小平方和問題歸約得到的。最小平方和問題： 有限集A,每個(gè) 的大小 ,正整數(shù) 和J。問：A是否能劃分成K個(gè)不相交的集合 ，使得 ？定理 1：對于母件每產(chǎn)生一個(gè)子工件都有一個(gè)確定的時(shí)間，母件加工不可中斷，母件產(chǎn)生子件個(gè)數(shù)任意，求 最小的問題是一般意義NP難問題。第22頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意證明：構(gòu)造調(diào)度的例子如下，母管的個(gè)數(shù)為K，每個(gè)母管切出的子管個(gè)數(shù)分別為 ，第j個(gè)母管經(jīng)過第一臺(tái)機(jī)器切出

12、的所有子工件的處理時(shí)間分別為0， ，所有工件在第二臺(tái)機(jī)器上的處理時(shí)間只有第一個(gè)工件的處理時(shí)間為 ，其余工件的處理時(shí)間都為0，調(diào)度的門檻值設(shè)為J。第23頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意如果最小平方和問題有解，可見目標(biāo)函數(shù)值不超過J。反過來如果門檻值不超過J，由于 ，可知必有 。調(diào)度函數(shù)值即為工件在第二臺(tái)機(jī)器上處理時(shí)間之和。必有 。問題得證。第24頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意在切管機(jī)在還沒有切出一個(gè)母件的所有子件時(shí)，可以改切另一個(gè)母件，求 最小問題。這里切管機(jī)上母件的切換有一個(gè)常數(shù)的切換時(shí)間。母件個(gè)數(shù)為n個(gè)

13、，設(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頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意初始值遞歸函數(shù)最優(yōu)解第26頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二母件分解子件個(gè)數(shù)任意定理：這個(gè)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜性為 。證明：狀態(tài)變量有Ln個(gè)，循環(huán)所用的時(shí)間最大為第二項(xiàng)，不會(huì)超過 ，算法的時(shí)間復(fù)雜性為 。第27頁，共28頁，2022年，5月20日，6點(diǎn)15分，星期二結(jié)束語本文研究的是一種