A Proposition for a Distance Measure in Neighbourhood Search for Scheduling Problems

演化啓發式解法重複執行移動至鄰近解的步驟，此方法可以有效避免部分機台的局部最佳化而使得現行解劣化。一個排程問題的解可顯示一連串的特質，求解時可依其特性進行排程。透過距離量測法可以增加搜尋潛在最佳解的可能性。而兩個字元間距的概念可以被應用於表達連續生產的形式。距離量測運算運用於相同字元間的互換，代表不同的單一機台之排程。當環狀連續符號交換距離爲零時，可以被應用於旅行售貨員問題。而連續符號可視爲旅行售貨員所往返的各城市。有時一些有象徵性的連續製程被分爲細項製程稱爲「字元」，而這些「字元」的順序並不重要，此例可以用於平行機台的排程問題或多運輸器具途徑問題，單一機台排程問題的距離測量和旅行售貨員問題的應用。此外，以上概念是否可應用於基因演算法已被廣泛討論。

關鍵字

演化啓發式解法；相似性；排程；旅行售貨員問題；車輛途逕問題

並列摘要

Meta-heuristics use iterations in which moves towards neighbourhood solutions are performed. Their power in escaping from local minima lies in accepting, according 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.

並列關鍵字

Meta-heuristics ； Similarity ； Scheduling ； Travelling salesman problem ； Vehicle Routing problem

參考文獻

Brucker P.(2001).Scheduling Algorithms.

Google Scholar

Campos V.,M. Laguna,R. Marti(2003).Journal on Computing.

Google Scholar

Chang S.,H. Matsuo,G. Tang(1990).Worst-case analysis of local search heuristics for the one-machine total tardiness problem.Naval Research Logistics Quarterly.37,111-121.

Google Scholar

Chen C-L.,V. S. Vampati,N. Aljaber(1995).An application of genetic algorithms for flow shop problems.European Journal of Operational Research.80,389-396.