Analysis of concurrent systems is plagued by the state explosion problem. The constrained expression analysis technique uses necessary conditions, in the form of linear inequalities, to verify certain properties of co...
详细信息
ISBN:
(纸本)9780818643606
Analysis of concurrent systems is plagued by the state explosion problem. The constrained expression analysis technique uses necessary conditions, in the form of linear inequalities, to verify certain properties of concurrent systems without enumerating the system's states. While effective against the state explosion due to interleaving, the technique fails to yield a tractable analysis if the size of the components themselves grow exponentially due to the use of variables in the components. As a partial solution to this problem, we present a technique for representing certain program variables as integerprogramming variables. We also present a synergistic technique for efficiently representing many identical components in the context of an integerprogramming analysis.< >
This thesis develops a prototypic integerprogramming model to aid in solving the Naval Postgraduate School academic course scheduling problem. The simplified model schedules faculty members to teach their assigned co...
详细信息
This thesis develops a prototypic integerprogramming model to aid in solving the Naval Postgraduate School academic course scheduling problem. The simplified model schedules faculty members to teach their assigned courses in specific rooms at specific times and schedules groups of students to the courses they have requested. The model assures, as best possible, that room capacity is not exceeded, students and faculty have time for lunch and faculty requesting "back-to-back" courses are accommodated. To make the problem managable, we concentrate on just one building, Glasgow Hall, and three departments, Operations Research, Mathematics and National Security Affairs. Even doing this, the model generated in GAMS (Generalized Algebraic Modeling System) has about 287,778 variables and 148,161 constraints and is too large to solve. Consequently, a simplified model, restricted to the Operations Research Department, is solved. This problem encompasses 19 faculty members, 26 courses, 83 sections and 11 classrooms. The model has less than 32,000 variables and 17,000 constraints and is solved using GAMS and the X-System on an Amdahl 8995-700A in 3488.4 seconds
A heuristic procedure for the solution of pure integer linear programming problems is developed, and computational results are presented. The technique alternates sequences of local univariate exploratory moves with e...
详细信息
A heuristic procedure for the solution of pure integer linear programming problems is developed, and computational results are presented. The technique alternates sequences of local univariate exploratory moves with extrapolations (or pattern moves). The basis for the method is the intuitive presumption that a strategy that was successful in the past will be successful in the future. One example problem is presented in detail, and the results of numerous other test cases are also tabulated.< >
A neural net structure has been developed which is capable of solving deterministic job-shop scheduling problems, part of the large class of np-complete problems. The problem was translated in an integerlinear progra...
详细信息
A neural net structure has been developed which is capable of solving deterministic job-shop scheduling problems, part of the large class of np-complete problems. The problem was translated in an integer linear programming format which facilitated translation in an adequate neural structure. Use of the presented structure eliminated the need for integer adjustments. The search space was reduced by the use of precalculation, allowing the rapid calculation of feasible solutions. The neural net structure was reliable in simulated operation and its performance was superior to structures which have been presented previously.
The authors propose a synthetic technique to derive a correct protocol specification from a given service specification modeled as a nondeterministic extended finite state machine (EFSM). Each EFSM has a finite state ...
详细信息
The authors propose a synthetic technique to derive a correct protocol specification from a given service specification modeled as a nondeterministic extended finite state machine (EFSM). Each EFSM has a finite state control and a finite number of registers. In the model, the next state and the next values of the registers are determined depending on not only the current state and input but also the current values of the registers. The registers correspond to the system resources and they are allocated to some of the protocol entities in a distributed system. The derived protocol entities' specifications satisfy the resource allocation specified by the designer. A procedure solving 0-1 integer linear programming problems is used to reduce the number of the messages exchanged among the protocol entities.< >
The problem of finding approximate solutions for a subclass of 0-1 integer linear programming denoted by I L P(k,p) is considered. The problem involves finding X in
The problem of finding approximate solutions for a subclass of 0-1 integer linear programming denoted by I L P(k,p) is considered. The problem involves finding X in
Hopfield network, which was firstly proposed in 1982, can deal with only quadratic programming. For higher-order programming, a higher-order network architecture is necessary. Although generalized higher-order Hopfiel...
详细信息
ISBN:
(纸本)0780314212
Hopfield network, which was firstly proposed in 1982, can deal with only quadratic programming. For higher-order programming, a higher-order network architecture is necessary. Although generalized higher-order Hopfield network is a straight forward solution, the network convergence property has to be restudied before it can be put into application. Inheriting from Hopfield network, the existence of non-zero self-reinforcing terms is expected to give rise to network oscillation. A reshaping strategy, which is speculated from similar strategy for Hopfield network, is derived to guarantee generalized higher-order Hopfield network's convergence. Numerical example is given to illustrate its validity.
A model in integer linear programming (ILP) for the scheduling problem in the high-level synthesis of digital systems at register transfer level is developed using a new approach based on penalty weights. This approac...
详细信息
A model in integer linear programming (ILP) for the scheduling problem in the high-level synthesis of digital systems at register transfer level is developed using a new approach based on penalty weights. This approach avoids the inflexibility of the ILP formulations developed in related works where the functional unit performing each type of operation is fixed before scheduling. The Tabu search method was adapted for this purpose. The mathematical formulation developed takes into account almost all the area parameters and allows an unrestricted search in a large space delimited only by the components available in the library used.< >
Presents a fast recursive technique for estimating a lower-bound performance of data path schedules. The method relies on the determination of an ASAPUC (as soon as possible under constraint) time-step value for the r...
详细信息
Presents a fast recursive technique for estimating a lower-bound performance of data path schedules. The method relies on the determination of an ASAPUC (as soon as possible under constraint) time-step value for the root of the DFG (data flow graph) that is based on the ASAPUC values of its predecessor nodes, etc., until the leaf nodes are reached where this value becomes the regular ASAP value. The method computes a tighter lower-bound than the greedy technique and is only two times slower on the same benchmarks. Synthesis methods that depend on the exploration of the solution space directed by a lower-bound estimation, such a local microcode generation and behavioral synthesis, can benefit from our method. This is because bad solutions can be pruned earlier. We illustrate this dramatic effect on the reduction of the search space during the synthesis of an optimal microcode sequence for the elliptic wave filter benchmark and a fixed data path (containing a multiport RAM and a ROM).< >
This paper presents linearprogramming neural networks for job-shop scheduling. The starting times of tasks and constraints are formulated as the linearprogramming problem. A modified Hopfield neural network is propo...
详细信息
ISBN:
(纸本)0780314212
This paper presents linearprogramming neural networks for job-shop scheduling. The starting times of tasks and constraints are formulated as the linearprogramming problem. A modified Hopfield neural network is proposed for solving job-shop scheduling.
暂无评论