Browsing by Subject "scheduling"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Delay-aware Scheduling in Wireless Coding Networks: To Wait or Not to Wait(2012-02-14) Ramasamy, SolairajaWireless technology has become an increasingly popular way to gain network access. Wireless networks are expected to provide efficient and reliable service and support a broad range of emerging applications, such as multimedia streaming and video conferencing. However, limited wireless spectrum together with interference and fading pose signi cant challenges for network designers. The novel technique of network coding has a significant potential for improving the throughput and reliability of wireless networks by taking advantage of the broadcast nature of wireless medium. Reverse carpooling is one of the main techniques used to realize the benefits of network coding in wireless networks. With reverse carpooling, two flows are traveling in opposite directions, sharing a common path. The network coding is performed in the intermediate (relay) nodes, which saves up to 50% of transmissions. In this thesis, we focus on the scheduling at the relay nodes in wireless networks with reverse carpooling. When two packets traveling in opposite directions are available at the relay node, the relay node combines them and broadcasts the resulting packet. This event is referred to as a coding opportunity. When only one packet is available, the relay node needs to decide whether to wait for future coding opportunities, or to transmit them without coding. Though the choice of holding packets exploits the positive aspects of network coding, without a proper policy in place that controls how long the packets should wait, it will have an adverse impact on delays and thus the overall network performance. Accordingly, our goal is to find an optimal control strategy that delicately balances the tradeoff between the number of transmissions and delays incurred by the packets. We also address the fundamental question of what local information we should keep track of and use in making the decision of of whether to transmit uncoded packet or wait for the next coding opportunity. The available information consists of queue length and time stamps indicating the arrival time of packets in the queue. We could also store history of all previous states and actions. However, using all this information makes the control very complex and so we try to find if the overhead in collecting waiting times and historical information is worth it. A major contribution of this thesis is a stochastic control framework that uses state information based on what can be observed and prescribes an optimal action. For that, we formulate and solve a stochastic dynamic program with the objective of minimizing the long run average cost per unit time incurred due to transmissions and delays. Subsequently, we show that a stationary policy based on queue lengths is optimal, and the optimal policy is of threshold-type. Then, we describe a non-linear optimization procedure to obtain the optimal thresholds. Further, we substantiate our analytical ndings by performing numerical experiments under varied settings. We compare systems that use only queue length with those where more information is available, and we show that optimal control that uses only the queue length is as good as any optimal control that relies on knowing the entire history.Item Integrated Simulation and Optimization for Decision-Making under Uncertainty with Application to Healthcare(2014-11-26) Alvarado, MichelleMany real applications require decision-making under uncertainty. These decisions occur at discrete points in time, influence future decisions, and have uncertainties that evolve over time. Mean-risk stochastic integer programming (SIP) is one optimization tool for decision problems involving uncertainty. However, it may be challenging to develop a closed-form objective for some problems. Consequently, simulation of the system performance under a combination of conditions becomes necessary. Discrete event system specification (DEVS) is a useful tool for simulation and evaluation, but simulation models do not naturally include a decision-making component. This dissertation develops a novel approach whereby simulation and optimization models interact and exchange information leading to solutions that adapt to changes in system data. The integrated simulation and optimization approach was applied to the scheduling of chemotherapy appointments in an outpatient oncology clinic. First, a simulation of oncology clinic operations, DEVS-CHEMO, was developed to evaluate system performance from the patient and managements perspectives. Four scheduling algorithms were developed for DEVS-CHEMO. Computational results showed that assigning patients to both chairs and nurses improved system performance by reducing appointment duration by 3%, reducing waiting time by 34%, and reducing nurse overtime by 4%. Second, a set of mean-risk SIP models, SIP-CHEMO, was developed to determine the start date and resource assignments for each new patients appointment schedule. SIP-CHEMO considers uncertainty in appointment duration, acuity levels, and resource availability. The SIP-CHEMO models utilize the expected excess and absolute semideviation mean-risk measures. The SIP-CHEMO models increased throughput by 1%, decreased waiting time by 41%, and decreased nurse overtime by 25% when compared to DEVS-CHEMOs scheduling algorithms. Finally, a new framework integrating DEVS and SIP, DEVS-SIP, was developed. The DEVS-CHEMO and SIP-CHEMO models were combined using the DEVS-SIP framework to create DEVS-SIP-CHEMO. Appointment schedules were determined using SIP-CHEMO and implemented in DEVS-CHEMO. If the system performance failed to meet predetermined stopping criteria, DEVS-CHEMO revised SIP-CHEMO and determined a new appointment schedule. Computational results showed that DEVS-SIP-CHEMO is preferred to using simulation or optimization alone. DEVSSIP-CHEMO held throughput within 1% and improved nurse overtime by 90% and waiting time by 36% when compared to SIP-CHEMO alone.Item Scheduling in STAPL(2013-05-07) Sharma, ShishirWriting efficient parallel programs is a difficult and error-prone process. The Standard Template Adaptive Parallel Library (STAPL) is being developed to make this task easier for programmers with little experience in parallel programming. STAPL is a C++ library for writing parallel programs using a generic programming approach similar to writing sequential programs using the C++ Standard Template Library (STL). STAPL provides a collection of parallel containers (pContainers) to store data in a distributed fashion and a collection of pViews to abstract details of the data distribution. STAPL algorithms are written in terms of PARAGRAPHs which are high level descriptions of task dependence graphs. Scheduling plays a very important role in the efficient execution of parallel programs. In this thesis, we present our work to enable efficient scheduling of parallel programs written using STAPL. We abstract the scheduling activities associated with PARAGRAPHs in a software module called the scheduler which is customizable and extensible. We provide support for static scheduling of PARAGRAPHs and develop mechanisms based on migration of tasks and data to support dynamic scheduling strategies for PARAGRAPHs with arbitrary dependencies. We also provide implementations of different scheduling strategies that can be used to improve the performance of applications suffering from load imbalance. The scheduling infrastructure developed in this thesis is highly customizable and can be used to execute a variety of parallel computations. We demonstrate its usefulness by improving the performance of two applications: a widely used synthetic benchmark (UTS) and a Parallel Motion Planning application. The experiments are conducted on an Opteron cluster and a massively parallel Cray XE6 machine. Experimental results up to 6144 processors are presented.Item Simultaneous Design, Scheduling and Operation Through Process Integration(2009-05-15) Al-Mutairi, Eid M.Processing facilities are normally designed with sufficient flexibility to handle nominal variations. When the process features planned changes in feedstock and products, scheduling is often used to optimize process operation. The objective of this dissertation is to develop a new approach to design and scheduling with economic, environmental, heat integration and inherently safer design objectives. Specifically, this work introduces a systematic framework and the associated mathematical formulation for simultaneous process design and scheduling while simultaneously addressing economic, environmental, heat integration and inherently safer design objectives. Therefore, more than one type of proper tradeoffs are established between these objectives. The environmental issues pertaining to the parameterized process retrofitting, scheduling, and operation strategies are simultaneously considered along with the environmental impact of these changes. Similarly, the design synthesis of heat-exchange networks (HENs) is addressed in the context of optimizing energy consumption under scheduling scenarios. Finally, the goal of inherently safer design is simultaneously considered with the expected schedules of the process. Several optimization formulations are developed for the projected schedules while allowing design modifications and retrofitting changes. The modifications and changes include new environmental management units, synthesis of flexible and optimal HENs, and design of an inherently safer process. Process models with the appropriate level of relevant details are included in the formulations. A discretization approach has been adopted to allow for a multiperiod optimization formulation over a given time horizon. The resulting framework identifies opportunities for synergism between the economic, environmental, heat integration and inherently safer design objectives. It also determines points of diminishing return beyond which tradeoffs between the above mentioned objectives are established. The devised procedure is illustrated with case studies.