近年來通訊網路的進步與寬頻網路的發展，使得更多新型的網路服務迅速應運而生，對網路服務的品質(QoS)也更加要求。眾多新興的應用服務中，即時性的應用服務(real-time traffic)，像是Voice over IP (VoIP)以及video on demand (VoD)，對於封包的傳遞延遲時間(delay time)以及抖動(jitter)具有嚴格的要求，router在處理即時性封包時，並非僅將封包快速送出即可，而須在一定的延遲時間內送出。本研究在BBQ﹙Budget-Base QoS﹚的架構下，發展一套簡單而有效的方法，在封包所經過的每一個router時，根據其緊急程度、服務等級及網路處理能力賦予合適的profit function，再對封包重新排程以獲得最大的profit，期望減小在接收端的jitter絕對值總和，進而增進網路的效能。在此我們設計了四種profit function配合Greedy演算法在兩種不同的router架構上調整封包傳送順序，並利用網路模擬工具NS2在即時性訊務分為單一服務等級及雙服務等級的情況下評估我們方法的效能，證明我們的方法較既有的方法更可以有效控制jitter，且能對不同的服務等級做適當的差異化處理以提高整體服務滿意度。 / With fast growth of Internet traffic and applications, real-time streaming applications have attracted significant attention in the current Internet society. Novel real-time Internet applications such as Voice over IP (VoIP) and video on demand (VoD), have stringent delay and jitter requirements. Under these requirements a router not only have to forward real-time packet as fast as possible, it also have to accomplish the job within a time bound. Our research is based on BBQ﹙Budget-Based QoS﹚management architecture. In order to minimize the jitter of real-time services, we propose a new jitter control mechanism that uses per-hop packet scheduling. Four profit function are designed to represent different scheduling preferences. When a packet gets into a router, the router will assign a profit function based on its timeness and the class of service. The scheduler will re-schedule their order in output queue aiming to maximize total profit. Finally we evaluate our proposed mechanism by NS2 simulator in two situations, single real-time service class and two real-time service classes. Simulation results show that by using our approach the performance is better than other approaches. And we investigate the performance of the combination of profit function in handling multiple classes of service.

