半導體產業的發展是相當快速多變，在競爭激烈與利潤降低之下，為了兼顧成本與競爭力，大多數企業從改善現有機台的使用效率著手。隨著技術的更新，為了讓自己保有一定的競爭力，會於不同時期購入新的機台增加產能，而每階段所購入的機台性能不盡相同，在處理的速度上可能有所差異，因此在銲線站就會出現大量非等效的機台派工問題。 一般封裝廠都會將瓶頸站設置在銲線站，但在銲線站的下一站模壓站，有著很大的設置時間，因此本研究除了原本將銲線站當成瓶頸的情境外，將多考慮加入模壓站，將瓶頸擴大考慮為兩站的情境。除了瓶頸的假設外，在本研究將採取兩個機台的選擇方法(Earliest Completion of Available Machines, ECAM與Earliest Completion of ALL Machines, ECALLM)，來進行瓶頸站的派工比較，希望能找出一個較為有效的瓶頸派工方法。 研究結果發現：ECALLM在兩種瓶頸情境之下，在Makespan與Mean Flow Time表現皆優於ECAM；雙瓶頸的情境之下，表現也皆優於只考慮單瓶頸的情境。

In this research, we study flexible flow line scheduling problems with unrelated parallel machines and with a bottleneck stage. The measures of performances are to minimize makespan, to minimize the number of tardy jobs, and to minimize total tardiness, considered respectively. Several bottleneck-based heuristics are developed to solve these scheduling problems. A bottleneck-driven multiple insertion heuristic (BDMIH) is proposed to solve problems with makespan as the objective. The essential idea of BDMIH is that we think the scheduling of jobs at the bottleneck stage may affect the performance of a heuristic for scheduling jobs in all stages. Therefore, in this heuristic we let jobs entering the sequence at the first stage be driven by their sequence entering at the bottleneck stage. Given an FFL problem with a bottleneck stage, this heuristic first identifies the bottleneck stage, then generates an initial sequence of jobs by a variant of Johnson’s rule (SPT-LPT rule), and finally applies a multiple insertion heuristic to find the best schedule. Another heuristic, a bottleneck-based due-date decision heuristic (BBDDDH), is developed to solve problems with the number of tardy jobs as the objective. The heuristic consists of three steps: (1) Identifying the bottleneck stage, (2) Scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage, and (3) Using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule jobs at bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at bottleneck stage. The last bottleneck-based heuristic, a bottleneck-driven adaptable multiple insertion heuristic (BDAMIH), is constructed to solve problems with total tardiness as the objective. The main idea of BDAMIH is combined with the ideas of BDMIH and BBDDDH. The main difference between BDAMIH and BDMIH is that BDMIH generates an initial sequence of jobs before performing the insertion heuristic; however, BDAMIH is adaptable to select a job within the process of the insertion heuristic. To evaluate the performance of the proposed heuristics, several well-known dispatching rules and heuristics are investigated for comparison purposes and computational experiments are performed on randomly generated test problems. Computational results show that the proposed heuristics significantly outperform all well-known dispatching rules or heuristics. Also, an analysis of the experimental factors is performed, and several interesting insights of the proposed heuristics are discovered.

本研究將探討非等效平行機台問題中具備順序相依整備時間及不同開始工作時間（Unequal ready-time）之情況，並以最小化總延遲工件權重數為目標值，其目的在改善非等效平行機台問題應用於實際產業中製造環境裡所面對的各項挑戰，如印刷電路板的鑽孔和半導體的測試製程。因本研究欲求解之問題是屬於NP - Hard problems 性質之尋優問題，故利用啟發式方法(heuristics)求解為合適的選擇。此外，本研究計畫開發混合式巨集啟發式方法來求解非等效平行機台問題，主要以禁忌搜尋法為主，在鄰域的搜尋上，也藉由變動鄰域尋優法能夠透過鄰域轉換的機制，進而找出更多好的解。由於啟發式方法對於尋優問題常需花費許多時間來計算才能獲得更好的解，為確保增進求解效率與品質，將針對問題特性開發數種初始解產生法，並也嘗試定義幾個能夠減少尋找鄰近解之鄰域。在後續求解改善的過程中，主要整合變動鄰域(VND)及禁忌(TS)巨集啟發式演算法搜尋最佳解。此外，為了評估本文推導之演算法效能，本研究利用設定之條件隨機產生適量模擬現場狀況的測試情境，進而比較本研究所提出之混合式巨集啟發式方法及標準禁忌搜尋法在不同情境下之表現。 / The problem considered in this paper is a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and with unequal ready times so as to minimize total weighted tardy jobs. These problems can be found in real-life manufacturing environments, such as PCB fabrication drilling operations and semiconductor wafer manufacturing dicing. Since the problems are NP-hard in the strong sense, heuristics are an acceptable practice to finding good solutions. A hybrid meta-heuristics are proposed to solve this scheduling problem. The proposed heuristics belong to a type of solution improvement heuristic; therefore, the heuristics start with an effective initial feasible solution then a meta-heuristic is applied to improve the solution. To enhance both the efficiency and efficacy of the heuristics, several different initial solution generators, based on the characteristics of problems, are developed. The meta-heuristic is a hybrid heuristic integrating the principles of Variable Neighborhood Descent approach (VND) and Tabu Search (TS). In order to evaluate the performance of the proposed heuristics, two sets of large number test scenarios will be designed to simulate practical shop floor problems. Computational experiments will be performed to compare the performance of the proposed heuristics, and a basic tabu search algorithm. The results show the proposed heuristic perform better than the basic tabu search algorithm.