Extending snBench to Support Hierarchical and Configurable Scheduling

It is useful in systems that must support multiple applications with various temporal requirements to allow application-specific policies to manage resources accordingly. However, there is a tension between this goal and the desire to control and police possibly malicious programs. The Java-based Sensor Execution Environment (SXE) in snBench presents a situation where such considerations add value to the system. Multiple applications can be run by multiple users with varied temporal requirements, some Real-Time and others best effort. This paper outlines and documents an implementation of a hierarchical and configurable scheduling system with which different applications can be executed using application-specific scheduling policies. Concurrently the system administrator can define fairness policies between applications that are imposed upon the system. Additionally, to ensure forward progress of system execution in the face of malicious or malformed user programs, an infrastructure for execution using multiple threads is described.

Dynamic Programming for Optimal Control of Set-Up Scheduling with Neural Network Modifications

This paper demonstrates an optimal control solution to change of machine set-up scheduling based on dynamic programming average cost per stage value iteration as set forth by Cararnanis et. al. [2] for the 2D case. The difficulty with the optimal approach lies in the explosive computational growth of the resulting solution. A method of reducing the computational complexity is developed using ideas from biology and neural networks. A real time controller is described that uses a linear-log representation of state space with neural networks employed to fit cost surfaces.

Bridge-vehicle interaction for structural health monitoring: potentials, applications, and limitations

Structural Health Monitoring (SHM) is an integral part of infrastructure maintenance and management systems due to socio-economic, safety and security reasons. The behaviour of a structure under vibration depends on structure characteristics. The change of structure characteristics may suggest the change in system behaviour due to the presence of damage(s) within. Therefore the consistent, output signal guided, and system dependable markers would be convenient tool for the online monitoring, the maintenance, rehabilitation strategies, and optimized decision making policies as required by the engineers, owners, managers, and the users from both safety and serviceability aspects. SHM has a very significant advantage over traditional investigations where tangible and intangible costs of a very high degree are often incurred due to the disruption of service. Additionally, SHM through bridge-vehicle interaction opens up opportunities for continuous tracking of the condition of the structure. Research in this area is still in initial stage and is extremely promising. This PhD focuses on using bridge-vehicle interaction response for SHM of damaged or deteriorating bridges to monitor or assess them under operating conditions. In the present study, a number of damage detection markers have been investigated and proposed in order to identify the existence, location, and the extent of an open crack in the structure. The theoretical and experimental investigation has been conducted on Single Degree of Freedom linear system, simply supported beams. The novel Delay Vector Variance (DVV) methodology has been employed for characterization of structural behaviour by time-domain response analysis. Also, the analysis of responses of actual bridges using DVV method has been for the first time employed for this kind of investigation.

Resonant power conversion topologies for inductive charging of electrical vehicle batteries

This thesis is concerned with inductive charging of electric vehicle batteries. Rectified power form the 50/60 Hz utility feeds a dc-ac converter which delivers high-frequency ac power to the electric vehicle inductive coupling inlet. The inlet configuration has been defined by the Society of Automotive Engineers in Recommended Practice J-1773. This thesis studies converter topologies related to the series resonant converter. When coupled to the vehicle inlet, the frequency-controlled series-resonant converter results in a capacitively-filtered series-parallel LCLC (SP-LCLC) resonant converter topology with zero voltage switching and many other desirable features. A novel time-domain transformation analysis, termed Modal Analysis, is developed, using a state variable transformation, to analyze and characterize this multi-resonant fourth-orderconverter. Next, Fundamental Mode Approximation (FMA) Analysis, based on a voltage-source model of the load, and its novel extension, Rectifier-Compensated FMA (RCFMA) Analysis, are developed and applied to the SP-LCLC converter. The RCFMA Analysis is a simpler and more intuitive analysis than the Modal Analysis, and provides a relatively accurate closed-form solution for the converter behavior. Phase control of the SP-LCLC converter is investigated as a control option. FMA and RCFMA Analyses are used for detailed characterization. The analyses identify areas of operation, which are also validated experimentally, where it is advantageous to phase control the converter. A novel hybrid control scheme is proposed which integrates frequency and phase control and achieves reduced operating frequency range and improved partial-load efficiency. The phase-controlled SP-LCLC converter can also be configured with a parallel load and is an excellent option for the application. The resulting topology implements soft-switching over the entire load range and has high full-load and partial-load efficiencies. RCFMA Analysis is used to analyze and characterize the new converter topology, and good correlation is shown with experimental results. Finally, a novel single-stage power-factor-corrected ac-dc converter is introduced, which uses the current-source characteristic of the SP-LCLC topology to provide power factor correction over a wide output power range from zero to full load. This converter exhibits all the advantageous characteristics of its dc-dc counterpart, with a reduced parts count and cost. Simulation and experimental results verify the operation of the new converter.

Adenovirus F protein as a delivery vehicle for botulinum B.

BACKGROUND: Immunization with recombinant carboxyl-terminal domain of the heavy chain (Hc domain) of botulinum neurotoxin (BoNT) stimulates protective immunity against native BoNT challenge. Most studies developing a botulism vaccine have focused on the whole Hc; however, since the principal protective epitopes are located within beta-trefoil domain (Hcbetatre), we hypothesize that immunization with the Hcbetatre domain is sufficient to confer protective immunity. In addition, enhancing its uptake subsequent to nasal delivery prompted development of an alternative vaccine strategy, and we hypothesize that the addition of targeting moiety adenovirus 2 fiber protein (Ad2F) may enhance such uptake during vaccination. RESULTS: The Hcbetatre serotype B immunogen was genetically fused to Ad2F (Hcbetatre/B-Ad2F), and its immunogenicity was tested in mice. In combination with the mucosal adjuvant, cholera toxin (CT), enhanced mucosal IgA and serum IgG Ab titers were induced by nasal Hcbetatre-Ad2F relative to Hcbetatre alone; however, similar Ab titers were obtained upon intramuscular immunization. These BoNT/B-specific Abs induced by nasal immunization were generally supported in large part by Th2 cells, as opposed to Hcbetatre-immunized mice that showed more mixed Th1 and Th2 cells. Using a mouse neutralization assay, sera from animals immunized with Hcbetatre and Hcbetatre-Ad2F protected mice against 2.0 LD50. CONCLUSION: These results demonstrate that Hcbetatre-based immunogens are highly immunogenic, especially when genetically fused to Ad2F, and Ad2F can be exploited as a vaccine delivery platform to the mucosa.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

A new heuristic for three-machine flow shop scheduling

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.

Shop scheduling problems under precedence constraints

The paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, we study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence rela-tions are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.

Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Heuristics for short route job shop scheduling problems

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

A heuristic algorithm for two-machine re-entrant shop scheduling

This paper considers the problem of sequencing n jobs in a two‐machine re‐entrant shopwith the objective of minimizing the maximum completion time. The shop consists of twomachines, M1 and M2 , and each job has the processing route (M1 , M2 , M1 ). An O(n log n)time heuristic is presented which generates a schedule with length at most 4/3 times that ofan optimal schedule, thereby improving the best previously available worst‐case performanceratio of 3/2.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.