亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        運(yùn)輸與倒垛集成的多吊機(jī)調(diào)度問(wèn)題

        2014-03-25 01:49:26李彥平
        關(guān)鍵詞:下界吊機(jī)工件

        謝 謝, 李彥平

        (沈陽(yáng)大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽(yáng) 110044)

        本文研究了在鋼鐵企業(yè)鋼卷倉(cāng)庫(kù)中出現(xiàn)的一個(gè)問(wèn)題,如圖1所示.一些成品或半成品板卷已經(jīng)被存放在倉(cāng)庫(kù)中等待被客戶或下道工序選擇.根據(jù)實(shí)際存儲(chǔ)的需求,每個(gè)板卷已經(jīng)被放在了預(yù)先指定的按兩層擺放的位置上.如果一個(gè)需求板卷在上層或無(wú)板卷阻礙的下層,它可以被直接運(yùn)輸?shù)街付ㄎ恢?如果一個(gè)需求板卷在下層并且由上層的一個(gè)或兩個(gè)板卷阻礙,直到阻礙板卷需要被運(yùn)到另外的位置后,它才能被運(yùn)輸?shù)街付ㄎ恢?為了便于描述問(wèn)題,前一種情況稱為運(yùn)輸操作,后一種情況稱為倒垛操作.這兩種操作都由貴重的設(shè)備即上方移動(dòng)的許多吊機(jī)實(shí)施.目的就是確定一個(gè)聯(lián)合運(yùn)輸和倒垛操作的多吊機(jī)調(diào)度,使得所有的需求板卷盡快被運(yùn)輸?shù)街付ㄎ恢?同時(shí)確定每個(gè)阻礙板卷需要倒垛的位置.這個(gè)問(wèn)題經(jīng)常出現(xiàn)于存儲(chǔ)成品或半成品板卷的鋼鐵企業(yè)倉(cāng)庫(kù)中,如熱軋后庫(kù)、熱鍍鋅原料庫(kù)、酸洗原料庫(kù)和酸軋后庫(kù).另外,在集裝箱終端的垛場(chǎng)和造船廠原料庫(kù)也存在該問(wèn)題.然而,現(xiàn)有的文獻(xiàn)幾乎沒(méi)有研究該問(wèn)題的.

        圖1 鋼鐵企業(yè)生產(chǎn)物流圖Fig.1 Production and logistics flow chart in iron and steel enterprises

        該問(wèn)題通常如下描述. 給定一些位于倉(cāng)庫(kù)某區(qū)中的候選板卷.一旦收到來(lái)自客戶和生產(chǎn)線的需求板卷列表,這些板卷由處于上方的覆蓋該區(qū)的雙向跨上的一些吊機(jī)實(shí)施操作,如圖2所示.為了方便描述,定義一個(gè)板卷為一個(gè)工件.每個(gè)吊機(jī)從一個(gè)地方移動(dòng)到另一個(gè)地方意味著它的提起設(shè)備(吊鉤)隨著吊機(jī)不僅沿著平行的跨移動(dòng),而且在跨之間移動(dòng),兩方向的移動(dòng)是同時(shí)進(jìn)行的.本文中,將吊鉤看作吊機(jī).本文研究在避免吊機(jī)碰撞的約束下,決策聯(lián)合運(yùn)輸操作和倒垛操作以最小化最后一個(gè)需求板卷被運(yùn)輸?shù)街付ㄎ恢玫耐瓿蓵r(shí)間(makespan).

        圖2 鋼卷倉(cāng)庫(kù)一個(gè)區(qū)域的板卷存儲(chǔ)Fig. 2 Coil storage in a block of steel coil warehouse

        有關(guān)吊機(jī)調(diào)度的文獻(xiàn)通常僅考慮吊機(jī)的一種操作[如集裝箱碼頭的岸吊(QC)或場(chǎng)吊(YC)調(diào)度和電鍍生產(chǎn)線中的吊機(jī)(HS)調(diào)度],并沒(méi)有考慮多吊機(jī)的運(yùn)輸與倒垛的集成操作.一些研究致力于和其他設(shè)備的集成研究以調(diào)度吊機(jī)[1-5]. 一些研究?jī)H致力于研究?jī)膳_(tái)或多吊機(jī)調(diào)度問(wèn)題.Lei和Wang[6]提出了兩臺(tái)吊機(jī)周期調(diào)度的一個(gè)算法.他們通過(guò)劃分兩個(gè)區(qū)域?qū)⒚颗_(tái)吊機(jī)分配給專門的區(qū)域進(jìn)行研究,然而連續(xù)的相鄰兩區(qū)不能保證吊機(jī)之間不碰撞.Armstrong等[7]提出了一個(gè)貪婪搜索算法以確定吊機(jī)的最小數(shù)目.Liu和Jiang[8]研究了工件具有固定加工時(shí)間和移動(dòng)時(shí)間的兩臺(tái)吊機(jī)調(diào)度問(wèn)題,提出了一個(gè)多項(xiàng)式時(shí)間最優(yōu)算法.Zhou和Liu[9]提出了解決具有重疊區(qū)域的兩臺(tái)吊機(jī)周期調(diào)度問(wèn)題的一個(gè)啟發(fā)式算法.對(duì)于多吊機(jī)調(diào)度問(wèn)題,Varnier 等[10]使用約束邏輯規(guī)劃的方法確定當(dāng)給定吊機(jī)分配時(shí)的最優(yōu)調(diào)度.Jiang和Liu[11]提出了具有固定加工時(shí)間和移動(dòng)時(shí)間的多吊機(jī)問(wèn)題的多項(xiàng)式時(shí)間最優(yōu)算法.

        然而,之前提及的這些問(wèn)題或者是本文考慮問(wèn)題的特殊情況,或者與本文研究的問(wèn)題不同.研究目的就是減少存儲(chǔ)時(shí)間,但并沒(méi)有同時(shí)考慮到吊機(jī)的運(yùn)輸?shù)苟饧烧{(diào)度.盡管有一些研究主要考慮倒垛,但在這些問(wèn)題中,工件按照每個(gè)工件上僅有一個(gè)工件阻礙的方式堆放,比起上述研究的問(wèn)題簡(jiǎn)單得多.此外,大部分的研究主要考慮單吊機(jī)調(diào)度,多吊機(jī)調(diào)度問(wèn)題研究得相對(duì)較少.大多數(shù)研究主要考慮智能計(jì)算以獲得近優(yōu)解,很少有研究對(duì)吊機(jī)調(diào)度問(wèn)題進(jìn)行理論分析.因此,大部分文獻(xiàn)不能直接應(yīng)用于解決上述問(wèn)題.該問(wèn)題有如下兩個(gè)特點(diǎn):吊機(jī)操作集成了運(yùn)輸和倒垛兩道工序;協(xié)調(diào)調(diào)度吊機(jī),避免相鄰吊機(jī)之間碰撞.這需要在考慮問(wèn)題特點(diǎn)和約束的基礎(chǔ)上提出新的算法.

        1 問(wèn)題的符號(hào)和分析

        2 問(wèn)題模型

        為了更清晰地描述上面描述的問(wèn)題,在這部分中,提出了一個(gè)混合整線性規(guī)劃模型(MILP).

        2.1 問(wèn)題參數(shù)

        輸入數(shù)據(jù)如下.

        μ對(duì)應(yīng)于吊機(jī)上提和下放一個(gè)工件的時(shí)間.

        v1,v2和λ1,λ2對(duì)應(yīng)于吊機(jī)帶著工件和不帶工件沿著兩個(gè)方向移動(dòng)的速度 ,為了表達(dá)方便,本文中,令λ=min{λ1,λ2},v=min{v1,v2}.不失一般性,假設(shè)λ≥v≥1.

        A是一個(gè)很大的正整數(shù).

        決策變量如下:

        xmij=1,如果工件Ji被吊機(jī)m倒到工件Jj的位置(Ji,Jj∈Ω0,m∈M);否則,xmij=0.

        zij=1,如果工件Jj的一道工序(倒垛或運(yùn)輸)在工件Ji的一道工序(倒垛或運(yùn)輸)結(jié)束后開(kāi)始(Ji,Jj∈Ω0);否則,zij=0.

        smi,吊機(jī)m(m∈M)從工件Ji的位置移動(dòng)的開(kāi)始時(shí)間(Ji∈Ω或Ji∈Ω0).根據(jù)吊機(jī)的移動(dòng)可知,如果吊機(jī)帶著工件開(kāi)始移動(dòng),這是裝載移動(dòng)的開(kāi)始時(shí)間;否則,是空移動(dòng)的開(kāi)始時(shí)間.

        emi,吊機(jī)m(m∈M)將工件Ji(Ji∈Ω0)倒垛后的結(jié)束時(shí)間.

        Cmax,最后一個(gè)工件被運(yùn)到指定位置的完成時(shí)間.

        2.2 數(shù)學(xué)模型

        問(wèn)題的數(shù)學(xué)模型表示如下:

        minCmax=max{Ci|Ji∈Ω}.

        (1)

        s.t.

        (2)

        (3)

        (4)

        (5)

        (6)

        (7)

        (?Ji,Jj∈Ω0,?m∈M);

        (8)

        (?Ji∈Ω0,Jj∈Ω,?m∈M);

        (9)

        (?Ji∈Ω,Jj∈Ω0,?m∈M);

        (10)

        (?Ji,Jj∈Ω0,?m∈M);

        (11)

        (?Ji,Jj∈Ω,?m∈M);

        (12)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (13)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (14)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (15)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (16)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (17)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (18)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (19)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (20)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (21)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (22)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (23)

        (?Ji,Jj∈Ω0,?m1,m2∈M);

        (24)

        xmij∈{0, 1} (?Ji,Jj∈Ω0,?m∈M);

        (25)

        (26)

        (27)

        (28)

        (29)

        zij∈{0, 1} (?Ji,Jj∈Ω0,?m∈M).

        (30)

        由于文獻(xiàn)[12]中研究的單吊機(jī)調(diào)度問(wèn)題已經(jīng)證明為強(qiáng)NP難的,因此,本文考慮的多吊機(jī)調(diào)度問(wèn)題也是強(qiáng)NP難問(wèn)題.這使得最優(yōu)算法不能解決實(shí)際中的大規(guī)模問(wèn)題,啟發(fā)式算法能夠有效地解決上述問(wèn)題.在下面的部分中,提出了問(wèn)題的一些最優(yōu)性質(zhì),這些性質(zhì)將應(yīng)用在后面的啟發(fā)式算法及其性能分析中.

        3 啟發(fā)式算法及其最壞性能分析

        3.1 啟發(fā)式算法

        第3步 吊機(jī)的操作原則:一旦吊機(jī)空閑,如果存在沒(méi)有被阻礙的需求工件,則吊機(jī)對(duì)該工件進(jìn)行運(yùn)輸操作;否則,吊機(jī)進(jìn)行倒垛操作.

        第3.1步 對(duì)于運(yùn)輸操作,如果存在多需求工件,吊機(jī)選擇權(quán)最大的工件進(jìn)行操作.

        第3.2步 對(duì)于倒垛操作,吊機(jī)選擇距離當(dāng)前位置最近的阻礙工件,將其倒到最近的下層空位置,如果不存在這樣的空位,則選擇上層中不阻礙需求板卷的位置;否則,吊機(jī)選擇距離當(dāng)前位置次最近的阻礙工件進(jìn)行操作.如果一個(gè)需求工件被運(yùn)輸?shù)街付ㄎ恢?則從列表中刪除.

        第4步 當(dāng)兩臺(tái)或多臺(tái)吊機(jī)同時(shí)可利用時(shí),根據(jù)第5步分配吊機(jī).根據(jù)第3步執(zhí)行每臺(tái)吊機(jī)的操作.一旦發(fā)生吊機(jī)沖突,轉(zhuǎn)第6步.

        第5步 檢驗(yàn)吊機(jī)操作的可行性.

        第5.1步 檢驗(yàn)分配的吊機(jī)號(hào)是否在可行范圍內(nèi),如果可行,則構(gòu)建一個(gè)吊機(jī)啟發(fā)式;否則,轉(zhuǎn)第6步.

        第5.2步 為避免吊機(jī)碰撞,分別檢驗(yàn)在相鄰兩行或同一行中的各種可能的情況.如果可行,則構(gòu)建一個(gè)吊機(jī)啟發(fā)式;否則,轉(zhuǎn)第6步.

        第6步 避免吊機(jī)碰撞的原則:

        第6.1步 交換彼此的操作;

        第6.2步 一臺(tái)吊機(jī)等待直到另一臺(tái)吊機(jī)完成當(dāng)前的操作.

        性質(zhì)1 啟發(fā)式的計(jì)算復(fù)雜度為o(n2N2×|M|2).

        證明 在第2步中,需要時(shí)間o(|M|×NlogN).第3步和第4步中,吊機(jī)運(yùn)行時(shí)間分別為o(nN)和o(nN|M|).第5步中,檢驗(yàn)吊機(jī)操作的可行性時(shí)間為o(nN|M|).因此,算法的復(fù)雜度為o(n2N2|M|2).

        3.2 最壞性能分析

        為了分析算法的最壞性能比,根據(jù)三種不同的情況得到了三個(gè)下界.由于幾個(gè)下界之間互相補(bǔ)充,沒(méi)有一個(gè)能代替另一個(gè),因此,進(jìn)一步采用復(fù)合下界的策略,使得得到的問(wèn)題的下界可以更接近最優(yōu)值.基于這個(gè)界,分析了問(wèn)題啟發(fā)式的最壞性能.

        自然的,可以把多吊機(jī)對(duì)工件的操作看作平行機(jī).一個(gè)下界為

        當(dāng)所有的需求工件位于上層或無(wú)阻礙板卷壓迫的下層時(shí),這個(gè)界的值更緊.等式右邊第一項(xiàng)的值需要決策,第二項(xiàng)的值為常數(shù).注意,這個(gè)下界忽略了吊機(jī)的空移動(dòng)時(shí)間.因此,不采用它作為問(wèn)題的下界.

        從吊機(jī)運(yùn)輸操作的角度看,一個(gè)可行調(diào)度的最大完工時(shí)間不能小于運(yùn)輸一個(gè)工件的時(shí)間.因此,得到的下界為

        從吊機(jī)倒垛操作的角度看,一個(gè)可行調(diào)度的最大完工時(shí)間不能小于一個(gè)工件在|R|-|M|+1相鄰行內(nèi)由一臺(tái)吊機(jī)進(jìn)行倒垛操作的時(shí)間.顯然,得到的另一個(gè)下界為

        由上面的討論可以直接得到以下結(jié)論.

        令啟發(fā)式算法得到的調(diào)度為σH.

        性質(zhì)2 問(wèn)題的下界LB可由下面兩個(gè)下界獲得:LB=max{LB2,LB3}.

        定理由啟發(fā)式得到調(diào)度σH的最壞性能比為

        證明 不失一般性,考慮一種最差的情況,即一臺(tái)吊機(jī)m∈M對(duì)所有需求工件在|R|-|M|+1相鄰行中進(jìn)行操作.顯然,在這種情況下,不需要考慮吊機(jī)間的彼此碰撞.如果沒(méi)有阻礙工件,問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解.因此,一個(gè)可行調(diào)度的最大完工時(shí)間或許依賴于阻礙工件:阻礙工件的個(gè)數(shù)越少,可以更容易地得到一個(gè)調(diào)度.根據(jù)阻礙工件的個(gè)數(shù),算法的最壞性能可以根據(jù)阻礙工件的個(gè)數(shù)從下面3種情況中得到.

        在這種情況下,算法可以得到最優(yōu)調(diào)度,有Cmax(σH)=Cmax(σ*).

        在這種情況下,可以為阻礙工件提供足夠的倒垛位置而不會(huì)使需求工件再次被阻礙.根據(jù)第3步,在運(yùn)輸所有需求板卷之前,首先將所有阻礙板卷倒垛.調(diào)度σH的目標(biāo)函數(shù)值不能超過(guò)需要倒垛的所有阻礙板卷的最長(zhǎng)時(shí)間(兩項(xiàng)的和)與需要運(yùn)輸?shù)乃行枨蟀寰淼淖疃虝r(shí)間(后三項(xiàng)的和).

        (a)

        (b)

        在這種情況下,由于阻礙工件沒(méi)有足夠的倒垛位置,因此,阻礙工件或許被倒到已經(jīng)運(yùn)走的需求工件的位置.也就是,一些需求工件被運(yùn)輸?shù)酶?為了盡可能地減少倒垛時(shí)間,吊機(jī)或許將對(duì)工件進(jìn)行倒垛和運(yùn)輸操作.因此,最大完工時(shí)間Cmax(σH)總是滿足下式:

        式中,右邊第一項(xiàng)為吊機(jī)從初始位置到一個(gè)工件的最大空移動(dòng)時(shí)間,后3項(xiàng)的和為最大的倒垛與運(yùn)輸時(shí)間的和.

        因此,最壞性能為max{(a),(b),(c),(d)}.

        4 結(jié) 語(yǔ)

        本文不同于之前的相關(guān)文獻(xiàn),對(duì)這個(gè)實(shí)際問(wèn)題通過(guò)理論分析的方式進(jìn)行了研究.問(wèn)題被描述為一個(gè)混合整規(guī)劃模型,由于問(wèn)題是強(qiáng)NP難的,提出了一個(gè)有效的啟發(fā)式算法,這個(gè)算法的性能與問(wèn)題的參數(shù)有關(guān),這個(gè)算法為改進(jìn)吊機(jī)的運(yùn)行效率、及時(shí)地為下道工序運(yùn)輸工件、提高鋼鐵企業(yè)的產(chǎn)能提供了一個(gè)依據(jù).

        上述問(wèn)題適用于在鋼鐵企業(yè)倉(cāng)庫(kù)中解決避免吊機(jī)碰撞的約束下,運(yùn)輸需求板卷多吊機(jī)協(xié)調(diào)調(diào)度問(wèn)題.除了鋼卷倉(cāng)庫(kù)中的問(wèn)題可以應(yīng)用,這個(gè)研究在考慮具體的實(shí)施細(xì)節(jié)時(shí)也可以擴(kuò)展到類似的板坯倉(cāng)庫(kù)和集裝箱碼頭的倒垛、重倒垛問(wèn)題.

        協(xié)調(diào)調(diào)度吊機(jī)與其他物流和運(yùn)輸設(shè)備,如鋼鐵企業(yè)的臺(tái)車和卡車、集裝箱碼頭的船只和場(chǎng)吊,都是將來(lái)進(jìn)一步研究的問(wèn)題.

        參考文獻(xiàn):

        [ 1 ]Guan Y, Cheung R K. The Berth Allocation Problem: Models and Solution Methods[J]. OR Spectrum, 2004,26(1):75-92.

        [ 2 ]Imai A, Sun X, Nishimura E, et al. Berth Allocation in a Container Port: Using a Continuous Location Space Approach[J]. Transportation Research Part B: Methodological, 2005,39(3):199-221.

        [ 3 ]Park Y M, Kim K H. A Scheduling Method for Berth and Quay Cranes[J]. OR Spectrum, 2003,25(1):1-23.

        [ 4 ]Kim K H, Moon K C. Berth Scheduling by Simulated Annealing[J]. Transportation Research Part B: Methodological, 2003,37(6):541-560.

        [ 5 ]Neumann K, Zimmermann J. Procedures for Resource Leveling and Net Present Value Problems in Project Scheduling with General Temporal and Resource Constraints[J]. European Journal of Operational Research, 2000,127(2):425-443.

        [ 6 ]Lei L, Wang T J. The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints[J]. Management Science, 1991,37(12):1629-1639.

        [ 7 ]Armstrong R, Gu S, Lei L. A Greedy Algorithm to Determine the Number of Transporters in a Cyclic Electroplating Process[J]. IIE Transactions, 1996,28(5):347-355.

        [ 8 ]Liu J Y, Jiang Y. An Efficient Optimal Solution to the Two-hoist No-wait Cyclic Scheduling Problem[J]. Operations Research, 2005,53(2):313-327.

        [ 9 ]Zhou Z L, Liu J Y. A Heuristic Algorithm for the Two-hoist Cyclic Scheduling Problem with Overlapping Hoist Coverage Ranges[J]. IIE Transactions, 2008,40(8):782-794.

        [10]Varnier C, Bachelu A, Baptiste P. Resolution of the Cyclic Multi-hoists Scheduling Problem with Overlapping Partitions[J]. INFOR, 1997,35(4):309-324.

        [11]Jiang Y, Liu J Y. Multihoist Cyclic Scheduling with Fixed Processing and Transfer Times[J]. IEEE Transactions on Automation Science and Engineering, 2007,4(3):435-450.

        [12]謝謝,李彥平. 鋼卷倉(cāng)庫(kù)中的吊機(jī)調(diào)度問(wèn)題[J]. 沈陽(yáng)大學(xué)學(xué)報(bào):自然科學(xué)版, 2014,26(2):159-165.

        (Xie Xie, Li Yanping. Crane Scheduling in Warehouse of Coil[J]. Journal of Shenyang University: Natural Science, 2014,26(2):159-165.)

        猜你喜歡
        下界吊機(jī)工件
        吊機(jī)的哀鳴
        原料碼頭橋式吊機(jī)調(diào)度的分組與算法
        考慮非線性誤差的五軸工件安裝位置優(yōu)化
        Lower bound estimation of the maximum allowable initial error and its numerical calculation
        三坐標(biāo)在工件測(cè)繪中的應(yīng)用技巧
        大跨度懸索橋鋼箱梁吊裝之跨纜吊機(jī)吊裝探討
        豪氏威馬慶祝中國(guó)生產(chǎn)基地第100臺(tái)吊機(jī)交付
        智能制造(2015年10期)2015-11-04 00:10:02
        焊接殘余形變?cè)诠ぜ苎b配中的仿真應(yīng)用研究
        焊接(2015年9期)2015-07-18 11:03:52
        矩陣Hadamard積的上下界序列
        最大度為10的邊染色臨界圖邊數(shù)的新下界
        国产成人精品无码一区二区老年人| 日韩av他人妻中文字幕| 久久老熟女一区二区三区| 丰满少妇人妻无码| 亚洲熟女乱色综合亚洲图片| 亚洲va欧美va| 偷柏自拍亚洲综合在线| 蜜桃91精品一区二区三区| 久久精品国产久精国产果冻传媒| 欧美婷婷六月丁香综合色| 亚洲va欧美va人人爽夜夜嗨| 国产二区中文字幕在线观看| 无码无套少妇毛多18p| 免费xxx在线观看| 久久99中文字幕久久| 欧美性xxx久久| 亚洲一区中文字幕一区| 文字幕精品一区二区三区老狼| 在线观看精品视频网站| 麻豆国产人妻欲求不满谁演的 | 国产av精品一区二区三区视频| 大地资源网在线观看免费官网| 又粗又硬又黄又爽的免费视频| 国产高潮刺激叫喊视频| 中文字幕日本熟妇少妇| 久久蜜桃资源一区二区| 久久综合九色综合97欧美| 亚洲av中文无码字幕色三| 久久久久久久久中文字幕| 久久亚洲乱码中文字幕熟女| 国产精品a免费一区久久电影| 影音先锋每日av色资源站| 免费观看久久精品日本视频| 亚洲韩日av中文字幕| 日韩人妻ol丝袜av一二区 | 无码不卡一区二区三区在线观看| 伊人影院成人在线观看| 国产麻豆剧果冻传媒一区| 两个人看的www中文在线观看| 激情内射亚洲一区二区| 痴汉电车中文字幕在线|