利用塔布搜尋法求解流程型工廠群組排程問題

Solving Flow Shop Group Scheduling Problem by Tabu Search

吳家塘(Chia-Tang Wu)

指導教授 ： 張百棧

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

摘要

本研究主要是探討利用塔布搜尋法來解決流程型工廠群組排程的問題，
實際工廠的生產形態中，目前大部分工廠採用多階的生產形態，而多階
生產方式的群組排程是屬於NP-complete的問題，此類型的問題在以尋
找最佳解為目標的前提之下，往往必須花費大量的運算時間。本研究第
一階段透過啟發式方法來計算群組排程問題的初始排程，第二階段將初
始排程各個工件予以擾動，產生不同的排程，經由塔布表單中短期架構
，記錄本次決策前的數次記憶，由這些記憶配合鄰近解和移動路徑做出
最佳決策，逐步逼近最佳解，試圖在短時間內減少總完工時間，直至符
合結束法則為止。

本研究中，經過塔布搜尋法的尋優改善，在不同大小問題下，可行解的
平均改善率可達2.84%~12.34%的改善率﹔而塔布搜尋法的交換法則部份
，經由平均改善率的比較，可得到插入式變動法明顯優於交換式變動法
的結論。

關鍵字

流程型工廠 ； 群組排程 ； 塔布搜尋法

並列摘要

This research addresses the group scheduling in a flowhsop
environment using Tabu search. In most real world manufacturing
environment, multi-stage scheduling is adopted for most
industry. This problem is proved to be NP-complete and
therefore lots of computations are required for achieving
the optimal solution. The procedure developed in this research
is divided into two stages. At the first stage, a heuristic
algorithm is developed to find an initial schedule for group
scheduling. At the second stage, the initial job is disturbed
and different schedules is therefore produced. The approach that
tabu search employed is to keep a list of our last few moves
through the short-term scheme in tabu list. Before reaching the
local optimum the neighborhood procedure incorporated with the
moving path will improve the solution and force
diversification to the optimal solution in a short elapsed time.
The procedure is continued until the termination rules is
reached and therefore the makespan is decreased.

Experimental results show that the proposed tabu search
improves the overall average quality from 2.81% to 12.34% and
the insert move is compared favorably with the swap move term
of average quality improvement in the exchanging rules of tabu
search.

並列關鍵字

flow shop ； group scheduling ； Taub search

參考文獻

【40】陳宗明，「流程型工廠之群組排程研究」，私立元智工學院工業工程研究所，碩士論文，民國82年

【1】Johnson, S. M.," Optimal Two and Three Stage Production Schedules with Setup Times," Naval Research Logistics Quarterly, no.1, pp.61-68,1954.

【3】Ignall, E., and Schrage, L.E., "Application of the Branch-and-Bound Technique to Some Flow-Shop Scheduling to Some Flow-Shop Scheduling Problems," Operations Research, No.13, pp.401-412, 1965.

【5】Emmons, H.," One-Machine Sequencing to Minimize Certain Functions of Job Tardiness," Operations Research, 17(4),pp.701-715, 1969.

【6】Campbell, H. G., Dudek, R. A., and Smith, M. L.," A heuristic algorithm for the n-job m-machine sequencing problem," Management Science, B, No.16, pp.630-637, 1970.