The Optimization of a Two - Stage Fspm under Space Constraint by Tabu Search

禁制搜尋法對空間限制下的二階層FSPM最佳化之應用

翁維珠(W. C. Weng) ； 洪振發(C. F. Hung)

《中國造船暨輪機工程學刊》 22卷3期 (2003/08) Pp. 133-141

https://doi.org/10.29982/JTSNAME.200308.0003

摘要

本文探討一個二階層FSPM問題：一個工作流動場(flow shop)中，第一層施工場配有相同機器數台，第二層相同機器配置數未知且有空間限制，每項工作必須由第一層施工完成後，檢查第二層空間是否夠用且有閒置機器可用才能進入第二層施工，目標是為所有工作進行最佳排序，使得總施工時間(makespan)最短且第二階層配置相同機器台數最少。為了簡化這多目標最佳化問題，本文提出二步驟排程法(two-step scheduling approach)，並且應用禁制搜尋法搭配回跳機制，針對三種不同問題大小的研究範例進行最佳工作排列的搜尋，使得總施工時間最短。最後並以甘梯圖和第二層施工場的未用空間歷程變化圖來顯示結果。

關鍵字

排程最佳化 ； 總工時 ； 平行機器 ； 空間限制條件 ； 禁制搜尋法

並列摘要

In this paper we studied the optimization of a two-stage flow shop problem with parallel machines (FSPM) where the
free space of stage 2 must be checked if it is enough for the job to be processed due to the space limitation. The job
sequence is optimized so that the makespan is shortest and the number of parallel machines needed on stage 2 is minimum.
To simplify the two criteria optimization problem, a two-step scheduling approach is proposed in this paper. The tabu
search method with back jump is used to find the optimal job sequence in order to minimize the makespan. Three cases
have been examined and the results have been shown in the form of Gantt chart and the time history of unused space in
stage 2.

並列關鍵字

Scheduling Optimization ； FSPM ； Makespan ； Parallel Machines ； Space Constraint