An optimal time to sleep for an auto-sleep system considering multi-usage states

An auto-sleep system is defined by the following two properties:

• 1.(i) a call for the system occurs randomly and intermittently
• 2.(ii) the system automatically goes to sleep if there occurs no call during a prespecified time T.

It considers four states:

• 1.(a) sleep
• 2.(b) warm-up
• 3.(c) nonusage
• 4.(d) usage.

For such a system, the time to sleep has been discussed based on suitable criteria. This study extends the model for an auto-sleep system so that the model can deal with multi-usage states. With a view to determining an optimal time to sleep under the extended model, the expected energy consumed per unit time is formulated as a criterion to be minimized. The existence of an optimal time to sleep is examined under a general call distribution. Numerical examples are also provided for a Weibull as well as a log-normal call distribution.     

Single machine scheduling with common due date assignment in a group technology environment

We consider a scheduling problem in which n jobs are grouped into F groups and are to be processed on a single machine. A machine setup time is required when the machine switches from one group of jobs to the other. All jobs have a common due date that needs to be determined. The objective is to find an optimal common due date and an optimal sequence of jobs to minimize the sum of the cost of tardy jobs and the cost related to the common due date. We consider two cases:

• 1.(i) the jobs have to be processed in groups; and
• 2.(ii) the jobs do not have to be processed in groups.

Analytical results are presented and computational algorithms are developed.     

Determining the optimal place and capacity of spare parts warehouses in the construction industry

In the construction industry, places, capacities and levels of demand in basic spare parts are changing in relatively short periods of time. This creates an optimization problem of the following form.We are given the following:o

1. (i)The location and the level of demand for each basic spare part in each work site for a specific time period.
2. (ii)The places and the levels of demand can be altered.
3. (iii)There are more than one supplier of each part geografically distributed.
4. (iv)The number of basic equipment spare parts.
5. (v)The transportation cost per load of spare parts.
6. (vi)The purchasing and functioning cost of the various air houses used as warehouses of spare parts.

In this paper we present an algorithm which determines the place, capacity and number of supply points to minimize the total cost of the supply system under the constraints (i) to (vi) above.     

Mathematical modelling of the flotation deinking process

The overall flotation deinking process can be divided into four basic microprocesses:

• 1.(1) collision or capture of an (ink) particle by an air bubble
• 2.(2) adhesion of an (ink) particle to the air bubble by sliding
• 3.(3) development of a three-phase contact at the air bubble/water/particle interface, and
• 4.(4) bubble/particle stability or instability after an aggregate is formed each of these microprocesses have an associated probability that they will occur successfully in a flotation cell.

In this paper, the associated probabilities of each microprocess are employed in the development of a kinetic- or population balance-type model of the overall flotation process. The overall model contains two kinetic constants: the first, k₁ governs the overall probability of a free ink particle successfully intercepting and adhering to an air bubble; the second, k₂ is a measure of the probability that a bubble/particle aggregate pair will become unstable and split to yield a “new” free ink particle.The solution to the kinetic model is presented in terms of k₁ and k₂, which are themselves functions of system parameters such as bubble and particle physical properties (e.g., diameter, density), fluid properties (e.g., viscosity, surface tension), etc. From this solution, a definition of a theoretical flotation efficiency, as well as other system performance parameters are presented.     

Common knowledge revisited

We consider the common-knowledge paradox raised by Halpern and Moses: common knowledge is necessary for agreement and coordination, but common knowledge is unattainable in the real world because of temporal imprecision. We discuss two solutions to this paradox:

• 1.(1) modeling the world with a coarser granularity, and
• 2.(2) relaxing the requirements for coordination.

     

Methods for routing with time windows

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required together with their routes and schedules, so that each trip begins within his given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips are minimized. The problem is a generalization of the m-travelling salesman problem.We compare numerical results for 3 algorithms developed by our research team:

• 1.(1) Column generation on a set partitioning problem solved by simplex and branch-and-bound; columns are generated by a shortest path algorithm with time constraints on the nodes.
• 2.(2) Adaptation of the Carpaneto-Toth algorithm for the asymmetric travelling salesman problem: solution of network problems by relaxing scheduling constraints, and branch-and-bound on flow variables.
• 3.(3) Solution of network problems by relaxing scheduling constraints and branch-and-bound based on dividing the time windows.

     

