Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

Track assignment is a critical step between global routing and detailed routing in modern VLSI chip designs. It greatly affects some very important design characteristics, such as routability, via usage and timing performance. Crosstalk, which is largely decided by wire adjacency, has significant impact on interconnect delay and circuit performance. Therefore, the amount of crosstalk should be restrained in order to satisfy timing constraints. In this work, a track assignment approach is proposed to control crosstalk-induced performance degradation. The problem is formulated as a Traveling Salesman Problem (TSP) and solved by a graph-based heuristic. The proposed approach is implemented and tested on benchmark circuits from the ISPD2011 contest and the experimental results are quite promising.

none

none

In this thesis, we consider a capacity allocation problem in flexible manufacturing systems. We assume limited time and tool magazine capacities on the Computer Numerically Controlled (CNC) machines. We have a set of operations that have to be assigned to the machines and each operation requires a set of tools to be processed. Our problem is to allocate the available capacity of the CNC machines to operations and their required tools. We consider two problems in this study: maximizing the total weight of operations where there are a limited number of tools of each type available and maximizing total weight minus total tooling cost where the tools can be used or purchased at a cost. We model the problems as Integer Linear Programs and show that they are NP-hard in the strong sense. For the total weight problem, we propose upper bounds, branch and bound algorithm for exact solutions and several heuristics for approximate solutions. For the bicriteria problem, we use Lagrangean relaxation technique to obtain lower and upper bounds. Our computational results have revealed that all solution approaches give satisfactory results in reasonable times.

Bluetooth Piconet has become an important area of research and development in the short-range wireless network system. It is well known that bluetooth causes disturbing interference since sharing frequency band is used in communication channels. This thesis proposes a new and efficient method to solve the retransmission problem that occurs in wireless interference. The proposed method is developed based on average transmit times and margin of grouping to find out the grouping rule of the Bluetooth Piconet. A computer simulation shows in this thesis that the performance of the proposed group assignment approach is much bettter than can be obtained by other conventional means. Furthermore, in order to reduce retransmit time and save time-slot, a new packet combine retransmit method is developed based on different reliability of packet's transmit conditions in this thesis. As a consequence, for total duty cycle and time slots, the proposed packet combine retransmit method obtains a better performance than the conventional retransmit method.

Police authority is an extremely huge institution within the administrative organization. How to establish a complete and sound promotion system to enable police officers to be promoted in a fair and reasonable method and by which to inspire their morale and reinforce police efficiency is exactly the essential mechanism to fulfill permanent service of police personnel and achieve the goal of administrative reformation. However, those who with outstanding performance don¡¦t necessarily get promoted accordingly owing to numerous restrictions imposed on police officers¡¦ promotion system. Consequently, the efficiency is failed to be improved and the situation of bad money driving out good occurs within the agency and result in adverse selection. Therefore, establishing a sound and complete promotion system can not only facilitate organizers to get promotion based on accomplishments and contributions individually by placing them in the right positions according to their professional specialties but also can inspire their morale to bring talents into full play and therefore increase working proficiency out of great loyalty. The establishment theory of police officers¡¦ promotion system takes ¡§theory¡¨ as the ¡§basis¡¨ and ¡§law¡¨ as the ¡§application.¡¨ The decrees and regulations it acts pursuant to and applies to are divided into law, order, and slip law. Police officers¡¦ promotion methods, standards, and operation principles are proclaimed in detail in the existing ¡§Civil Service Employment Act,¡¨ ¡§The Statute For Personnel Affairs Involving Police Staff,¡¨ ¡§Police Officers¡¦ Promotion Measures,¡¨ and ¡§Regulation Governing the Extended Authorization of Personnel Affairs of National Police Agency, Ministry of the Interior.¡¨ Nevertheless, police officers¡¦ promotion frequency is relatively higher compared to general civil service staff. Though it¡¦s the outcome of considering the specialty of duty and business, police officers¡¦ positions are adjusted easily owing to punishment and therefore they have to adapt to new environment all the time. Whether it will result in adverse influence on social security preservation requires further exploration. Police officers¡¦ promotion legal system is hereby taken as the main research subject, supported with further explanation of other associated administrative regulations and basic principles of administrative law, the five major frameworks including ¡§Administrative Principles, Administrative Organization, Limitation of Administrative Power, Administrative Relief, and Administrative Supervision¡¨ serve as the research approaches to examine police officers¡¦ promotion system of the Republic of China.

A general framework is presented for replacing static traffic assignment with dynamic traffic assignment within the standard four step transportation planning model. Issues including model consistency and the implementation of a proper feedback loop are explored. The new model is compared with the standard four step model in order to highlight the benefits of using dynamic traffic assignment rather than static. The model is then extended to include a term for the difference between experienced and free-flow travel times, which can be used as a proxy for travel time reliability and highlights the benefits of time-dependent DTA. Additionally, a study on improving the quality of convergence for dynamic traffic assignment is conducted in order to help facilitate the usefulness of this modeling approach in practice. A variety of equilibration techniques are tested, and analysis is performed to contrast these techniques with the method of successive averages. / text

