Planning algorithm for development of an intelligent scheduling system.

Prostean, Gabriela ; Taroata, Anghel ; Taucean, Ilie 等

1. INTRODUCTION

The efficient and effective manufacturing operations planning require the assistance of methodologies and information systems meant for decision support. The PIS is designed first to decide for the best planner that determines what sequence of different operations should pass through the production facilities (Beerel, 1993).

To build a planning intelligent system today, a knowledge engineer performs different types of activities such as: knowledge-processing that refers to extracting knowledge, organizing knowledge, assembling knowledge and refining knowledge; planning algorithms, expertises and reports (Prostean, 2007). These are the primary tasks in the process of building an intelligent system in operation planning. Each primary task involves some specific knowledge engineering activities (Prostean & Prostean, 2002).

At the basis of building the model of the knowledge base there have been the pieces of knowledge furnished by the following 3 algorithms also called "computation procedures applied to knowledge", representing the assembly of the representation formalism associated to the inference strategy of the Planning Intelligent System (Cantor, 1998):

1) The Computation of the Critical Path,

2) The Project Synchronization,

3) The algorithm of the diagnosis analysis of the evolution of the project activities.

This paper presents the essential aspects referring to the implementation of the computation algorithm of the Critical Path.

The Critical Path represents the sequence of the activities of maximum time length between the initial event and the final event of the project.

This algorithm has been inspired by Floyd's algorithm (Crefu, 1992) for the computation of the minimum path in a graph, being reconceived for the computation of the maximum path in a graph.

The algorithm uses a "work" adjacency matrix. On account of the fact that the lengths of the activities are greater or equal to "0", there has been conventionally established that:

* In the initial state (before a project specific data are activated) all the elements of "Work" matrix are equal to "-1";

* If there is a path between knot i and knot j, then work[i][j] is equal to the average optimistic/probable/pessimistic value of the given activity.

2. THE SEARCHING ALGORITHM IN THE SPACE OF THE STATES FOR THE IDENTIFICATION OF THE CRITICAL PATH

The algorithm can be defined as follows: there shall be executed maximum iterations on "work" matrix, and after k iteration, each location from "work" matrix will contain the maximum length of any path to knot i to knot j, a path that shall not pass through any knot with the index greater than k.

The knots i and j can be any two knots of the graph which mark the beginning and the end of the path, and k marks any intermediate smaller knot. For the computation of work matrix, there shall be used the following relation (1), (figure 1).

[Work.sub.k] = maxim([work.sub.k-1][i][j], [work.sub.k-1][i][k] + [work.sub.k-1][k][j])(1) where k represents the moment for which there is computed work matrix. Work matrix is unique. The interpretation of relation (1) for the computation of the path from knot i to knot j ([work.sub.k][i][j]) shall be made as follows: There shall be compared [work.sub.k][i][j]--the value of the path from i to j without passing through knot k, with the sum [work.sub.k-1][i][k] + [work.sub.k-1][k][j]--the value of the path from i to k plus the value of the path from k to j.

If the path is longer, there shall be attributed to [work.sub.k][i][j] the value [work.sub.k-1][i][k] + [work.sub.k-1][k][j], on the contrary, the value [work.sub.k][i][j] = [work.sub.k-1][i][j] remains unchanged.

In figure 2 there is presented the activities network for a project.

The system follows 6 steps within the strategy of identifying the Critical Path with the help of work matrix, as follows:

1. The system verifies the maximum value of the activities path. work[i][k] + work[k][j] > work[i][j]. For: i = 0, k = 0, j = 0 [??] work[0][0] + work[0][0] > work[0][0]. For this situation, the system has not identified any links between the events.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2. For the values i = 0, k = 0, j = 1, ... 5, there shall be incremented "j", and the same situation can be observed up to j = 5, following which there shall be incremented "k".

3. For the values i = 0, k = 1, j = 0, ... 3, there shall be incremented "j" , and the same situation will result up to j = 3, for which there will be identified paths between knots (a sequence of activities): 0 [right arrow] 1 [right arrow] 3. By applying condition (1), there results the following:

work[i][k] + work[k][j] > work[i][j] [??]

work[0][1] + work[1][3] > work[0][3] [??] 1 + 5 > -1 [??] 6 > -1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

Element work[0][3] = -1 of work[i][j] matrix will be replaced by work[0][3] = 6, and there results the following [work.sub.1][ij] matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4. For the values i = 0, k = 1, j = 1, ... 5, there shall be incremented "j" up to j = 5, these being situations for which there have not been found paths between knots, following which there shall be incremented k = 2 and j = 0, ... 3, a situation for which there will be identified the paths (a sequence of activities): 0 [right arrow] 2 [right arrow] 3. Condition (1) shall be verified in order to establish the possible passage to the following state, and thus there results that:

work[i][k] + work[k][j] > work[i][j] [??]

[work.sub.1][0][2] + [work.sub.1][2][3] > [w.sub.1][0][3] [??] 2 + 3 > 6

Element [work.sub.1][0][3] = 6 of [work.sub.1][i][j] matrix is greater than the sum [work.sub.1][0][2] + [work.sub.1][2][3] = 5, consequently, there shall be selected [work.sub.1][0][3] = 6, and thus there can be got on to the following state.

5. For the values i = 0, k = 2, j = 4, there shall be incremented j = 4, for which the following paths will be identified (a sequence of activities): 0 [right arrow] 2 [right arrow] 4. By applying condition (1), there results the following situation:

[work.sub.1][0][2] + [work.sub.1][2][3] = 5, [work.sub.1][i,j] matrix remaining unchanged.

work[i][k] + work[k][j] > work[i][j] [??]

[work.sub.1][0][2] + [work.sub.1][2][4] > [work.sub.1][0][4] = 2 + 3 > -1 [??] 5 > -1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

6. For i = 0, k = 2, j = 5, and for i = 0, k = 3, j = 0, ... 1, respectively, the situation of the evolution within the space of the states is as follows: there shall be incremented j = 5, a situation for which there have not been identified paths between knots, after which there shall be incremented k=3 and j = 0, ... 5, the last situation being the one for which the following sequence of activities will be identified: 0 [right arrow] 1 [right arrow] 3 [right arrow] 5. Condition (1) shall be verified in order to establish the possible passage to the next state.

work[i][k] + work[k][j] > w[i,j] [??]

[work.sub.2][0,3] + [work.sub.2][3,5] > [work.sub.2][0,5] [??]

6 + 7 > -1 [??] 13 > -1

The maximum value attributed to the critical path is 13, it being retrieved in [work.sub.3][0][5] matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. CONCLUSIONS AND FUTURE WORK

The highlighting, by means of the states space representation of the computation process of the Critical Path by using the procedure of "The Critical Path Computation", enables to easily establish the acquisition forms of the knowledge for the PIS. The use of these operation scheduling techniques can be accepted to be successfully applied in manufacturing, in building industry, and as well in software development projects.

The main contribution of the planning intelligent system is the capacity to drastically shorten the project duration in real time, having the updated reports for the project and each specific task. The algorithm has been developed for a suitable embedding into a PIS, that is an object oriented planning intelligent system, where the computation is distributed in time.

4. REFERENCES

Beerel A. (1993). Expert System in Business, real world applications, Ellis Horwood Limited, ISBN:0-13-296633-6.

Cantor M., R. (1998). Object-Oriented Project Management with UML, Published by John Wiley & Sons, Inc, USA, ISBN: 0-471-25303-0.

Cretu V. I.(1992), Data structures and advanced programming techniques, Timisoara, Centrul de multiplicare al UTT.

Prostean G., Prostean O. (2002). Intelligent project manager using a plannifying, supervising and diagnosing integrated process, International Conference of Artificial Intelligence, Las Vegas, Nevada, USA, June 24-27, CSREA Press

Prostean G. (2007). Considerations above Operations Scheduling Intelligent System, Proceedings of the 5th IEEE International Conference on Computational Cybernetics, Gammarth, Tunisia, Oct. 19-21, 2007, pag.173-178