由於製造業在生產的過程中常常面對複雜的排程計畫以及現場的不確定狀況，使其在應用ERP或SCM系統時，因缺乏有效的現場管制功能而無法發揮這些系統的整體效能。因為排程問題是現場管制系統的核心，尋找有效且快速求解排程問題的方法是開發現場管制系統成敗的關鍵。過去十年間，針對零工式生產排程問題的研究上已有許多傑出的成果，但我們發現過去研究中所使用的零工式生產排程問題與現場實際的問題之間有許多差異，因此這些研究成果並無法完全由現場所使用。 本研究所強調之現場零工式生產排程問題包括兩個主要特性：1、每一工件可以擁有不等之操作數目，2、事先知道某些機器為瓶頸機器。這是相對於過去研究中的零工式生產排程問題皆假設每一工件會使用每一機器，因此其所產生的問題將使每一工件擁有相等之操作數，且每一機器的重要性皆相等。針對這兩個主要差異，本研究設計兩個實驗：實驗一產生工件擁有’等操作數’與’不等操作數’的問題；實驗二產生現場’無瓶頸機器’與’有瓶頸機器’的問題。在每一實驗中，我們以三個因素：機器使用率、交期設定和操作時間變異，模擬產生12種不同的狀況。然後以7種評量準則比較16個常用的派工法則在不同狀況下的表現。 研究結果發現，在’不等操作數’以及’有瓶頸機器’的生產排程問題中，派工法則的表現確實與其在’等操作數’以及’無瓶頸機器’的問題中的表現有極大的差異。本研究將這些其差異加以分析，並嘗試整理出一些規則以提供現場的使用者在面對不同狀況下選擇適當之派工法則的依據。我們相信本研究的成果不論對理論研究者、現場工程師、或生管軟體系統開發者都有極大價值。

現今企業在面臨市場需求快速變化、接單多樣化，及交貨期短的多重壓力下， 無不致力於改善作業流程以求獲利極大化，尤其是現場生產排程規劃一直是相當複雜而難以管理的部分。現行的軟體例如：企業資源規劃(ERP)、供應鏈管理(SCM)，即是希望藉由資訊科技以解決複雜的生產排程問題。 然而，大部分企業在使用這些系統時都發現，由於缺乏有效的現場管制功能(Shop Floor Control)，使得這些系統的效能受到很大的限制，而目前大多數的現場排程問題為零工式生產問題(Job Shop Problem)。 過去在零工式生產問題的理論上雖有許多傑出的研究，但研究與現場實際的問題之間有許多差異。其中最大的差異在於過去研究所使用的零工式生產問題假設所有的工作會以不同的流程經過所有的機器，然而在現場實際的零工式生產問題中卻顯示每一機器所處理的工作數目變異非常大。現場零工式生產生產排程問題包括兩個主要特性：1、每一工件可以擁有不等之操作數目；2、事先知道某些機器為瓶頸機器。本研究分別針對此兩個特性設計實驗一：產生工件擁有’等操作數’與’不等操作數’的問題；與實驗二：’無瓶頸機器’與’有瓶頸機器’的問題。在實驗中，我們以三個因素：工件數、機器數、和操作時間變異，模擬產生18種不同的狀況。然後以7種評量準則比較50個常用的派工法則在不同狀況下的表現。 研究結果發現，在實驗一與實驗二中，理論與實際現場排程問題在派工法則的表現上確實有極大的差異。本研究將這些其差異加以分析，並嘗試整理出一些規則以提供現場的使用者在面對不同狀況下選擇適當之派工法則的依據。我們相信本研究的成果不論對理論研究者、現場工程師、或生管軟體系統開發者都有極大價值。

由於科技快速的進步以及消費者需求型態的改變，現在的企業面臨到許多的挑戰。因此，企業的競爭型態還必須強調企業整合供應鏈的能力。然而這樣的改變對於企業傳統的生產規劃與排程系統來說是一個相當大的衝擊，因此，能夠妥善的分配有限資源並即時回應環境變動的先進規劃與排程(Advanced Planning and Scheduling; APS)系統成為了最近幾年相當重要的研究課題。而排程問題是其中相當重要的部分，但大部分的研究都是針對生產系統在正常的狀況下所做的討論，而在異常狀況下所做的研究略顯不足，因此本研究希望針對異常狀況發生時最常採取的加班決策來做探討，建立了一個較完整的加班決策模式，使APS系統更為完整，進而提昇企業資源規劃與供應鏈管理系統的使用效率。 / With the rapid progression of technology and changing consumer demand, businesses are facing many challenges and required to be capable of integrating their supply chain. However, this also makes a great impact on the production planning and scheduling systems of traditional industries, and this makes APS, which could allocate limited resources and provide prompt response to the environmental changes, a hot topic. Scheduling problem is important, but most studies are still focusing on production systems under normal situation. Therefore, to make APS system more sound, the study will specifically center on overtime decision that mostly happens under abcdrmal situation, to build up a more complete overtime decision model that further increase the efficiency of enterprise resource planning and supply chain management system.

