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.

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. …

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 …

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 …

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 …

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 …

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 …

Adaptive Large Neighborhood Search For Vehicle Routing Problem With Cross-Docking, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

Cross-docking is considered as a method to manage and control the inventory flow, which is essential in the context of supply chain management. This paper studies the integration of the vehicle routing problem with cross-docking, namely VRPCD which has been extensively studied due to its ability to reducethe overall costs occurring in a supply chain network. Given a fleet of homogeneous vehicles for delivering a single type of product from suppliers to customers through a cross-dock facility, the objective of VRPCD is to determine the number of vehicles used and the corresponding vehicle routes, such that the vehicleoperational and transportation …

A Matheuristic Algorithm For Solving 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, namely VRPCD. The aim is to find a set of routes to deliver single 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 approach that uses the routes of the local optima of an adaptive large neighborhood search (ALNS) as columns in a set-partitioning formulation of the VRPCD is designed. This matheuristic outperforms the state-of-the-art algorithms in solving a subset of …

A New Intra-Cluster Scheduling Scheme For Real-Time Flows In Wireless Sensor Networks, Gohar Ali, Fernando Moreira, Omar Alfandi, Babar Shah, Mohammed Ilyas

All Works

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. Real-time flows using time division multiple access (TDMA) scheduling in cluster-based wireless sensor networks try to schedule more flows per time frame to minimize the schedule length to meet the deadline. The problem with the previously used cluster-based scheduling algorithm is that intra-cluster scheduling does not consider that the clusters may have internal or outgoing flows. Thus, intra-cluster scheduling algorithms do not utilize their empty time-slots and thus increase schedule length. In this paper, we propose a new intra-cluster scheduling algorithm by considering that clusters may have having internal or outgoing …

Multi-Robot Coordination And Scheduling For Deactivation & Decommissioning, Sebastian A. Zanlongo

FIU Electronic Theses and Dissertations

Large quantities of high-level radioactive waste were generated during WWII. This waste is being stored in facilities such as double-shell tanks in Washington, and the Waste Isolation Pilot Plant in New Mexico. Due to the dangerous nature of radioactive waste, these facilities must undergo periodic inspections to ensure that leaks are detected quickly. In this work, we provide a set of methodologies to aid in the monitoring and inspection of these hazardous facilities. This allows inspection of dangerous regions without a human operator, and for the inspection of locations where a person would not be physically able to enter.

First, …

Scheduling In Mapreduce Clusters, Chen He

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

MapReduce is a framework proposed by Google for processing huge amounts of data in a distributed environment. The simplicity of the programming model and the fault-tolerance feature of the framework make it very popular in Big Data processing.

As MapReduce clusters get popular, their scheduling becomes increasingly important. On one hand, many MapReduce applications have high performance requirements, for example, on response time and/or throughput. On the other hand, with the increasing size of MapReduce clusters, the energy-efficient scheduling of MapReduce clusters becomes inevitable. These scheduling challenges, however, have not been systematically studied.

The objective of this dissertation is to …

Mechanism Design For Strategic Project Scheduling, Pradeep Varakantham, Na Fu

Research Collection School Of Computing and Information Systems

Organizing large scale projects (e.g., Conferences, IT Shows, F1 race) requires precise scheduling of multiple dependent tasks on common resources where multiple selfish entities are competing to execute the individual tasks. In this paper, we consider a well studied and rich scheduling model referred to as RCPSP (Resource Constrained Project Scheduling Problem). The key change to this model that we consider in this paper is the presence of selfish entities competing to perform individual tasks with the aim of maximizing their own utility. Due to the selfish entities in play, the goal of the scheduling problem is no longer only …

