• 作者： Hwang, Gene-Ware; Lee, Liang-Sun
• 中文摘要： 回流程序計算之解環問題可以三個步驟得到有效的解法-環路確定,環路矩陣化簡,及 0-1整數線性規劃。由於選擇解環集合之計算時間對問題大小呈指數關係增加,本文提出兩個計算方法克服此困擾。第一個方法以有向圖形代表程序流程圖找出全部環路,並以強連結成分劃分環路出現的區域節省搜尋時間。此方法之計算時間對流程圖之環路數目及分流數目呈線性。第二個方法利用化簡規則相依性質可在低次多項式時間上限內化簡環路矩陣。同時,我們以數個化工程序實例說明求環及化簡方法之效能,0-1規劃的計算時間可大幅減少。本文提出的方法可應用在其它集合涵蓋問題,如網路鎖死,空勤排班,設施位置,電路設計,及失誤檢驗等。
• 英文摘要： An efficient approach is proposed to solve the tearing problem for process flowsheeting in three steps: circuit identification, circuit matrix reduction, and 0-1 integer linear programming. The computation time of torn set selection is in exponential order of the problem size. To overcome this perplexity, two algorithms are set forward in this paper: (1) to determine the circuit matrix of recycle process flow diagram, and (2) to reduce the circuit matrix to decrease the search space of torn sets. The former algorithm is based on a depth-first search method on digraph with the strong component partitioning technique. The computing time needed to find all circuits is linear with the number of circuits and the number of streams in the process flow diagram. For circuit matrix reduction, we prove and employ the interdependence property of reduction rules to develop a polynomial-time algorithm. Several process examples are presented to illustrate the effectiveness and efficiency of the proposed method. The computing time in the 0-1 programming step decreases drastically after the circuit matrix is reduced. The proposed algorithms can also be used in many other set- covering problems such as network deadlock, airline crew scheduling, facility location, circuit design, and fault testing.
• 中文關鍵字： 解環; 解環集合; 集合涵蓋問題; 環路矩陣化簡; 回流程序計算
• 英文關鍵字： Tearing; Torn Set; Set Covering Problem; Circuit Matrix Reduction; Recycle Calculation