中文摘要 主計處每年必需編製中央政府總預算書至立法院審議，而目前總預算書的編製是由八百餘家單位預算及分預算機關使用主從式架構的預算編製系統執行編製作業，然後逐層由上級機關彙編而成。本研究欲探討的是若此一主從式架構的系統改採多層式架構時，在其眾多效能的問題之中，討論應用伺服器叢集上的派工法則在工作平均等待時間的表現情況。 使用預算編製作業系統的機關及使用者幾乎是固定而且範圍容易掌握。所以，本研究在此前提下，從部份使用者的作業習慣及資料庫中，估算出模擬模型所需之數據、機率分配及公式。在選擇派工法則的部份，則除了一般常用之「輪流法(Round-robin, RR)、最少連線數法(Least Connections, LC)及最小負載法(Least Load, LL)」之外，本研究另提出「估計負載法(Estimated Load, EL)」。即是因為在瞭解使用者端特性的前提下，事先計算影響負載的數據，便可以估算負載情況並運用在派工法則上。 本研究的結果顯示EL法在各項工作的服務時間估算誤差愈小時，其表現的結果愈好，其各項工作的平均等待時間相當接近做為測試基準的最小負載法。 / Abstract The Directorate-General of Budget, Accounting and Statistics (DGBAS) of the Executive Yuan (EY) is responsible to compile the General Budget for Central Government and submit to Legislative Yuan every year. The sources of General Budget are processed by 832 government agencies and subordinate agencies by using the same software that is based on client/server architecture. This paper discusses about performance of dispatching rules on cluster-based application servers when this software architecture transferring to n-tiered architecture. We carry out the comparative studies using four dispatching rules, namely, Round-robin (RR), Least Connections (LC), Estimated Load (EL), and Least Load (LL). The LL rule is used as the baseline in our analysis and the performance metric is average waiting time. Unlike general web-based software, we know clients who use this software. So we can estimate job arrival rate, job size, and even service time. In view of this, we proposed the EL rule in this paper. Our analyses indicate that the EL rule performs very well. As long as accuracy in estimating service time getting better, the EL rule is a good choice.

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.

由於網際網路的發展，使得全球環境變遷，競爭越來越激烈，企業必須面臨快速的需求變化，以及訂單履行時間縮短的問題，因此如何有效的利用生產規劃和現場排程來幫助企業達到較高的訂單達成率和即時反應現場產能一直是製造業努力的目標。 在排程的問題中，用派工法則來解決排程問題的工廠類型，主要集中在零工式生產系統及流程式生產系統，而進一步加入平行機器概念，即是彈性零工式生產及彈性流程式生產。而現在許多的服務業也都是屬於彈性流程式生產的模式，而且還具有迴流(recirculation)之性質，而之前使用在不具迴流性質之彈性流程式生產的派工法則，在具有迴流性質之彈性流程式生產中是否仍然可以表現良好，是值得探討的。然而更進一步在此具有迴流性質之彈性流程式生產中加入多工的性質，使工作可以被兩個或兩個以上的機器或操作人員進行處理，則運用哪個派工法則讓機器或操作人員選擇工作來進行處理，可以使得選定的目標值有良好的表現，是相當值得研究之問題。 / As information technology advances, whole world environmental trend and the competition is more and more intense. The enterprise must face faster demand changes and the problem of shorter order fulfillment. Therefore, how to apply efficient production planning and shop floor scheduling to attain a better order fulfillment and real time production of shop floor capacity is the goal enterprises strive toward. The shop floor scheduling problems using dispatching rules to solve are focus on job shop scheduling problems and flow shop scheduling problems. Moreover, those problems adding the concept of parallel machine will change into flexible job shop scheduling problems and flexible flow shop scheduling problems. Many service industries also belong to this type. In addition, those service industries’ processes also contain the important characteristic of recirculation. Now, there are two problems I would like to solve. First, Whether the dispatching rules which can get good results in flexible flow shop scheduling problems will also get good results in flexible flow shop scheduling problems with recirculation. Second, I add the characteristic of parallel machine into my problem, so it means jobs in the process can be operated by two or more workers. Therefore, which dispatching rule will get better results based on chosen achievement targets in the problem is very interesting to research.