Approximate Algorithm for Solving the General Problem of Scheduling Theory With High Accuracy

Background

Experimental studies of algorithms KN, NZ, KP, first of all, were taken to determine the following their characteristics:

• 1.

  Average error and average counting time as task size function N at n/m – const;

• 2.

  Average errors and average counting time as a function of the relationship n/m at N= const.

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.

Formalization And Properties Of The Problem

We 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 I_i – {iq_j │ 1≤ j ≤ j_i}, specific for this item. Operation iq_j ϵ I_i; executed by the machine qϵ Q during t_iqj > 0, without interrupts and can begin after the completion of the immediately preceding operations iq_j-1 ϵI_i. 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.