In this dissertation, a multiprocess scheduling model is developed and a set of performance theorems is constructed for the set of scheduling functions associated with the model. Each theorem describes the conditions under which a scheduling function exhibits a particular type of performance.

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

Furthermore, we show that geometric retransmission algorithm is intrinsically unstable for large population sizes. On the other hand, exponential backoff algorithm is more robust and scalable. Even for infinity population sizes, the stable throughput and bounded delay region still exists under certain conditions. / In the light of the concern, we propose a queueing model of the general CSMA protocol with probability-based backoff scheduling algorithm. The input buffer of each node is modeled as a Geo/G/1 queue, in which the service time distribution of each individual head-of-line (HOL) packet can be described by a Markov chain. By means of this queueing model, we can obtain the characteristic equation of throughput, the packet queueing delay as well as the stable conditions with admissible input traffic. We also specify stable throughput and bounded delay regions with respect to the retransmission factor and input rate. / Last but not least, the proposed queueing model can be systematically generalized to investigate various types of MAC protocols, such as ALOHA, CSMA protocols, IEEE 802.11 protocols. Specifically, we illustrate the methodology by full analyses of the non-persistent CSMA and 1-persistent CSMA protocols in this thesis. / Medium Access Control (MAC) protocols have been continuously updated to keep up with the emerging new services and QoS requirements. Despite of the rapid changes of MAC protocols, a comprehensive performance analysis of any MAC protocol remains an open issue for over several decades. / Most of existing analysis of MAC protocols focused on the network throughput and packet access delay under the assumption that the network is saturated which is not realistic. We know very little about the stability of MAC protocol under the normal network operation for lack of a systematic model that can be adaptively applied to various MAC protocols with different service requirements and backoff scheduling algorithms. / Other than the probability-based backoff algorithm, this thesis also includes the study of window-based backoff algorithm. It is shown that the probability-based and window-based backoff algorithms are equivalent to each other. Moreover, we find that the characteristic equation of network throughput is invariant to backoff scheduling algorithms. / Wong, Pui King. / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 125-133). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Ngo-Tai Fong. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 158-168). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Manufacturing Systems: An Overview --- p.1 / Chapter 1.2 --- Previous Research --- p.3 / Chapter 1.3 --- Motivation --- p.5 / Chapter 1.4 --- Outline of the Thesis --- p.8 / Chapter 2 --- Preliminaries --- p.11 / Chapter 2.1 --- Problem Formulation: Deterministic Production Planning --- p.11 / Chapter 2.2 --- Markov Chain --- p.15 / Chapter 2.3 --- Problem Formulation: Stochastic Production Planning --- p.18 / Chapter 2.4 --- Some Lemmas --- p.24 / Chapter 3 --- Open-Loop Production Planning in Stochastic Flowshops --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- Limiting Problem --- p.29 / Chapter 3.3 --- Weak-Lipschitz Continuity --- p.34 / Chapter 3.4 --- Constraint Domain Approximation --- p.41 / Chapter 3.5 --- Asymptotic Analysis: Initial States in Sε --- p.47 / Chapter 3.6 --- Asymptotic Analysis: Initial States in S \ Sε --- p.61 / Chapter 3.7 --- Concluding Remarks --- p.70 / Chapter 4 --- Feedback Production Planning in Deterministic Flowshops --- p.72 / Chapter 4.1 --- Introduction --- p.72 / Chapter 4.2 --- Assumptions --- p.75 / Chapter 4.3 --- Optimal Feedback Controls --- p.76 / Chapter 4.3.1 --- The Case c1 < c2+ --- p.78 / Chapter 4.3.2 --- The Case c1 ≥ c2+ --- p.83 / Chapter 4.4 --- Concluding Remarks --- p.88 / Chapter 5 --- Feedback Production Planning in Stochastic Flowshops --- p.90 / Chapter 5.1 --- Introduction --- p.90 / Chapter 5.2 --- Original and Limiting Problems --- p.91 / Chapter 5.3 --- Asymptotic Optimal Feedback Controls for pε --- p.97 / Chapter 5.3.1 --- The Case c1 < c2+ --- p.97 / Chapter 5.3.2 --- The Case c1 ≥ c2+ --- p.118 / Chapter 5.4 --- Concluding Remarks --- p.124 / Chapter 6 --- Computational Evaluation of Hierarchical Controls --- p.126 / Chapter 6.1 --- Introduction --- p.126 / Chapter 6.2 --- The Problem and Control Policies under Consideration --- p.128 / Chapter 6.2.1 --- The Problem --- p.128 / Chapter 6.2.2 --- Hierarchical Control (HC) --- p.131 / Chapter 6.2.3 --- Kanban Control (KC) --- p.133 / Chapter 6.2.4 --- Two-Boundary Control (TBC) --- p.137 / Chapter 6.2.5 --- "Similarities and Differences between HC, KC, and TBC" --- p.141 / Chapter 6.3 --- Computational Results --- p.142 / Chapter 6.4 --- Comparison of HC with Other Polices --- p.145 / Chapter 6.5 --- Concluding Remarks --- p.151 / Chapter 7 --- Conclusions and Future Research --- p.153 / Bibliography --- p.158

