工件加工的排序問題

1、工件加工的排序問題摘要作為經(jīng)典排序問題的推廣,處理機的排序問題具有廣泛的實際背景.對于目標函數(shù)是極小化排序時間表長度的情況,可以采用啟發(fā)性的搜索方法。此文中根據(jù)所提的問題采用了局部搜索方法，對問題進行描述與解答，力求通過局部搜索問題的最優(yōu)解或近似最優(yōu)解。第一問的第（1）小問，為單機排序問題，利用Spt規(guī)則，按工件加工時間長短，從短到長順序排列，可使平均流程時間最小。這種方法又稱“最短加工時間規(guī)則”應用SPT規(guī)則，可減少加工其它零件時它們的等待時間的和。得到的最優(yōu)總時間為171.9h，加工次序為：J-J-J-J-J-J-J-J-J-J-J-J639710512811412或者J-J-J-J-J-

2、J-J-J-J-J-J-J6391075128114第一問的第（2）小問，要求規(guī)定的完工時間內(nèi)，選擇完成工件，使獲得的價值量最大。很容易可以得到，最優(yōu)解的加工次序必然可以通過調(diào)換得到工件的完工時間先后的順序一致。從而建立一個0T規(guī)劃模型，求得最優(yōu)解MAXU=117,選擇的工件和加工次序為：J-J-J-J-J-J-J-J-J-J9112371064118第二，三問中要求工件的加工順序使得加工工件的總時間最短。加工工件的總時間等于每個工件的加工時間與加工其他工件時它的等待時間的和。而問題中的工件的加工時間是一定的，因此問題可以轉(zhuǎn)化為求等待時間的最小。建立等待時間的目標函數(shù)，把工件按在第一臺機器的加

3、工時間的升序進行一個重新排列，得到的新序列，通過局部的交換工件的次序，再比較等待時間，若時間段則繼續(xù)進行迭代，否則繼續(xù)交換工件的加工次序，直到所有的工件的順序交換完為止。這樣可以得到第二問的總加工時間的最優(yōu)值為：225.6h。工件加工的總周期為：35h。加工次序為：J-J-J-J-J-J-J-J-J-J-J-J627310514981112第三問的總加工時間的最優(yōu)值為：242.5h。工件加工的總周期為：35.7h。加工次序為：J-J-J-J-J-J-J-J-J-J-J-J。362710518119412關鍵字SPT規(guī)則加工時間工件等待時間機器等待時間局部搜索問題重述計劃排序問題中的車間作業(yè)問題

4、，研究n個工件在m臺機器上有序的加工問題，每個工件都有完工的日期（DD，Duedate），加工的時間（PT，Processingtime）和工件的價值（VAL,Valuefjobisselected）.車間作業(yè)計劃研究一個工廠生產(chǎn)工序的計劃和安排，需要計劃與合理安排各個工件在這些機器上加工的先后次序，即擬訂加工工序，通過各個工件在各種機器上加工次序的合理安排，使得完成這批工件加工任務所需的總時間最?。ㄗⅲ嚎倳r間即為各個零件的加工時間和加工其他零件時它們等待時間之和）或要求整個選擇加工的工件價值最大。有一個工廠現(xiàn)在有12種工件（編號為工件1，工件2，工件12）需要在車床，鉆床，銑床幾種不同的設備

5、上加工?？紤]下面的工件加工的排序問題：（一）這12種工件都要求在車床上加工，車床一次只能加工一種工件，這12種工件加工所需時間，每個工件的完工時間和每個工件的價值如表（1）所示：1）不考慮工件的完工時間和工件的價值，建立數(shù)學模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務所需的總時間最省。2）由于工件必須在它們要求的時間內(nèi)完工，按照表（1）的數(shù)據(jù)，建立數(shù)學模型，為該工廠安排選擇加工工件的種類及加工的次序，使得整個選擇加工的工件價值最大。（二）如果這12種工件都要求先在車床上加工，然后再在鉆床上加工（即工件在鉆床加工之前必須先在車床上加工過），每種機器一次只能加工一種工件，這12種工件

6、加工所需時間如表（2）所示：建立數(shù)學模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務所需的總時間最省。（三）如果這12種工件都要求先在車床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機器一次只能加工一種工件，這12種工件加工所需時間如表（三）所示：建立數(shù)學模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務所需的總時間最省。模型假設1、是在工作過程中是不會出現(xiàn)故障的，且第一個機器為連續(xù)作業(yè)安排，無需等待時間，故閑置時間為零；2、作業(yè)系列已知，處理過程開始后不再有新作業(yè)，作業(yè)不會被撤消，不存在加工過程的中斷，如機器故障、意外事故等；3、工件在每一臺機器上的加工次序是不變的

