Digital Commons Network^™

Scheduling, Complexity, And Solution Methods For Space Robot On-Orbit Servicing, Susan E. Sorenson

Graduate Theses and Dissertations

This research proposes problems, models, and solutions for the scheduling of space robot on-orbit servicing. We present the Multi-Orbit Routing and Scheduling of Refuellable On-Orbit Servicing Space Robots problem which considers on-orbit servicing across multiple orbits with moving tasks and moving refuelling depots. We formulate a mixed integer linear program model to optimize the routing and scheduling of robot servicers to accomplish on-orbit servicing tasks. We develop and demonstrate flexible algorithms for the creation of the model parameters and associated data sets. Our first algorithm creates the network arcs using orbital mechanics. We have also created a novel way to …

Experience-Driven Control For Networking And Computing, Zhiyuan Xu

Dissertations - ALL

Modern networking and computing systems have become very complicated and highly dynamic, which makes them hard to model, predict and control. In this thesis, we aim to study system control problems from a whole new perspective by leveraging emerging Deep Reinforcement Learning (DRL), to develop experience-driven model-free approaches, which enable a network or a device to learn the best way to control itself from its own experience (e.g., runtime statistics data) rather than from accurate mathematical models, just as a human learns a new skill (e.g., driving, swimming, etc). To demonstrate the feasibility and superiority of this experience-driven control design …

Experience-Driven Control For Networking And Computing, Zhiyuan Xu

Dissertations - ALL

Modern networking and computing systems have become very complicated and highly dynamic, which makes them hard to model, predict and control. In this thesis, we aim to study system control problems from a whole new perspective by leveraging emerging Deep Reinforcement Learning (DRL), to develop experience-driven model-free approaches, which enable a network or a device to learn the best way to control itself from its own experience (e.g., runtime statistics data) rather than from accurate mathematical models, just as a human learns a new skill (e.g., driving, swimming, etc). To demonstrate the feasibility and superiority of this experience-driven control design …

Scheduling Multiple Parallel Jobs Online, Kefu Lu

McKelvey School of Engineering Theses & Dissertations

The prevalence of parallel processing has only increased in recent years. Today, most computing machines available on the market shifted from using single processors to possessing a multicore architecture. Naturally, there has been considerable work in developing parallel programming languages and frameworks which programmers can use to leverage the computing power of these machines. These languages allow users to create programs with internal parallelism. The next, and crucial, step is to ensure that the computing system can efficiently execute these parallel jobs. Executing a single parallel job efficiently is a very well-studied problem in parallel computing. In the area of …

Permutation Flow Shop Via Simulated Annealing And Neh, Pooja Bhatt

UNLV Theses, Dissertations, Professional Papers, and Capstones

Permutation Flow Shop Scheduling refers to the process of allocating operations of jobs to machines such that an operation starts to process on machine j only after the processing completes in j-1machine. At a time a machine can process only one operation and similarly a job can have only one operation processed at a time. Finding a schedule that minimizes the overall completion times for Permutation Flow Shop problems is NP-Hard if the number of machines is greater than 2. Sowe concentrates on approaches with approximate solutions that are good enough for the problems. Heuristics is one way to find …

Sky Surveys Scheduling Using Reinforcement Learning, Andres Felipe Alba Hernandez

Graduate Research Theses & Dissertations

Modern cosmic sky surveys (e.g., CMB S4, DES, LSST) collect a complex diversity of astronomical objects. Each of class of objects presents different requirements for observation time and sensitivity. For determining the best sequence of exposures for mapping the sky systematically, conventional scheduling methods do not optimize the use of survey time and resources. Dynamic sky survey scheduling is an NP-hard problem that has been therefore treated primarily with heuristic methods. We present an alternative scheduling method based on reinforcement learning (RL) that aims to optimize the use of telescope resources for scheduling sky surveys.

We present an exploration of …

Pharmaceutical Scheduling Using Simulated Annealing And Steepest Descent Method, Bryant Jamison Spencer

Graduate Theses, Dissertations, and Problem Reports

In the pharmaceutical manufacturing world, a deadline could be the difference between losing a multimillion-dollar contract or extending it. This, among many other reasons, is why good scheduling methods are vital. This problem report addresses Flexible Flowshop (FF) scheduling using Simulated Annealing (SA) in conjunction with the Steepest Descent heuristic (SD).

FF is a generalized version of the flowshop problem, where each product goes through S number of stages, where each stage has M number of machines. As opposed to a normal flowshop problem, all ‘jobs’ do not have to flow in the same sequence from stage to stage. The …

Smartphone-Based Self Rescue System For Disaster Rescue, Xitong Zhou