Practical issues concerning the implementation and application of genetic algorithms to a number of optimisation problems are the main subjects dealt with in this thesis. Genetic algorithms (GAs) are an attractive class of computational models that attempt to mimic the mechanisms of natural evolution to solve problems in a wide variety of domains. A general purpose genetic algorithm toolkit is developed and applied to the Steiner Problem in Graphs and the Radio Link Frequency Assignment Problem. The toolkit is then extended to cover a large number of parallel genetic algorithm models which are then compared. Solutions for the two case studies are presented with each of the parallel GAs. The thesis begins with a general introduction to genetic algorithms. Holland's original genetic algorithm is described and it's workings illustrated on a simple function minimisation problem. The notion of a schema or similarity template as a basic building block in genetic algorithms is introduced and the schema theory presented. A description of important theoretical results is given and the introduction to genetic algorithms continues with practical issues that are dealt with in the second chapter. The basic components of a modern genetic algorithm are outlined and examples for important components, as found in the Jiterature, are given. The second chapter concludes with the description of a number of applications of genetic algorithms to areas such as function optimisation, combinatorial optimisation, genetic programming, process control and classifier systems. In Chapter 3, the sequential GA toolkit, GAmeter, is described. The General Search paradigm around which the toolkit is implemented is introduced. Notable characteristics of the genetic algorithms kernel and the user interface are mentioned. A popular function optimisation problem is used to illustrate important aspects of genetic algorithms and aspects specific to the toolkit. The Steiner Tree problem in graphs is the first of two case studies examined in detail in this thesis. This is a popular NP-complete problem with a range of applications in areas such as communications, scheduling and printed circuit design. A survey of standard techniques, such as simplification methods, exact algorithms and heuristics is given. Two possible representations for solving it using genetic algorithms are described and applied to a well-known set of problems. Chapter 4 concludes with a comparison of the best GA technique with other heuristics for this problem. The Radio Link Frequency Assignment Problem, described in Chapter 5, is the second case study investigated in this thesis. Genetic algorithms were applied to this problem as part of a EUCLID (European Cooperation for the Long Term in Defence) funded multi-national study to compare exact and heuristic techniques for hard combinatorial problems associated with military applications. A number of approaches used to solve this highly constrained, hard problem for genetic algorithms are described. These include a range of new genetic operators and catalytic terms that are added to the fitness function. Apart from the direct approach to solving this problem using genetic algorithms, for which the majority of operators and catalytic terms apply, an indirect approach which combines genetic algorithms with backtracking is described. The possibility of using a meta genetic algorithm to chose the best of a multitude of options, e.g. genetic operators and parameter settings for a GA applied to the Radio Link Frequency Assignment Problem is investigated. Results are reported for two sets of problems that were used by all participants in this project. An overview of the techniques investigated for this project is given and the chapter concludes with comparisons between all these techniques. In Chapter 6, an overview of general aspects in parallel processing is given. Parallel computer architectures, parallel programming paradigms and performance measurement are the main subjects dealt with in this chapter. Special emphasis is given to material relevant to the investigation on parallel genetic algorithms, presented in the following chapter. In Chapter 7, parallel genetic algorithms are examined in some detail. A number of parallel GA models are described and classified according to whether they are designed around the sequential GA or around a more natural model. A ParallelSequential General Search paradigm is presented that unifies the various parallel models and is used to extend the GA toolkit into a parallel GA toolkit for a parallel system based on Transputers. The parallel GA models are applied to problems from both of the case studies considered in this thesis. A comparison between the various parallel GA models concludes this chapter. The thesis finishes with a summary of a number of conclusions drawn from this research together with some suggestions for how this work may be continued in the future.

Transportation planning and operation requires determining the state of the transportation system under different network supply and demand conditions. The most fundamental determinant of the state of a transportation system is time-varying traffic flow pattern on its roadway segments. It forms a basis for numerous engineering analyses which are used in operational- and planning-level decision-making process. Dynamic traffic assignment (DTA) models are the leading modeling tools employed to determine time-varying traffic flow pattern under changing network conditions. DTA models have matured over the past three decades, and are now being adopted by transportation planning agencies and traffic management centers. However, DTA models for large-scale regional networks require excessive computational resources. The problem becomes further compounded for other applications such as congestion pricing, capacity calibration, and network design for which DTA needs to be solved repeatedly as a sub-problem. This dissertation aims to improve the efficiency of the DTA models, and increase their viability for various planning and operational applications. To this end, a suite of computational methods based on the combinatorial approach for dynamic traffic assignment was developed in this dissertation. At first, a new polynomial run time combinatorial algorithm for DTA was developed. The combinatorial DTA (CDTA) model complements and aids simulation-based DTA models rather than replace them. This is because various policy measures and active traffic control strategies are best modeled using the simulation-based DTA models. Solution obtained from the CDTA model was provided as an initial feasible solution to a simulation-based DTA model to improve its efficiency – this process is called “warm starting” the simulation-based DTA model. To further improve the efficiency of the simulation-based DTA model, the warm start process is made more efficient through parallel computing. Parallel computing was applied to the CDTA model and the traffic simulator used for warm starting. Finally, another warm start method based on the static traffic assignment model was tested on the simulation-based DTA model. The computational methods developed in this dissertation were tested on the Anaheim, CA and Winnipeg, Canada networks. Models warm-started using the CDTA solution performed better than the purely simulation-based DTA models in terms of equilibrium convergence metrics and run time. Warm start methods using solutions from the static traffic assignment models showed similar improvements. Parallel computing was applied to the CDTA model, and it resulted in faster execution time by employing multiple computer processors. Parallel version of the traffic simulator can also be embedded into the simulation-assignment framework of the simulation-based DTA models and improve their efficiency. / text