Augmenting Decisions Of Taxi Drivers Through Reinforcement Learning For Improving Revenues, Tanvi Verma, Pradeep Varakantham, Sarit Kraus, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Taxis (which include cars working with car aggregation systems such as Uber, Grab, Lyft etc.) have become a critical component in the urban transportation. While most research and applications in the context of taxis have focused on improving performance from a customer perspective, in this paper,we focus on improving performance from a taxi driver perspective. Higher revenues for taxi drivers can help bring more drivers into the system thereby improving availability for customers in dense urban cities.Typically, when there is no customer on board, taxi driverswill cruise around to find customers either directly (on thestreet) or indirectly (due to a …

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

Duplicate record, see https://ink.library.smu.edu.sg/sis_research/3271. The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the …

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP, …

Mixed-Criticality Scheduling To Minimize Makespan, Sanjoy K. Baruah, Arvind Easwaran, Zhishan Guo

Computer Science Faculty Research & Creative Works

In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs …

A Dynamic Run-Profile Energy-Aware Approach For Scheduling Computationally Intensive Bioinformatics Applications, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

High Performance Computing (HPC) resources are housed in large datacenters, which consume exorbitant amounts of energy and are quickly demanding attention from businesses as they result in high operating costs. On the other hand HPC environments have been very useful to researchers in many emerging areas in life sciences such as Bioinformatics and Medical Informatics. In an earlier work, we introduced a dynamic model for energy aware scheduling (EAS) in a HPC environment; the model is domain agnostic and incorporates both the deadline parameter as well as energy parameters for computationally intensive applications. Our proposed EAS model incorporates 2-phases. In …

Dual Formulations For Optimizing Dec-Pomdp Controllers, Akshat Kumar, Hala Mostafa, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Decentralized POMDP is an expressive model for multi-agent planning. Finite-state controllers (FSCs)---often used to represent policies for infinite-horizon problems---offer a compact, simple-to-execute policy representation. We exploit novel connections between optimizing decentralized FSCs and the dual linear program for MDPs. Consequently, we describe a dual mixed integer linear program (MIP) for optimizing deterministic FSCs. We exploit the Dec-POMDP structure to devise a compact MIP and formulate constraints that result in policies executable in partially-observable decentralized settings. We show analytically that the dual formulation can also be exploited within the expectation maximization (EM) framework to optimize stochastic FSCs. The resulting EM algorithm …

Strategic Planning For Setting Up Base Stations In Emergency Medical Systems, Supriyo Ghosh, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Emergency Medical Systems (EMSs) are an important component of public health-care services. Improving infrastructure for EMS and specifically the construction of base stations at the ”right” locations to reduce response times is the main focus of this paper. This is a computationally challenging task because of the: (a) exponentially large action space arising from having to consider combinations of potential base locations, which themselves can be significant; and (b) direct impact on the performance of the ambulance allocation problem, where we decide allocation of ambulances to bases. We present an incremental greedy approach to discover the placement of bases that …

Simulation-Based Evaluation Of An Integrated Planning And Scheduling Algorithm For Maintenance Projects, Rohit Patil, Nagesh Shukla, Senevi Kiridena

SMART Infrastructure Facility - Papers

The field of maintenance project planning and scheduling is attracting increasing attention due to ever growing competition among manufacturing organisations. There is a lack of studies that has tackled all the aspects of maintenance project implementation such as costs, resources, down times, uncertainties, operational constraints, among others. Therefore, an approach which uses a unitary structuring method and discrete event simulation to integrate relevant data about the maintenance projects is proposed. The results of the evaluation, on a case from paper-pulp industry, have shown that the proposed approach is able to overcome most of the issues of maintenance planning and scheduling.

Single Machine Scheduling With Job-Dependent Machine Deterioration, Wenchang Luo, Xu Yao, Weitian Tong, Guohui Lin

Department of Computer Science Faculty Publications

We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance …

Moneyware: Simulating Software Portfolio Quality Management, Robert David Beverly

Masters Theses & Specialist Projects

In this research we introduce MoneyWare, a simulator designed to explore and ultimately to provide guidance on simulating software portfolio quality management. The name “MoneyWare” is inspired by the movie Moneyball. It chronicled a baseball team which used more descriptive statistics to achieve a higher quality ball club with limited resources. MoneyWare is inspired by the observation that the problem of software development is somewhat analogous. Management is faced with an incoming stream of tasks for development. The tasks vary in terms of size, priority, risk, and date needed. But, in any case, the demands come to more than the …

Fresh: Fair And Efficient Slot Configuration And Scheduling For Hadoop Clusters, Jiayin Wang, Yi Yao, Ying Mao, Bo Sheng, Ningfang Mi

Department of Computer Science Faculty Scholarship and Creative Works

Hadoop is an emerging framework for parallel big data processing. While becoming popular, Hadoop is too complex for regular users to fully understand all the system parameters and tune them appropriately. Especially when processing a batch of jobs, default Hadoop setting may cause inefficient resource utilization and unnecessarily prolong the execution time. This paper considers an extremely important setting of slot configuration which by default is fixed and static. We proposed an enhanced Hadoop system called FRESH which can derive the best slot setting, dynamically configure slots, and appropriately assign tasks to the available slots. The experimental results show that …