Lattices of processes for graphs

The structure of the lattice of processes of a finite digraph with entries is investigated. Necessary and sufficient conditions for the isomorphism of a given lattice to the lattice of processes of a certain digraph are obtained. Bibliography: 5 titles. Translated by K. V. Shakhbazyan. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 135–153.     

Solution of two sequencing problems

The solution of the following problems is offered. Suppose a multiset J (¦J¦=p) is given. For each pair of elements and J, a number 1 P is given. Moreover, if 1 < x<p then x is undefined. If x=1, then x=p. Problem 1. Find the permutation ₁..._F of elements of the multiset J satisfying the following conditions. Let _i, _i=. If i,j < x, thenj <i. If i,j > x, then i<j. Such a permutation is called a PC-schedule. Problem 2. Find a PC-schedule in which the following property holds: if i < x < j, _i=, _j=, then. Such a PC-schedule is called an SC-schedule. The conditions under which these problems have solutions are studied. For their solution an algorithm of shifts is used with the complexity O(¦B(J)¦²¦J¦).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 44–72, 1983.     

A spanning-tree algorithm for constructing streams in pipelines

An algorithm based on the construction of a spanning subgraph of the pipeline is proposed for determining streams in pipelines. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 159, pp. 40–46, 1987.     

Scheduling theory problems of type n¦1∥σci(t)

The class of problems n¦1∥σc_i(t) is considered for special sets of penalty functions c_i(t). Using the structural properties of the sets of functions c_i(t), one selects subclasses of problems which possess a polynomial complexity.     

Stevens Rearrangement of Anilinium Salts By the Action Sodium Carbonate Hexahydrate

Anilinium salts containing an allyl-like group together with various functionally substituted receiving groups undergo Stevens rearrangement by the action of sodium carbonate hexahydrate in the absence of a solvent. As a result, both N-methylaniline derivatives and nucleophilic substitution products are formed.     

Optimal schedulings with gaps for independent jobs in a service system withN servers

One considers the problem of forming the optimal schedulings with gaps for a service system withN identical parallel processors. In the service one performsK jobs, each of which consists of V_i homogeneous independent operations and has lower and upper directive times d_i and D_i. For the operations which constitute the jobs, one considers linear penalty functions outside the interval [d_i,D_i]. One solves the problem of finding the schedulings with a minimal total penalty and having the origin in a given interval [t₁,t₂]. It is proved that for an arbitrary set Z of jobs, the penalty function F_Z(t), where t is the origin of the scheduling, has a unique minimum for t∈(?∞,+∞). We present an algorithm for the construction of the optimal scheduling requiring \(C \cdot K\left( {\mathop {\max }\limits_i \left\{ {D_i } \right\} - \mathop {\min }\limits_i \left\{ {d_i } \right\} + \sum\limits_1^\kappa {V_i } } \right)\) operations on an electronic computer.     

Algorithm of shifts for optimal structural schedules

The following problem is solved. Multiset J is given. Find the permutation of its elements that minimizes the value of functional ƒ defined on all permutations of multiset J. Restrictions on functional ƒ are formulated under which the solution is obtained with the aid of the algorithm of shifts with complexity O(¦B(J)¦²¦J¦) of computations of the values of functional ƒ. It is proved that functional satisfies the formulated conditions, and the algorithm of shifts is applicable to it.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 73–92, 1983.     

Synthesis of Allyl 2-Dialkylamino-4-pentenoates and Their Analogs via Stevens Rearrangement

Stevens rearrangement of ammonium salts containing an allyloxycarbonylmethyl group in benzene in the presence of sodium phenoxide yields allyl 2-dialkylamino-4-pentenoates. The rearrangement in the presence of sodium methoxide is accompanied by transesterification to afford methyl 2-dialkylamino-4-pentenoates.     

Ordering the structural set of jobs,minimizing the total penalty

The problem of setting up a schedule minimizing the total penalty is solved. A job set is specified. There are no precedence conditions. Each job consists of elementary operations. Job interruptions are allowed. Interruptions of elementary operations are not allowed. The penalty for an operation of a job to be executed at instantt is. A schedule is evaluated by a penalty that is the sum of the penalties of all the elementary operations of all jobs in set. It is assumed that set is structural. The problem is to find the schedule with a start in a prescribed interval [ T₁,T₂] with the least penalty. Compatible structural schedules are introduced into consideration. The class of compatible structural schedules contains the solution of the problem. An algorithm solving the problem is proposed having complexity, in the worst case, whereK is the number of jobs in the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 229–264, 1979.