隨著智慧家庭概念與技術的興盛與成熟，未來ISP(Internet Service Provider)業者勢必面臨管理大量智慧家庭中各種不同應用競爭頻寬資源的情況。為因應大量且繁雜類型的應用服務彼此競爭智慧家庭端及ISP端的頻寬資源，考量並應用適當的頻寬分配法則以盡可能優化使用者體驗(QoE)是本研究的研究動機。相關文獻的排程演算法如TDPSS (Time Domain Priority Set Scheduler)、MSCDL (Mac Scheduler)、Proportional Fair (PF)及Adaptive Modified Largest Weighted Delay First (AMLWDF)等。若要用以管理大量智慧家庭的頻寬資源時，ISP業者須將家庭申辦頻寬方案以及ISP端的系統頻寬分開考量。ISP在整合(aggregate)多個家庭的頻寬資源請求時，會依服務類別分配頻寬，最後依據不同類別採取適當處理，進而提升不同應用的QoS品質。 本篇論文著重於延遲時間的考量，提出能分類來自各個智慧家庭中，屬於不同 QCI (QoS Class Identifier)級別的頻寬請求並以不同佇列存放，依DADS (Delay Aware Dynamical Scheduling)演算法計算優先權值。我們利用保障頻寬與動態配置頻寬給不同用戶服務佇列，並優先分配頻寬給較高優先權的用戶服務，以期在維持一定公平性的前提下，盡可能地降低延遲來提升QoS品質。 在我們的實驗數據分析中，我們將DADS和其他方法如MSCDL、PF、TDPSS以及AMLWDF進行公平性、產能、延遲以及抖動率等效能優劣的比較與分析。最後在總結與未來研究方向，我們歸納與整理了DADS與PF、MSCDL、TDPSS以及AMLWDF等演算法的效能優劣。實驗結果顯示，在延遲上，DADS勝過PF和TDPSS，但略輸MSCDL及AMLWDF；在抖動率及產能上，DADS均較其它四者為差；公平性上則是劣於TDPSS、PF及MSCDL但優於AMLWDF。雖然DADS在整體的表現並非最好，但在特別重視延遲時間的Category1類別(包含QCI級別為1、2及5的應用服務)的延遲效能僅輸AMLWDF些許，而產能卻明顯勝過AMLWDF，由此可見DADS在Category1的表現最佳。 / With the concept and technology of smart homes becoming more and more mature and popular, Internet service provider (ISP) must face managing large set of various applications from smart homes which competing for bandwidth resources. In order to enhance Quality of Services (QoS) of a lot of various applications while they are competing bandwidth resources of both smart homes (home internal) and Internet service provider (home external), we propose a QoS aware bandwidth allocation criterion to optimize Quality of user Experience (QoE). Since ISP has to manage bandwidth resources of large set of smart homes, in the proposed criterion each ISP separates the bandwidth resources for home external bandwidth and system bandwidth of ISP, respectively. Then, aggregates bandwidth requests of large number of smart homes according to distinct service classes. This thesis focuses on the performance index of delay. We proposed to classify bandwidth requests from smart homes and put them into different queues, finally, calculate priority values by DADS (Delay Aware Dynamical Scheduling) algorithm. The proposed method is able to effectively reduce delay time with certain degree of fairness guarantee by dynamically allocate bandwidth resources for services with distinct service priorities. In the experiments, we compared DADS with other algorithms such as MSCDL (Mac Scheduler), PF (Proportional Fair), TDPSS (Time Domain Priority Set Scheduler) and AMLWDF (Adaptive Modified Largest Weighted Delay First), etc. in terms of fairness, throughput, delay and jitter. The experiments results show that DADS performs much better than PF and TDPSS but a bit worse than MSCDL and AMLWDF in terms of delay. However, DADS shows no better performance than all other algorithms in terms of jitter and throughput. In fairness comparison, DADS is worse than PF, TDPSS and MSCDL but is better than AMLWDF. Though DADS has no superior performance on overall indices, it is a bit worse than AMLWDF in delay of Category1 (including QCI 1, 2 and 5), its throughput is better than AMLWDF. Therefore, DADS’s performance is the best on Category1 considering overall indices.

隨著全球通訊技術的發展，第四代行動通訊系統(4G)已進入我們的生活之中。其中又以長期演進技術（Long Term Evolution, LTE）為代表。LTE使用了正交分頻多工(Orthogonal Frequency-Division Multiplexing, OFDM)以及多輸入多輸出(Multi-Input Multi-Output, MIMO)技術，使得第四代行動網路在上傳以及下載時，能擁有更大的傳輸量，及更遠的傳輸距離。 　　當下載時，因為每位使用者所在的環境不同，造成傳輸量、延遲時間因而不同，所以基地台分配資源時，尚有許多改善的空間。目前，許多文獻在探討如何公平且有效地分配資源塊(Resource Block, RB)給使用者裝置(User Equipment, UE)，如Proportional Fair (PF)與Modified Largest Weighted Delay First (MLWDF)兩種排程機制。前者考量了優先權的公平性，但沒有考量服務品質(Quality of Service, QoS)；後者對於較即時的封包有較高的優先權，卻導致資源分配不均，將大量的資源給部份使用者。本篇論文著重於公平性以及服務品質的考量，使用不同方式的佇列存放各種不同的資源型態(resource type)，依照資源型態佔整體資源數量的比例，以及計算出Adaptive Modified Largest Weighted Delay First (AMLWDF)的優先權值，針對各個UE與各個通道(channel)做全面性地配置，來提昇公平性及降低延遲以符合QoS要求。 / Owing to the development of global communication technology, the Long Term Evolution (LTE) is the latest technology for the fourth generation mobile communication systems (4G) that has entered into our lives. LTE uses Orthogonal Frequency Division Multiplexing (OFDM) and Multiple-Input Multiple-Output (MIMO) technology to provide high data rate transmission and long distance transmission when users doing download and upload. When doing download, users may have different throughput, delay time, and jitter due to they are in different locations. To improve these performance indexes, the E-UTRAN Node B (eNodeB) has to allocate resource blocks efficiently. In the literature, many works explore how to fairly allocate resource blocks (RB) to users. Proportional Fair (PF) and Modified Largest Weighted Delay First (MLWDF) are two example scheduling mechanisms. PF considers service priority and fairness, but doesn't consider the Quality of Service (QoS). MLWDF considers QoS but not service priority and fairness, and allows eNodeB giving more resources to particular users. In this thesis, we focus on resource allocation problem of downlink scheduling in LTE. Considering fairness and QoS, we store various resource types into particular queues and calculate the priorities using Adaptive Modified Largest Weighted Delay First (AMLWDF). The relationships between users and channels are coordinated according to the priorities for the sake of enhancing the fairness and reducing the delay time and jitter.

