基于工期求解的排序模型算法設計與實現

摘要：在任意M×N流程調優排序模型的產品加工順序已確定之前提下，通過分析其加工時標流線圖的結構特征，進而提出了基于表格數據的總工期求解遞推算法，并基于標準C完成了該算法的仿真實現，自動繪制了時標流線圖，還考慮了模型數據的隨機生成和對現成模型數據的讀取并求解等內容。該算法簡潔、明快、可操作性極強，且不受模型規模之限制，時間復雜度為O（n2）。

關鍵詞：網絡規劃；時間間隔；工期；時標流線圖；算法；仿真實現

中圖分類號：TP311 文獻標識碼：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

網絡規劃中的M×N排序問題應用十分廣泛，當工序道數M≤2時通過約翰遜定律即可輕松求解，但M≥3時常用的分組法或分界法僅可得到近優解，這也成了運籌學領域中的一個熱點問題，即排序問題[1]。

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

本文正是針對該狀況，通過分析時標流線圖的結構特征，提出了基于產品加工順序確定時直接從原始數據表上求取工期TKW的算法，并完成了基于標準C的算法仿真實現。

1 基于間隔時間的工期求解

屬于多項式級別，效果理想。

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