基于工期求解的排序模型算法設(shè)計(jì)與實(shí)現(xiàn)

摘要：在任意M×N流程調(diào)優(yōu)排序模型的產(chǎn)品加工順序已確定之前提下，通過分析其加工時(shí)標(biāo)流線圖的結(jié)構(gòu)特征，進(jìn)而提出了基于表格數(shù)據(jù)的總工期求解遞推算法，并基于標(biāo)準(zhǔn)C完成了該算法的仿真實(shí)現(xiàn)，自動繪制了時(shí)標(biāo)流線圖，還考慮了模型數(shù)據(jù)的隨機(jī)生成和對現(xiàn)成模型數(shù)據(jù)的讀取并求解等內(nèi)容。該算法簡潔、明快、可操作性極強(qiáng)，且不受模型規(guī)模之限制，時(shí)間復(fù)雜度為O（n2）。

關(guān)鍵詞：網(wǎng)絡(luò)規(guī)劃；時(shí)間間隔；工期；時(shí)標(biāo)流線圖；算法；仿真實(shí)現(xiàn)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）18-4280-04

The Algorithm Design and Implementation of sorting Based on the Time Solving

CAO Ying-huai

（China Maritime Police Academy， Ningbo 315801， China ）

Abstract： In any M x N process optimization scheduling model of product processing sequence identified premise， through the analysis of the processing time scale chart structure characteristics， then based on the tabular data total time solving recursive algorithm， automatic drawing of timing chart Based on standard C completed the simulation algorithm， also consider the model data randomly generated and ready-made model data to read and solving etc.. The algorithm is concise， sprightly， extremely strong maneuverability， and not affected by scale models of the restrictions， the time complexity is O（N 2）

Key words： graph planning； time interval； construction period； timing chart； algorithm； simulation

網(wǎng)絡(luò)規(guī)劃中的M×N排序問題應(yīng)用十分廣泛，當(dāng)工序道數(shù)M≤2時(shí)通過約翰遜定律即可輕松求解，但M≥3時(shí)常用的分組法或分界法僅可得到近優(yōu)解，這也成了運(yùn)籌學(xué)領(lǐng)域中的一個(gè)熱點(diǎn)問題，即排序問題[1]。

雖然確定N個(gè)產(chǎn)品之加工順序是排序問題的關(guān)鍵，但順序確定后的工期TKW求解在目前尚無有效算法，一般通過繪制時(shí)標(biāo)流線圖，再從圖上數(shù)出TKW值，顯然這是個(gè)近乎手工的處理方法。該方法在分組（界）法中使用頻繁，工作量可觀。當(dāng)排序模型規(guī)模較大時(shí)，繪圖本身就不太現(xiàn)實(shí)，編程固然可行，但不是對每個(gè)人都適用[2]。

本文正是針對該狀況，通過分析時(shí)標(biāo)流線圖的結(jié)構(gòu)特征，提出了基于產(chǎn)品加工順序確定時(shí)直接從原始數(shù)據(jù)表上求取工期TKW的算法，并完成了基于標(biāo)準(zhǔn)C的算法仿真實(shí)現(xiàn)。

1 基于間隔時(shí)間的工期求解

屬于多項(xiàng)式級別，效果理想。

該算法的可操作性很強(qiáng)，在給定的表上即可直接處理，基本不受m和n的限制。

不過，局限在于各產(chǎn)品的加工順序必須確定，所以，結(jié)合分組（界）法處理效果更佳，可使分組法走向?qū)嵱谩?/p>

當(dāng)然，結(jié)合窮舉N件產(chǎn)品的全排列，對于任意的在線排序模型來說，這也不失為求最優(yōu)解的一種可行的算法[4]。

5 基于標(biāo)準(zhǔn)C的算法仿真實(shí)現(xiàn)[5]

5.1 之所以基于標(biāo)準(zhǔn)C

