<p>This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.</p>

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 145-151).

Compared to conventional Steiner tree signal net routing, non-tree topology is often superior in many aspects including timing performance, tolerance to open faults and variations. In nano-scale VLSI designs, interconnect delay is a performance bottleneck and variation effects are increasingly problematic. Therefore the advantages of non-tree topology are particularly appealing for timing critical net routings in nano-scale VLSI designs. We propose Steiner network construction heuristics which can generate either tree or non-tree of signal net with different slack wirelength tradeoffs, and handle both long path and short path constraints. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches while increasing only slightly in wirelength. These results show that our algorithm is a very promising approach for timing critical net routings.

This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.

The presented thesis project is a study on train energy consumption calculation and optimal train driving strategies for minimum energy consumption. This study is divided into three parts; the first part is a proposed model for energy consumption calculation for trains based on driving resistances. The second part is a presentation of a method based on dynamic programming and the Hamilton-Jacobi-Bellman equation (Bellman’s backward approach) for obtaining optimal speed and control profiles leading to minimum energy consumption. The third part is a case study for a Bombardier Transportation case. It includes the presentation of a preliminary algorithm developed within this thesis project; an algorithm based on the HJB equation that can be further improved in order to be used online in real-time as an advisory system for train drivers.

A time series is composed of a sequence of data items that are measured at uniform intervals. Many application areas generate or manipulate time series, including finance, medicine, digital audio, and motion capture. Efficiently searching a large time series database is still a challenging problem, especially when partial or subseries matches are needed. This thesis proposes a new denition of subseries join, a symmetric generalization of subseries matching, which finds similar subseries in two or more time series datasets. A solution is proposed to compute the subseries join based on a hierarchical feature representation. This hierarchical feature representation is generated by an anisotropic diffusion scale-space analysis and a non-uniform segmentation method. Each segment is represented by a minimal polynomial envelope in a reduced-dimensionality space. Based on the hierarchical feature representation, all features in a dataset are indexed in an R-tree, and candidate matching features of two datasets are found by an R-tree join operation. Given candidate matching features, a dynamic programming algorithm is developed to compute the final subseries join. To improve storage efficiency, a hierarchical compression scheme is proposed to compress features. The minimal polynomial envelope representation is transformed to a Bezier spline envelope representation. The control points of each Bezier spline are then hierarchically differenced and an arithmetic coding is used to compress these differences. To empirically evaluate their effectiveness, the proposed subseries join and compression techniques are tested on various publicly available datasets. A large motion capture database is also used to verify the techniques in a real-world application. The experiments show that the proposed subseries join technique can better tolerate noise and local scaling than previous work, and the proposed compression technique can also achieve about 85% higher compression rates than previous work with the same distortion error.

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.

This thesis is an approach to improve a two-mode hybrid electric vehicle, which is currently under development by GM, with respect to fuel consumption. The study is not only restricted to the specific two-mode HEV but also presents results regarding parallel as well as serial HEV’s. GM whishes to verify if the online-based controller in the prototype vehicle utilizes the most of the HEV ability and if there is more potential to lower the fuel consumption. The purpose is that the results and conclusions from this work are to be implemented in the controller to further improve the vehicle’s performance. To analyze the behavior of the two-mode HEV and to see where improvements can be made, models of its driveline and components are developed with a focuson losses and efficiency. The models are implemented in MATLAB together with an optimization algorithm based on Dynamic Programming. The models are validated against data retrieved from the prototype vehicle and various cases with different inputs is set up and optimized over the NEDC cycle. Compensation for cold starts and NOx emissions are also implemented in the final model. Deliberate simplifications are made regarding the modeling of the power split’s functionality due to the limited amount of time available for this thesis. The optimizations show that there is potential to lower the fuel consumptionfor the two-mode HEV. The results are further analyzed and the behavior of the engine, motors/generators and battery are compared with recorded data from a prototype vehicle and summarized to a list of suggestions to improve fuel economy.

Increased environmental awareness together with new legislative demands on lowered emissions and a rising fuel cost have put focus on increasing the fuel efficiency in new vehicles. Hybridization is a way to increase the efficiency of the powertrain.The Haldex electric Torque Vectoring Device is a rear axle with a built in electric motor, designed to combine all-wheel drive with hybrid functionality. A method is developed for creating a real time control algorithm that minimizes the fuel consumption. First the consumption reduction potential of the system is investigated using Dynamic Programming. A real time control algorithm is then devised that indicates a substantial consumption reduction potential compared to all-wheel drive, under the condition that the assumed and measured efficiencies are accurate. The control algorithm is created using equivalent consumption minimization strategy and is implemented without any knowledge of the future driving mission. Two ways of adapting the control according to the battery state of charge are proposed and investigated. The controller optimizes the torque distribution for the current gear as well as assists the driver by recommending the gear which would give the lowest consumption. The simulations indicate a substantial fuel consumption reduction potential even though the system primarily is an all-wheel drive concept. The results from vehicle tests show that the control system is charge sustaining and the driveability is deemed good by the test-drivers.

The situation when driving in dense traffic and at low speeds is called Stop and Go. A controller for automatic following of the car in front could under these conditions reduce the driver's workload and keep a safety distance to the preceding vehicle through different choices of gear and engine torque. The aim of this thesis is to develop such a controller, with an additional focus on lowering the fuel consumption. With help of GPS, 3D-maps and sensors information about the slope of the road and the preceding vehicle can be obtained. Using this information the controller is able to predict future possible control actions and an optimization algorithm can then find the best inputs with respect to some criteria. The control method used is Model Predictive Control (MPC) and as the name indicate a model of the control object is required for the prediction. To find the optimal sequence of inputs, the optimization method Dynamic Programming choose the one which lead to the lowest fuel consumption and satisfactory following. Simulations have been made using a reference trajectory which was measured in a real traffic jam. The simulations show that it is possible to follow the preceding vehicle in a good way and at the same time reduce the fuel consumption with approximately 3 %.