Search

Search Results

• MODIFIED GENETIC PROJECT PLANNING ALGORITHM IMPLEMENTED WITH THE USE OF CLOUD COMPUTING

  А. А. Mogilev, V.M. Kureichik

  2020-07-20

  Abstract ▼

  The paper proposes a structure of a modified genetic algorithm for solving resource constrained
  project scheduling problem implemented with the use of cloud computing, a computational
  experiment was conducted, during which the results of the proposed algorithm were compared
  with the best known, at the moment, results. Based on the results of the experiment, it was concluded
  that the proposed algorithm can be used to plan the work of real projects, since it is possible
  to draw up schedules for projects with the number of works n = 90 for an acceptable period of
  time. When planning projects with the number of jobs n = 30, n = 60, n = 90, 120, the execution
  time of the proposed algorithm was less than the execution time of the standard genetic algorithm
  by 2.8, 4, 5.5 and 6.8 times, respectively. Due to the fact that the task of constructing a project
  schedule taking into account limited resources is NP-difficult, the problem of creating new and
  modifying existing methods for solving it remains relevant. For planning projects with a large
  number of works, it is advisable to use cloud computing, since planning such projects can require
  a lot of time and computing resources. In this regard, the algorithm proposed in this paper differs
  from the existing ones by using cloud computing to distribute the load between workstations on
  which this algorithm is simultaneously running. The use of modified operators in the genetic algorithm,
  as well as the use of cloud infrastructure as a service for implementing a distributed genetic
  algorithm, determines the scientific novelty of the study.

• BIOINSPIRED SIMULATION METHOD FOR SCHEDULING OF PARALLEL FLOWS APPLICATIONS IN GRID-SYSTEMS

  D.Y. Kravchenko, Y.A. Kravchenko, V. V. Kureichik, A.E. Saak

  2020-07-20

  Abstract ▼

  The article is devoted to solving the problem of parallel requests scheduling flows in spatially
  distributed computing systems. The relevance of the task is justified by a significant increase in
  the demand for the distributed computing paradigm in the conditions of information overflow and
  uncertainty. The article discusses the problems of scheduling user requests that require severalprocessors at the same time, which goes beyond the classical theory of schedules. The aspects of
  the efficiency of using heuristic algorithms for scheduling planar resources are analyzed. The
  reasons for their insufficiency are determined both in terms of effectiveness and empirical approaches.
  The paper proposes to solve the problem of scheduling parallel applications based on
  the integrated application of intelligent agents coalition and an event simulation model. It is proposed
  to classify incoming applications on the basis of using a modified bio-inspired optimization
  method for cuckoo search. The joint use of a coalition of intelligent agents and a bio-inspired
  method will allow for unprecedented parallelism of calculations, and the subsequent determination
  of the processing classified applications ways on the basis of a simulation model will allow us
  to form sets of alternative solutions to speed up problem solving and optimize the distribution of
  available computing resources depending on the sets of incoming applications. To evaluate the
  effectiveness of the proposed approach, a software product was developed and experiments were
  conducted with a different number of incoming applications. Each incoming application has a
  certain set of attributes, which is a vector of the application characteristics. The degree of the
  application similarity feature vector and the vertex reference feature vector in the distributing
  simulation model is a classification criterion for the application. To improve the quality of the dispatch
  process, new procedures for duplicating unclassified applications have been introduced, which
  allow intensifying the search for matches in feature vectors. It also provides backup dispatching trajectories
  necessary for processing precedents for the appearance of applications with absolute priority
  at the inputs. The quantitative estimates obtained demonstrate time savings in solving problems of
  relatively large dimension (from 500,000 vertices) of at least 10%. The time complexity in the considered
  examples was O (n 2). The described studies have a high level of theoretical and practical significance
  and are directly related to the solution of classical problems of artificial intelligence
  aimed at finding hidden dependencies and patterns on a large set of big data.

• METHOD AND ALGORITHM FOR OPERATION PLANNING BASED ON FUZZY FINITE AUTOMATA MODEL

  М. V. Knyazeva, А. V. Bozhenyuk, I.N. Rozenberg

  2022-05-26

  Abstract ▼

  In this paper the planning and scheduling problem as an important optimization problem in
  many transportation and robotic applications is discussed. To solve planning problems, the main
  approaches are based on optimization methods, sampling-based methods, and usually such kinds
  of problems are NP-hard and high dimensional. In this work, the method for planning and scheduling
  based on the fuzzy finite state machine model is developed. Fuzzy graph presentation of the
  scheduling problem and operation planning is given. The paper presents two approaches to the
  formulation of the planning problem with limited resources and temporal variables: state-oriented
  (with transitions between states), temporal ordering-oriented (on a time scale). Temporal modeling
  for planning problems implies a qualitative approach to managing the distribution of operations
  or topological ordering, as well as a quantitative approach to handling imprecise durationsrelationships between operations in multiple parameters. The concepts of fuzzy intervals and fuzzy
  relations are introduced for planning operations on a graph. A planning algorithm based on the
  theory of automata and temporal modeling under uncertainty has been developed. Using this formalism,
  a path planning problem is solved by successively altering a state using various operations
  until a solution is found. The idea of temporal-ordered partial schedule associated with the
  planning state of the system is discussed. A model of a finite automaton for a planning system under
  conditions of uncertainty is proposed. A method and algorithm for scheduling operations
  based on a non-deterministic finite automaton and an enumeration scheme have been developed.
  The non-deterministic computation for a scheduling problem is a decision tree whose root corresponds
  to the beginning of the scheduling process, and each branch point in the tree corresponds
  to a computation point at which the machine has multiple choices. And the finite state machine
  model (automata) for the planning system under uncertainty is suggested.