本實(shí)現(xiàn)的算法實(shí)現(xiàn)之所以基于標(biāo)準(zhǔn)C，主要是基于以下想法。盡量側(cè)重于算法實(shí)現(xiàn)的細(xì)節(jié)描述，無須過多地關(guān)注模擬仿真界面的設(shè)計(jì)（諸如視窗、對象和事件等）和效果等其他因素。在盡可能短的論文篇幅里給出盡可能詳盡的源程序代碼。標(biāo)準(zhǔn)C可適應(yīng)盡可能大的讀者群體，不論是熟悉C++、VC還是C#的讀者，均可直接引用之。而且，標(biāo)準(zhǔn)C與目前絕大多數(shù)院校的教學(xué)內(nèi)容相一致。

5.2 算法實(shí)現(xiàn)的參量指標(biāo)

本次實(shí)現(xiàn)取M≥3。同時(shí)，基于教學(xué)過程中的模擬仿真之現(xiàn)實(shí)，一般無須太大規(guī)模的模型描述，故僅考慮M≤100?？紤]盡量簡潔的仿真直觀性視覺要求，時(shí)標(biāo)流線圖的顏色并未做區(qū)別處理，依然采用標(biāo)準(zhǔn)的黑白效果。

另外，對排序模型數(shù)據(jù)也做了一定的限制，僅考慮整型值（int）。實(shí)用中如果有浮點(diǎn)需求，可通過調(diào)整數(shù)據(jù)量化的單位來靈活處理，并不影響該算法的實(shí)質(zhì)。

加工時(shí)間不可能出現(xiàn)負(fù)值，但可以為零，這也是現(xiàn)實(shí)情況決定的[6]。

鑒于視覺效果的考慮，本實(shí)現(xiàn)通過自動隨機(jī)產(chǎn)生出的排序模型數(shù)據(jù)限定在[5，40]區(qū)間中，當(dāng)然，若讀者有具體的排序模型要借助該程序來求解，本實(shí)現(xiàn)亦支持。

通過系統(tǒng)隨機(jī)產(chǎn)生的排序模型數(shù)據(jù)亦可保存在指定的磁盤文件當(dāng)中。保存的模型數(shù)據(jù)采用文本文件，首行即M和N的值，后面是各道工序上各零件之加工時(shí)間。

各零件在每道工序上的加工時(shí)間，在仿真實(shí)現(xiàn)時(shí)以屏幕象素為單位展開，因此，當(dāng)M、N較大時(shí)，TKW可能超出屏幕的顯示范圍。

標(biāo)準(zhǔn)C的圖形顯示模式支持的最大分辨率是640×480，所以，如果TKW超過了該范圍，作為仿真實(shí)現(xiàn)而言，針對該算法源程序的簡單性來考慮，此時(shí)已失去了課堂教學(xué)之需求范疇，故本實(shí)現(xiàn)不再研究對其時(shí)標(biāo)流線圖的左右拖動和縮放等功能。endprint

5.3 標(biāo)準(zhǔn)C的圖形模式

基于圖形模式做仿真設(shè)計(jì)是很自然的選擇，而標(biāo)準(zhǔn)C的視覺效果相對于C++和VC相對較弱。另外，一般的C語言教材均很少介紹圖形設(shè)計(jì)方面的內(nèi)容，這便在一定程度上增加了設(shè)計(jì)的難度。圖形模式設(shè)置可通過函數(shù)initgraph（）完成，再通過graphresult（）函數(shù)探測設(shè)置是否成功。圖形繪制完成后，用 closegraph（）在關(guān)閉圖形模式的同時(shí)，將自動釋放其占據(jù)的內(nèi)存資源。另外，基于象素定位的文本輸出函數(shù)outtextxy、類型轉(zhuǎn)化的*itoa，以及在本實(shí)現(xiàn)中使用較多的line、putpixel等，因相對簡單不再贅述。

5.4 空間復(fù)雜度與時(shí)間復(fù)雜度的平衡

基于程序簡潔性和運(yùn)行效率等諸多考慮，本實(shí)現(xiàn)做了大量的技巧性處理，將其中“間隔時(shí)間”的計(jì)算、TKW遞推求解處理等環(huán)節(jié)融合在一起，并將求解計(jì)算與流線圖繪制融合在一起，這也是基于運(yùn)行過程中的空間優(yōu)化需求。

6 算法仿真實(shí)現(xiàn)的效果分析