Theses, Dissertations and Capstones

Recent ubiquitous earthquakes have been leading to mass destruction of electrical power and cellular infrastructures, and deprive the innocent lives across the world. Due to the wide-area earthquake disaster, unavailable power and communication infrastructure, limited man-power and resources, traditional rescue operations and equipment are inefficient and time-consuming, leading to the golden hours missed. With the increasing proliferation of powerful wireless devices, like smartphones, they can be assumed to be abundantly available among the disaster victims and can act as valuable resources to coordinate disaster rescue operations. In this paper, we propose a smartphone-based self-rescue system, also referred to as RescueMe, …

A Framework To Audit Scheduling Events In The Linux Operating System, Edward G. Hudgins

Open Access Theses & Dissertations

Soft real-time systems have responsiveness requirements that are desirable but not critical for operational effectiveness. This Thesis describes a new scheduler logging framework named "Integrated Process Scheduler Archiver" (IPSA) intended to assist with this analysis. Due to human sensitivity to interface delays on gesture-driven devices, mobile devices are a common case of soft-real time systems. Mobile systems generally do not incorporate real-time schedulers, but instead utilize over-provisioning and a variety of scheduling heuristics to generally provide acceptable responsiveness. These devices are highly multi-programmed Energy limitations on mobile limit the extent of overprovisioning, thereby increasing the sensitivity of system behavior to …

Building Efficient Large-Scale Big Data Processing Platforms, Jiayin Wang

Graduate Doctoral Dissertations

In the era of big data, many cluster platforms and resource management schemes are created to satisfy the increasing demands on processing a large volume of data. A general setting of big data processing jobs consists of multiple stages, and each stage represents generally defined data operation such as ltering and sorting. To parallelize the job execution in a cluster, each stage includes a number of identical tasks that can be concurrently launched at multiple servers. Practical clusters often involve hundreds or thousands of servers processing a large batch of jobs. Resource management, that manages cluster resource allocation and job …

Decentralized Scheduling For Many-Task Applications In The Hybrid Cloud, Brian Lyle Peterson

LSU Doctoral Dissertations

While Cloud Computing has transformed how we solve many computing tasks, some scientific and many-task applications are not efficiently executed on cloud resources. Decentralized scheduling, as studied in grid computing, can provide a scalable system to organize cloud resources and schedule a variety of work. By measuring simulations of two algorithms, the fully decentralized Organic Grid, and the partially decentralized Air Traffic Controller from IBM, we establish that decentralization is a workable approach, and that there are bottlenecks that can impact partially centralized algorithms. Through measurements in the cloud, we verify that our simulation approach is sound, and assess the …

The Asynchronous T-Step Approximation For Scheduling Batch Flow Systems, David R. Grimsman

Theses and Dissertations

Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work …

Efficient Execution Of Top-K Closeness Centrality Queries, Paul W. Olsen

Legacy Theses & Dissertations (2009 - 2024)

Many of today's applications can benefit from the discovery of the most central entities in real-world networks.

Online Dormitory Reservation System, Adithya Mothe, Koushik Kumar Suragoni, Ramya Vakity

All Capstone Projects

This project is Online Dorms Systems which allows users to book their room in the dorm from anywhere; this is an automated system where the user can search the availability of rooms in the dorm.

The search can be done based on the dates. The rooms that available are come with the status available, it will display all the rooms available as of that particular search date. Once the room has been booked the user can cancel the reservation within 48 hours. And there is concept of user login. As the user creates his own account with his email id, …

Resource Allocation In Vehicular Cloud Computing, Puya Ghazizadeh

Computer Science Theses & Dissertations

Recently, we have witnessed the emergence of Cloud Computing, a paradigm shift adopted by information technology (IT) companies with a large installed infrastructure base that often goes under-utilized. The unmistakable appeal of cloud computing is that it provides scalable access to computing resources and to a multitude of IT services. Cloud computing and cloud IT services have seen and continue to see a phenomenal adoption rate around the world.

Recently, Professor Olariu and his coworkers through series of research introduced a new concept, Vehicular Cloud Computing. A Vehicular Cloud (VC) is a network of vehicles in a parking lot …

A Branch And Bound Method For Sum Of Completion Permutation Flow Shop, Swapna Kodimala

UNLV Theses, Dissertations, Professional Papers, and Capstones

We present a new branch and bound algorithm for solving three machine permutation flow shop problem where the optimization criterion is the minimization of sum of completion times of all the jobs. The permutation flow shop problem (F||∑C_i ) belongs to the class of NP-hard problems; finding the optimal solution is thus expected to be highly computational. For each solution our scheme gives an approximation ratio and finds near optimal solutions. Computational results for up to 20 jobs are given for 3 machine flow shop problem when the objective is minimizing the sum of completion times. The thesis also …

Scheduling And Resource Allocation In Wireless Sensor Networks, Yosef Alayev

Dissertations, Theses, and Capstone Projects

In computer science and telecommunications, wireless sensor networks are an active research area. Each sensor in a wireless sensor network has some pre-defined or on demand tasks such as collecting or disseminating data. Network resources, such as broadcast channels, number of sensors, power, battery life, etc., are limited. Hence, a schedule is required to optimally allocate network resources so as to maximize some profit or minimize some cost. This thesis focuses on scheduling problems in the wireless sensor networks environment. In particular, we study three scheduling problems in the wireless sensor networks: broadcast scheduling, sensor scheduling for area monitoring, and …

Runtime Pipeline I/O Scheduling System For Gpu-Based Heterogeneous Architectures, Julio Cesar Olaya

Open Access Theses & Dissertations

Heterogeneous architectures can improve the performance of applications with computationally intensive operations. Even when these architectures may reduce the execution time of applications, there are opportunities for additional performance improvement as the memory hierarchies of the central processor cores and the coprocessor cores are separate. Applications running on heterogeneous architectures where graphics processing units (GPUs) execute throughput-intense, data-parallel operations may run in a single address space provided by unified virtual addressing or expand the upper bounds of scalability and high performance computing by explicitly partitioning and transferring data across orthogonal host and device address spaces. For explicit handling, applications must …

Energy Awareness And Scheduling In Mobile Devices And High End Computing, Sachin S. Pawaskaw

Student Work

In the context of the big picture as energy demands rise due to growing economies and growing populations, there will be greater emphasis on sustainable supply, conservation, and efficient usage of this vital resource. Even at a smaller level, the need for minimizing energy consumption continues to be compelling in embedded, mobile, and server systems such as handheld devices, robots, spaceships, laptops, cluster servers, sensors, etc. This is due to the direct impact of constrained energy sources such as battery size and weight, as well as cooling expenses in cluster-based systems to reduce heat dissipation. Energy management therefore plays a …

Scheduling Jobs On Two Uniform Parallel Machines To Minimize The Makespan, Sandhya Kodimala

UNLV Theses, Dissertations, Professional Papers, and Capstones

The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q₂||C_max. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q₂||C_max using pseudo-polynomial algorithms based on dynamic programming method. The pseudo-polynomial algorithm has time complexity O (n T²) and can be run on reasonable time for small number of jobs and small processing times. This optimal offline algorithm is …

Simulated Annealing Approach To Flow Shop Scheduling, Sadhana Yellanki

UNLV Theses, Dissertations, Professional Papers, and Capstones

Flow Shop Scheduling refers to the process of allotting various jobs to the machines given, such that every job starts to process on a machine n only after it has finished processing on machine n-1, with each job having n operations to be performed one per machine. To find a schedule that leads to the optimal utilization of resources, expects the schedule to finish in a minimum span of time, and also satisfy the optimality criterion set for the related scheduling problem is NP-Hard, if n > 2. In this thesis, we have developed an algorithm adopting a heuristic called Simulated …

Adaptive Security-Aware Scheduling For Packet Switched Networks Using Real-Time Multi-Agent Systems, Ma'en Saleh Saleh

Dissertations

Conventional real-time scheduling algorithms are in care of timing constraints; they don’t pay any attention to enhance or optimize the real-time packet’s security performance. In this work, we propose an adaptive security-aware scheduling with congestion control mechanism for packet switching networks using real-time agentbased systems. The proposed system combines the functionality of real-time scheduling with the security service enhancement, where the real-time scheduling unit uses the differentiated-earliest-deadline-first (Diff-EDF) scheduler, while the security service enhancement scheme adopts a congestion control mechanism based on a resource estimation methodology.

The security service enhancement unit was designed based on two models: singlelayer and weighted …

Heterogeneity-Aware And Energy-Aware Scheduling And Routing In Wireless Sensor Networks, Mahesh Kumar Vasanthu Somashekar

Theses

A Wireless Sensor Network (WSN) is a group of specialized transducers, called sensor nodes, with a communication infrastructure intended to monitor and record conditions at diverse locations. Since WSN applications are usually deployed in an open environment, the network is exposed to rough weather conditions, such as rain and snow. Another problem that WSN applications need to deal with is the energy constraints of sensor nodes. Both problems adversely affect the lifetime of WSN applications. A lot of research has been conducted to prolong the lifetime of WSN applications considering energy constraints of sensor nodes, but not much research has …

