Browsing by Subject "Scheduling"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Collaborative data processing in wireless sensor networks.
    (2008-12) Zhang, Qingquan
    Wireless Sensor Networks (WSNs) have been used in many application domains, such as target tracking or environmental monitoring. Due to limitations of power supplies, power management and power efficient target tracking techniques have become more and more critical. In this dissertation, systematic approaches are proposed to address the above problems. In particular, efficient energy-aware architectural design aspects of a sensor network are developed, with the goal to reduce the control scheduling algorithm complexity and the power consumption of various components while maintaining the data quality and performance requirements. Research results on an efficient error-bounded sensing scheduling algorithm, a novel collaborative global error implied assisted scheduling algorithm(CIES) and fast target localization for mobile wireless sensor network are presented. Dynamic scheduling management in wireless sensor networks is one of the most challenging problems in long-lifetime monitoring applications. In this thesis, we propose and evaluate a novel data correlation-based stochastic scheduling algorithm, called Cscan. Our system architecture integrates an empirical data prediction model with a stochastic scheduler to adjust a sensor node’s operational mode. We demonstrate that substantial energy savings can be achieved while assuring that the data quality meets specified system requirements. We have evaluated our model using a light intensity measurement experiment on a Micaz testbed, which indicates that our approach works well in an actual wireless sensor network environment. We have also investigated the system performance using Wisconsin- Minnesota historical soil temperature data. The simulation results demonstrate that the system error meets specified error tolerance limits and up to a 70 percent savings in energy can be achieved in comparison to fixed probability sensing schemes. Building on the results obtained from CScan, we further propose and evaluate a collaborative error implication assisted scheduling algorithm, called CIES. This computationdistributive system integrates an implied-error based prediction model together with a stochastic scheduler to adjust neighboring sensors’ operational modes during the occurrence of rare or unusual sensing events. We demonstrate that substantial energy savings can be achieved while also satisfying a global error constraint. We have conducted extensive simulations to investigate the system performance by using realistic Wisconsin-Minnesota historical soil temperature data. The simulation results demonstrate that the system error meets the specified error tolerance and produces up to a 60 percent energy savings compared several fixed probability sensing references. In order to manage data link quality, a distributed sensor network with mobility provides an ideal system platform for surveillance as well as search and rescue applications. We consider a system design consisting of a set of autonomous robots communicating with each other and with a base station to provide image and other sensor data. A robot-mounted sensor which detects interesting information will coordinate with other mobile robots in its vicinity to stream its data back to the base station in a robust and energy-efficient fashion. The system is partitioned into twin sub-networks in such a way that any transmitting sensor will pair itself with another nearby robot to cooperatively transmit its data in a multiple-input, multiple-output (MIMO) fashion. At the same time, other robots in the system will cooperatively position themselves in such a way that the overall link quality is maximized and the total transmission energy in minimized. We efficiently simulate the system’s behavior using the Transaction Level Modeling (TLM) capability of SystemC. Our results demonstrate the efficiency of our simulation approach and provide insights into operation of the network. Finally, a fast target acquisition algorithm without the assistance of a map, call GraDrive, is introduced for search and rescue applications. We evaluate a novel gradientdriven method, which integrates per-node prediction with global collaborative prediction to estimate the position of a stationary target and to direct mobile nodes towards the target along the shortest path. We demonstrate that a high accuracy in localization can be achieved much faster than with random walk models, without any assistance from stationary sensor networks. We evaluate our model through a light-intensity matching experiment using MicaZ motes, which indicates that our model works well in a wireless sensor network environment. Through simulation, we demonstrate almost a 40% reduction in the target acquisition time, compared to a random walk model, while obtaining a small error in the estimate of the target position.
  • Thumbnail Image
    Item
    Cross-Elasticities in Frequencies and Ridership for Urban Local Routes
    (2016-08-01) Totten, Joseph C; Levinson, David M
    Observational data from the Minneapolis-Saint Paul region’s Metro Transit, are analyzed to determine the effects of service levels on ridership levels at different intervals. This research is innovative because it compares changes in service levels and ridership in several service intervals, and includes the elasticities and cross elasticities, or the influence that these service levels have on different service intervals’ ridership. These cross-elasticities are not known to have been researched previously, and are found to have little effect during the week; however, weekend ridership was found to be influenced by rush hour and overnight frequencies. Future research should replicate this study in other cities, and should use express and suburban routes.
  • Thumbnail Image
    Item
    Decentralized Allocation of Tasks with Temporal and Precedence Constraints to a Team of Robots
    (2017-01) Nunes, Ernesto
    The use of multiple robots is beneficial, and sometimes required, to complete sets of tasks. Designing functional multi-robot systems is particularly relevant in application domains such as search and rescue, surveillance, and warehouse management. Allocation of tasks to a team of robots is a well studied topic in the multi-robot systems field. In contrast, task allocation problems where tasks have constraints on where, when and in which order they should be performed have received limited attention, especially in decentralized settings where multiple decision makers are allowed. Here, we investigate multi-robot task allocation problems with temporal and precedence constraints. To address this class of problems, we employ decentralized algorithms to find approximate solutions that minimize the maximum time needed to complete all tasks. To achieve decentralization, we use auction-based insertion heuristics that allow robots to divide work among themselves. To do so, robots take active part in computing schedules that help the team achieve its objectives. This leads to solutions that are robust to the failure of any single robot or task. In this thesis, the use of decentralized algorithms in multi-robot task allocation is explored in four chapters. First, we propose a taxonomy for task allocation problems with temporal and ordering constraints. The taxonomy is the first in the multi-robot task allocation literature to focus specifically on these constraints. It also distinguishes between studies in which task allocation is done deterministically vs. stochastically, and between works that assume hard vs. soft constraints. The taxonomy provides a broad classification of the existing literature, and places our technical work within its different subclasses. Second, we explore the task allocation problem with temporal constraints and propose the temporal sequential single-item auction (TeSSI). TeSSI's key innovation is its combination of sequential single-item auctions and simple temporal networks. The auctions allows robots to distribute work among themselves. Each robot also controls its own simple temporal network, which is used to ensure that new allocations respect tasks' temporal constraints. One of the attractive aspects of the approach is that can be readily used in offline allocations, where tasks are known upfront, or in online scenarios, where tasks arrive over time. We validate the method experimentally, and show its competitiveness when compared to an optimal method, and its advantage over another state of the art auction, and a baseline greedy algorithm. Third, we study task allocation problems with general precedence constraints and propose the simple and prioritized iterated auctions (sIA and pIA). These auctions' novelty is the decomposition of precedence constraints, such that an auctioneer agent handles the precedence constraints, while individual robots bid on pairwise unconstrained tasks. The auctioneer abstracts the precedence graph into layers, and in each iteration a set of pairwise unconstrained tasks is formed and sent to the robots for bidding. We show via thorough experimental evaluations that the method is competitive, and in some instances achieves solutions that are 10% from an optimal solution. Fourth, we address the allocation and execution of tasks with temporal and precedence constraints. A re-purposed pIA auction that relies on a modified TeSSI auction is used for task allocation. A simple executor is also proposed. The executor is made robust by fast adjustments to robots' schedules when robots are delayed, and by a single-shot auction which is used when robots can no longer perform a task in their schedule. We validate the framework in simulation and also run experiments in a robotic testbed with three Turtlebot 2 robots. Additionally, we leverage the power of simulation as a schedule evaluation tool. We present risk and probabilistic analysis that enable users to assess when to readjust tasks' constraints to improve task completion. Taken together, this thesis proposes methods that divide tasks and constraints among the robots, such that each robot controls a subset of the constraints. This decomposition leads to low computational costs, flexibility to handle local failures, and greater individual robot autonomy. These features are important in designing responsive systems for groups of robots that operate in environments where exogenous events are common and may affect robot performance.
  • Thumbnail Image
    Item
    Dynamic resource allocation in wireless fading channels with delay requirements.
    (2010-01) Lee, Juyul
    In this dissertation we investigate resource allocation in fading channels with delay constraints. We first consider scheduling communication resources over time-varying channels when constrained by a hard deadline requirement. The basic problem setting is given as follows: a packet of B bits must be transmitted by a hard deadline of T time slots over a time-varying channel. The transmitter/scheduler must determine how many bits to transmit, or equivalently how much energy to transmit with, during each time slot based on the current channel quality and the number of unserved bits, with the objective of minimizing expected total energy. Our focus is on the interplay between opportunism (adapting to the fading behavior) and the delay requirements. Under the Shannon energy cost function, the optimal solution can only be numerically determined in general, and thus we develop simple and near-optimal policies, which are shown to be asymptotically optimal. Then, we consider monomial cost, under which we can obtain the optimal policy in closed form. We attempt to extend the result to the case for multi-user scheduling and scheduling with outage. In these resource allocation problems, our interests are in formulating an analytical solution. Additionally, we consider parallel/MIMO channel scheduling and wideband scheduling with a hard deadline constraint. As an alternative view of delay requirements, we consider the fairness of each user's traffic. In this regard, we investigate the symmetric capacity of MIMO broadcast channels along with high SNR analysis of MIMO broadcast channels.
  • Thumbnail Image
    Item
    Energy Sustainability in Changeable Manufacturing Systems
    (2017-10) Ghaneizare, Shima
    In a dynamic production environment, not only the product portfolio and demands are varying throughout a multi-period horizon, but also the economic aspects of the environment, such as energy pricing, change with time. The thesis of this work states that energy price fluctuation has a considerable optimizable effect on manufacturing system structural and operational decisions. This work progressively presents three novel linear mathematical models to optimize that effect. In the first step, a novel basic linear mixed integer mathematical model is proposed to maximize the sustainability of changeable manufacturing systems (MSCM) on the operational level. The model focuses on three factors, which are the change pattern in energy prices throughout the day, the transportation cost of jobs between machines, and the setup cost of each machine, which is dependent on the job sequence. The model output is a system configuration plan, indicating arrangement of machines in the system, and the sequence of jobs, which need to be produced on one day. It is solved by CPLEX solver in GAMS software for nine different problem sizes. The new LMI model finds the optimum configuration plan and job sequence in a reasonable time, which illustrates the efficiency and practicality of the proposed model. In the second step, a new linear mathematical model is presented to maximize the sustainability of changeable manufacturing systems on the structural level (MSSCM) by selecting the layout reconfiguration and material handling system in each period. It is solved by CPLEX solver in GAMS software to analyze influence of energy pricing and demand fluctuation on system convertibility and scalability, which can affect layout configuration selection. In the last step, a novel mixed integer linear mathematical model (MILTEC) is presented to maximize the sustainability of RMS on both the structural and operational levels. The system configuration planning in each period of time consists of machines layout and task scheduling which are the most interrelated decisions on the system level. The novel aspect of the presented model is the consideration of energy sustainability concurrently with system configuration and task scheduling decisions in a changing manufacturing environment. The model objective is to minimize total costs of energy consumption, system reconfiguration throughout the planning horizon, and part transportation between machines, which all depend on fluctuations in energy pricing and demand during different periods of time. Several case studies are solved by GAMS Software using the branch-and-bound technique to illustrate the performance of the presented model and analyze its sensitivity to the volatility of energy pricing and demand and their effect on system changeability. An efficient genetic algorithm (GA) has been developed to solve the proposed model in larger scale due to its NP-hardness (non-deterministic polynomial-time hardness). The results are compared to GAMS to validate the developed GA. It shows that the proposed GA finds near-optimal solutions in 70% shorter time than GAMS on average. Different examples are also solved resulting in negligible differences between solutions in several runs of each example to verify the efficiency of the proposed GA.
  • Thumbnail Image
    Item
    Minutes: Senate Committee on Educational Policy: Classroom Advisory Subcommittee: February 21, 2005
    (University of Minnesota, 2005-02-21) University of Minnesota: Classroom Advisory Subcommittee
  • Thumbnail Image
    Item
    Optimized Scheduling Of Electric Vehicle Charging And Discharging In A Vehicle-To-Grid System
    (2015-06) Hosseinpour, Shima
    The increase in electric vehicle (EV) demand and the associated electricity load on the power network have made researchers to start working on managing and controlling EVs' connection time to the electricity grid. Vehicle to grid concept was introduced to enable EVs to connect to the grid and discharge their extra electricity to the network so that the utility company could use it for regulation purposes. In this thesis, offline and online scheduling optimization models are developed for EV charging and discharging. The objective of the optimization models is to maximize the satisfaction of EV customers. Customer satisfaction is incorporated using different factors through multiple scenarios. In the offline model, all EVs and grid information are known for the V2G management to decide the scheduling for EVs. Mixed integer linear programming is used to solve the offline model. The result of the offline model is the optimum solution the scheduling problem could get. On the other hand in the online model, which is a more realistic case, EVs arrival and departure times and their parameters are not identified in advance. For this model, rolling horizon optimization is used in the online scheduling algorithm. Applying rolling horizon enables the author to get the optimal solution for the online model. Mixed integer linear programing is linked with a MATLAB algorithm to solve the online scheduling model. A numerical example, including a large number of EVs in a parking lot is generated to test the efficacy of both proposed models.