When integer programming (IP) models are used in operational situations there is a need to consider the tradeoff between the conflicting goals of solution quality and solution time, since for many problems solving realistic-size instances to a tight tolerance is still beyond the capability of state-of-the-art solvers. However, by appropriately defining small instances, good primal solutions frequently can be found quickly. We explore this approach in this thesis by studying the design of algorithms that produce solutions to an integer program by solving restrictions of the problem via integer programming technology. We refer to this type of algorithm as IP-based search and present algorithms for network design problems of both real-world and academic interest. Along with algorithms that exploit the structure of the problem studied we also present a general integer programming algorithm that uses column generation to choose the restrictions to solve.

Motivated by operational issues in real-world glass manufacturing, this thesis addresses a problem of laying out and sequencing the orders so as to minimize wasted glass, called scrap. This optimization problem combines aspects of traditional cutting problems and traditional scheduling and sequencing problems. In so far as we know, the combination of cutting and scheduling has not been modeled, or solved. We propose a two-phase approach: snap construction and constructing cutting and offload schedules. Regarding the second phase problem, we introduce FGSP (float glass scheduling problem), and provide its solution structure, called coveys. We analyze simple sub-models of FGSP considering the main elements: time, unit, and width. For each model, we provide either a polynomial time algorithm or a proof of NP-completeness. Since FGSP is NP-complete, we propose a heuristic algorithm, Longest Unit First (LUF), and analyze the worst case performance of the algorithm in terms of the quality of solutions; the worst case performance bound is {1+(m-1)/m}+{1/3-1/(3m)} where m is the number of machines. It is 5/3 when m=2. For the real-world problem, we propose two different methods for snap construction, and we apply two main approaches to solve cutting and offloading schedules: an MIP approach and a heuristic approach. Our solution approach produces manufacturing yields greater than 99%; current practice is about 95%. This is a significant improvement and these high-yield solutions can save millions of dollars.

Load balancing has been a topic of interest in both academia and industry, mainly because of the scope for performance enhancement that is available to be exploited in many parallel and distributed processing environments. Among the many approaches that have been used to solve the load balancing problem, we find that only very few use prediction of code execution times. Our reasoning for this is that the field of code prediction is in its infancy. As of this writing, we are not aware of any prediction-based load balancing approach that uses prediction8 of code-execution times, and uses neither the information provided by the user, nor an off-line step that does the prediction, the results of which are then used at run-time. In this context, it is important to note that prior studies have indicated the feasibility of predicting the CPU requirements of general application programs. Our motivation in using prediction-based load balancing is to determine the feasibility of the approach. The reasoning behind that is the following: if prediction-based load balancing does yield good performance, then it may be worthwhile to develop a predictor that can give a rough estimate of the length of the next CPU burst of each process. While high accuracy of the predictor is not essential, the computation overhead of the predictor must be sufficiently' small, so as not to offset the gain of load balancing. As for the system, we assume a set of autonomous computers, that are connected by a fast, shared medium. The individual nodes can vary in the additional hardware and software that may be available in them. Further, we assume that the processes in the workload are sequential. The first step is to fix the parameters for our assumed predictor. Then, an algorithm that takes into account the characteristics of the predictor is proposed. There are many trade-off decisions in the design of the algorithm, including certain steps in which we have relied on trial and error method to find suitable values. The next logical step is to verify the efficiency of the algorithm. To assess its performance, we carry out event driven simulation. We also evaluate the robustness of the algorithm with respect to the characteristics of the predictor. The contribution of the thesis is as follows: It proposes a load-balancing algorithm for a heterogeneous cluster of workstations connected by a fast network. The simulation assumes that the heterogeneity is limited to variability in processor clock rates; but the algorithm can be applied when the nodes have other types of heterogeneity as well. The algorithm uses prediction of CPU burst lengths as its basic input unit. The performance of the algorithm is evaluated through event driven simulation using assumed workload distributions. The results of the simulation show that the algorithm yields a good improvement in response times over the scenario in which no load redistribution is done.

Lean distribution networks have been facing an increased exposure to the risk of unpredicted disruptions causing significant economic forfeitures. At the same time, the existing literature contains very few studies that examine the impact of fortification of facilities for improving network reliability. This dissertation presents three related classes of models that support the design of reliable distribution networks. The models extend the uncapacitated P-median and fixed-charge location models by considering heterogeneous facility failure probabilities, supplier backups, and facility fortification within a finite budget. The first class of models considers binary fortification via linear fortification functions. The second class of models extends binary fortification to partial (continuous) reliability improvement with linear fortification. This extension allows a more efficient utilization of limited fortification resources. The third class of models generalizes linear fortification to nonlinear to reflect the effect of diminishing marginal reliability improvement from fortification investment. For each of the models, we develop solution algorithms and demonstrate their computational efficiency. We present a detailed discussion on the novelty of the proposed models. The models are intended to support corporate decisions on the design of robust distribution networks using limited fortification resources.

The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions. / text