Recource Limited Testing Center Scheduling For A Web-Based Testing Application, Adam J. Graham

All Graduate Plan B and other Reports, Spring 1920 to Spring 2023

Testing centers are a useful tool to help instructors deliver computer-based tests, but computers resources are expensive and therefore limited. This paper describes a method by which testing center(s) may use iNetTest, a web-based computer aided testing system, to house and administer exams. The algorithm discussed in this paper makes it possible for instructors to schedule tests for a given time frame while ensuring that enough computer resources will be available to all of the students. The algorithm prevents the testing center from getting overwhelmed with students while attempting to maximize the usage of the valuable computer resources.

Random Keys Genetic Algorithms Scheduling And Rescheduling Systems For Common Production Systems, Elkin Rodriguez-Velasquez

Engineering Management & Systems Engineering Theses & Dissertations

The majority of scheduling research deals with problems in specific production environments with specific objective functions. However, in many cases, more than one problem type and/or objective function exists, resulting in the need for a more generic and flexible system to generate schedules. Furthermore, most of the published scheduling research focuses on creating an optimal or near optimal initial schedule during the planning phase. However, after production processes start, circumstances like machine breakdowns, urgent jobs, and other unplanned events may render the schedule suboptimal, obsolete or even infeasible resulting in a "rescheduling" problem, which is typically also addressed for a …

Probabilistic Models For Patient Scheduling, Adel Alaeddini

Wayne State University Theses

In spite of the success of theoretical appointment scheduling methods, there have been significant failures in practice primarily due to the rapid increase in the number of no-shows and cancelations from the individuals in recent times. These disruptions not only cause inconvenience to the management but also has a significant impact on the revenue, cost and resource utilization. In this research, we develop a hybrid probabilistic model based on logistic regression and Bayesian inference to predict the probability of no-shows in real-time. We also develop two novel non-sequential and sequential optimization models which can effectively use no-show probabilities for scheduling …

Quality Of Service Based Data-Aware Scheduling, Archit Kulshrestha

LSU Doctoral Dissertations

Distributed supercomputers have been widely used for solving complex computational problems and modeling complex phenomena such as black holes, the environment, supply-chain economics, etc. In this work we analyze the use of these distributed supercomputers for time sensitive data-driven applications. We present the scheduling challenges involved in running deadline sensitive applications on shared distributed supercomputers running large parallel jobs and introduce a ``data-aware'' scheduling paradigm that overcomes these challenges by making use of Quality of Service classes for running applications on shared resources. We evaluate the new data-aware scheduling paradigm using an event-driven hurricane simulation framework which attempts to run …

A Ptas For The Uncertain Capacity Knapsack Problem, Matthew Dabney

All Theses

The standard NP-hard knapsack problem can be interpreted as a scheduling problem with n jobs with weights w₁ . . .w_n and processing times p₁ . . . p_n, where our goal is to order the jobs on a single machine so as to maximize the weight of all jobs completing prior to a known common deadline d. In this paper, we study the uncertain capacity knapsack problem (UCKP), a generalization of this problem in which the deadline d is not known with certainty, but rather is provided as a probability distribution, and our goal …

Filter Scheduling Function Model In Internet Server: Resource Configuration, Performance Evaluation And Optimal Scheduling, Minghua Xu

Wayne State University Dissertations

ABSTRACT

FILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:

RESOURCE CONFIGURATION, PERFORMANCE EVALUATION AND

OPTIMAL SCHEDULING

by

MINGHUA XU

August 2010

Advisor: Dr. Cheng-Zhong Xu

Major: Computer Engineering

Degree: Doctor of Philosophy

Internet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarity

and long-range dependency (LRD). This greatly complicates the problem of

server performance modeling and optimization. On the other hand, popularity of Internet

has created numerous client-server or peer-to-peer applications, with most of them,

such as online payment, purchasing, trading, searching, publishing and media streaming,

being timing sensitive and/or financially critical. The scheduling policy in Internet servers …

Sensor Control And Scheduling Strategies For Sensor Networks, Victoria U. Manfredi

Open Access Dissertations

We investigate sensor control and scheduling strategies to most effectively use the limited resources of an ad hoc network or closed-loop sensor network. In this context, we examine the following three problems. Where to focus sensing? Certain types of sensors, such as cameras or radars, are unable to simultaneously collect high fidelity data from all environmental locations, and thus require some sort of sensing strategy. Considering a meteorological radar network, we show that the main benefits of optimizing sensing over expected future states of the environment are when there are multiple small phenomena in the environment. Considering multiple users, we …