本文分為個部分：多技能員工調問題，和集合覆蓋、裝運和劃分混合問題多面體研究，其中第一部分問題啟發我們第二部分的探。 / 首先，我們研究在一個大型機場的國際客運站中客戶服務人員的調問題。員工有同的技能和技能水平。技能定義是二維的，包括操作技能和語言能。在學模型中，我們也考慮用餐和休息時間的調和多處工作地點。我們證明該問題是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
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328634 |
| Date | January 2013 |
| Contributors | Kuo, Yong Hong., Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (x, 129 leaves) : ill. (some col.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0029 seconds