隨著經濟的高度成長及電廠興建的日益困難，電力的需求問題是愈來愈嚴重。如何有效率地安排核能機組進行例行性的停機大修及燃料再裝填工作是重要的課題。本論文中考慮核能發電機組五年時程的大修排程問題，我們將這個大修排程問題描繪成一個大型混合型整數線性規劃模型。由於問題的龐大與複雜，此問題的最佳解難以求出。因此，我們發展數個邏輯條件式有效地縮小解集合空間；另外並發展出一個啟發性演算法，採用合併變數法將0/1決策變數合併，使原問題轉成較小的合併模型。先解合併後的合併模型，利用合併模型答案的資訊來固定原始模型的部分變數值之後，再解原始問題。幾個實例計算顯示此演算法的可行性。 / Since the growth of economics and the difficulty to build a new power plant, the supply of electric power has become very tight. It is important to ensure the efficient operation of nuclear power plants, including timely shutdown, refueling and maintenance schedule. In this thesis, we deal with the scheduling shutdown and maintenance of nuclear power plants for a five-year time period. This problem can be formulated as a large-scale mixed integer linear problem. The difficulty of solving this problem is due to the large number of binary variables. We then develop several valid logical constraints to reduce the complexity in processing using the branch and bound technique. Also, a heuristic based on the aggregation and dis-aggregation techniques has been developed to yield a good solution. Several examples are given to show the applicability of the algorithm.

本研究開發一個以區域最佳解為基礎的群體式 (population-based) 啟發式演算法(簡稱HLBS)，來求解流程式排程（flow shop）之最大流程時間的最小化問題。其中，HLBS會先建置一個跟隨模型來導引搜尋機制，然後，運用過濾策略來預防重複搜尋相同解空間而陷入區域最佳解的困境；但搜尋仍有可能會陷入區域最佳解，這時，HLBS則會啟動跳脫策略來協助跳出區域最佳解，以進入新的區域之搜尋；為驗證HLBS演算法的績效，本研究利用著名的Taillard 測試題庫來進行評估，除證明跟隨模型、過濾策略和跳脫策略的效用外，也提出實驗結果證明HLBS較其他知名群體式啟發式演算法(如基因演算法、蟻群演算法以及粒子群最佳化演算法)之效能為優。 / This research proposes population-based metaheuristic based on the local best solution (HLBS) for the permutation flow shop scheduling problem (PFSP-makespan). The proposed metaheuristic operates through three mechanisms: (i) it introduces a new method to produce a trace-model for guiding the search, (ii) it applies a new filter strategy to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima, and (iii) it initiates a new jump strategy to help the search escape if the search does become trapped at a local optimum. Computational experiments on the well-known Taillard's benchmark data sets will be performed to evaluate the effects of the trace-model generating rule, the filter strategy, and the jump strategy on the performance of HLBS, and to compare the performance of HLBS with all the promising population-based metaheuristics related to Genetic Algorithms (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).

