No description available.

This dissertation concerns the problem of scheduling real-time traffic in wireless TDMA channels. The most important characteristic of real-time traffic is that it has straight end-to-end delay constraint. We begin the investigation by studying a scheduling principle which naturally achieves the best delay performance in stationary channel conditions. Since the resulting scheduling algorithm maintains equal flow delays across the whole system, it is termed the equal-delay policy. There are a number of advantages associated with this scheduling method. First, it is very simple and practical to implement in real system. Secondly, it can be easily modelled mathematically and admits an analytical solution, which is very important for the construction of an admission control algorithm, we present a mathematical model describing the dynamics of the scheduling system, as well as devising a tractable analytical solution to the problem. A third advantage of the equal-delay policy is that it can be easily extended to support flows with multiple delay constraints. We propose a multiple-class scheduling scheme based on similar allocation concepts as the equal-delay technique. The extended scheme can similarly be mathematically modelled and analytically characterized. A natural objection to the above proposed techniques is that wireless transmission resources can be under-utilized, since the scheduling algorithm pays no attention to the changing individual channel conditions. The reduction in channel utilization can also adversely affect the delay performance, We explain this phenomenon and study the impacts for a variety of different channel characteristics, Specifically, we propose an alternative channel-aware scheduling policy, which aims to maximize channel utilization while keeping a minimum probability of delay violation, The proposed channel-aware policy achieves near-optimal delay performance. However, unlike in the equal-delay case, the channel-aware policy is not practical to implement in a real system. The complicated system dynamics associated with the channel-aware scheme also hamper the development of a mathematical model and analytical solution for admission control. On the other hand, we observe from simulation results that under most circumstances, the equal-delay scheme achieves close to the pertonnance obtained by the channel-aware technique, With the additional benefits of simplicity and admitting analytical analysis. the equal-delay policy appears to be a more practical and suitable choice for scheduling real-time traffic in wireless networks.