7、，即在第一臺機器上加工的第i個工件排在第j個工件前，則在第二臺機器上加工，第i個工件也排在第j個工件前。4、對加工任務所需總時間的理解有兩種：總時間即為各個零件的加工時間和加工其他零件時它們等待時間之和；從第一個工件加工開始算起到最后一個工件加工完成所用的時間。這里對問題的求解都采用第一種理解。符號說明P是個mxn矩陣，其元素pj表示工件J在機器“j上加工的時間pij表示工件J在機器Mj上加工的時間；c工件的數(shù)量ti工件i完工時間Li最遲加工時間，表示工件i的完工時間減去工件i的加工時間MAXU最大工件價值量x二i1表示第i個工件被選上x二i0表示第i個工件沒有被選上vi表示加工工件j的價值量

8、iQk表示按完工時間先后排列后工件k的加工時間T工件的總加工時間qij工件的一個重新排序后工件J在機器Mj上加工的時間Tp工件的加工時間之和Tw工件的等待時間之和gij第i臺機器在加工第j個工件時的機器等待時間W第i個工件的等待時間i模型分析與模型建立問題一:N個工件在一臺設備上的加工的作業(yè)排序。單一設備（單工序）排序是作業(yè)的排序最簡單,最基本的問題。顯然，當N個工件在一臺設備上進行加工時，可能有N!種排序方案。但是，不管是哪種方案,N個工件的最大流程時間是固定值，即與工件的加工先后排序無關。所以，單一設備的優(yōu)化排序評價標準，通常是平均流程時間最小，最大拖期量最小或者為零。單一機床的零件加工排

9、序問題可按以下規(guī)則進行。SPT規(guī)則按工件加工時間長短，從短到長順序排列，可使平均流程時間最小。這種方法又稱“最短加工時間規(guī)則”應用SPT規(guī)則，可減少在制品占用量，節(jié)省流動資金。由于未考慮交貨期，有可能產(chǎn)生交貨延遲現(xiàn)象。同時也可以考慮建立目標函數(shù)，MinC=弋kxy其中y為J的一個排kkkk=1列。(2)由于工件都有各自的完工時間限制,和不同的加工時間,顯然,主要的約束條件是完工時間。工件的加工順序是于完工時間的排列順序一致。若不一致我們可以調(diào)換其中不一致的工件加工順序。在j,j都能在規(guī)定的完工時間內(nèi)完i+1成時,假如工件j的完工時間為t,j的完工時間為t,j排在j之前且ii+1i+1ii+1t

10、t,那么此時調(diào)換j,j的順序,將不會造成j無法在規(guī)定的時間完成。因為i+1ii+1i有條件tt保證。因此，可以肯定工件的加工順序于完工時間的排列順序一ii+1致。這只是充分條件，不是必要條件。引進最遲加工時間L=tpiii所以我們對數(shù)據(jù)做了一個按完工時間先后的重新排列的處理并對其重新編號，得到下表：新序號工件加工時間(h)完工時間(h)工件價值最遲加工時間191.7775.3223.27.544.3312.8986.2452.71077.35124.711186.3631.2151613.8772.5171714.58102.5181215.5960.9222021.1104423319111

