The paper is concerned with scheduling trains moving in both directions between two stations connected by a single-track railway with a siding. The paper presents dynamic programming based algorithms which minimizes two objective functions: maximum lateness and total weighted completion time. The complexity of these algorithms is O(n2).
This paper considers a network game as follows. In each node of a network, economy is described by the simple two-period Romer’s model of endogenous growth with production and knowledge externalities. The sum of knowledge levels in the neighbor nodes causes an externality in the production of each network node. The concept of node type is introduced and a corresponding typology of networks is suggested. As demonstrated below, all inner equilibria of the game are determined by this typology. For several typologies, the equilibrium knowledge levels are found in explicit form for the nodes that have different positions in the network.
This paper derives upper and lower bounds of the price in the optimal stopping problem for a consistent random sequence in the case of finite horizon. As is demonstrated below, the bounds can be found by solving the maximax and maximin setups of optimal stopping problems. For these setups, we obtain conditions under which 1) a recurrent relation is satisfied for the upper (lower) truncated sequence of optimal stopping prices; 2) an optimality criterion is constructed for the stopping times; 3) the structure and invariance of the optimal stopping times are established. Some examples with explicit solutions of the maximax and maximin setups of optimal stopping problems are given.
A modification of the decoding q-ary Sum Product Algorithm (q-SPA) was proposed for the nonbinary codes with small check density based on the permutation matrices. The algorithm described has a vector realization and operates over the vectors defined on the field GF(q), rather than over individual symbols. Under certain code parameters, this approach enables significant speedup of modeling.
We offer a general approach to describing power indices that account for preferences as suggested by F. Aleskerov. We construct two axiomatizations of these indices. Our construction generalizes the Laruelle-Valenciano axioms for Banzhaf (Penrose) and Shapley-Shubik indices. We obtain new sets of axioms for these indices, in particular, sets without the anonymity axiom.
An axiomatics of power indices in voting with quota was proposed. It relies on the additivity and dictator axioms. Established was an important property that the player’s power index is representable as the sum of contributions of the coalitions in which it is a pivot member. The coalition contributions are independent of the players’ weights or the quota. The general theorem of power index representation and the theorem of representation for a power index of anonymous players were formulated and proved.
We formulate the optimal control problem for a class of nonlinear objects that can be represented as objects with linear structure and state-dependent coefficients. The linear structure of the transformed nonlinear system and the quadratic quality functional let us, in the optimal control synthesis, to pass from Hamilton–Jacobi equations to a state-dependent Riccati equation. The main problem is the implementation of an optimal control problem is related to the search for solutions of this equation in the rate of the object functioning. This paper proposes a method of an algorithmic parameter optimization of the controller based on the use of the necessary conditions for the optimality of the considered control systems. The constructed algorithms can be used both for optimizing the non-stationary objects themselves, if the corresponding parameters are selected for this purpose, and for optimizing the entire managed system by means of the corresponding parametric adjustment of the regulators. The effectiveness of the developed algorithms is demonstrated by the example of medical treatment of patients with HIV.
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT j and for the problem of maximizing the number of tardy jobs 1‖maxΣU j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT j is polynomially solvable. For several special cases of problem 1‖maxΣT j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
We present the basic properties of the a new pattern analysis method in the system of parallel coordinates; results of the method do not depend on the ordering of data in the original sample of objects being analyzed. We prove that clusters obtained with this method do not overlap. We also show the possibility of representing objects of one cluster in the form of monotonically increasing/decreasing functions.
Для передачи по mesh-сети потоковых данных, предъявляющих высокие требования к качеству обслуживания, удобно использовать описанный в стандарте IEEE 802.11s механизм MCCA детерминированного доступа к среде. При использовании этого механизма станции резервируют для своих передач определенные периодически повторяющиеся интервалы времени, тем самым получая бесконкурентный доступ к каналу связи. Однако, чтобы обеспечить успешную доставку данных в условиях помех, необходимо устанавливать дополнительные резервирования под повторные попытки передачи. В работе построена аналитическая модель процесса передачи неординарного потока по многошаговым беспроводным сетям с помощью механизма MCCA. Модель позволяет определить наибольший период резервирований, при котором выполнены требования на время доставки и долю потерянных пакетов.