頁籤選單縮合
題 名 | A Proposition for a Distance Measure in Neighbourhood Search for Scheduling Problems=對於應用路徑量測以鄰近搜尋法求解排程問題之研究 |
---|---|
作 者 | Janssens,Gerrit K.; | 書刊名 | 工業工程學刊 |
卷 期 | 21:3 2004.05[民93.05] |
頁 次 | 頁262-271 |
分類號 | 494.542 |
關鍵詞 | 演化啟發式解法; 相似性; 排程; 旅行售貨員問題; 車輛途徑問題; Meta-heuristics; Similarity; Scheduling; Travelling salesman problem; Vehicle routing problem; |
語 文 | 英文(English) |
中文摘要 | 演化啟發式解法重複執行移動至鄰近解的步驟,此方法可以有效避免部分機臺的局部最佳化而使得現行解劣化。一個排程問題的解可顯示一連串的特質,求解時可依其特性進行排程。透過距離量測法可以增加搜尋潛在最佳解的可能性。而兩個字元間距的概念可以被應用於表達連續生產的形式。距離量測運算運用於相同字元間的互換,代表不同的單一機臺之排程。當環狀連續符號交換距離為零時,可以被應用於旅行售貨員問題。而連續符號可視為旅行售貨員所往返的各城市。有時一些有象徵性的連續製程被分為細項製程稱為「字元」,而這些「字元」的順序並不重要,此例可以用於平行機臺的排程問題或多運輸器具途徑問題,單一機臺排程問題的距離測量和旅行售貨員問題的應用。此外,以上概念是否可應用於基因演算法已被廣泛討論。 |
英文摘要 | Meta-heuristics use iterations in which moves towards neighbourhood solutions are performed. Their power in escaping from local minima lies in accepting, accor-ding to some mechanism, solutions which worsen the current solution. It is generally accepted, that perturbations of solutions should be small. A solution for a scheduling problem is represented many times as a string of characters. The characters identify jobs to be scheduled. The use of a distance measure can enhance the search mechanism in a set of potential solutions. The notion of distance between two strings can be applied to patterns of production sequences. A distance measure is computed between permutations of the same string, which represent various single machine schedules. If cyclic permutations of the symbol sequence have distance zero, it is applicable to the Travelling Salesman Problem, where the symbol sequence represents the sequence of cities in the tour. Sometimes symbol sequences are divided into sub-strings called 'words' where the sequence of the words has no importance. This example can serve as a scheduling problem on parallel processors or as a multiple vehicle routing problem. The application of the distance measure to the single machine scheduling problem and the travelling salesman problem is shown. Also some implementation issues are discussed if the concept is applied within a genetic algorithm approach. |
本系統中英文摘要資訊取自各篇刊載內容。