排序問題之時標流線圖繪制仿真實現

摘要：在排序問題（Sequencing Program）中，當工序道數M≥3時，計算總加工時間常用的方法便是繪制時標流線圖，但在教學過程中手工繪圖相對煩瑣，因此，筆者開發的網絡規劃仿真模塊不僅實現了時標流線圖的自動繪制，而且形象直觀，經教學實踐，效果良好。

關鍵詞：排序問題;工期;時標流線圖;模擬仿真

Abstract： During the sorting problem （sequencing program），And when the number of steps m≥3，The common way to calculate the total processing time is to draw the time scale streamline diagram. But in the process of teaching， manual drawing is relatively cumbersome. Therefore， The network planning simulation module developed by the author not only realizes the automatic drawing of time scale streamline diagram. And the image is intuitive， through teaching practice， the effect is good.

Key words： sequencing problem; time limit for a project; Timeline Flow Chart; analog simulation

流程調優又稱排序問題（sequencing program），亦稱工件加工安排問題，是一類典型的組合優化問題，它一直是運籌學研究的熱點和難點之一。N個產品在M道工序的加工排序問題之M×N模型，當各產品加工次序相同時稱流水作業，當各產品之加工次序不同時也稱加工作業，顯然流水作業是加工作業的特殊情況。雖然當M=2時，通過約翰遜定理可得最優解，但當M≥3時該問題卻是典型的NP問題[1]，目前尚無最優解求解算法。

1 流程調優

雖然約翰遜定理號稱解決了M=2時的排序問題，但他給出的只是產品的最優加工順序，并未對最后的總加工時間作出公式性結論，實用中需通過手動繪制時標流線圖來計算總工期。筆者曾給出了基于給定加工順序時的表上工期遞推算法[2]，但計算相對復雜煩瑣，并不利于課堂教學。考慮教學過程中對排序問題求解算法原理的形象和直觀性要求，筆者在開發《軍事運籌學原理仿真模擬系統》（已獲軟著登記）時針對流程調優中的時標流線圖也做了專門設計，后經教學實踐，效果良好。圖1即“流程調優”模塊的操作主界面。

其中的“M×N模型”按鈕和“1×N模型”按鈕分別維護的兩種模型的具體加工數據，因在1×N模型中，關注的角度一般不再是總加工時間，而是諸如平均等待時間之類的轉換思路[3]，所以，單獨設置了操作界面。當M=2時，可以利用圖1中的“約氏解法”模擬約翰遜定律之求解示意，鑒于本文的重點是時標流線圖，故這里對“約氏解法”不再做詳細說明。基于同樣的原因，本文也不再對“分組法”“分界法”和“窮舉法”逐一介紹。

2 M×N模型之時標流線圖

在圖1所示之操作主界面中，單擊“M×N模型”按鈕即可打開該子模塊[4]，如圖2。

M×N排序模型比較復雜。其模型規模，即M和N的值，可通過圖1中的“設置”命令按鈕來設定（細節從略），圖2即6道工序（M=6）、8個產品（N=8）時的模型狀態示意。當然，圖中的數據是通過隨機模式自動產生的，亦可手動維護之[5]。其實，使用中亦可通過“導入”命令按鈕將以前保存的模型數據導入當前系統，亦可將當前的模型數據“保存”起來以備后用。模型數據維護完備后，單擊圖1中的“流線圖”命令按鈕，即可自動繪制當前M×N排序模型以當前默認的產品加工順序時的時標流線圖，圖3所示就是一個6道工序7個產品的時標流線圖繪制結果。

時標流線圖繪制完成后，可通過屏幕左上角的三組藍色箭頭，對流線圖做適當處理，諸如平移、拉伸和壓縮等操作。當鼠標移動到“工期”文本框時，當前模型對應之總加工時間即顯示出來，如圖4。

3 時標流線圖設計與實現

為盡量滿足仿真的實用性，考慮仿真軟件的最大產品數為50，最大工序數為20，加工時間取值范圍為1-50。為方便后面對各時標流線的靈活控制或處理，還設置了移動、拉伸、壓縮等諸多操作。將每個產品對應之每道工序的加工時間都用一個線性控件來表示。繪制時標流線圖之前，須根據當前排序模型的實際狀態，提前計算并設置（或顯示）流線圖坐標之水平標尺線（像素點），而縱坐標始終在框架高度之中間（像素點），橫向從左邊界開始至框架右邊界。每隔一個時間單位（可在“設置”模塊中靈活改變）做標記。其對應部分VB代碼如下：

接著還需計算當前排序模型對應之各示意流線的坐標（像素點）。先計算第一項產品之第一道工序對應的流線坐標，再計算第一道工序上所有產品對應的流線坐標（第一個產品除外，它已經賦值），還得計算第一個產品在各道工序上加工時，對應的流線坐標（第一道工序除外，它已經計算完成），最后計算當前排序模型中，第2道工序及其以后的，從第2個產品開始的所有加工時間對應之流線，以及各分隔線，即第一道工序中各產品之分隔線、各道工序最后一產品之分隔線等內容。

當然，以時標流線圖繪制為基礎，結合分組和分界等算法，考慮教學過程中小規模模型窮舉仿真之可能性，當可輕松解決M≥3時該排序問題的最優解分析，但限于篇幅，暫且從略。

因水平所限，不妥和錯誤之處，敬請大家批評指正！

參考文獻：

[1] 錢頌迪.運籌學[M].北京：清華大學出版，1993.

[2] 曹迎槐.基于工期求解的排序模型算法設計與實現[J].電腦知識與技術，2014，10（18）：4280-4283.

[3] 曹迎槐，尹健，梁春美.軍事運籌學[M].北京：國防工業出版社，2013.

[4] 曹迎槐，張靜，趙強.矩陣對策之降階算法設計與實現[J].信息系統工程，2020（10）：121-122.

[5] 曹迎槐.LP模型標準化教輔軟件設計與實現[J].電腦知識與技術，2018，14（17）：87-88.

【通聯編輯：謝媛媛】