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.