在任何一個工廠之中，排程活動皆居於生產管理的樞鈕位置，本研究擬就幾個基本和 擴充的單機排程模型（各具有不同的假設、目標、方法），作一番有系統的整理與探 討。 第一章導論。內容包含生產系統的排程問題、排程的功用、排程理論的歷史背景、文 獻探討、研究動機、目的、架構、範圍、方法等。 第二章單機生產排程模型。內容包含各類單機模型之前提、假設、問題定義、理論、 解法邏輯、程式流程、實例分析等。 第三章整排程子系統與生產系統之基本考慮。內容包含動態單機模型器、軟體工程系 統實施、介面問題等。 第四章模擬與其他模型之比較。內容包含模擬及其他模型之數據結果分析、比較評估 。 第五章結論。內容包含生產排程在管理上之意義、應用與展望（電腦輔助排程及工廠 自動化）等。

由於科技快速的進步以及消費者需求型態的改變，現在的企業面臨到許多的挑戰。因此，企業的競爭型態還必須強調企業整合供應鏈的能力。然而這樣的改變對於企業傳統的生產規劃與排程系統來說是一個相當大的衝擊，因此，能夠妥善的分配有限資源並即時回應環境變動的先進規劃與排程(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.

IEEE 802.16標準中，有所謂Multi-hop Relay (MR)的概念，其中存在很多問題需要解決，所以在IEEE 802.16j標準中提出中繼傳輸站(Relay Station，RS)來延伸原來的涵蓋範圍及解決遮蔽效應造成訊號衰弱的問題。但在MR中由於多了中繼傳輸站來傳遞資料，網路拓樸變得相對複雜，資料從發送端到接收端的路徑變長了，在資料大量傳輸的狀況下，會因干擾及壅塞的問題變得嚴重而導致整個網路效能低落。本研究提出一套具干擾感知的排程方法，可有效提升網路效能。本方法分為三個部分，首先在允入控制階段盡可能選取高調變的連線，其次利用空間距離的分群概念提出TZG (Time Zone Grouping)方法，以逆時針的方式區分不同RS傳輸的時區，最後以調整分區內non-real time服務的頻寬需求，減少RS在access zone頻寬的浪費。我們利用NS2進行模擬實驗分析，驗證所提出的方法在利用分區傳送避免碰撞下，UGS的delay time相較於未分群的方法可有效改善約33%，ertPS可改善約29%，rtPS可改善約20%，而系統throughout相較於其他僅選擇最大access link的頻寬需求作為access zone大小的方法最多可提升約15.5%的效能。 / As we know, there is Multi-hop Relay concept in standard of IEEE 802.16. But there are still many problems unsolved in WiMAX, so IEEE 802.16j propose a new station type, relay station, to extend signal coverage and improve the signal intensity which affected by shadow fading. Since there are many relay stations in the coverage of base station, data transmission and path routing become more complexity. At the same time, the transmissions become close, more interference and network congestion will decrease the efficiency of data transmission in the network. This research proposes a frame scheduling with interference aware, which consist of three parts. First, we make the better modulation of links get higher priority; Second, we use concept of distance to proposed Time Zone grouping (TZG), which set RS into different group in counterclockwise way to reduce interference; Third, adjusting bandwidth allocation in access zone to decrease bandwidth waste in access zone. We implement our algorithm in NS2 simulator, the result shows that our method can improve delay of UGS about 33%, ertPS about 20%, rtPS about 20% than RTDS(Real time Distributed Scheduling ), and the system throughput can grow about 15.5% than the mechanism that just choose maximum requirement in access link of all BS/RS as access zone.

IEEE 802.16標準是針對無線城域網路(Wireless Metropolitan Area Network)而設計的，它支援服務品質(QoS)，而且具有相當高的傳輸速率。每一種應用服務都有不同的型態，根據這些不同的型態，802.16 定義了四個不同的服務品質類別。然而，最關鍵的部份－封包排程卻沒有被定義在802.16標準裡面。在這篇論文中，我們提出了一套完整的允入控管(call admission control)和上行封包排程的架構。首先，我們先以令牌桶(token bucket)機制為基礎，設計了一套802.16專用的允入控管和上行封包排程的模組。接著我們介紹如何將令牌桶機制套用至一般的連線。我們找出了一個預測連線的延遲(delay)和漏失率(loss rate)的模型，接著可以利用這個模型，並透過簡單的搜尋演算法來找出適合的令牌速率和令牌桶的大小。模擬的結果表示，我們的允入控管和上行封包排程能夠確實對具有即時性質的連線的提供保證，且我們將令牌桶機制套用到一般連線的模組也能準確的運作。最後，我們也提出了一個簡單的整合實例並評估其效能。 / The IEEE 802.16 standard was designed for Wireless Metropolitan Area Network (WMAN). It supports QoS and has very high transmission rate. According to different application types, there are four QoS classes defined in the IEEE 802.16 standard. The key part of 802.16 for QoS– packet scheduling, was undefined. In this thesis, a complete call admission control (CAC) and uplink packet scheduling is presented. We first proposed a token-bucket based uplink packet scheduling combined with CAC. Then a model of characterizing traffic flows by token bucket parameters, namely token rate and bucket size, is presented. We proposed a queuing model to predict the delay and loss rate for a token bucket controlled traffic flow. In order to fulfill token bucket based CAC, we need to find appropriate token rate and bucket size for any flows. A simple search algorithm coupled with our queuing model can be used to achieve this. Multiplexing of two traffic flows is also introduced. The simulation results show that our CAC and uplink packet scheduling can promise the delay requirement of real-time flows and prevent each class from starvation. The precision of our token rate estimation model is also validated. Finally, a simple integration of our CAC, uplink scheduling, and multiplexing is evaluated.

本論文共壹一冊，約四萬五千字，分七章。 提要： 考慮一工作站中有一組工作（Ji, i ＝１……Ｎ）需經由一部機器完成之排程問題。 假設每一工作Ji有已知之到期日Di，其過期之違約金計算可為任意函數，且由於技術 或工作性質等因素而使得工作之進行有一定之順序限制。對此模型最佳解之求得可結 合二元結構表示法及動態規劃法找出使總違約金為最少之工作順序。本文假設工作J 之完成日Ci，違約金Pi，而過期之違約金計算函數為Pi、MAX ｛Ci－Di０｝，而探討 如何結合二元結構表示法及動態規劃法，以較節省之電腦空間求得最佳解，及在允許 改變工作間飲優先順序後，如何迅速求得新解。此外將模型一般化，允許工作之完成 時間為多變量常態分配之隨機變數，並求得最佳解。

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

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

IEEE 802.11/802.16無線網路的MAC機制為儘可能爭取傳輸機會，此機制於壅塞的網狀網路環境中將造成傳輸速率過高及非必要封包碰撞的問題，進而嚴重降低網路傳輸效能。 / 本篇論文的目的旨在改善無線網狀網路環境中，因IEEE 802.11/ 802.16本身的MAC機制所導致的效能低落問題。我們利用賽局理論中零和賽局以強化競爭方式並計算及應用合理傳輸機會(Transmission Opportunities)及傳輸時機(Transmission Timing)，再依此將傳輸速率調降至合理的數值以降低無效封包的傳輸率。同時，此傳輸機會及傳輸時機將作為路徑選擇的重要依據。末了，我們利用網路模擬器NS2 (Network Simulator ver. 2)驗證及評估本論文所提出之方法的效能。 / The MAC mechanism of IEEE 802.11 and 802.16 competes as much transmission opportunities as possible. In a congested wireless mesh network, this greedy competition will result in inappropriate data rates and unintentional packet collision problems, and thus reduce network performance seriously. / The objective of this research is aimed to solve these two problems to enhance the performance of wireless mesh networks. We propose a zero-sum-game based contention-enhancement in MAC mechanism to estimate rational transmission opportunities and transmission timing dynamically. These estimations will then be used in reducing unsuitable packet data rates and selecting better routing paths. At last, we use NS2 (Network Simulator ver.2) to evaluate the system performance of our proposed methods.

受到封包網路原本忽略時效性特性之影響，對時效性要求極高的多媒體網路服務，如Voice over IP (VoIP)以及Video on Demand (VoD)在All-IP整合的核心網路上提供時，其服務品質低於傳統之電路交換網路。 封包在網路的傳遞過程中受到各種因素之影響，於到達目的地時，可能會造成long delay time，high jitter或packet loss，而在目的地端幾乎已經沒有補救機會，故而如果能在傳遞的過程中，依封包的時效性及重要性做適度的次序調動(rescheduling)而不要依序傳遞(FIFO)，讓過遲的封包提前送出，而將有時間餘裕的封包稍緩送出，如此截長補短，可提高網路效能及整體QoS滿意度。 我們在BBQ (Budget-Base QoS)的架構下發展一套簡單而有效的方法，在單佇列(Single Preemptive Queue)及多佇列(Multiple FIFO Queue)的router架構下，根據封包時效性及重要性賦予合適的profit function，並參考封包在後續路程上各router的負載狀態以便能更精確預估封包是否能及時到達目的地並調整profit function參數以調整封包的送出順序，如此能提高排程的效能。 我們先對單一服務等級的封包排程進行研究，獲得參數調整之技巧，再根據其結果設計多服務等級的封包排程方法，其重點在於如何調配profit function給不同的服務等級。 我們藉由NS-2模擬模擬器進行實驗，評估本方法的效能，實驗結果顯示我們的方法可以較每個router僅根據自身所知的資訊進行排程更可以有效提高網路效能，且能對不同的服務等級做差異化處理以提高整體QoS滿意度。最後在多等級服務的實驗環境及評估指標下，網路高負載的情況，本方法與Simulated Priority Queue排程演算法比較可以提升34%的整體滿意度。 / Running time sensitive multimedia services such as Voice-over-IP (VoIP) and Video-on-Demand (VoD) on All-IP networks may have lower quality than that on the traditional circuit-switched networks. Influenced by many factors, packets transported on a packet-switched network, may suffer from long delay time, large jitter and high packet loss rate. When a packet arrives its destination late, there is no way to correct the problem. Thus, it will be beneficial if routers could forward packets base on their timeliness and importance, instead of using First-In-First-Out (FIFO) service plan, giving important late packets proper precedence. The overall QoS satisfaction will be improved significantly. In this thesis, we develop a simple and effective scheduling policy based on this concept for the environments where packets have predefined hop-by-hop time schedule. Routers are assumed in two different queue architectures: ideal Single Preemptive Queue router and practical Multiple FIFO Queue router. To forward a packet, a router first assigns a suitable profit function to the packet based on its timeliness and importance as well as the loading status in its succeeding routers along its predefined traveling path, then inserts the packet into an appropriate position in the output queues. Taking the loading status of succeeding routers into account could predict more accurately whether the packet could reach its destination on time or not. We conduct the research for the single service class environments first to learn the characteristics of this new scheduling policy, and then for the multiple service class environments based on the knowledge acquired. The challenge is to find the best way to assign proper profit functions to different classes of packets in order to utilize resources more wisely, e.g. urgent and important packets get precedence. We evaluate the performance of this approach by simulation using NS-2 network simulator. Simulation results show that our approach outperforms our previous version which doesn't take the loading status of succeeding routers into account. Furthermore, our approach can outperform the Simulated Priority Queue by at least 34% under heavy load and our evaluation metrics.

MapReduce 是目前最熱門的雲端技術之一，用來處理大量資料，不論資料探勘、非結構化的紀錄檔、網頁索引處理及其他需要大量資料處理的科學研究，都可透過 MapReduce 得到極佳的執行效率。MapReduce 為一分散式批次資料處理程式框架，將一個工作分解為許多較小的 map 任務以及 reduce 任務，由map 處理每個小問題，再由reduce將問題彙整，得到最終的結果。 Hadoop 是一個開放原始碼的 MapReduce 架構，並且被廣泛地應用在以大規模資料運算為主的雲端計算。Hadoop有一個非常重要的元件稱為scheduler ，是 hadoop的中樞，負責調度、指派任務和資源分配的優先順序。Scheduler的任務選擇與分配方式，將會影響 MapReduce 工作的執行效率與整個叢集的使用率，目前Hadoop預設的scheduler是將任務以先進先出(FIFO)的方式進行排程。提升MapReduce運算效能的挑戰之一為如何適當的分配Mapper 和 Reducer給雲端裡的每個節點來執行。儘管過去已經有許多改善MapReduce運算效能的研究，但是大部分的方法在實際的運作中，仍存在很多的問題，如工作節點的動態負載、data locality的問題，計算節點的異質性等等。我們發現目前Hadoop對於這些問題並沒有妥善處理，並且在相關的情況下，整體效能仍有改進空間。 我們提出Data Locality Driven Scheduler(DLDS)的方法，並實踐在 Hadoop上，試圖提高scheduler的效能。我們設計不同的實驗，比較DLDS在不同狀況下和其他的排程演算法的差異。實驗結果顯示，透過提高資料的地域性，平均可提昇10% 至 15% 的效能。 / MapReduce is programming model for processing large data set. It is typically used to do distributed computing on clusters of computers such as Cloud computing platform. Examples of bit data set include unstructured logs, web indexing, scientific data, surveillance data, etc. MapReduce is a distributed processing program framework, a computing job is broken down into many smaller Map tasks and a Reduce task.Each Map task processes a partition of the given data set and Reduce aggregates the results of Maps to produce final result. Hadoop is an open-source MapReduce architecture, and is widely used in many cloud-based services.To best utilize computing resource in a cloud server, a task scheduler is essential to assign tasks to appropriate processors as well as to prioritize resource allocation. The default scheduler of Hadoop is first-in-first-out (FIFO) scheduler which is simple but has a performance inefficiency yet to be improved. Although there have been many researches aiming to improve the performance of MapReduce platform in the past year, there still have many issues hindering the performance improvement, such as dynamic load balance, data locality, and heterogeneity of computing nodes. To improve data locality, we propose a new scheduler called Data Locality Driven Scheduler (DLDS) based on Hadoop platform. DLDS improve Hadoop's performamce by allocating Map tasks as close as possible to the data block they are to process. We evaluated the proposed DLDS against several other schedulers by simulation on an 8 nodes real Hadoop system. Experimental results show that DLDS can improve data locality by 10-15%, which results in a significant performamce improvement.