【精品】最短時(shí)間生產(chǎn)計(jì)劃安排.doc

【精品】最短時(shí)間生產(chǎn)計(jì)劃安排 最短時(shí)間生產(chǎn)計(jì)劃安排曹?chē)?guó)威 1、馬俊欽 2、何秀平 21、韶關(guān)學(xué)院04級(jí)數(shù)學(xué)系信息與計(jì)算科學(xué) 51xx2、韶關(guān)學(xué)院04級(jí)數(shù)學(xué)系數(shù)學(xué)與應(yīng)用數(shù)學(xué)51xx摘要離散系統(tǒng)仿真在工業(yè)生產(chǎn)的工序安排中起到了相當(dāng)重要的作用，如何就一些內(nèi)部機(jī)制復(fù)雜的離散問(wèn)題建立簡(jiǎn)單易行、可監(jiān)測(cè)性強(qiáng)的數(shù)學(xué)模型一直是仿真技術(shù)的研究熱點(diǎn)離散事件系統(tǒng)現(xiàn)有三種仿真建模策略，即事件調(diào)度法，活動(dòng)掃描法和進(jìn)程交互法本文則采用了其中的活動(dòng)掃描法對(duì)生產(chǎn)中的一個(gè)實(shí)際例子進(jìn)行了處理活動(dòng)掃描法對(duì)于各事件之間相關(guān)性很強(qiáng)的系統(tǒng)有著很好的適用性本文針對(duì)該類(lèi)方法仿真程序難以實(shí)現(xiàn)的特點(diǎn)，特意附加了matlab6.5對(duì)該問(wèn)題的實(shí)現(xiàn)程序關(guān)鍵詞:離散時(shí)間動(dòng)態(tài)系統(tǒng)；仿真建模；活動(dòng)掃描法問(wèn)題的提出在許多工廠(chǎng)生產(chǎn)過(guò)程中，由于設(shè)備的數(shù)量、產(chǎn)品加工的次序限制，往往不能簡(jiǎn)單地安排生產(chǎn)任務(wù)我們?cè)O(shè)想，應(yīng)用強(qiáng)大的數(shù)學(xué)軟件配合簡(jiǎn)單易行的方法進(jìn)行安排設(shè)某重型機(jī)械廠(chǎng)產(chǎn)品都是單件性的，其中有一車(chē)間共有4種不同設(shè)備，現(xiàn)接受6件產(chǎn)品的加工任務(wù)，每件產(chǎn)品接受的程序在指定的設(shè)備上加工，其工序與加工周期如下表產(chǎn)工序品S T S T S T S138122432144523333347115242736421154102438461124173（表一）（S設(shè)備號(hào)、T周期）現(xiàn)在我們根據(jù)這一實(shí)際問(wèn)題，尋求安排的方法要求 1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒 2、每臺(tái)設(shè)備在同一時(shí)間只能擔(dān)任一項(xiàng)任務(wù)（每件產(chǎn)品的每個(gè)工序?yàn)橐粋€(gè)任務(wù)）、在盡可能短的時(shí)間里，完成所接受的全部任務(wù)為了節(jié)省電能，合理分配生產(chǎn)任務(wù)，廠(chǎng)方還要求 1、做出每件產(chǎn)品的每個(gè)工序開(kāi)工、完工時(shí)間表 2、給出每臺(tái)設(shè)備承擔(dān)任務(wù)的時(shí)間表12345678T S244xx4134TS68161251TSTST36412351841332模型的準(zhǔn)備2.1模型的簡(jiǎn)化該問(wèn)題要求在盡可能短的時(shí)間內(nèi)完成所有產(chǎn)品的各個(gè)工序，其中每件產(chǎn)品的各個(gè)工序之間是有先后順序的；各型號(hào)設(shè)備只有一臺(tái)，且同一時(shí)間只能承擔(dān)一個(gè)任務(wù)在解決這個(gè)問(wèn)題之前，我們可以先考慮一個(gè)類(lèi)似的經(jīng)簡(jiǎn)化的問(wèn)題現(xiàn)有編號(hào)為A，B，C，D，E，F(xiàn)，G的七個(gè)零件安排在同一臺(tái)機(jī)床上加工設(shè)各零件的加工時(shí)間依次為,12,18,6,12,24,6,147654321?ttttttt（分鐘）該機(jī)床一次只能加工一個(gè)零件，每個(gè)零件加工完畢即可運(yùn)走投入下一工序要求安排一個(gè)加工次序，使各零件的加工與等待的時(shí)間總和最小顯然,加工與等待時(shí)間的總和為?K?71)ik t8(kT其中iiktt?，k意味著第i個(gè)零件被安排在第k步進(jìn)行加工總和最小加工順序是CFAGDEB?其中B和E，D和G的位置可對(duì)調(diào)，T288（分鐘）推廣對(duì)于一臺(tái)設(shè)備，n（n1）個(gè)耗時(shí)不同的操作，如果每次只能執(zhí)行其中的一個(gè)，那么使得等待時(shí)間總和最少的方案為按時(shí)間大小排序，先處理時(shí)間小的工序在多臺(tái)設(shè)備的情況中，對(duì)于每一臺(tái)設(shè)備，如果在同一時(shí)間內(nèi)有多個(gè)不同的任務(wù)可供選擇，則我們先選擇耗時(shí)較短的那一個(gè)任務(wù)，這樣可使得總耗時(shí)最少2.2符號(hào)約定iS第i件設(shè)備(4,2,1?i)jkT第j件產(chǎn)品的第k道工序的加工周期(82,1?62,1?kj)t加工過(guò)程的某時(shí)刻(t1,2,3,4,)3模型的建立及求解為解決之前提出的生產(chǎn)實(shí)例，我們列出如下的表格S/t1234567891011121314151S62222offoffoffoffoffoff11662S4444444666655553S3331111111144444S555555555522222(表二)（其中S表示設(shè)備號(hào)，t表示加工過(guò)程的某時(shí)刻，數(shù)字代表產(chǎn)品號(hào)，off表示關(guān)機(jī)）對(duì)于每時(shí)刻t，若iS處于開(kāi)機(jī)狀態(tài)，則在該時(shí)刻記錄產(chǎn)品的號(hào)碼，若處于關(guān)機(jī)狀態(tài)，則標(biāo)記off這樣既能記錄各個(gè)設(shè)備的工作狀態(tài)，也便于及時(shí)找到有空閑（處于關(guān)機(jī)狀態(tài)）的設(shè)備并分配任務(wù)道理如問(wèn)題分析中的簡(jiǎn)單例子，假如1S現(xiàn)有mnT和pqT兩個(gè)任務(wù)可選，且pqmnTT?，那么選擇mnT將帶來(lái)更多的等待時(shí)間（因?yàn)榇藭r(shí)有一道工序等待著這道工序的完工，然后投入工作），為了使得總的等待時(shí)間最短，我們?cè)诿看蔚倪x擇中選出造成等待時(shí)間最小的進(jìn)行加工3.1具體演算如下（I）創(chuàng)建表格TURN S/t123456789101112131415161S off off off off off off offoffoffoffoffoffoff off off off2S off off off off off off offoffoffoffoffoffoff offoffoff3S offoffoffoffoffoff offoffoffoffoffoffoff offoffoff4S offoffoffoffoffoff offoffoffoffoffoffoff offoffoff(II)搜索第1列，1S處于關(guān)機(jī)狀態(tài)，在表一中知道1S可以接21T或61T，其中61T時(shí)間較短，所以在第1S1行，t1到t61T11列填上j6；2S、3S、4S行也如此操作，得表三S/t123456789101112131415161S6offoffoffoffoffoffoffoffoffoffoffoffoff offoff2S4444444offoffoffoffoffoffoff offoff3S333offoffoffoffoffoffoffoffoffoffoff offoff4S5555555555offoffoffoffoffoff（表三）（III）搜索第二列，其中1S處于關(guān)機(jī)狀態(tài)，可知61T已經(jīng)完成，所以6號(hào)產(chǎn)品可以進(jìn)行第二個(gè)工序的加工1S可執(zhí)行的操作為21T，所以在第1S1行，t2到t21T15列填上j2（IV）繼續(xù)上面的循環(huán)直至所有的工序都完成在matlab6.5語(yǔ)言環(huán)境下演算步驟如下設(shè)置時(shí)間表格TURN的初始狀態(tài)(表二中各格填上OFF);設(shè)定t的初值為1;WHILE(工序未全部完成)掃描TURN:FOR i=1TO4IF(MARK(i,t)=OFF)THEN掃描iS能執(zhí)行的任務(wù);IF(搜索成功)THEN設(shè)找到且此刻最短時(shí)間的任務(wù)所耗時(shí)間為jkT，將iS行的第t到1?jkTt列的內(nèi)容改為加工的產(chǎn)品的序號(hào)j;ELSE搜索1?iS(若i=3);或使t+1并執(zhí)行下一個(gè)循環(huán)(若i=4);ENDIF ELSE搜索1?iS(若imeson(m)(x(k),y(k)a=x(k)y(k);end end if turnon(m),j=off&meson(m)(a (1),a (2)=100%若時(shí)間為100則意味著這個(gè)步驟不屬于我們希望使用的那件設(shè)備while tim(a (1),a (2)0turnon(m),tim(a (1),a (2)+j-1=a (1);tim(a (1),a (2)=tim(a (1),a (2)-1;endendendfori=1:4if turni,j=offdai(i)=turni,j;endendfori=1:4if turni,j=off&turni,j+1=offgongxu(turni,j)=gongxu(turni,j