排序問題之時標(biāo)流線圖繪制仿真實現(xiàn)

摘要：在排序問題（Sequencing Program）中，當(dāng)工序道數(shù)M≥3時，計算總加工時間常用的方法便是繪制時標(biāo)流線圖，但在教學(xué)過程中手工繪圖相對煩瑣，因此，筆者開發(fā)的網(wǎng)絡(luò)規(guī)劃仿真模塊不僅實現(xiàn)了時標(biāo)流線圖的自動繪制，而且形象直觀，經(jīng)教學(xué)實踐，效果良好。

關(guān)鍵詞：排序問題;工期;時標(biāo)流線圖;模擬仿真

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

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

1 流程調(diào)優(yōu)

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

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

2 M×N模型之時標(biāo)流線圖

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

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

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

3 時標(biāo)流線圖設(shè)計與實現(xiàn)

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

接著還需計算當(dāng)前排序模型對應(yīng)之各示意流線的坐標(biāo)（像素點）。先計算第一項產(chǎn)品之第一道工序?qū)?yīng)的流線坐標(biāo)，再計算第一道工序上所有產(chǎn)品對應(yīng)的流線坐標(biāo)（第一個產(chǎn)品除外，它已經(jīng)賦值），還得計算第一個產(chǎn)品在各道工序上加工時，對應(yīng)的流線坐標(biāo)（第一道工序除外，它已經(jīng)計算完成），最后計算當(dāng)前排序模型中，第2道工序及其以后的，從第2個產(chǎn)品開始的所有加工時間對應(yīng)之流線，以及各分隔線，即第一道工序中各產(chǎn)品之分隔線、各道工序最后一產(chǎn)品之分隔線等內(nèi)容。

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

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

參考文獻：

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

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

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

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

[5] 曹迎槐.LP模型標(biāo)準化教輔軟件設(shè)計與實現(xiàn)[J].電腦知識與技術(shù)，2018，14（17）：87-88.

【通聯(lián)編輯：謝媛媛】