隨著無線通訊技術快速的發展，使用者對無線傳輸及品質的要求日益提升。第三代合作夥伴計劃3rd Generation Partnership Project (3GPP)所提出的長期演進技術Long Term Evolution (LTE)，是邁入第四代行動通訊系統(4G)的極佳選擇。其中以Single Carrier - Frequency Division Multiple Access (SC-FDMA)系統作為上行鏈路的主要通信技術。 然而，在上行SC-FDMA中有連續性資源塊配置的規定以及所配置之資源塊需使用相同調變技術的限制。一般而言資源分配的好壞會影響傳輸速率(data rate)與系統效能。因此，如何分配資源以改善傳輸速率與增進系統效能是本論文的研究重點。 目前，已有許多文獻在探討如何透過偵測頻率響應(frequency response)，解決資源分配的問題。但我們發現，透過偵測頻率響應的好壞進行優先權排班，無法有效符合現實網路服務的實際需求。在本論文中，我們擬以三階段的演算法來改善系統中資源分配的問題。第一階段，在time domain排班時根據不同的Quality of Service (QoS)特性區分User Equipment (UE)。在第二階段frequency domain排班時依據通道品質好壞決定優先權以分配無線電資源給UE。最後，我們根據SC-FDMA的兩大重要限制，提出在LTE上行系統中資源分配方法，在滿足Guaranteed Bit Rate (GBR)服務之時間延遲的限制時，亦能提升整體系統效能。 在模擬分析中，我們利用NS3進行模擬實驗分析，將我們所提出的三階段演算法在不同比例之網路服務類別的要求下，與固定子載波動態資源分配機制以及適應性動態子載波分配機制進行比較。實驗結果顯示，我們的方法在VoIP的average delay time相較於適應性動態分配法最多可改善約82.9%，real time gaming最多可改善約84.9%，而整體系統頻帶利用率(spectrum utilization)相較於固定與適應性分配機制最多可提升約15.3%。 / Long Term Evolution (LTE) is the latest standard of 3rd Generation Partnership Project (3GPP), which is one of the most promising technology for 4G mobile networks. The goal of LTE is to provide high data rate transmission, scalable bandwidth, low latency, and high-mobility. To achieve this goal, the LTE employs Orthogonal Frequency Division Multiplexing (OFDM) for downlink data transmission and Single Carrier - Frequency Division Multiple Access (SC-FDMA) for uplink transmission. This thesis focuses on the resource allocation problem of LTE SC-FDMA system. We propose a three-stage approach to improve resource allocation performance. In the first stage, we design a time domain scheduling according to different QoS features and time delay requirement to distinguish user equipment (UE). In the second stage, we design a frequency domain scheduling based on channel state information to give priorities to UEs. Finally, we propose resource allocation methods for LTE uplink under the two constraints of SC-FDMA. The proposed methods are proved to be able to meet the real-time service delay constraints and enhance overall system performance. In the simulations, the proposed three stage algorithms are compared to fixed sub-carrier dynamic resource allocation algorithm and adaptive dynamic sub-carrier algorithm against different proportions of network services. Simulation results show that our method outperforms the other two methods in terms of throughput, transmission delay and packet loss ratio.