實(shí)現(xiàn)中的溢出含義[7]有二，一指流線圖超出屏幕邊界，二是指在求解過程中，當(dāng)模型規(guī)模較大時(shí)，因變量數(shù)據(jù)類型的限制而產(chǎn)生的溢出。對于前者，經(jīng)筆者多次運(yùn)行比較，一般當(dāng)M≤15、N≤8時(shí)，視覺效果良好。對于后者，當(dāng)M≤150、N≤150時(shí)程序運(yùn)行正常，而超出該范圍時(shí)程序的穩(wěn)定性不良，有時(shí)會出現(xiàn)因內(nèi)存不足而無法裝載圖形驅(qū)動的現(xiàn)象，擴(kuò)充內(nèi)存后效果良好。鑒于篇幅所限，程序運(yùn)行時(shí)的時(shí)標(biāo)流線效果圖從略。

參考文獻(xiàn)：

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)[M].2版.北京：清華大學(xué)出版社， 1990.

[2] 許創(chuàng)杰.軍事運(yùn)籌學(xué)[M].1版.北京：國防大學(xué)出版社， 1998.

[3] 曹迎槐.M×N在線排序模型之工期求解算法分析[J].公安海警學(xué)院學(xué)報(bào)， 2012（1）.

[4] 曹迎槐.排序模型之TKW遞推算法研究[C].管理科學(xué)與系統(tǒng)科學(xué)研究新進(jìn)展，2003： 19-23.

[5] 曹迎槐.基于標(biāo)準(zhǔn)C的排序模型工期算法仿真實(shí)現(xiàn)[J].公安海警學(xué)院學(xué)報(bào)， 2012（3）.

[6] 浦在明.網(wǎng)絡(luò)法基本原理及其應(yīng)用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.運(yùn)籌學(xué)與實(shí)驗(yàn)[M].北京：電子工業(yè)出版社，2008.endprint

5.3 標(biāo)準(zhǔn)C的圖形模式

基于圖形模式做仿真設(shè)計(jì)是很自然的選擇，而標(biāo)準(zhǔn)C的視覺效果相對于C++和VC相對較弱。另外，一般的C語言教材均很少介紹圖形設(shè)計(jì)方面的內(nèi)容，這便在一定程度上增加了設(shè)計(jì)的難度。圖形模式設(shè)置可通過函數(shù)initgraph（）完成，再通過graphresult（）函數(shù)探測設(shè)置是否成功。圖形繪制完成后，用 closegraph（）在關(guān)閉圖形模式的同時(shí)，將自動釋放其占據(jù)的內(nèi)存資源。另外，基于象素定位的文本輸出函數(shù)outtextxy、類型轉(zhuǎn)化的*itoa，以及在本實(shí)現(xiàn)中使用較多的line、putpixel等，因相對簡單不再贅述。

5.4 空間復(fù)雜度與時(shí)間復(fù)雜度的平衡

基于程序簡潔性和運(yùn)行效率等諸多考慮，本實(shí)現(xiàn)做了大量的技巧性處理，將其中“間隔時(shí)間”的計(jì)算、TKW遞推求解處理等環(huán)節(jié)融合在一起，并將求解計(jì)算與流線圖繪制融合在一起，這也是基于運(yùn)行過程中的空間優(yōu)化需求。

6 算法仿真實(shí)現(xiàn)的效果分析

實(shí)現(xiàn)中的溢出含義[7]有二，一指流線圖超出屏幕邊界，二是指在求解過程中，當(dāng)模型規(guī)模較大時(shí)，因變量數(shù)據(jù)類型的限制而產(chǎn)生的溢出。對于前者，經(jīng)筆者多次運(yùn)行比較，一般當(dāng)M≤15、N≤8時(shí)，視覺效果良好。對于后者，當(dāng)M≤150、N≤150時(shí)程序運(yùn)行正常，而超出該范圍時(shí)程序的穩(wěn)定性不良，有時(shí)會出現(xiàn)因內(nèi)存不足而無法裝載圖形驅(qū)動的現(xiàn)象，擴(kuò)充內(nèi)存后效果良好。鑒于篇幅所限，程序運(yùn)行時(shí)的時(shí)標(biāo)流線效果圖從略。

參考文獻(xiàn)：

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)[M].2版.北京：清華大學(xué)出版社， 1990.