System dynamics and feedback control problem formulations for real time dynamic traffic routing

This paper formulates the Dynamic Traffic Routing (DTR) problem as a real-time feedback control problem. Three different forms of the formulation are presented:

• 1.(1) distributed parameter system form derived from the conservation law;
• 2.(2) space discretized continuous lumped parameter form;
• 3.(3) space and time discretized lumped parameter form.

These formulations can be considered as the starting points for development of feedback control laws for the different control problems stated in this paper. This paper presents the feedback control problems, and does not discuss in detail the methodology of solution techniques which could be used to solve these problems. However, for the sake of completeness a brief treatment of the three forms are included in this paper to show possible ways to design the controllers.     

Cellularity of first countable spaces

In this paper, we find subspaces of the Pixley-Roy space on the irrationals which are

• 1.(1) a first countable ccc space which does not have a σ-linked base,
• 2.(2) for each n>1, a first countable space which has a σ-n-linked base but which does not have a (σ−n+1)-linked base and
• 3.(3) a first countable space which has, for each n>1, a σ-n-linked base but which does not have a σ-centered base.

It is consistent with ¬CH that (1) and (2) have cardinality ℵ₁. (3) is constructed from a graph G on the continuum c which is not the union of countably many complete subgraphs but has no uncountable pairwise incompatible family of finite complete subgraphs (complete subgraphs A and B are compatible if there is a complete subgraph C which contains A and B).     

A Note on Old Babylonian Computational Techniques

Analysis of the errors in two Old Babylonian “algebraic” problems shows

• •that the computations were performed on a device where additive contributions were no longer identifiable once they had entered the computation;
• •that this device must have been some kind of counting board or abacus where numbers were represented as collections of calculi;
• •that units and tens were represented in distinct ways, perhaps by means of different calculi.

© 2002 Elsevier Science (USA).Eine Analyse der Rechenfehler in zwei altbabylonischen “algebraischen” Aufgaben läßt mehrere Rückschlüsse auf ein Hilfsmittel zu, das zur Durchführung von Rechnungen benutzt worden sein kann:

• •Additive Beiträge waren nach ihrer Eintragung in die Rechnung nicht länger identifizierbar.
• •Das Gerät war eine Art Rechenbrett, auf welchem Zahlen als Haufen von Rechensteinen erschienen.
• •Einer und Zehner wurden in verschiedener Weise, evtl. mittels verschiedener Rechensteine repräsentiert.

© 2002 Elsevier Science (USA).MSC subject classification: 01A17.     

On the computational complexity of the theory of Abelian groups

We develop a series of Ehrenfeucht games and prove the following results:

• 1.(i) The first order theory of the divisible and indecomposable p-group, the first order theory of the group of rational numbers with denominators prime to p and the first order theory of a cyclic group of prime power order can be decided in 2^{2cn log n} Turing time.
• 2.(ii) The first order theory of the direct sum of countably many infinite cyclic groups, the first order theory of finite Abelian groups and the first order theory of all Abelian groups can be decided in 2^2dn Turing space.

     

The dynamic programming method in the generalized traveling salesman problem

A procedure of the dynamic programming (DP) for the discrete-continuous problem of a route optimization is considered. It is possible to consider this procedure as a dynamic method of optimization of the towns choice in the well-known traveling salesman problem. In the considered version of DP, elements of a dynamic optimization are used. Two variants of the function of the aggregations of losses are investigated:

• 1.(1) the additive functions;
• 2.(2) the function characterizing the aggregation of losses in the bottle-neck problem.

     

Ultrafilters,independent collections,and applications to topology

The following are consequences of the main results in this paper:

• 1.(1) The number of countably compact, completely regular spaces of density κ is 2^22κ.
• 2.(2) There are 2^2κ points in U(κ) (= space of uniform ultrafilters on κ), each of which has tightness 2^κ in U(κ) and is a limit point of a countable subset of U(κ).
• 3.(3) There are 2^2κ points in U(κ), each of which has tightness 2^κ and is a weak P-point of κ¹.
• 4.(4) For each λ ⩽ κ there are at least 2^2λ · κ points in βκ, each of which has tightness 2^λ in β κ and is a weak P-point of κ¹. Moreover, under GCH there are at least 2^2λ · κ^λ such points.

     