本文分為個部分：多技能員工調問題，和集合覆蓋、裝運和劃分混合問題多面體研究，其中第一部分問題啟發我們第二部分的探。 / 首先，我們研究在一個大型機場的國際客運站中客戶服務人員的調問題。員工有同的技能和技能水平。技能定義是二維的，包括操作技能和語言能。在學模型中，我們也考慮用餐和休息時間的調和多處工作地點。我們證明該問題是NP-hard 的。我們推導出有效等式，以方計算過程。我們的學模型能夠幫助規劃者做出決策，及可計算同型的活性對業務的影響。我們的模型也可以幫助決策者計劃長遠工作調和培訓。 / 多技能人員調問題啟發我們這篇文的第二部分：集合覆蓋、裝運和劃分混合問題多面體研究。我們首先證明如覆蓋（或裝運）的等式被删去，該多面體是相當於一個放寬的裝運（或覆蓋）多面體的投影。然後我們考慮混合奇穴多面體（即是一個由覆蓋和裝運等式組成的多面體），並採用圖方法研究，通過考慮同型的等式的互動，推導出混合奇穴等式和完全描繪多面體的特徵。我們再推導出集合覆蓋和裝運混合問題的混合奇穴等式。計算結果顯示，混合奇穴等式有助於減少計算時間。我們還提供子明如何用等式幫助決策。 / This thesis is divided into two parts: Multi-Skilled Staff-Scheduling Problem and a polyhedral study on the Mixed Set Covering, Packing and Partitioning Problem, where the first part is a motivating example of the latter. / In the multi-skilled staff-scheduling problem, we study the problem of scheduling customer service agents at an international terminal of a large airport. The staff members are heterogeneous with different skills and skill levels. The skill specification is two-dimensional, defined by operational skills and language proficiency. In the mathematical model, we also consider the scheduling of meal and rest breaks, and multiple locations. The problem is shown to be NP-hard. We derive valid inequalities to speed up the computational procedure. With our mathematical model, we are able to help schedule planners make decisions and examine the impacts of different types of flexibility on the level of service provided. Our model can also help decision makers with long-term work-schedule planning. / Motivated by the staff-scheduling problem, the second part of this thesis studies the polyhedral structure of the mixed set covering, packing and partitioning problem, i.e., a problem that contains set covering, set packing and set partitioning constraints. We first study the mixed odd hole polytope, which is the polytope associated with a mixed odd hole consisting of covering and packing "edges". Adopting a graphical approach and considering the "interactions" between the different types of inequalities, we derive the mixed odd hole inequality, thereby completely characterizing the mixed odd hole polytope. We then generalize the mixed odd hole inequality for the general mixed covering and packing polytope. Computational results show that the mixed odd hole inequalities are helpful in reducing solution time. We also provide examples of problem settings in which the inequalities can be used to help decision making. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Kuo, Yong Hong. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 119-129). / Abstracts also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter I --- Scheduling of Multi-skilled Staff Across Multiple Locations --- p.1 / Chapter 1 --- Introduction --- p.2 / Chapter 2 --- Literature Review --- p.8 / Chapter 3 --- Mathematical Model --- p.14 / Chapter 3.1 --- Problem Formulation --- p.14 / Chapter 3.2 --- Valid Inequalities --- p.20 / Chapter 3.3 --- Shift Scheduling and Longer-Term Work-Schedule Planning --- p.21 / Chapter 4 --- Computational Studies --- p.24 / Chapter 4.1 --- Dataset and Input Parameters --- p.24 / Chapter 4.1.1 --- Staffing Requirements and Shortage Penalties --- p.24 / Chapter 4.2 --- Computational Study: Managerial Insights --- p.26 / Chapter 4.2.1 --- Effect of Three Types of Flexibility --- p.26 / Chapter 4.2.2 --- Impact of Different Types of Flexibility --- p.28 / Chapter 4.3 --- Computational Study: Benefits Compared with Benchmarks --- p.33 / Chapter 4.3.1 --- Heuristic H1: CSA Assignment by Time Period --- p.35 / Chapter 4.3.2 --- Heuristic H2: CSA Assignment by Criticality --- p.35 / Chapter 4.3.3 --- Comparison with Benchmarks --- p.37 / Chapter 4.4 --- Computational Study: Computational Efficiency --- p.40 / Chapter 5 --- Conclusions --- p.44 / Chapter II --- On the Polyhedral Structure of the Mixed Set Covering, Packing and Partitioning Polytope --- p.47 / Chapter 6 --- Introduction --- p.48 / Chapter 7 --- Preliminaries --- p.51 / Chapter 8 --- Overview of Packing, Covering and Partitioning Polyhedra --- p.58 / Chapter 8.1 --- Set Packing Polytope --- p.58 / Chapter 8.1.1 --- Intersection Graph --- p.59 / Chapter 8.1.2 --- Lifting Procedures --- p.63 / Chapter 8.1.3 --- Facet-Producing Subgraphs --- p.66 / Chapter 8.2 --- Set Covering Polytope --- p.71 / Chapter 8.2.1 --- Polyhedral Structure and the Associated Graphs --- p.71 / Chapter 8.3 --- Set Partitioning Polytope --- p.76 / Chapter 8.4 --- Blocking and Anti-Blocking Pairs --- p.78 / Chapter 8.4.1 --- Blocking polyhedra --- p.78 / Chapter 8.4.2 --- Anti-blocking polyhedra --- p.80 / Chapter 8.5 --- Perfect, Ideal and Balanced Matrices --- p.81 / Chapter 8.5.1 --- Perfect Matrices --- p.81 / Chapter 8.5.2 --- Ideal Matrices --- p.83 / Chapter 8.5.3 --- Balanced Matrices --- p.84 / Chapter 9 --- Mixed Set Covering, Packing and Partitioning Polytope --- p.87 / Chapter 9.1 --- Mixed Set Partitioning and Covering/Packing Polytope --- p.87 / Chapter 9.2 --- Mixed Set Covering and Packing Polytope --- p.88 / Chapter 9.2.1 --- Mixed odd hole --- p.90 / Chapter 9.2.2 --- General Mixed Covering and Packing Polytope --- p.97 / Chapter 9.3 --- Computational Experiments --- p.108 / Chapter 9.4 --- Applications of the Mixed Odd Hole Inequality --- p.112 / Chapter 9.4.1 --- Railway Time-Tabling --- p.112 / Chapter 9.4.2 --- Team Formation --- p.113 / Chapter 9.4.3 --- Course Registration --- p.114 / Chapter 10 --- Conclusions --- p.117 / Bibliography --- p.119

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Mathematics / Master / Master of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy