Physical Sciences and Mathematics Commons^™

Multitasking Scheduling With Shared Processing, Bin Fu, Yumei Huo, Hairong Zhao

Computer Science Faculty Publications and Presentations

Recently, the problem of multitasking scheduling has raised a lot of interest in the service industries. Hall et al. (Discrete Applied Mathematics, 2016) proposed a shared processing multitasking scheduling model which allows a team to continue to work on the primary tasks while processing the routinely scheduled activities as they occur. With a team being modeled as a single machine, the processing sharing of the machine is achieved by allocating a fraction of the processing capacity to routine jobs and the remaining fraction, which we denote as sharing ratio, to the primary jobs. In this paper, we generalize this model …

A Data-Driven Approach For Scheduling Bus Services Subject To Demand Constraints, Brahmanage Janaka Chathuranga Thilakarathna, Thivya Kandappu, Baihua Zheng

Research Collection School Of Computing and Information Systems

Passenger satisfaction is extremely important for the success of a public transportation system. Many studies have shown that passenger satisfaction strongly depends on the time they have to wait at the bus stop (waiting time) to get on a bus. To be specific, user satisfaction drops faster as the waiting time increases. Therefore, service providers want to provide a bus to the waiting passengers within a threshold to keep them satisfied. It is a two-pronged problem: (a) to satisfy more passengers the transport planner may increase the frequency of the buses, and (b) in turn, the increased frequency may impact …

Streaming Approximation Scheme For Minimizing Total Completion Time On Parallel Machines Subject To Varying Processing Capacity, Bin Fu, Yumei Huo, Hairong Zhao

Computer Science Faculty Publications and Presentations

We study the problem of minimizing total completion time on parallel machines subject to varying processing capacity. In this paper, we develop an approximation scheme for the problem under the data stream model where the input data is massive and cannot fit into memory and thus can only be scanned a few times. Our algorithm can compute an approximate value of the optimal total completion time in one pass and output the schedule with the approximate value in two passes.

Research On Modeling And Scheduling Of Virtual Power Plant With Dual Demand Response, Qiang Chen, Yi Wang, Kangshun Li

Journal of System Simulation

Abstract: Virtual power plant technology provides an effective means to aggregate distributed power and user side resources to participate in power scheduling. Most of the existing research focus on the scheduling optimization of distributed energy instead of the demand response of user side. The user side resources are divided into contracted reliable response load and non-contracted random response load, and the load response is regulated through price adjustment mechanism to adapt to the change of distributed. A virtual power plant optimal scheduling model with dual demands response is constructed, in which the maximizing overall profit of the power grid is …

Optimizing Course Offerings In A Science Department, Yu Kay Law

Academic Chairpersons Conference Proceedings

We will discuss how enrollment data and faculty/advisor input can be used to maximize schedule efficiency in course offerings and providing for student success. We will also discuss how best to monitor and rearrange course schedules in light of actual enrollment.

Scheduling Optimization Of Aluminum Extrusion Production Line Based On Timed Petri Net And Bso Algorithm, Yali Wu, Shuting He, Yanxi Yang, Lianqiang Feng, Fuqiang Wang, Yulu Chen

Journal of System Simulation

Abstract: For the problems of long production period and low efficiency caused by the complicated processes and large scheduling capacity of aluminum extrusion production line in industrial production, a timed Petri net (TdPN) scheduling model of aluminum extrusion production line is proposed and analyzed for reasonableness. The brain storm optimization (BSO) algorithm is introduced into the model, and an optimized scheduling algorithm for aluminum extrusion scheduling problems is proposed based on the individual encoding and decoding methods. The simulated annealing local search mechanism is used to improve the performance of BSO algorithm in the later stage, which can achieve the …

Rate-Monotonic Scheduler For Lora-Based Smart Space Monitoring System, Preti Kumari, Hari Prabhat Gupta, Sajal K. Das, Rahul Bansal

Computer Science Faculty Research & Creative Works

Smart spaces system equipped with sensors to collect data that can be used to generate insights about its environmental conditions. Those collected data is then transmitted to the applications to enhance the comfort, quality of life, and security of the space. Long Range (LoRa) technology provides long distance coverage and consumes low energy which makes it suitable for smart space application. There are six virtual channels to transmit data in LoRa, however network faces the interference problem when nodes transmitted data at the same time. The interference problem makes LoRa less suitable for time-critical applications. To mitigate the interference problem, …

The Living Breakwaters Pdr Efforts Econcrete Resource Analysis, Guianina Ferrari, Shervon Stephens, Calvin O. Walters Jr.

Publications and Research

On October 29, 2012, Superstorm Sandy impacted 443,000 people and caused nearly $19 billion (about $58 per person in the US) worth of damage within New York City. As part of the New York City infrastructure reparation plan, the Living Breakwaters project in Tottenville addressed coastal resilience, allocating $100M of public funds to a series of artificial breakwaters by the southwest coast of Staten Island. Each breakwater is constructed and designed to mitigate water flow in storm events. ECOncrete, a primary element of the breakwater, is a specialty cast cementitious product that is marine organism-friendly that encourages biocalcification and photosynthesis. …

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 …

Reinforcement Learning Approach To Solve Dynamic Bi-Objective Police Patrol Dispatching And Rescheduling Problem, Waldy Joe, Hoong Chuin Lau, Jonathan Pan

Research Collection School Of Computing and Information Systems

Police patrol aims to fulfill two main objectives namely to project presence and to respond to incidents in a timely manner. Incidents happen dynamically and can disrupt the initially-planned patrol schedules. The key decisions to be made will be which patrol agent to be dispatched to respond to an incident and subsequently how to adapt the patrol schedules in response to such dynamically-occurring incidents whilst still fulfilling both objectives; which sometimes can be conflicting. In this paper, we define this real-world problem as a Dynamic Bi-Objective Police Patrol Dispatching and Rescheduling Problem and propose a solution approach that combines Deep …

The Living Breakwaters Pdr Efforts: Conceptual Scheduling, Calvin O. Walters Jr.

Publications and Research

On October 29, 2012, Superstorm Sandy caused nearly $19 billion in damages in New York City including 69,000 residential units across the five boroughs. This disaster precipitated a post-disaster-rebuilding (PDR) project including roughly $4.2 billion in a Community Development Block Grant allocated towards PDR projects. A portion of the grant was used to construct a living breakwater in Tottenville, Staten Island, consisting of a resiliency approach to risk reduction through erosion prevention, wave energy attenuation, and enhancement of ecosystems and social resiliency to improve resistance to storms for the community of Tottenville. The ridges of each breakwater are designed with …

Design And Development Of A Simulation System For Scheduling In Cloud Manufacturing Based On Microservice Architecture, Yongkui Liu, Ming Zeng, Lin Zhang, Jinwei Guo, Siyang Yuan, Yaoyao Ping

Journal of System Simulation

Abstract: In view of the lack of the low coupling and highly extensible cloud manufacturing scheduling simulation system, that leads to inconvenience of the performance test on scheduling algorithms, a scalable cloud manufacturing scheduling model with the scheduling goal of the minimization of cost and completion time and the maximization of quality of service is proposed. A micro-service architecture based cloud manufacturing scheduling simulation system is designed and developed, which realizes the functions of system management, resource management, task management and simulation management, and has the characteristics of flexible autonomy, stability and scalability. The simulation system facilitates the …

Research On Optimization Of Network Resource Utilization In Static Segment Of Flexray Bus, Xinhang He, Erkang Li, Hongchao Zhang

Journal of System Simulation

Abstract: In order to improve the utilization of the network resources of the FlexRay bus, the network is optimized for static segment scheduling. The FlexRay communication mechanism is analyzed, the message model is established and the calculation method of bandwidth loss is derived, while considering the protocol overhead and network idling, taking the number of static frames and the length of the static frame payload as design variables, the overall optimal packaging scheme is obtained by solving this multi-objective optimization problem. This solution is finally applied to the vehicle chassis integrated control system for simulation analysis and verification. The results …

Scheduling Aircraft Departures To Avoid Enroute Congestion, Johannes Martinez

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

When scheduled flights are forecast to overcrowd sections of enroute airspace, an air traffic control authority may need to delay departures. Mixed integer linear programming can be used to compute a schedule that resolves the congestion while bringing the sum of all delays to a minimum. Standard linear programming constraint formulations for such scheduling problems, however, have poor run times for instances of realistic size. A new constraint formulation based on cycles and paths through a route graph reduces run times in computational experiments. It shows particularly strong performance for schedules that approach the worst-case solution times in standard formulations.

Hybrid Tabu Search Algorithm For Unrelated Parallel Machine Scheduling In Semiconductor Fabs With Setup Times, Job Release, And Expired Times, Changyu Chen, Madhi Fathi, Marzieh Khakifirooz, Kan Wu

Research Collection School Of Computing and Information Systems

This research is motivated by a scheduling problem arising in the ion implantation process of wafer fabrication. The ion implementation scheduling problem is modeled as an unrelated parallel machine scheduling (UPMS) problem with sequence-dependent setup times that are subject to job release time and expiration time of allowing a job to be processed on a specific machine, defined as: R|rj,eij,STsd|Cmax. The objective is first to maximize the number of processed jobs, then minimize the maximum completion time (makespan), and finally minimize the maximum completion times of the non-bottleneck machines. A mixed-integer programming (MIP) model is proposed as a solution approach …

Mathematical Formulations For Complex Resource Scheduling Problems., T. R. Lalita Dr.

Doctoral Theses

This thesis deals with development of effective models for large scale real-world resource scheduling problems. Efficient utilization of resources is crucial for any organization or industry as resources are often scarce. Scheduling them in an optimal way can not only take care of the scarcity but has potential economic benefits. Optimal utilization of resources reduces costs and thereby provides a competitive edge in the business world. Resources can be of different types such as human (personnel-skilled and unskilled), financial(budgets), materials, infrastructures(airports and seaports with designed facilities, windmills, warehouses’ area, hotel rooms etc) and equipment (microprocessors, cranes, machinery, aircraft simulators for …

Residential Demand Side Management Model, Optimization And Future Perspective: A Review, Subhasis Panda, Sarthak Mohanty, Pravat Kumar Rout, Binod Kumar Sahu, Mohit Bajaj, Dr Hossam Zawbaa, Salah Kamel

Articles

The residential load sector plays a vital role in terms of its impact on overall power balance, stability, and efficient power management. However, the load dynamics of the energy demand of residential users are always nonlinear, uncontrollable, and inelastic concerning power grid regulation and management. The integration of distributed generations (DGs) and advancement of information and communication technology (ICT) even though handles the related issues and challenges up to some extent, till the flexibility, energy management and scheduling with better planning are necessary for the residential sector to achieve better grid stability and efficiency. To address these issues, it is …

Optimizing Work Zone Schedules Considering Traffic Diversion With Artificial Bee Colony Algorithm, Celina Semaan

Dissertations

Highway maintenance activities often decrease roadway capacity and intrude traffic movements. The need to finish the project on time and under a specific budget while minimizing the traffic congestion and complying with the emission standards requires an appropriate work zone schedule optimization. The objective of this research is to improve the efficiency of work zone activities and minimize the total project cost including maintenance, user, and emission cost.

While previous studies investigated the work zone optimization problem, they did not consider the implementation of emission standards nor applied a green diversion strategy. This dissertation analyzes the optimization of work zone …

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 …

A Matheuristic Algorithm For The Vehicle Routing Problem With Cross-Docking, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

This paper studies the integration of the vehicle routing problem with cross-docking (VRPCD). The aim is to find a set of routes to deliver products from a set of suppliers to a set of customers through a cross-dock facility, such that the operational and transportation costs are minimized, without violating the vehicle capacity and time horizon constraints. A two-phase matheuristic based on column generation is proposed. The first phase focuses on generating a set of feasible candidate routes in both pickup and delivery processes by implementing an adaptive large neighborhood search algorithm. A set of destroy and repair operators are …

A Survey Of Edge Computing Resource Allocation And Task Scheduling Optimization, Wang Ling, Chuge Wu, Wenhui Fan

Journal of System Simulation

Abstract: With the rapid development of Internet of Things (IoT) and mobile terminals, the concept of edge computing arises. By moving the computation and storage capacity to the edge of network, edge computing is able to deal with a large amount of data produced by IoT devices and the responsive request from IoT application. To improve the utility of edge resource, the quality of service and quality of user experience, resource allocation and task scheduling optimization problems under edge computing attract wide attention. It becomes more difficult due to the geographic separated and heterogeneous features of edge computing resource as …

Quantifying Controllability In Temporal Networks With Uncertainty, James C. Boerkoel Jr., Lindsay Popowski, Michael Gao, Hemeng Li, Savana Ammons, Shyan Akmal

All HMC Faculty Publications and Research

Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We provide new insights inspired by a geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability - continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods …

Reinforcement Learning For Zone Based Multiagent Pathfinding Under Uncertainty, Jiajing Ling, Tarun Gupta, Akshat Kumar

Research Collection School Of Computing and Information Systems

We address the problem of multiple agents finding their paths from respective sources to destination nodes in a graph (also called MAPF). Most existing approaches assume that all agents move at fixed speed, and that a single node accommodates only a single agent. Motivated by the emerging applications of autonomous vehicles such as drone traffic management, we present zone-based path finding (or ZBPF) where agents move among zones, and agents' movements require uncertain travel time. Furthermore, each zone can accommodate multiple agents (as per its capacity). We also develop a simulator for ZBPF which provides a clean interface from the …

Online Traffic Signal Control Through Sample-Based Constrained Optimization, Srishti Dhamija, Alolika Gon, Pradeep Varakantham, William Yeoh

Research Collection School Of Computing and Information Systems

Traffic congestion reduces productivity of individuals by increasing time spent in traffic and also increases pollution. To reduce traffic congestion by better handling dynamic traffic patterns, recent work has focused on online traffic signal control. Typically, the objective in traffic signal control is to minimize expected delay over all vehicles given the uncertainty associated with the vehicle turn movements at intersections. In order to ensure responsiveness in decision making, a typical approach is to compute a schedule that minimizes the delay for the expected scenario of vehicle movements instead of minimizing expected delay over the feasible vehicle movement scenarios. Such …

Review On Agv Scheduling Optimization, Jianlin Fu, Hengzhi Zhang, Zhang Jian, Liangkui Jiang

Journal of System Simulation

Abstract: AGV scheduling plays an important role in improving the efficiency and reducing manufacturing cost, but it is also a very complex combinatorial optimization procedure. AGV scheduling optimization is divided into three types, AGV static scheduling, AGV dynamic scheduling and AGV simultaneous scheduling with other resources scheduling. Various methods are summarized and listed, including traditional analysis method, modeling and simulation method, intelligent optimization algorithm and hybrid optimization method, and the advantages and disadvantages of each method are also analyzed. The deficiencies of AGV scheduling research are pointed out and the research directions for future are presented.

Research Overview On Modeling And Solution Of Aerospace Tt&C Scheduling Problem, Qingqing Yan, Huairong Shen, Qiongling Shao

Journal of System Simulation

Abstract: The research of Aerospace TT&C Scheduling (ATT&CS) is very important, because of its support for TT&C scheme decision-making and TT&C resource net constructing. The classification and resolution flow of the ATT&CS problem were introduced. Then, the modeling methods and related key techniques, such as designing of object function, analysis of constraints, and priority determining, were analyzed. The solving algorithms and conflict resolution methods were summed up, and the major categories of algorithm were evaluated. The main content of scheduling evaluation research was summarized. The possible future researches for related techniques were discussed based on the analysis of development and …

Simulation And Optimization For Bulk Terminal Yard Scheduling, Dongbo Hu, Li Pan, Binbin Zhang, Guozhi Liang

Journal of System Simulation

Abstract: Yard is the central part of the operation process of the whole terminal. In fact, the operation of lots of bulk terminal is unscientific, which severely restricts the turnover efficiency and the throughput of the terminal. Taking the coal terminal as an example and based on its operation process, the dispatching simulation model involving all parts of the operation was established and the rules of use of the yard grids was brought forward. By optimizing the operation strategy and related parameters, it is significant to improve the input quantity of bulk terminal and the turnover efficiency.

Modeling And Simulation On Railway Bulk Oil Transit Operations, Jingheng Ma, Xingchang Liu, Youhong Fan, Kang Jin

Journal of System Simulation

Abstract: The railway bulk oil transit operation is a hybrid (discrete/continuous) system because of the main body of the continuous flow oil and a variety of discrete events. According to the system’s characteristics of complex process, great difficulty, high risk, the oil transit operation model was established based on discrete rate simulation and system’s continuity, predict events, emergencies were analyzed. The model was converted into linear programming, the effective rate was calculated under constraints, and the operation process and event scheduling was simulated. It was verified that the model is feasible. By obtaining the dynamic behavior and real-time data, its …

Research On Modeling And Scheduling Of Cluster Tools With Reentrant Process, Chunrong Pan, Li Liang

Journal of System Simulation

Abstract: Cluster tools reconfigured are increasingly adopted in wafer fabrication. With single-wafer processing technology, the productivity and quality of semiconductor manufacturing have been improved. The configurations of cluster tools and constraints of operation processes were proposed. Due to the increase of processing requirements of wafer revisiting, the scheduling of cluster tools becomes more complicated. Thus, modeling, performance analyzing and scheduling of cluster tools with reentrant process were reviewed. Meanwhile, an illustrative example was given to show the feasibility of simulation scheduling. By analyzing the advantages and disadvantages of research methods available, approaches and future directions which would be effective for …