International Journal of Foundations of Computer Science

In this paper we present a novel approach to find an optimum loop schedule under consideration of limited resources. The initiation interval λ is assumed to be a rational number. Our approach is formulated as a single optimization problem that can be solved using integer linear programming. The objective is to minimize the initiation interval, while both numerator and denominator of λ can be incorporated as variables of the optimization problem. the resources (functional units) may have a pipeline architecture; the approach also supports heterogeneous functional units.

In a real-time distribute transactional system, customers generate transactions, which should be scheduled to be executed on different servers. The transactions have temporal constraints and must be executed before their deadlines. To schedule these transactions the circulating mutisequencer, the multi-tokens and the consensus algorithms have been considered to obtain a global view of the system. In this paper, mathematical models are developed to obtain the average stay time of a transaction within the system. These models introduce a bulk arrival M/G/1 station with K classes of customers where bulks are considered according to FIFO discipline and customers (actions) are scheduled according to EDF within a group and with the HOL discipline for the algorithm operating. The response time distribution is also computed. This allowed us to determine the minimum relative deadline, to affect to a generated transaction, to guarantee a given probability p that the transaction does not miss its deadline. The system is then called p-feasible. This study enables to determine the number of tokens to use for the multi-tokens algorithm, for a given number of servers and shows that the circulating mutisequencer algorithm presents the best results.

A common way of scheduling jobs dynamically in a manufacturing system is by means of dispatching rules. The drawback of this method is that the performance of these rules depends on the state the system is in at each moment, and no one rule exists that overrules the rest in all the possible states that the system may be in. It would therefore be interesting to use the most appropriate rule at each moment. To achieve this goal, a scheduling approach which uses machine learning is presented in this paper. The methodology proposed in this paper may be divided into five basic steps. Firstly, definition of the appropriate control attributes for identifying the relevant manufacturing patterns. In second place, creation of a set of training examples using different values of the control attributes. Subsequently, acquiring of heuristic rules by means of a machine learning program. Then, using of the previously calculated heuristic rules to select the most appropriate dispatching rules, and finally testing of the performance of the approach. The approach that we propose is applied to a flow shop system and to a classic job shop configuration. The results demonstrate that this approach produces an improvement in the performance of the system when compared to the traditional method of using dispatching rules.

In this paper, we consider the problem of scheduling independent jobs in partitionable mesh connected systems. The problem is NP-hard, since it includes the multiprocessor scheduling problem as a special case when all jobs request for one processor. We analyze a simple approximation algorithm called A_m. In particular, we show that if the sizes of submeshes requested by jobs are independent and identically distributed (i.i.d.) random variables uniformly distributed in the range [1..M₁]×[1..M₂], where M₁×M₂ is the size of a partitionable mesh connected system, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio E(A_m(L))/E(OPT(L)) is asymptotically bounded from above by 1.6637594…. The average-case performance ratio improves significantly when jobs request for square submeshes or small submeshes.

This paper presents characteristics of optimal routing that assigns each arriving packet to one of two heterogeneous parallel servers, each with its own queue. The characteristics are derived from numerical solutions to an optimization problem, which is to find optimal routing that minimizes the average packet delay under the condition that all of the packets' arrival times as well as all of the packets' sizes are completely known in advance. There are four characteristics: (1) Under light or moderate traffic, the average packet delay of optimal routing is almost the same as that of join the shortest delay (JSD) policy. (2) Under heavier traffic, optimal routing comes to more often use fix queue based on size (FS) policy. (3) Under heavy traffic, optimal routing assigns small packets to the slower server. (4) As the ratio of the slower server's service rate to the faster server's service rate decreases, optimal routing comes to more often use FS policy under light or moderated traffic. These characteristics are verified by the fact that a mimic optimal routing designed based on the four characteristics attains almost the same performance as optimal routing.

In this paper we survey algorithms and complexity results for the multimessage multicasting problem and its variations under a unified notation. The main results apply to the multimessage multicasting problem for complete networks and pr-networks (multistage interconnection networks that can realize all permutations in one communication phase and replicate data on each switch). We also discuss algorithms that allow message forwarding and distributed algorithms where each processor only knows local information. Different applications where this problem naturally arises are explored.

We investigate the Maximum Traveling Salesman Problem on banded distance matrices. A (p, q)-banded matrix has all its non-zero elements contained within a band consisting of p diagonals above the principal diagonal and q diagonals below it. We investigate the properties of the problem and prove that the number K of different permutations which can be optimal solutions for different instances of the problem, is exponential in n where n is the problem size (= the number of cities). For the Maximum-TSP on the (2, 0)-banded matrices, K=O(λⁿ) where 1.7548 <λ< 1.7549, whereas on the (1, 1)-banded matrices K=O(λⁿ) where 1.6180 <λ< 1.6181. Using recursive equations, we derive a linear-time algorithm that exactly solves the Maximum-TSP on the (2, 0)-banded distance matrices.

We introduce some new models of infinite-state transition systems. The basic model, called a (reversal-bounded) counter machine (CM), is a nondeterministic finite automaton augmented with finitely many reversal-bounded counters (i.e. each counter can be incremented or decremented by 1 and tested for zero, but the number of times it can change mode from nondecreasing to nonincreasing and vice-versa is bounded by a constant, independent of the computation). We extend a CM by augmenting it with some familiar data structures: (i) A pushdown counter machine (PCM) is a CM augmented with an unrestricted pushdown stack. (ii) A tape counter machine (TCM) is a CM augmented with a two-way read/write worktape that is restricted in that the number of times the head crosses the boundary between any two adjacent cells of the worktape is bounded by a constant, independent of the computation (thus, the worktape is finite-crossing). There is no bound on how long the head can remain on a cell. (iii) A queue counter machine (QCM) is a CM augmented with a queue that is restricted in that the number of alternations between non-deletion phase and non-insertion phase on the queue is bounded by a constant. A non-deletion (non-insertion) phase is a period consisting of insertions (deletions) and no-changes, i.e., the queue is idle. We show that emptiness, (binary, forward, and backward) reachability, nonsafety, and invariance for these machines are solvable. We also look at extensions of the models that allow the use of linear-relation tests among the counters and parameterized constants as "primitive" predicates. We investigate the conditions under which these problems are still solvable.

Molecules with hairpin structure(s) form a natural extension of linear non-branched molecules, and they have been already used in experimental work in DNA computing. In this paper we introduce and investigate classes of string languages (hence languages modeling the sets of linear DNA molecules), consisting of strings which can (fold on itself and) form hairpins. We classify the complexity of these classes using language-theoretic techniques. We also discuss a further use of hairpin molecules in DNA computing.