Reformulating the traffic equilibrium problem via a smooth gap function

This paper proposes an alternate formulation of the traffic assignment problem using route flows and the shortest Origin-Destination (OD) travel times as the decision variables. This is accomplished through defining a gap function to convert the Nonlinear Complementarity Problem (NCP) formulation to an equivalent Mathematical Program (MP). This formulation has two advantages:

• 1.(i) it can model assignment problems with general route costs which cannot be accomplished with existing formulations that use link-flow variables
• 2.(ii) the objective function is smooth, convex, and bounded, which permits efficient MP algorithms for its solution.

Two solution approaches are developed to solve the proposed formulation. The first is based on a set of working routes, which are modeled as “known a priori” based on travelers' preferences or interviews. The second approach uses a column generation procedure to generate a new route in each iteration on a need basis. For each approach, we use a Successive Quadratic Programming (SQP) algorithm to solve for the solutions.To show that the formulation is correct, we solve a small example with a general route cost and compare it to the classic traffic equilibrium problem which assumes an additive route cost function. Finally, numerical results for a medium-sized network are provided to demonstrate the feasibility of the solution approach.     

Symplectic geometry,minors and graph Laplacians

In my talk, I will present some works done in the nineties on Laplacians on graphs: from eigenvalue problems to inverse problem for resistor networks. I will focus on the motivations and the main results as well as on the main ideas:

• •A differential topology point of view on the minor relation: a nice stratification associated to a finite graph Γ whose strata are associated to the minors of Γ
• •“Discrete” (graphs) versus “continuous” (Riemannian manifolds)
• •Stability of spectra with respect to singular limits: a finite dimensional theory of operators with domains (Von Neumann theory).

The link with topology will appear in some results about my graph parameter μ, in particular the planarity and the linkless embedding properties.     

Analysis of performance of an iron-bath reactor using computational fluid dynamics

The performance of an iron-bath reactor has been studied using a comprehensive numerical model that combines a computational fluid dynamics approach for the gas phase and a heat and mass balance model for the bath. The model calculates:

• •coal, ore, flux and oxygen consumption;
• •post-combustion ratio (PCR);
• •heat-transfer efficiency (HTE);
• •off-gas temperature and composition;
• •heat transfer and chemical reactions between gas and iron and slag droplets; and
• •heat transfer between gas and bath, refractories and lance.

The model was validated with data reported by the Nippon Steel Corporation for a 100 t pilot plant, and the calculated and measured data are in good agreement. Modelling results showed that the dominant mechanisms of heat transfer from the gas to the bath are radiation to the slag surface and convection heat transfer to droplets.     

Free energy and solutions of the Vlasov-Poisson-Fokker-Planck system: external potential and confinement (Large time behavior and steady states)

This paper is devoted to the characterization of external electrostatic potentials for which the Vlasov-Poisson-Fokker-Planck system satisfies one of the following properties:

• (i) the system admits stationary solutions,
• (ii) any solution to the evolution problem converges to a stationary solution, or, equivalently, no mass vanishes for large times,
• (iii) the free energy is bounded from below, We give conditions under which these different notions of confinement are equivalent.

     

Dynamic graph models

Research in graph theory has focused on studying the structure of graphs with the assumption that they are static. However, in many applications, the graphs that arise change with time, i.e., they are dynamic in nature. This is especially true of applications involving graph models in computer science. We present an expository study of dynamic graphs with the main driving force being practical applications. We first develop a formal classification of dynamic graphs. This taxonomy in the form of generalizations and extensions will in turn suggest new areas of application. Next, we discuss areas where dynamic graphs arise in computer science such as compilers, databases, fault-tolerance, artificial intelligence, and computer networks. Finally, we propose approaches that can be used for studying dynamic graphs. The main objective in any study of dynamic graphs should be to

• 1.(i) extend results developed for static graph theory to dynamic graphs,
• 2.(ii) study the properties that describe how a dynamic graph changes,
• 3.(iii) investigate problems and issues in dynamic graph theory that are raised by practical applications of dynamic graphs in computer science.