• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      帶單機(jī)器人的流水作業(yè)排序問題的復(fù)雜性

      2022-01-21 08:15:44龍彩燕
      關(guān)鍵詞:空閑排序工件

      時(shí) 凌,張 瓊,龍彩燕

      (廣州工商學(xué)院通識教育學(xué)院,廣東 廣州 510850)

      0 引言

      帶單機(jī)器人的流水作業(yè)排序問題可描述為:給定m臺機(jī)器M1,M2,…,Mm和n個(gè)工件J1,J2,…,Jn,每個(gè)工件Jj在m臺機(jī)器的工序?yàn)镼i,j(i=1,2,...,m;j=1,2,...,n),其加工順序?yàn)椋篞1,j→Q2,j→...→Qm,j.工序Qi,j在機(jī)器Mi上的加工時(shí)間為pi,j,且在加工時(shí)不可中斷.每臺機(jī)器在同一時(shí)間只能加工一個(gè)工件,而每個(gè)工件在同一時(shí)間只能在一臺機(jī)器上加工.筆者假設(shè)同一工件在一臺機(jī)器上完工后到下一臺機(jī)器加工之前存在一定的運(yùn)輸時(shí)間tj,k,所有的運(yùn)輸工作均由單機(jī)器人R來完成,且單機(jī)器人R同時(shí)只能運(yùn)輸一個(gè)工件,于是在機(jī)器人R和機(jī)器Mi之間就會出現(xiàn)一定的沖突.假設(shè)所有的加工時(shí)間pi,j和運(yùn)輸時(shí)間tj,k均為正整數(shù).

      1 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax 的復(fù)雜性

      由于排序問題F3||C存在同順序最優(yōu)解[8],所以該排序問題只考慮同順序的最優(yōu)解.用σ和τ分別表示工件在機(jī)器M1和M2上的加工順序,C(σ,τ)表示排序問題的最小完工時(shí)間.

      引理1[2]對于加工時(shí)間和運(yùn)輸時(shí)間分別為pi,j、tj的排序問題則:

      其中,σ-1(k)和τ-1(k)分別表示工件Jk在序列σ和τ中的相應(yīng)位置.

      定理1排序問題是強(qiáng)NP-困難的.

      證明利用強(qiáng)NP-困難的3-劃分問題[9]到排序問題的歸約來證明該排序問題也是強(qiáng)NP-困難的.

      3-劃分問題:給定正整數(shù)集X={x1,x2,...,x3m}和正整數(shù)b,且滿足

      確定整數(shù)集X是否存在包含3個(gè)元素的m個(gè)不相交的子集{X1,X2,...,Xm}的劃分,且

      給定3-劃分問題的一個(gè)實(shí)例,定義具有下面2類工件的排序問題

      (1)3m劃分工件,或者稱為P-工件:

      (2)m大工件,或者稱為L-工件:

      門檻值為y=3mb+3b,相應(yīng)的確定性問題為:是否存在完工時(shí)間C(S)不超過門檻值y=3mb+3b的加工順序S.

      假設(shè)3-劃分問題的解存在,設(shè) {X1,X2,...,Xm}是滿足式(3)的劃分,其中,Xi=(xξ(i),xη(i),x?(i))(i=1,2,...,m).

      對于每個(gè)工件Jj構(gòu)建包含工件ξ(j),η(j),?(j)和工件 3m+j,其加工順序?yàn)?((3m+1);ξ(1),η(1),?(1);(3m+2);ξ(2),η(2),?(2);...;(4m-1);ξ(m),η(m),?(m);4m),如圖1 所示.

      圖1 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax的甘特圖Fig.1 Gantt chart for the F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmaxscheduling problem

      則對于圖1給出的加工順序S,顯然滿足:C(S)≤y.

      于是得到同順序的S且C(S)=y,且有如下結(jié)論:

      (1)因?yàn)閜1,j>0,先加工工件(3m+1);

      (2)因?yàn)閜2,j>0(j≠m),工件4m安排在最后加工;

      (3)機(jī)器M1在區(qū)間[0,3mb]內(nèi)加工工件,且無空閑時(shí)間;

      (4)機(jī)器M2在區(qū)間[3b,3mb+3b]內(nèi)加工工件,且無空閑時(shí)間;

      (5)單機(jī)器人R在區(qū)間[(3i+2)b,(3i+4)b](i=0,1,...,(m-1))內(nèi)運(yùn)輸工件,且無空閑時(shí)間.

      不失一般性,假設(shè)機(jī)器以{1,2,...,m-1,m}的順序加工工件,即按單調(diào)遞增的順序加工工件.設(shè)工件(3m+1)與工件(3m+2)之間加工的工件子集為X1={i1,i2,...,ik},如圖2所示.

      圖2 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax的子圖Fig.2 Subgraph for theF2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmaxscheduling problem

      于是X1≠Φ,否則在工件(3m+1)和工件(3m+2)出現(xiàn)空閑時(shí)間,與結(jié)論(3)~(5)矛盾.下面證明k=3和成立.假設(shè)表示工件Jj按加工順序σ在機(jī)器Mi上的完工時(shí)間,則:

      如果k≤2,則有:

      如果k≥4,則有:

      另一方面,由于工件(3m+1)必須先完成運(yùn)輸才能加工,因此工件(3m+2)不會在時(shí)間2b+kb之前在機(jī)器M加工.于是工件(3m+1)在機(jī)器M完工時(shí)間為,但工件(3m+2)在機(jī)器M1上還沒有完成集合X1中工件的加工,與結(jié)論(4)矛盾,故必須有k=3.這就意味著單機(jī)器人R在時(shí)間段[2b,3b]和時(shí)間段[3b,4b]運(yùn)輸工件 (3m+1)和工件 (3m+2).所以,即:

      另外,由于機(jī)器M2在時(shí)間段[4b,6b]沒有空閑時(shí)間,因此工件(3m+1)在機(jī)器M2上的完工時(shí)間不遲于6b,則有:

      因?yàn)閜1,i=p2,i=xi,所以

      即X1是包含3個(gè)元素且滿足

      同理可證余下的集合X2,X3,...,Xm也是滿足包含3個(gè)元素且滿足故集合X1,X2,...,Xm就是包含3元素且滿足的3-劃分問題的解.

      證畢.

      2 小結(jié)

      猜你喜歡
      空閑排序工件
      恩賜
      詩選刊(2023年7期)2023-07-21 07:03:38
      排序不等式
      恐怖排序
      “鳥”字謎
      小讀者之友(2019年9期)2019-09-10 07:22:44
      考慮非線性誤差的五軸工件安裝位置優(yōu)化
      節(jié)日排序
      三坐標(biāo)在工件測繪中的應(yīng)用技巧
      刻舟求劍
      兒童繪本(2018年5期)2018-04-12 16:45:32
      彪悍的“寵”生,不需要解釋
      WLAN和LTE交通規(guī)則
      CHIP新電腦(2016年3期)2016-03-10 14:09:48
      故城县| 普洱| 临海市| 洪湖市| 京山县| 百色市| 轮台县| 白山市| 望城县| 临桂县| 贵州省| 宜都市| 汝阳县| 南乐县| 中牟县| 莲花县| 嘉荫县| 宝应县| 洞头县| 抚顺县| 科技| 佛坪县| 广汉市| 永定县| 平定县| 合水县| 凭祥市| 龙岩市| 平潭县| 台南县| 泸溪县| 绍兴县| 疏勒县| 济宁市| 南木林县| 云霄县| 观塘区| 颍上县| 西宁市| 东海县| 德江县|