by Lam Shiu-chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 107-113). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Task Scheduling Problem and Lower Bound --- p.3 / Chapter 1.3 --- Organization of the Thesis --- p.4 / Chapter 2 --- Teamwork-Task Scheduling Problem --- p.5 / Chapter 2.1 --- Problem Statement and Notations --- p.5 / Chapter 2.2 --- Classification of Scheduling --- p.7 / Chapter 2.3 --- Computational Complexity --- p.9 / Chapter 2.4 --- Literature Review --- p.12 / Chapter 2.4.1 --- Unrelated Machines Scheduling Environment --- p.12 / Chapter 2.4.2 --- Multiprocessors Scheduling Problem --- p.13 / Chapter 2.4.3 --- Search Algorithms --- p.14 / Chapter 2.4.4 --- Lower Bounds --- p.15 / Chapter 2.5 --- Summary --- p.17 / Chapter 3 --- Fundamentals of Genetic Algorithms --- p.18 / Chapter 3.1 --- Initial Inspiration --- p.18 / Chapter 3.2 --- An Elementary Genetic Algorithm --- p.20 / Chapter 3.2.1 --- "Genes, Chromosomes and Representations" --- p.20 / Chapter 3.2.2 --- Population Pool --- p.22 / Chapter 3.2.3 --- Evaluation Module --- p.22 / Chapter 3.2.4 --- Reproduction Module --- p.22 / Chapter 3.2.5 --- Genetic Operators: Crossover and Mutation --- p.23 / Chapter 3.2.6 --- Parameters --- p.24 / Chapter 3.3 --- A Brief Note to the Background Theory --- p.25 / Chapter 3.4 --- Key Factors for the Success --- p.27 / Chapter 4 --- Tasks Scheduling using Genetic Algorithms --- p.28 / Chapter 4.1 --- Details of Scheduling Problem --- p.28 / Chapter 4.2 --- Chromosome Coding --- p.32 / Chapter 4.2.1 --- Job Priority Sequence --- p.33 / Chapter 4.2.2 --- Engineer Priority Sequence --- p.33 / Chapter 4.2.3 --- An Example Chromosome Interpretation --- p.34 / Chapter 4.3 --- Fitness Evaluation --- p.37 / Chapter 4.4 --- Parent Selection --- p.38 / Chapter 4.5 --- Genetic Operators and Reproduction --- p.40 / Chapter 4.5.1 --- Job Priority Crossover (JOB-CRX) --- p.40 / Chapter 4.5.2 --- Job Priority Mutation (JOB-MUT) --- p.40 / Chapter 4.5.3 --- Engineer Priority Mutation (ENG-MUT) --- p.42 / Chapter 4.5.4 --- Reproduction: New Population --- p.42 / Chapter 4.6 --- Replacement Strategy --- p.43 / Chapter 4.7 --- The Complete Genetic Algorithm --- p.44 / Chapter 5 --- Lower Bound on Optimal Makespan --- p.46 / Chapter 5.1 --- Introduction --- p.46 / Chapter 5.2 --- Definitions and Assumptions --- p.48 / Chapter 5.2.1 --- Task Graph --- p.48 / Chapter 5.2.2 --- Graph Partitioning --- p.49 / Chapter 5.2.3 --- Activity and Load Density --- p.51 / Chapter 5.2.4 --- Assumptions --- p.52 / Chapter 5.3 --- Concepts of Lower Bound on the Minimal Time (LBMT) --- p.53 / Chapter 5.3.1 --- Previous Bound (LBMTF) --- p.53 / Chapter 5.3.2 --- Bound in other form --- p.54 / Chapter 5.3.3 --- Improved Bound (LBMTJR） --- p.56 / Chapter 5.4 --- Lower bound: Task graph reconstruction + LBMTJR --- p.59 / Chapter 5.4.1 --- Problem reduction and Assumptions --- p.60 / Chapter 5.4.2 --- Scenario I --- p.61 / Chapter 5.4.3 --- Scenario II --- p.63 / Chapter 5.4.4 --- An Example --- p.67 / Chapter 6 --- Computational Results and Discussions --- p.73 / Chapter 6.1 --- Parameterization of the GA --- p.73 / Chapter 6.2 --- Computational Results --- p.75 / Chapter 6.3 --- Performance Evaluation --- p.81 / Chapter 6.3.1 --- Solution Quality --- p.81 / Chapter 6.3.2 --- Computational Complexity --- p.86 / Chapter 6.4 --- Effects of Machines Eligibility --- p.88 / Chapter 6.5 --- Future Direction --- p.90 / Chapter 7 --- Conclusion --- p.92 / Chapter A --- Tasks data of problem sets in section 6.2 --- p.94 / Chapter A.l --- Problem 1: 19 tasks --- p.95 / Chapter A.2 --- Problem 2: 21 tasks --- p.97 / Chapter A.3 --- Problem 3: 19 tasks --- p.99 / Chapter A.4 --- Problem 4: 23 tasks --- p.101 / Chapter A.5 --- Problem 5: 27 tasks --- p.104 / Bibliography --- p.107

by Chu Kwok-Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 91-93). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Ordinary Dispatching Policies --- p.5 / Chapter 1.2.2 --- Setup-oriented Dispatching Policies --- p.7 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Slack Based Policies --- p.11 / Chapter 2.1 --- Definition of Slack --- p.12 / Chapter 2.2 --- Least Slack Policy (LS) --- p.13 / Chapter 2.3 --- Least Weighted Slack Policy (LWS) --- p.15 / Chapter 2.3.1 --- Definition of Weighted Slack --- p.15 / Chapter 2.3.2 --- Policy Mechanism and Discussion --- p.15 / Chapter 2.4 --- Least Mean Slack Policy (LMS) --- p.16 / Chapter 2.4.1 --- Batch Size and Its Lower Bound --- p.16 / Chapter 2.4.2 --- Policy Mechanism and Discussion --- p.17 / Chapter 2.5 --- Least Weighted Mean Slack Policy (LWMS) --- p.18 / Chapter 2.5.1 --- Definition of Weighted Mean Slack --- p.18 / Chapter 2.5.2 --- Policy Mechanism and Discussion --- p.18 / Chapter 2.6 --- Illustrative Example --- p.21 / Chapter 2.7 --- Due-date Window Expansion --- p.24 / Chapter 2.7.1 --- Due-date Window --- p.24 / Chapter 2.7.2 --- LWMS Policy: Due Date Window Expansion --- p.25 / Chapter 3 --- Simulation Study --- p.27 / Chapter 3.1 --- Models Description --- p.27 / Chapter 3.1.1 --- Two-Machines-Two-Products Model --- p.27 / Chapter 3.1.2 --- Assembly Lines Model --- p.29 / Chapter 3.1.3 --- Micro-Chips Testing Model --- p.31 / Chapter 3.2 --- Simulation Experiment Description --- p.32 / Chapter 4 --- Simulation Result and Analysis --- p.38 / Chapter 4.1 --- Simulation Result --- p.39 / Chapter 4.1.1 --- Two-Machines-Two-Products Model --- p.39 / Chapter 4.1.2 --- Assembly Lines Model --- p.39 / Chapter 4.1.3 --- Micro-Chips Testing Model --- p.43 / Chapter 4.2 --- Statistical Analysis --- p.44 / Chapter 4.2.1 --- Significance of Weighted Factor and Batch Size --- p.44 / Chapter 4.2.2 --- Comparison Among Different Policies --- p.46 / Chapter 4.3 --- Discussion of Results --- p.50 / Chapter 5 --- An Experimental Implementation and Conclusion Remarks --- p.51 / Chapter A --- Reducing MCT and SDCT by LS policy --- p.55 / Chapter A.1 --- Reducing Variance of Lateness --- p.55 / Chapter A.2 --- Reducing Variance of Cycle Time --- p.56 / Chapter A.3 --- Reducing Mean Cycle Time --- p.56 / Chapter B --- Complete Simulation Result --- p.58 / Chapter B.1 --- Two-Machines-Two-Products Model --- p.58 / Chapter B.1.1 --- "Wip, Batch Size and Throughput" --- p.58 / Chapter B.1.2 --- MCT and SDCT --- p.62 / Chapter B.1.3 --- Machine Utilization --- p.66 / Chapter B.2 --- Assembly Lines Model --- p.68 / Chapter B.2.1 --- "WIP, Batch Size and Throughput" --- p.68 / Chapter B.2.2 --- MCT and SDCT --- p.70 / Chapter B.2.3 --- Machine Utilization --- p.73 / Chapter B.3 --- Micro-Chips Testing Model --- p.82 / Chapter B.3.1 --- "WIP, Throughput, MCT and SDCT" --- p.82 / Chapter B.3.2 --- Machine Utilization --- p.84 / Chapter C --- MANOVA studies on Weighted Factor and Batch Size --- p.86 / Chapter C.1 --- Two-Machines-Two-Products Model --- p.86 / Chapter C.1.1 --- Least Weighted Slack Policy --- p.86 / Chapter C.1.2 --- Least Mean Slack Policy --- p.87 / Chapter C.1.3 --- Least Weighted Mean Slack Policy --- p.87 / Chapter C.2 --- Assembly Lines Model --- p.88 / Chapter C.2.1 --- Least Weighted Slack Policy --- p.88 / Chapter C.2.2 --- Least Mean Slack Policy --- p.88 / Chapter C.2.3 --- Least Weighted Mean Slack Policy --- p.89 / Chapter C.3 --- Micro-Chips Testing Model --- p.89 / Chapter C.3.1 --- Least Weighted Slack Policy --- p.89 / Chapter C.3.2 --- Least Mean Slack Policy --- p.90 / Chapter C.3.3 --- Least Weighted Mean Slack Policy --- p.90 / Bibliography --- p.91

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND AERO. / Bibliography: leaves 105-108. / by Herve J-M Duchesne de Lamotte. / M.S.

