No description available.

In this thesis, we consider a capacity allocation problem in flexible manufacturing systems. We assume limited time and tool magazine capacities on the Computer Numerically Controlled (CNC) machines. We have a set of operations that have to be assigned to the machines and each operation requires a set of tools to be processed. Our problem is to allocate the available capacity of the CNC machines to operations and their required tools. We consider two problems in this study: maximizing the total weight of operations where there are a limited number of tools of each type available and maximizing total weight minus total tooling cost where the tools can be used or purchased at a cost. We model the problems as Integer Linear Programs and show that they are NP-hard in the strong sense. For the total weight problem, we propose upper bounds, branch and bound algorithm for exact solutions and several heuristics for approximate solutions. For the bicriteria problem, we use Lagrangean relaxation technique to obtain lower and upper bounds. Our computational results have revealed that all solution approaches give satisfactory results in reasonable times.

Emergency surgeries are serviced by three main forms of capacity: dedicated operating room time reserved for emergency surgeries, alternative (on call) capacity, and lastly, canceling of elective surgeries. The objective of this research is to model capacity implications of meeting wait time targets for multiple priority levels in the context of emergency surgeries. Initial attempts to solve the capacity evaluation problem were made using a non-linear optimisation model, however, this model was intractable. A simulation model was then used to examine the trade-off between additional dedicated operating room capacity (and consequent idle capacity) versus increased re-scheduling of elective surgeries while keeping reserved time for emergency surgeries low. Considered performance measures include utilization of operating room time, elective re-scheduling, and wait times by priority class. Finally, the instantaneous utilization of different types of downstream beds is determined to aid in capacity planning. The greatest number of patients seen within their respective wait time targets is achieved by a combination of additional on call capacity and a variation of the rule allowing low priority patients to utilize on call capacity. This also maintains lower cancelations of elective surgeries than the current situation. Although simulation does not provide an optimum solution it enables a comparison of different scenarios. This simulation model can determine appropriate capacity levels for servicing emergency patients of different priorities with different wait time targets.

<p>During the past decade, Grid computing has gained popularity as a means to build powerful computing infrastructures by aggregating distributed computing capacity. Grid technology allows computing resources that belong to different organizations to be integrated into a single unified system image – a Grid. As such, Grid technology constitutes a key enabler of large-scale, crossorganizational sharing of computing resources. An important objective for the Virtual Organizations (VOs) that result from such sharing is to tame the distributed capacity of the Grid in order to manage it and make fair and efficient use of the pooled computing resources.</p><p>Most Grids to date have, however, been completely unregulated, essentially serving as a “source of free CPU cycles” for authorized Grid users. Whenever unrestricted access is admitted to a shared resource there is a risk of overexploitation and degradation of the common resource, a phenomenon often referred to as “the tragedy of the commons”. This thesis addresses this problem by presenting two complementary Grid capacity allocation systems that allow the aggregate computing capacity of a Grid to be divided between users in order to protect the Grid from overuse while delivering fair service that satisfies the individual computational needs of different user groups.</p><p>These two Grid capacity allocation mechanisms constitute the core contribution of this thesis. The first mechanism, the SweGrid Accounting System (SGAS), addresses the need for coordinated soft, real-time quota enforcement across Grid sites. The SGAS project was an early adopter of the serviceoriented principles that are now common practice in the Grid community, and the system has been tested in the Swegrid production environment. Furthermore, SGAS has been included in the Globus Toolkit, the de-facto standard Grid middleware toolkit. SGAS employs a credit-based allocation model where research projects are granted quota allowances that can be spent across the Grid resources, which charge users for their resource consumption. This enforcement of usage limits thus produces real-time overuse protection.</p><p>The second approach, employed by the Fair Share Grid (FSGrid) system, uses a share-based allocation model where project entitlements are expressed in terms of hierarchical share policies that logically divide the Grid capacity between user groups. By coordinating local job scheduling to maintain these global capacity shares, the Grid resources collectively strive to schedule users for a “share of the Grid”. We refer to this cooperative scheduling model as decentralized Grid-wide fairshare scheduling.</p>

Emergency surgeries are serviced by three main forms of capacity: dedicated operating room time reserved for emergency surgeries, alternative (on call) capacity, and lastly, canceling of elective surgeries. The objective of this research is to model capacity implications of meeting wait time targets for multiple priority levels in the context of emergency surgeries. Initial attempts to solve the capacity evaluation problem were made using a non-linear optimisation model, however, this model was intractable. A simulation model was then used to examine the trade-off between additional dedicated operating room capacity (and consequent idle capacity) versus increased re-scheduling of elective surgeries while keeping reserved time for emergency surgeries low. Considered performance measures include utilization of operating room time, elective re-scheduling, and wait times by priority class. Finally, the instantaneous utilization of different types of downstream beds is determined to aid in capacity planning. The greatest number of patients seen within their respective wait time targets is achieved by a combination of additional on call capacity and a variation of the rule allowing low priority patients to utilize on call capacity. This also maintains lower cancelations of elective surgeries than the current situation. Although simulation does not provide an optimum solution it enables a comparison of different scenarios. This simulation model can determine appropriate capacity levels for servicing emergency patients of different priorities with different wait time targets.

