利用模擬退火法及塔布搜尋法求解工件非同時到達之單機排程問題

On Scheduling Unequal Release Time for Single Machine by Simulated Annealing and Tabu Search Algorithm

邱竣鋒(Jiunn-Feng Chiou)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(1997年)

摘要

本研究主要在探討工件非同時到達時，以總加權完工時間最小為目標之單機排程問題。此問題不同於工件同時到達之靜態排程問題，也因為工件非同時到達的特性，再加上工件並非是一個個緊接著安排，也就是工件與工件間允許有閒置時間，故增加了解題的複雜度。

本研究透過問題的特性，把各個欲安排的工件以一分解演算法將之區分成數個區塊，再經由模擬退火演算法及塔布搜尋法，將各個工件的排序予以攪動（對調或插入），但不可違反原本之區塊順序，來產生不同之排程，以試圖減小總加權完工時間。而在模擬退火法或塔布搜尋法中，我們加入相鄰工件先後關係的判定，使我們在攪動的過程中所產生之新排序不會被完全的接受，以減少搜尋時間，進而迅速找出近似最佳解。

經過本研究實驗的結果顯示，模擬退火法雖然花費了比較多的求解時間，但是可求得一比較好的近似最佳解，與最佳解誤差約在0.1%；而塔布搜尋法求解時間則較快，且亦可求得誤差約0.5%的高品質解。

關鍵字

非同時到達 ； 單機排程 ； 模擬退火法 ； 塔布搜尋法

並列摘要

This research addresses a single machine scheduling problem with unequal release time to minimize the total weighted completion time. Due to the unequal release time, inserting idle time between consecutive jobs in some situations is necessitated. Therefore, the cost function is concave and the complexity of computing is increased.

We find that under certain conditions the problem can be decomposed into several blocks with smaller problem sizes. Therefore, a decomposition algorithm for this problem is developed. The algorithms of simulated annealing and tabu search are then proposed to disturb the job sequence in order to decrease the total weighted completion time while keeping the block sequence retained. We also present a theorem about the dominant relationship between consecutive jobs to eliminate unfavorable schedule for avoiding excessive computing in the process of disturbing.

Experimental results show that the simulated annealing procedure proposed in this study solves the problem accurately with 0.1% deviation from the optimal solution, while the tabu search procedure obtains the solution with 0.5% deviation from the optimal solution. The choice between these two procedure depends on the criteria of the user, or they can use both algorithms to find a better solution if computation time is not a real concern.

並列關鍵字

Unequal Release Time ； Single Machine Scheduling ； Simulated Annealing ； Tabu Search

參考文獻

1. A Islam and M Eksioglu, "A tabu search approach for the single machine mean tardiness problem," Journal of Operational Research Society, 48, 751-755, 1997.

2. A.M.A.HARIRI, C.N.POTTS "An Algorithm for Single Machine Sequencing with Release Dates to Minimize Total Weighted Completion Time," Discrete Applied Mathematics, 5, 99-109, 1983.

3. Barnes, J.W., and Laguna, M., "A Tabu Search Experirnce in Production Scheduling," Annals of Operation Research, 41, 141-156, 1993.

4. ─, "Solving The Multiple-Machine Weighted Flow Time Problem Using Tabu Search," IIE Transations, 25, 2, 121-128, 1993.

5. Burkard, R. E. and F. Rendle, "A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization," European Journal of Operational Research, 17. 169-174, 1984.