Kuo, Yong Hong. / "August 2010." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 130-133). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Ground Staff Allocation at Airports --- p.4 / Chapter 2.1 --- Background --- p.4 / Chapter 2.2 --- Literature Review --- p.8 / Chapter 2.3 --- Model --- p.12 / Chapter 2.3.1 --- Notation --- p.13 / Chapter 2.3.2 --- Basic Model --- p.17 / Chapter 2.3.3 --- Model Structure --- p.20 / Chapter 2.3.4 --- Definition of Tasks --- p.22 / Chapter 2.3.5 --- Job x Language Model --- p.25 / Chapter 2.3.6 --- Job + Language Model --- p.27 / Chapter 2.4 --- Methodology --- p.35 / Chapter 2.4.1 --- Branch-and-Cut Algorithm --- p.36 / Chapter 2.4.2 --- Constraint-Driven Approach --- p.40 / Chapter 2.5 --- Optimization Tool --- p.51 / Chapter 2.6 --- Computational Results --- p.53 / Chapter 2.6.1 --- Branch-and-Cut Algorithm --- p.53 / Chapter 2.6.2 --- Constraint-Driven Approach --- p.59 / Chapter 2.7 --- Conclusions and Future Work --- p.64 / Chapter 3 --- Staff Scheduling in Emergency Departments --- p.67 / Chapter 3.1 --- Background --- p.67 / Chapter 3.1.1 --- Patient Flows --- p.69 / Chapter 3.1.2 --- Doctor Duties --- p.71 / Chapter 3.2 --- Simulation Model --- p.72 / Chapter 3.2.1 --- Assumptions --- p.73 / Chapter 3.2.2 --- Event-Scheduling --- p.74 / Chapter 3.2.3 --- Arrival Events --- p.80 / Chapter 3.2.4 --- Service Activities --- p.82 / Chapter 3.2.5 --- Paperwork-Processing --- p.84 / Chapter 3.2.6 --- Impact of Doctors' Schedules --- p.85 / Chapter 3.3 --- Parameter Estimation --- p.87 / Chapter 3.3.1 --- Data Scarcity --- p.87 / Chapter 3.3.2 --- Estimation of Service Time Distributions --- p.87 / Chapter 3.3.3 --- Search Procedure for Parameter Estimation --- p.90 / Chapter 3.3.4 --- Parameter Estimation by Descent Method --- p.91 / Chapter 3.3.5 --- Parameter Estimation by Simulated An- nealing --- p.93 / Chapter 3.4 --- Data Analysis and Simulated Results --- p.97 / Chapter 3.5 --- Conclusions and Future Work --- p.114 / Chapter A --- Mathematical Proofs --- p.116 / Chapter B --- Getting Started with the Manpower Optimization Tool --- p.122 / Chapter B.l --- Required Files or Programs --- p.122 / Chapter B.2 --- Input Parameters --- p.123 / Chapter B.3 --- Operational Tasks --- p.125 / Chapter B.4 --- Language Requirements --- p.126 / Chapter B.5 --- Flight Schedules --- p.126 / Chapter B.6 --- Availabilities of Workers --- p.128 / Chapter B.7 --- Staff Assignments --- p.128 / Bibliography --- p.130

In this dissertation, a multiprocess scheduling model is developed and a set of performance theorems is constructed for the set of scheduling functions associated with the model. Each theorem describes the conditions under which a scheduling function exhibits a particular type of performance.

This study is concerned with the problem of resource-constrained project scheduling which includes splittable and nonsplittable jobs, renewable and nonrenewable resources, variation in resource availabi1ity, time-resource tradeoff, time-cost tradeoff, and multiple objectives. The problem is formulated as a zero-one integer programming model. A specialized solution technique is developed for the preemptive goal programming, resource-constrained project. scheduling problem for time, cost, and resource leveling objectives. In addition, single objective algorithms are also provided for the time, cost, and resource leveling objectives. These algorithms are based on the idea of the implicit enumeration process, and use the special structures of the problem to expedite the search process. Computer-generated problems are used to test each of the single objective algorithms. The results show that the algorithms give optimal solutions to tested problems with time and cost objectives using a reasonable computation time; however, heuristic solutions are more feasible for problems with resource leveling objective. The multiple objective algorithm is illustrated through application to a warehouse project problem. / Graduation date: 1993