Network resiliency pertains to the vulnerability of telecommunication networks in the case of failures and malicious attacks. With the increasing capacity catering of network for the booming multi-services in Next Generation Networks (NGNs), reducing recovery time and improving capacity efficiency while providing high quality and resiliency of services has become increasingly important for the future network development. Providing network resiliency means to rapidly and accurately reroute the traffic via diversely routed spare capacity in the network when a failure takes down links or nodes in the working path. Planning and optimization for NGNs require an efficient algorithm for spare capacity allocation (SCA) that assures restorability with a minimum of total capacity. This dissertation aims to understand and advance the state of knowledge on spare capacity allocation in network resiliency for telecommunication core networks. Optimal network resiliency design for restorability requires considering: network topology, working and protection paths routing and spare capacity allocation. Restorable networks should be highly efficient in terms of total capacity required for restorability and be able to support any target level of restorability. The SCA strategy is to decide how much spare capacity should be reserved on links and to pre-plan protection paths to protect traffic from a set of failures. This optimal capacity allocation problem for survivable routing is known as NP-complete. To expose the problem structure, we propose a model of the SCA problem using a matrix-based framework, named Distributed Resilience Matrix (DRM) to identify the dependencies between the working and protection capacities associated with each pair of links and also to capture the local capacity usage information in a distributed control environment. In addition, we introduce a novel ant-based heuristic algorithm, called Friend-or-Foe Resilient (FoF-R) ant-based routing algorithm to find the optimal protection cycle (i.e., two node-disjoint paths between a source-destination node pair) and explore the sharing ability among protection paths using a capacity headroom-dependent attraction and repulsion function. Simulation results based on the OMNeT++ and AMPL/CPLEX tools show that the FoF-R scheme with the DRM structure is a promising approach to solving the SCA problem for survivable routing and it gives a good trade off between solution optimality and computation speed. Furthermore, for the SCA studies of survivable networks, it is also important to be able to differentiate between network topologies by means of a robust numerical measure that indicates the level of immunity of these topologies to failures of their nodes and links. Ideally, such a measure should be sensitive to the existence of nodes or links, which are more important than others, for example, if their failure causes the network’s disintegration. Another contribution in this dissertation is to introduce an algebraic connectivity metric, adopted from the spectral graph theory, namely the 2nd smallest eigenvalue of the Laplacian matrix of the network topology, instead of the average nodal degree, to characterize network robustness in studies of the SCA problem. Extensive simulation studies confirm that this metric is a more informative parameter than the average nodal degree for characterizing network topologies in network resiliency studies.

In this study, we consider a capacity allocation problem in flexible manufacturing systems. We assume time and tool magazine capacities on the Numerical Controlled (NC) machines and limited number of available tools. Our problem is to allocate the available capacity of the NC machines to the required demand of the operations, so as to maximize the total weight of operation assignments. We formulate the problem as a Mixed Integer Linear Program and show that it is NP-hard in the strong sense. We solve the moderate-sized problems optimally by the available Integer Programming software. We also develop Lagrangean relaxation based upper bounds and several heuristic procedures. Our computational results have revealed that the Lagrangean upper bounds are very close to optimal solutions and the heuristic procedures produce near optimal solutions in very small solution times even when the problem sizes are large.

Emergency surgeries are serviced by three main forms of capacity: dedicated operating room time reserved for emergency surgeries, alternative (on call) capacity, and lastly, canceling of elective surgeries. The objective of this research is to model capacity implications of meeting wait time targets for multiple priority levels in the context of emergency surgeries. Initial attempts to solve the capacity evaluation problem were made using a non-linear optimisation model, however, this model was intractable. A simulation model was then used to examine the trade-off between additional dedicated operating room capacity (and consequent idle capacity) versus increased re-scheduling of elective surgeries while keeping reserved time for emergency surgeries low. Considered performance measures include utilization of operating room time, elective re-scheduling, and wait times by priority class. Finally, the instantaneous utilization of different types of downstream beds is determined to aid in capacity planning. The greatest number of patients seen within their respective wait time targets is achieved by a combination of additional on call capacity and a variation of the rule allowing low priority patients to utilize on call capacity. This also maintains lower cancelations of elective surgeries than the current situation. Although simulation does not provide an optimum solution it enables a comparison of different scenarios. This simulation model can determine appropriate capacity levels for servicing emergency patients of different priorities with different wait time targets.