This study explored what cognitive resources (i.e., units of knowledge necessary to learn) first-semester organic chemistry students used to make decisions about acid strength and how those resources guided the prediction, explanation and justification of trends in acid strength. We were specifically interested in the identifying and characterizing the mental models, assumptions and heuristics that students relied upon to make their decisions, in most cases under time constraints. The views about acids and acid strength were investigated for twenty undergraduate students. Data sources for this study included written responses and individual interviews.The data was analyzed using a qualitative methodology to answer five research questions. Data analysis regarding these research questions was based on existing theoretical frameworks: problem representation (Chi, Feltovich & Glaser, 1981), mental models (Johnson-Laird, 1983); intuitive assumptions (Talanquer, 2006), and heuristics (Evans, 2008). These frameworks were combined to develop the framework from which our data were analyzed.Results indicated that first-semester organic chemistry students' use of cognitive resources was complex and dependent on their understanding of the behavior of acids. Expressed mental models were generated using prior knowledge and assumptions about acids and acid strength; these models were then employed to make decisions. Explicit and implicit features of the compounds in each task mediated participants' attention, which triggered the use of a very limited number of heuristics, or shortcut reasoning strategies. Many students, however, were able to apply more effortful analytic reasoning, though correct trends were predicted infrequently. Most students continued to use their mental models, assumptions and heuristics to explain a given trend in acid strength and to justify their predicted trends, but the tasks influenced a few students to shift from one model to another model. An emergent finding from this project was that the problem representation greatly influenced students' ability to make correct predictions in acid strength.

FlexRay is a deterministic communication bus in the automotive context that supports fault-tolerant and high-speed bus system. It operates based on the time-division-multiple-access scheme and allows transmission of event-driven and time-driven messages between nodes in a system. A FlexRay bus has two periodic segments which form a bus cycle: static segment and dynamic segment. Such a bus system could be used in a wide area of real-time automotive applications with soft and hard timing constraints. Recent research has been focused on the FlexRay static segment. As opposed to the static segment, however, the dynamic one is based on an event-triggered scheme. This scheme is more difficult to be temporally predicted. Nevertheless, the event-triggered paradigm provides more flexibility for further incremental design. The dynamic segment is also suitable for applications with erratic data size. Such advantages motivate for more research on the dynamic segment. In a real-time system, results of the computations have to be ready by a specific instant of time called deadline . However, in a soft real-time application, the result can be used with a degraded Quality of Service even after the deadline has passed while in a hard real-time system, missing a deadline leads to a catastrophe. This thesis aims at optimizing some of the parameters of the FlexRay bus for soft real-time applications. The cost function which helps to assess the solution to the optimization problem is the deadline miss ratio and a solution to our problem consists of two parts: (1) Frame identifiers to messages which are produced at each node. (2) The size of each individual minislot which is one of the FlexRay bus parameters. The optimization is done based on genetic algorithms. To evaluate the proposed approach, several experiments have been conducted based on the FlexRay bus simulator implemented in this thesis. The achieved results show that suitable choice of the parameters which are generated by our optimization engine improves the timing behavior of simulated communicating nodes.

This dissertation makes contributions to areas of research on planning with POMDPs: complexity theoretic results and heuristic techniques. The most important contributions are probably the complexity of approximating the optimal history-dependent finite-horizon policy for a POMDP, and the idea of heuristic search over the space of FFTs.

With the increasing effect of disasters and long term issues on human well-being and economy over the recent years, effective management of humanitarian supply chains has become more important. This thesis work focuses on three problems in humanitarian supply chains where uncertainty is inherent, namely (i) post-disaster debris clearance with uncertain debris amounts, (ii) allocation of a health/humanitarian commodity in a developing country setting with multiple demand types, and (iii) distribution of specialized nutritious foods by a large scale humanitarian organization. In each of the three parts, the problem is formally defined, and a novel optimal solution approach incorporating the inherent uncertainty in the environment and updates is proposed. In cases where optimal models cannot be solved within reasonable time, novel heuristics are developed. Through structural analysis and computational experiments based on real data, the proposed approaches are compared to those that ignore the uncertainty in the environment and/or updates of information as new data becomes available. Using computational experiments, the proposed approaches are compared to those that are applied in practice, and the aspects of the system where performance improvements are more significant are analyzed.

Šiame darbe apžvelgti dalelių spiečių algoritmai ir jų taikymai, išanalizuotas dirbtinės bičių kolonijos (ABC) algoritmas. Sukurta programinė ABC algoritmo realizacija, skirta optimizuoti žaidimo „Path of Exile“ veikėjo pasyvių įgūdžių grafui. Šio uždavinio sprendimui buvo panaudotas dirbtinės bičių kolonijos algoritmas su „godžiąja“ euristika. Atliktas programos testavimas, rezultatų palyginimas su žmonių sukurtais pasyvių įgūdžių grafais, padarytos išvados. / In this work an overview of particle swarm algorithms and their applications was given. Also artificial bee colony (ABC) algorithm was analyzed. The software realization of the ABC algorithm for optimizing “Path of Exile” game characters passive skill graph was developed. For solving this problem, ABC algorithm with greedy heuristic was used. Created software was tested, results were compared with passive skill graphs created by players and conclusions are given.