Article Preview
TopBackground
Experimental studies of algorithms KN, NZ, KP, first of all, were taken to determine the following their characteristics:
In other works, the task was to confirm or reject the properties of algorithms, obtained previously in as analytical way.
The proposed algorithm is using to increase the speed of the algorithm KN, it can reach it, parallelization of computations and implementing a parallel version of computation multiprocessor. The elements of parallel computation are explicitly contained in third steps of this algorithm.
TopWe formulate the general problem the traditional supply. Given finite sets of objects I{i│1≤ I ≤ n}and processing of their machines Q{q │1 ≤ q ≤ m} object processing iϵ I prescription of the operation sequence Ii – {iqj │ 1≤ j ≤ ji}, specific for this item. Operation iqj ϵ Ii; executed by the machine qϵ Q during tiqj > 0, without interrupts and can begin after the completion of the immediately preceding operations iqj-1 ϵIi. Any machine qϵQ, only one operation can be performed at time. In view of this, all the sets of operation
break up into
classes
– first operation, performed by each machine. The task of scheduling is for each machine
specifies the order of the operation from the class
and thus determine such months their beginning, which would provide processing a lot of all items I, in the minimum time. In view of the fact, that any operation
uniquely identify the item number
, sequence of operation, defined on sets
,
, represent the permutations of the number of objects on the machines. In this way, the meaning of the problem is to determine the set of permutations m machine number, minimizing the total processing time. To find out the problem properties as an extreme object, and a convenient representation of solving algorithms we describe in the language of graph. To this end, each linear order sequence of operations
we will represent a sequential graph
with many vertices
, arc
and functions
so, every vertexes
this graph corresponds to one and only one operation
subject
, each pair of vertices
arc connected
which come from the top
and goes to the top
; function
is defined as
. Then a finite acyclic graph
with many vertices
, arcs
and functions
it will represent the initial data of the task. Set of vertices
top up
,
and put
. We connect the top
with outgoing arcs
from the top
, these with
zero stage of approach. Vertices of
zero stage of the outcome to
we connect it to the top
of arcs
, directed to this vertex. As a result, we will receive a technological network.