La gestion des revenus d’un réseau de compagnies aériennes, un des problèmes le plus critiques dans le secteur du transport aérien, a reçu une attention significative depuis ces dernière décennies. Cependant, de nombreuses problématiques doivent encore être traitées. Cette thèse étudie quatre nouveaux problèmes de la gestion des revenus dans un réseau de compagnies aériennes. D'abord, un problème de dimensionnement de capacité du réseau avec alliances concurrentes est étudié. Dans ce problème, les concurrences horizontales et verticales sont considérées et la demande est supposée déterministe. L’objectif est de maximiser les revenus globaux de l’alliance en déterminant la capacité (en nombre de places) dans les vols pour chaque classe tarifaire de chaque compagnie. Le problème est formulé en programmation linéaire en nombres entiers et résolu à l’aide du solveur CPLEX. Deuxièmement, un problème intégrant la localisation de p-hub médian et le dimensionnement des capacités (places) est étudié pour maximiser une combinaison du bénéfice moyen et du bénéfice au pire cas. Pour ce problème, un seul hub à capacité illimitée est considéré. De plus, les incertitudes sur la demande sont représentées à l’aide d’un ensemble fini des scénarios. Le problème est formulé en programmation stochastique à deux étapes. Ensuite, un algorithme génétique (GA) est proposé pour résoudre le problème pour chaque scénario. Les résultats numériques montrent que la méthode est meilleure que celles dans la littérature qui considèrent uniquement le bénéfice moyen. Le troisième problème étudié est une extension naturelle du deuxième dans lequel la capacité de hub à localiser est limitée et les perturbations qui peuvent impacter la capacité du hub, telles que des conditions météorologiques, sont prises en compte. Deux formulations du problème sont proposées : (1) une programmation stochastique à deux étapes sur la base des scénarios, et (2) optimisation hybride de programmation stochastique à deux étapes à l’aide de pondération. Ensuite, l’approximation moyenne par échantillonnage (SAA) et le GA sont appliqués pour résoudre le problème, respectivement. Les résultats numériques montrent que la SAA est plus performante que le GA. Le quatrième problème est aussi une extension du deuxième problème où la compagnie aérienne doit respecter le niveau d'émissions de CO2 imposé. Le problème est modélisé en programmation stochastique à deux étapes sur la base des scénarios. De plus, une méthode SAA est proposée pour sa résolution. / As one of critical problems in aviation industry, airline network revenue management has received significant attention in recent decades. However, many issues still need to be addressed. This thesis investigates four new airline network revenue management problems. Firstly, a network capacity allocation problem with competitive alliances is studied. In this problem, horizontal and vertical competitions and deterministic demand are considered. The aim is to maximize the global alliance revenue by determining the (seat) capacities in flights for each fare class of each airline. The problem is formulated into a mixed integer programming and is solved by a commercial solver CPLEX. Secondly, an integrated p-hub median location and (seat) capacity allocation problem is investigated to maximize the combined average-case and worst-case profits of an airline. For this problem, an uncapacitated hub is considered and uncertain demand is represented by a finite set of scenarios. The studied problem is formulated based on a two-stage stochastic programming framework. Then a Genetic Algorithm (GA) is proposed to solve the problem for each scenario. Computational results show that the proposed method outperforms those in the literature only considering average-case profit. The third studied problem is a generalization of the second one in which the capacity of hub to be located is limited and disruptions which can impact airline hub capacity, such as adverse weather, are considered. Two formulations of the problem are proposed based on : (1) a scenario-based two-stage stochastic programming, and (2) a weight-based hybrid two-stage stochastic programming-robust optimization framework. Then a Sample Average Approximation (SAA) method and a GA are applied to solve them, respectively. Computational results show that the SAA is more effective than the GA. The fourth problem is also an extension of the second one where an airline is subjected to a CO2 emission limit. The problem is modeled into a scenario-based two-stage stochastic programming. And a SAA method is proposed to solve it.

The two important metrics for any primary care practice are: (1) Timely Access and (2) Patient-physician Continuity. Timely access focuses on the ability of a patient to get access to a physician as soon as possible. Patient-physician continuity refers to building a strong or permanent relationship between a patient and a specific physician by maximizing patient visits to that physician. In the past decade, a new paradigm called advanced access or open access has been adopted by practices nationwide to encourage physician to “do today’s work today.” However, most clinics still reserve pre-scheduled appointments for long lead-time appointments due to patient preference and clinical necessities. Therefore, an important problem for clinics is how to optimally manage and allocate limited physician capacities as much as possible to meet the two types of demand – pre-scheduled (non-urgent) and open access (urgent) – while simultaneously maximizing timely access and patient-physician continuity. In this study we use a quantitative approach to apply the ideas of manufacturing process flexibility to capacity management in a primary care practice. We develop a closed form expression for capacity allocation for an individual physician and a two physician practice. In the case of multiple physicians, we use a two-stage stochastic integer programming approach to investigate the value of flexibility under different levels of flexibility and provide the optimal capacity allocation solution for each physician. We find that flexibility has the greatest benefit when system utilization is balanced and when the individual physicians have unequal utilizations. The benefits of flexibility also increase as the practice gets larger.