[2] 許創(chuàng)杰.軍事運(yùn)籌學(xué)[M].1版.北京：國防大學(xué)出版社， 1998.

[3] 曹迎槐.M×N在線排序模型之工期求解算法分析[J].公安海警學(xué)院學(xué)報(bào)， 2012（1）.

[4] 曹迎槐.排序模型之TKW遞推算法研究[C].管理科學(xué)與系統(tǒng)科學(xué)研究新進(jìn)展，2003： 19-23.

[5] 曹迎槐.基于標(biāo)準(zhǔn)C的排序模型工期算法仿真實(shí)現(xiàn)[J].公安海警學(xué)院學(xué)報(bào)， 2012（3）.

[6] 浦在明.網(wǎng)絡(luò)法基本原理及其應(yīng)用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.運(yùn)籌學(xué)與實(shí)驗(yàn)[M].北京：電子工業(yè)出版社，2008.endprint

5.3 標(biāo)準(zhǔn)C的圖形模式

基于圖形模式做仿真設(shè)計(jì)是很自然的選擇，而標(biāo)準(zhǔn)C的視覺效果相對于C++和VC相對較弱。另外，一般的C語言教材均很少介紹圖形設(shè)計(jì)方面的內(nèi)容，這便在一定程度上增加了設(shè)計(jì)的難度。圖形模式設(shè)置可通過函數(shù)initgraph（）完成，再通過graphresult（）函數(shù)探測設(shè)置是否成功。圖形繪制完成后，用 closegraph（）在關(guān)閉圖形模式的同時(shí)，將自動釋放其占據(jù)的內(nèi)存資源。另外，基于象素定位的文本輸出函數(shù)outtextxy、類型轉(zhuǎn)化的*itoa，以及在本實(shí)現(xiàn)中使用較多的line、putpixel等，因相對簡單不再贅述。

5.4 空間復(fù)雜度與時(shí)間復(fù)雜度的平衡

基于程序簡潔性和運(yùn)行效率等諸多考慮，本實(shí)現(xiàn)做了大量的技巧性處理，將其中“間隔時(shí)間”的計(jì)算、TKW遞推求解處理等環(huán)節(jié)融合在一起，并將求解計(jì)算與流線圖繪制融合在一起，這也是基于運(yùn)行過程中的空間優(yōu)化需求。

6 算法仿真實(shí)現(xiàn)的效果分析

實(shí)現(xiàn)中的溢出含義[7]有二，一指流線圖超出屏幕邊界，二是指在求解過程中，當(dāng)模型規(guī)模較大時(shí)，因變量數(shù)據(jù)類型的限制而產(chǎn)生的溢出。對于前者，經(jīng)筆者多次運(yùn)行比較，一般當(dāng)M≤15、N≤8時(shí)，視覺效果良好。對于后者，當(dāng)M≤150、N≤150時(shí)程序運(yùn)行正常，而超出該范圍時(shí)程序的穩(wěn)定性不良，有時(shí)會出現(xiàn)因內(nèi)存不足而無法裝載圖形驅(qū)動的現(xiàn)象，擴(kuò)充內(nèi)存后效果良好。鑒于篇幅所限，程序運(yùn)行時(shí)的時(shí)標(biāo)流線效果圖從略。

參考文獻(xiàn)：

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)[M].2版.北京：清華大學(xué)出版社， 1990.

[2] 許創(chuàng)杰.軍事運(yùn)籌學(xué)[M].1版.北京：國防大學(xué)出版社， 1998.

[3] 曹迎槐.M×N在線排序模型之工期求解算法分析[J].公安海警學(xué)院學(xué)報(bào)， 2012（1）.

[4] 曹迎槐.排序模型之TKW遞推算法研究[C].管理科學(xué)與系統(tǒng)科學(xué)研究新進(jìn)展，2003： 19-23.

[5] 曹迎槐.基于標(biāo)準(zhǔn)C的排序模型工期算法仿真實(shí)現(xiàn)[J].公安海警學(xué)院學(xué)報(bào)， 2012（3）.

[6] 浦在明.網(wǎng)絡(luò)法基本原理及其應(yīng)用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.運(yùn)籌學(xué)與實(shí)驗(yàn)[M].北京：電子工業(yè)出版社，2008.endprint