11、13.625521.41283.3331129.7模型的建立：引進12個0-1變量，x(i=1，2，12)，x=1表示第i個工件被選ii上,x二0表示第i個工件沒有被選上，建立目標函數(shù):MAXU=昱vXxiiii=1v為加工工件j的價值量。約束條件是對工件j加工的開始時間必須小于最遲開iii工時間，而工件的開始加工時間等于加工工件j到j所用的時間，對于工件j的1i-1i開始加工時間應該等于遲Qxx，所以可以得到12個約束條件：kkk=1s.t.(遲QL(i=1,2,12)。kkiik=1這樣就建立了一個0-1規(guī)劃問題。問題二：該題目所求的總時間即為各個零件的加工時間和加工其他零件時它們等待時間

12、之和，由于對每一個工件的加工都必須經(jīng)過2臺機器的加工，即他們的加工時間為：T=繭cp。pijj=1i=1所以對于任一種工件的加工次序，他們的加工時間總和是不變的。該題是求加工次序使得加工工件的總時間最小，即求min:T=T+T，而T是一定的，因此pwp問題等價于求工件的等待時間T最小。w分析任一種加工次序的等待時間如下：第一個工件的等待時間為0，因為該工件從第一臺機器加工完立刻進入第二臺機器加工，直到該工件加工完成。所以有：W=g=0121第二個工件的等待時間為第一個工件在第一臺機器的加工時間，加上工件在第一臺機器加工完成后在第二臺機器的加工時間減去第二個工件在第一臺機器的時間于0的最大值，即

13、：W=q+Max0,q一q+g11122111如果q12-q210則第二臺機器存在機器的等待時間:g21=1x(qq+g)122111否則g21=021即g=max0,1x(qq+g)22122111第三個工件的等待時間為：W二q+q+Max0,q+qqq+g+g1121122221312122此時的機器等待時間為：g二max0,1x(q+qqq+g+g)23122221312122第四個工件的等待時間為：W二q+q+q+Max0,q+q+qqqq+g+g+g112131122232213141212223機器等待時間為：24一q41+g21+g22+g23)=Max0,一1x(q+q+q一q

14、一q1222322131第五個工件的等待時間為：W二q+q+q+q+Max0,q+q+q+qqqqq+g+g+g+g11213141122232422131415121222324機器等待時間為：g=Max0,1x(q+q+q+qqqqq+g+g+g+g)25122232422131415121222324第i個工件的等待時間為：W=藝qik1k=1+Max0,藝qk2k=1工qk1k=2-遲g2kk=1此時的機器等待時間為：g=Max0,1x(EqYq遲g)TOC o 1-5 h z2ik2k12kk=1k=2k=1 HYPERLINK l bookmark62 從而建立目標函數(shù)：min:T

15、=T+T=p+EWpwijkj=1i=1k=1問題三：相對第二問，該問只是增加了機器的臺數(shù)，其他條件不變，因此這里的機器等待時間有兩個，即第二臺機器的等待時間和第三臺機器的等待時間。分析任一種加工次序的等待時間如下：第一個工件的等待時間為0，因為該工件從第一臺機器加工完立刻進入第二臺機器加工，再到第三臺機器，直到該工件加工完成。所以有：W=g=g=012131第二個工件的等待時間為W=q+Max0,qq+g+Max0,qq+gg1112212113223121此時第二臺機器的等待時間為：g=Max0,1x(qq+g)122121第三臺機器的等待時間為：g=Max0,1x(qq+gg)32132

16、23121第三個工件的等待時間為：W=q+q+Max0,q+qqq+g+gTOC o 1-5 h z1121122221312122 HYPERLINK l bookmark44 +Max0,q+qqq+g+ggg1323223231322122此時第二臺機器的等待時間為：g=Max0,1x(q+qqq+g+g)122221312122第三臺機器的等待時間為：g=Max0,1x(q+qqq+g+ggg)331323223231322122第四個工件的等待時間為：23g+22g+112g+114q31q112q23q+22q+2W二q+q+q+Max0,4112131+Max0,33q+32q+

17、333g+23g+g+q32g此時第二臺機器的等待時間為：g二Max0,1x(q+q+qqqq+g+g+g)24122232213141212223第三臺機器的等待時間為：g34=Max0,1x(q+q+qqqq+g+g+g132333223242313233g21g22g23)第i個工件的等待時間為:W=Sq+Max0,Sq_工q+ik1k2k1k=1k=1k=2遲g+Max02kk=1,Sq3_Sq2+Sg3_Sg2k23k2kk=2k=1k=1k3k=1_Sq+Sgk1k=2k=12k)此時第二臺機器的等待時間為：g=Max0,_1x(SqTOC o 1-5 h zik2k=1第三臺機器

18、的等待時間為：g=Max0,_1x(Sq_Sq+Sg_Sg)3ik3k23k2kk=1k=2k=1k=1同理建立目標函數(shù)：min:T=T+T=SSp+SWpwijkj=1i=1k=1模型求解問題一：工件加工時間（h）完工時間（h）工件價值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118解：（1）12種工件的排序分析過程如下：F=St=33.1加工周期maxi，這是一定的，與工件的加工順序無關。按照上述的SPT規(guī)則，加工順序為J_J_J_J_J_J_J_J_J_J_J_J39710512811412或為J6_J3_J9_J10_J7_J5_J1_J2_J8_J11_J4_J12，平均流程時間最小完成這批工件加工任務所需的總時間最小為：Cmin=171.9。（2）為了利用數(shù)學軟件LINGO求解，我們簡化約束條件的形式:k=1Xx+100XxT進入第四步，否則T=T,進入第一步0第四步，交換回第i個位置和第i+j個位置上的工件，i+,如果i=13-j,則i=l,j+,進入第五步第五