禁忌搜尋法在彈性零工型製造系統排程之探討

摘要

在過去排程問題之求解中，往往爲了縮減問題的範圍以提昇求解的效率，而大多以「單一製造途程」爲前提來從事其相關之硏究：然而在彈性零工型工廠之排程研究上，毎—個工作的製造途程不再只是一已經決定、一成不變的條件，因此在探討此類排程問題的同時必須加以考慮其多製程規劃的特性，如此才能使排程績效得以提高。本研究所探討的問題即是同時考慮多製程規劃及各工件的作業排程特性，將研究過程分爲二階段，統籌運用一套「啓發式」的解法來達成使工件的平均遝延時問最小化之排程目標。首先，本研究分析現有排程法則之特性與功能後，發展出一可供笫二階段使用之啓發式初始解演算法，並以一實驗分析來驗證與突顯出此構建的演算法與先前學者所發表之演算法在效率與品質上的差距。再者，研究中採用禁忌捜尋法，運用其觀念與作法以發展出針對預定排程目標的啓發式改善解演算法。並針對影響禁忌捜尋法捜尋成效之參數或因子作實驗分析，透過分析結果尋找禁忌捜尋結構之最佳設定，期望能透過本硏究的完成有助於日後探討此領域學者的參考與發展。

Abstract

In this research, a heuristic algorithm is proposed to solve the flexible job shop scheduling problems. The approach is divided into three phases: first, a rule called ESCII is designed to get the initial solution for the addressed problem. Secondly, a near optimal improving method known as Tabu Search is employed to improve the solution found in the first phase. Finally, through statistical analysis to analyze the factors which affect the performance of the designed heuristics significantly, and show the adaptability of designed heuristics.

關鍵字:

• 排程
• 彈性零工型工廠
• 多製程規劃
• 平均延遲時問
• 禁忌捜尋法

Keywords:

• flexible job shop scheduling
• Tabu Search