當發生大規模的地震或強烈的颱風等重大天然災害時，通訊系統常常隨著電力與交通系統的損毀而癱瘓。由歷年大型災變中多數災區內之行動通訊系統全面中斷即可印證行動通訊系統其實是極為脆弱的，然而有效運作的通訊系統卻是災情傳遞、資源調度及救災是否順利的關鍵因素。本文所探討的應急通訊系統利用倖存的連通基地台和斷訊卻沒有損毀的基地台，以無線電連接起來建構一個臨時性的通訊系統，稱為應急蜂巢式行動通訊網路(Contingency Cellular Network，CCN)。由於各地災情狀況不完全相同，CCN的建構順序必須考慮災區的輕重緩急、時間的急迫等因素依序建構。因此當CCN拓樸規劃完成後，根據CCN拓樸、各地災情嚴重程度以及拓樸中基地台間的相對距離(運輸時間)進行基地台建構排程規劃，以達到最大的總救災效益。 本文考慮各基地台所能發揮的救災效益、所需建構時間、以及運輸工具從任一基地台到另一基地台所需運輸時間，提出兩個適合CCN拓樸樹狀結構的考慮資源運輸路徑之最佳化排程模型CCNDS-AC和CCNDS-UC。CCNDS-AC限制建構順序必須從連網台往下循序建構，但CCN-UC則否。因發生突發性大型天然災害時，可容許的計算時間相當短暫，因此提出了兩個快速的啟發式演算法DS-ACG與DS-UCB，可在短時間內求出一組相當逼近於最佳解的建構排程順序，與DS-UCB相互比較。本文以電腦模擬的方式進行小規模實驗與大規模實驗評估，並且用Genetic Algorithm來比較啟發式演算法的效能。結果顯示DS-UCB明顯優於DS-ACG及Genetic Algorithm。在小規模實驗中DS-UCB可求得與最佳解的總救災效益誤差平均約0.9%的近似最佳解建構順序。而在大規模實驗下， DS-UCB與十萬個解中的最佳解─pseudo optimal solution相較，總救災效益平均高出約16.7%，而總救災時間平均約少了19.4%。 / When stricken by a large-scale disaster, the efficiency of disaster response operation is very critical to life saving. However, cellular networks were usually crashed in earthquake, typhoons or other natural disasters due to power outage or backhaul breakage. Unfortunately, the efficiency of communication system is a critical factor to the success of disaster response operation. We designed a contingency cellular network (CCN) by connecting physically intact but service-disrupted base stations together with wireless links. Since the transportation capacity may be very limited, scheduling of CCN deployment order according to the demand of disaster operation and traveling time between base stations becomes an important issue. We propose two optimization models: CCN Deployment Scheduling Antecessor Constrained Problem (CCNDS-AC) and CCN Deployment Scheduling Unconstrained Problem (CCNDS-UC), aiming to maximize the efficiency of disaster response operation. Both problems are proven to be NP Hard. We also designed two rapid heuristic algorithms, DS-ASG and DS-UCB to solve the problems respectively when it is needed in urgent. Finally, we evaluated the proposed algorithms against optimal solutions (in small cases only) as well as genetic algorithm by simulation. The experimental results show that DS-UCB outperforms all other algorithms. In small scale cases, the profit obtained by DS-UCB is only 0.9% smaller than what the optimum solution can get. In large scale cases, as compared to the pseudo optimum solution, which is the best solution among 100,000 solutions, DS-UCB outperforms pseudo optimum solutions in profit by 16.7%, and in traveling time by 19.4%, both in average.

在本篇論文裡, 我們提出一個"油輪排程規畫"的方法。處理在計畫期間中, 有關原油供應商的供給, 油輪的運輸與需求地儲油庫存貨管理的問題。藉由一些性質的探討來分析運輸排程與存貨管理。由供應油商契約量中供應量的情形, 提出最大累積可提運量表, 並藉由該表來輔助我們做排程; 由分油的概念與訂貨週期的制定, 分析運輸工具的排程狀況與儲油庫油量存貨的關係; 由運輸與儲油庫油料之間的互動關係, 提出管理的方案; 最後再藉由理想存貨量的關念來確立租用臨時運輸工具的可行性。並藉由所提出的性質來處理租用運輸工具的排程。在各個階段的處理過程中, 包括分析限制條件是否滿足的情形等, 總共提出了四個演算法, 找出滿足整個問題限制條件的可行排程。最後, 引用實務上的例子, 來說明油輪排程規畫的方法。 / In this paper, we consider an inventory problem of which the lead time depends on vehicles chosen from a restricted set. The inventory itself hasother constraints that must satisfy the demand and capacity limitation. Inspecific, a problem that considers scheduling oil tankers for transportingcrude oils from supplies to a refinery is represented. With the help of some properties discovered while analyzing the problem of oil tanker scheduling with inventory management, such as largest accumulated supplies from oil suppliers, demand intervals and reorder intervals, and an ideal inventory level, we develope an oil tanker scheduling model to determine each vehicle's schedule and satisfy all constraints. The model consists of four heuristic algorithms which are described step by step asthe solution procedure. A realworld example from an oil company is used to illustrate the four algorithms and suggest a feasible schedule for transporting crude oils. In short, we not only give 1 overall viewpoint of inventory and transportation problems but also provide a heuristic procedurefor solving it.