THE NETWORK PROGRAMMING METHOD APPLICATION IN THE SCHEDULING TASKS

The article considers the application of the network programming method to the solution of the discrete problem of minimizing the cost of the project for a given duration of its implementation. The essence of the method is that the target function and the restriction in the scheduling problem can be represented as a superposition of simpler functions. This representation is convenient to depict in the form of a network, at the lower level of which there are vertices corresponding to variables (network inputs), intermediate vertices correspond to the functions included in the superposition, and the final vertex (output) corresponds to the original function.

Calendar planning tasks are very common in practice and at the same time belong to the class of NP-difficult. This makes the development of algorithms for their solution actual. The paper describes two basic algorithms for solving the problem for the cases of independent and sequential works. More complex cases (tree-type network and an aggregated network) can be represented as a combination of these cases and solved based on sequential application of basic algorithms. As an example of a production network is given a network of the type "Assembly with a components". For it the method which consists in definition of a set of works which fixing of duration leads to one of the cases considered above (tree-type network or aggregated network) is offered. Next all possible options for fixing the duration of the work of the selected set and the solution of the problem for each option are considered. The best of all the options is chosen.

The algorithms proposed in paper may be useful in the of the project management, particularly in solving scheduling tasks.

1. Burkov V.N., Landa B.D., Loveckij S.E. i dr. Setevye modeli i zadachi upravleniya. Moscow, Sovetskoe radio Publ.,1967, 144 p.

2. Barkalov S.A., Burkova I.V., Voropaev V.I. i dr. Matematicheskie osnovy upravleniya proektami; ed. by Burkov V.N. Moscow, Vysshaya shkola Publ., 2005, 423 p.

3. Andres C., Hatami S. Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times. International Journal of Production Research, 2011, no. 44, pp. 4713-4735.

4. Allaoui H., Artiba A., Johnson’s algorithm: a kay to solve optimally or approximately flow shop scheduling problems with unavailability periods. International Journal of Production Economics, 2009, no. 121,pp. 81-87.

5. Chenkong V., Haimes Y.Y. The tree stage assembly permutation flowshop scheduling problem. Proceedings of the 5th International Conference on Industrial Engineering and Industrial Management, Cartagena, September 7-9, 2011.

6. Demeulemeester E.L., Herroelen W. Project scheduling: a research handbook. Kluwer Academic Publisher, 1976, p. 710.

7. Garey M.R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1976, no. 1 (2),pp. 117-129.

8. Sun Y., Zhang C.Y., Gao L., Wang, X.J. Multy-objactive optimization algorithms for flow shop scheduling problem: a review and prospects. International Journal of Advanced Manufacturing Technology, 2011, no. 55, pp. 723-739.

9. Lisicin L.A., Halin YU.A., Lisicin A.L. Sistemy podderzhki prinyatiya upravlencheskih reshenij v usloviyah nepolnoj informacii. Izvestija Jugo-Zapadnogo gosudarstvennogo universiteta, 2012, no. 4-2 (43), pp. 95-99.

10. Halin Yu.A., Sizov A.S., Ignatenko A.N. Nechyotko-mnozhestvennaya model'mnogokriterial'noj ocenki konkurentosposobnosti predpriyatiya. Izvestiya Jugo-Zapadnogo gosudarstvennogo universiteta, 2011, no. 5-1 (38), pp. 53-57.

11. Kuz'bozhev Eh.N., Mozhejko A.G., Halin Yu.A. Upravlenie innovacionnymi processami na osnove intellektual'nyh informacionnyh tekhnologij. Izvestija JugoZapadnogo gosudarstvennogo universiteta, 2011, no. 6-2 (39), pp. 83-86.

12. Burkova I.V. Metod setevogo programmirovaniya v zadachah nelinejnoj optimizacii. Avtomatika i telemekhanika, 2009, no. 10, pp. 15-21