應用塔布搜尋法於非等效平行機台之研究－以PCB鑽孔作業為例

A tabu search algorithm for the unrelated parallel machines scheduling problem of drilling operations in PCB factoty

徐烈昭(Lich-Chao Hsu)

指導教授 ： 張百棧

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

摘要

非等效平行機台在製造現場是常見的一個情形，工廠為了加快產品的生產速度或是解決瓶頸機台的問題，常會添購具有相同處理功能的新機台，由於機台間製程能力相仿但加工效率不同，在排程上便產生了許多的問題，因為效能的不同，適當的機台生產組合可有效地減少產品加工時間、機台整備次數、提升生產力並能符合交期。
工件分割的用意在於利用不同的機台加工同一筆工件，使其得以在交期內準時完工。因此，若工件分割的太少就會造成工件的延遲，使得成本上升；若工件分割的適當時，則可有效的在交期內完成加工作業，使排程總成本得以最小化。
本研究以PCB製程中的鑽孔作業為例，探討非等效平行機台在排程時面對工件分割、優先權與整備時間的限制下如何使延遲損失與加工機台成本最小化。本研究提出工件分割準則，使得排程求解時間與LINGO求取最佳解相比得以大幅降低，透過塔布搜尋法改善後可達到穩定且不錯的解。

關鍵字

非等效平行機台排程 ； 塔布搜尋法 ； 印刷電路板 ； 工件分割

並列摘要

Unrelated parallel machines are often seen in the shop floor. For accelerating production rate or to ease the workload of bottleneck machine, new similar machines are acquired. The production capabilities of the parallel machines are similar but production rates are not totally equivalent. Owing to the differences, how to sequence the parallel machines are important not only to effectively reduce the cycle times, numbers of changeovers but also to promote the utility and meet the due-dates.
The purpose of dividing the part is to distribute the divided parts onto the parallel machines for meeting the due-date. Therefore few numbers of divided parts leads to tardiness and high penal cost. If the numbers of divided parts is appropriate, the part will be processed with the minimized total cost.
In this research, we investigate the unrelated parallel machine scheduling problem of drilling operations in PCB factory. Tabu search is applied to minimize the tardiness and production costs of machines under the considerations of part-dividing, priorities, and setup times. It finally leads to satisfactory and stable results.

並列關鍵字

Unrelated parallel machines scheduling ； Tabu search ； Printed Circuit Board ； Preemptive

參考文獻

[46] 邱竣鋒，「利用模擬退火法及塔布搜尋法求解工件非同時到達之單機排程問題」，私立元智大學，碩士論文，民國87年。

[1] Adamopoulos, G.I. and Pappis, P.C., “Scheduling under a common due-date on parallel unrelated machines,” European Journal of Operation Research, Vol.105, pp.494-501, 1998.

[2] Aoyama, E. et al., “Study an small diameter drilling in GFRP,” Composite Structures, Vol.32, pp.567-573, 1995.

[3] Arementano, V.A. and Ronconi, D.P., “Tabu search for total tardiness minimization in flowshop scheduling problems,” Computers & Operations Research, Vol.26, No.3, pp.219-235, 1999.

[4] Armentano, V.A. and Scrich, C.R., “Tabu search for minimizing total tardiness in a job shop,” International Journal Of Production Economics, Vol.63, No.2, pp.131-140, 2000.