Digital Commons Network^™

The Pulled-Macro-Dataflow Model: An Execution Model For Multicore Shared-Memory Computers, Daniel Joseph Richins

Theses and Dissertations

The macro-dataflow model of execution has been used in scheduling heuristics for directed acyclic graphs. Since this model was developed for the scheduling of parallel applications on distributed computing systems, it is inadequate when applied to the multicore shared-memory computers prevalent in the market today. The pulled-macro-dataflow model is put forth as an alternative to the macro-dataflow model, having been designed specifically to accurately describe the memory bandwidth limitations and request-driven nature of communications characteristic of today's machines. The performance of the common scheduling heuristics DSC and CASS-II are evaluated under the pulled-macro-dataflow model and it is shown that their …

Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We propose and explore, in the context of benchmark problems for flowshop scheduling, a risk-based concept of robustness for optimization problems. This risk-based concept is in distinction to, and complements, the uncertainty-based concept employed in the field known as robust optimization. Implementation of our concept requires problem solution methods that sample the solution space intelligently and that produce large numbers of distinct sample points. With these solutions to hand, their robustness scores are easily obtained and heuristically robust solutions found. We find evolutionary computation to be effective for this purpose on these problems.

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 …

Optimization Models And Approximate Algorithms For The Aerial Refueling Scheduling And Rescheduling Problems, Sezgin Kaplan

Engineering Management & Systems Engineering Theses & Dissertations

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for fighter aircrafts (jobs) on multiple tankers (machines) to minimize the total weighted tardiness. ARSP can be modeled as a parallel machine scheduling with release times and due date-to-deadline window. ARSP assumes that the jobs have different release times, due dates, and due date-to-deadline windows between the refueling due date and a deadline to return without refueling. The Aerial Refueling Rescheduling Problem (ARRP), on the other hand, can be defined as updating the existing AR schedule after being disrupted by job related events including the …

Due-Date Assignment And Optional Maintenance Activity Scheduling Problem With Linear Deterioreting Jobs, Chou-Jung Hsu, Suh-Jenq Yang, Dar-Li Yang

Journal of Marine Science and Technology

The focus of this work is to analyze linear deteriorating jobs in a single-machine scheduling problem with due-date assignment and maintenance activity. The linear deteriorating jobs means its processing time is an increasing function of their starting time. The objective is to minimize the total of earliness, tardiness and due-date cost. To solve the scheduling problem addressed in this work, we have to determine the job sequence, the common due-date, and the location of a maintenance activity. We show that the problem can be solved optimally in O(n2 log n) time.

Gis-Based Irrigation District Flow Routing/Scheduling, Charles M. Burt, Beau Freeman

BioResource and Agricultural Engineering

In 2007, the Irrigation Training and Research Center (ITRC) at California Polytechnic State University, San Luis Obispo undertook to develop a prototype of an intelligent and scalable real-time GIS-based water scheduling and routing software system for irrigation districts, capable of integrating multiple data sources into an information access and management facility featuring collaborative tools with automatic reasoning and analytical capabilities. Improving the infrastructure and management capabilities of irrigation districts in order to provide flexible delivery schedules and increase participation in peak demand reduction programs has been identified as having a significant potential to achieve energy conservation and resource efficiencies.

The …

Leveraging Multi-User Diversity, Channel Diversity And Spatial Reuse For Efficient Scheduling In Wireless Relay Networks, Shen Wan, Jian Tang, Brendan Mumey, Richard S. Wolff, Weiyi Zhang

Electrical Engineering and Computer Science - All Scholarship

Relay stations can be deployed in a wireless network to extend its coverage and improve its capacity. In this paper, we study a scheduling problem in OFDMA-based wireless relay networks with consideration for multi-user diversity, channel diversity and spatial reuse. First, we present a Mixed Integer Linear Programming (MILP) formulation to provide optimum solutions. It has been shown by previous research that performance of a wireless scheduling algorithm is usually related to the interference degree δ, which is the maximum number of links that interfere with a common link but do not interfere with each other. Therefore, we then show …

Integrating Multiple Clusters For Compute-Intensive Applications, Zhifeng Yun

LSU Doctoral Dissertations

Multicluster grids provide one promising solution to satisfying the growing computational demands of compute-intensive applications. However, it is challenging to seamlessly integrate all participating clusters in different domains into a single virtual computational platform. In order to fully utilize the capabilities of multicluster grids, computer scientists need to deal with the issue of joining together participating autonomic systems practically and efficiently to execute grid-enabled applications. Driven by several compute-intensive applications, this theses develops a multicluster grid management toolkit called Pelecanus to bridge the gap between user's needs and the system's heterogeneity. Application scientists will be able to conduct very large-scale …