Metoda skracania przekrojów ścieżek niedopuszczalnych sieci jako narzędzie optymalizacji

• Autorzy: Helena Gaspars-Wieloch

Warianty tytułu

A Method of Reducing the Cut of Inadmissible Paths as a Tool for Optimizing the Time-Cost of a Project

• Języki publikacji: PL

Abstrakty

W literaturze można znaleźć wiele różnych algorytmów optymalizacji czasowo-kosztowej projektu. W ramach wspomnianej optymalizacji najczęściej poszukuje się wektora czasów trwania czynności wchodzących w skład przedsięwzięcia, który minimalizuje czas całego projektu przy dostępnych środkach finansowych (tzw. Budget Problem) lub który minimalizuje koszt realizacji przy przyjętym czasie dyrektywnym (tzw. Deadline Problem). Niektóre algorytmy są dokładne, czyli pozwalają uzyskać optymalne rozwiązanie, lecz zazwyczaj działają wolno. Inne natomiast są heurystyczne, a więc niekoniecznie prowadzą do uzyskania najlepszego rozwiązania, lecz za to są mniej czasochłonne. Proponowany w pracy algorytm, zwany metodą skracania przekrojów ścieżek niedopuszczalnych sieci (metoda SPSN), pozwala bezpośrednio rozwiązywać problem minimalizacji kosztu przy danym czasie, a pośrednio - problem minimalizacji czasu przy dostępnych środkach finansowych. Można go stosować zarówno wtedy, gdy jednostkowe koszty skracania są stałe, jak i wówczas, gdy te koszty są zmienne. Algorytm SPSN został już wcześniej opisany w innym artykule. Natomiast w tej pracy przedstawiono bardziej sformalizowany, szczegółowy i kompleksowy opis procedury. Ponadto zwrócono uwagę na różne kwestie związane z jego komputerową implementacją i efektywnością. (abstrakt oryginalny)

EN

In the literature, many algorithms designed for the time-cost optimization of a project can be found. Usually, this optimization has as the goal of setting certain durations for particular activities pertaining to the project that minimize the project completion time within a specifi ed budget (the so called Budget Problem), or that minimize time-dependent project costs within a specifi ed project deadline (the so called Deadline Problem). Some algorithms are accurate, that is they allow the optimal solution to be obtained, but in general the computations are slow. Whereas other algorithms are heuristic, hence they do not necessarily lead to the best solution, but are less time consuming. Th e procedure proposed in the paper, called the method of reducing the cut of inadmissible paths (SPSN method), allows the problem to be solved directly by minimizing the cost within a given time; and indirectly - the problem of minimizing the time within the available fi nancial resources. It can be used when the unit shortening cost is either fi xed or variable. Th e algorithm for SPSN has already been described in another article; however, this paper presents a more formalized, detailed and comprehensive description of the procedure. Additionally, the author raises some essential issues connected with the computer implementation and eff ectiveness of the algorithm. (original abstract)

Słowa kluczowe

PL

Implementacja; Efektywność; Efektywność algorytmów

EN

Implementation; Effectiveness; Algorithmic effectiveness

• Czasopismo: Studia Oeconomica Posnaniensia
• Rocznik: 2013
• Tom: 1
• Numer: nr 10
• Strony: 26--45

Twórcy

autor

Helena Gaspars-Wieloch

• Uniwersytet Ekonomiczny w Poznaniu

Bibliografia

• Anholcer, M., Gaspars-Wieloch, H., 2011, Th e Efficiency Analysis of the Kaufmann and Desbazeille Algorithm for the Deadline Problem, Operations Research and Decisions, 2, Wydawnictwo Politechniki Wrocławskiej, Wrocław, s. 5-18.
• Anholcer, M., Gaspars-Wieloch, H., 2013, Accuracy of the Kaufmann and Desbazeille Algorithm for time-cost trade-off project problems, Statistical Review, vol. 3, s. 341-358.
• Bell, C.E., Han, J., 1991, A New Heuristic Solution Method in Resource-Constrained Project Scheduling, Naval Research Logistics, vol. 38, s. 315-333.
• Bladowski, S., 1970, Metody sieciowe w planowaniu i organizacji pracy, Państwowe Wydawnictwo Ekonomiczne, Warszawa.
• Gaspars, H., 2006, Analiza czasowo-kosztowa (CPM-COST). Algorytm a model optymalizacyjny, Badania Operacyjne i Decyzje, nr 1, Wydawnictwo Politechniki Wrocławskiej, Wrocław, s. 5-19.
• Gaspars, H., 2006, Propozycja nowego algorytmu w analizie czasowo-kosztowej przedsięwzięć, Badania Operacyjne i Decyzje, nr 3-4, Wydawnictwo Politechniki Wrocławskiej, Wrocław, s. 5-27.
• Gaspars-Wieloch, H., 2008a, Analiza sieciowa przedsięwzięć, w: Sikora, W. (red.), Badania operacyjne, Polskie Wydawnictwo Ekonomiczne, Warszawa.
• Gaspars-Wieloch, H., 2008b, Przegląd modeli optymalizacyjnych stosowanych w analizie czasowo- kosztowej przedsięwzięć, w: Sikora, W. (red.), Z prac Katedry Badań Operacyjnych, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań.
• Gaspars-Wieloch, H., 2008c, Przegląd wybranych metod skracania czasu realizacji przedsięwzięcia, w: Kopańska-Bródka, D. (red.), Metody i zastosowania badań operacyjnych, Prace Naukowe Akademii Ekonomicznej w Katowicach, Wydawnictwo Akademii Ekonomicznej w Katowicach, Katowice.
• Gaspars-Wieloch, H., 2009, Metody optymalizacji czasowo-kosztowej przedsięwzięcia [praca doktorska], Uniwersytet Ekonomiczny w Poznaniu, Poznań.
• Goyal, S.K., 1975, A Note on "A simple CPM time-cost tradeoff algorithm", Management Science, vol. 216, s. 718-722.
• Guzik, B., Sikora, W., 1993, Badania operacyjne i ekonometria, Akademia Ekonomiczna w Poznaniu, Poznań.
• Kaufmann, A., Desbazeille, G., Ventura, E., 1964, La methode du chemin critique, Dunod, Paris.
• Moder, J.J., Phillips, C.R., 1964, Project Management with CPM and PERT, Reinhold Publishing Corporation, New York.
• Moussourakis, J., Haksever, C., 2004, Flexible Model for Time/Cost Tradeoff Problem, Journal of Construction Engineering and Management, vol. 130/3, s. 307-314.
• Phillips, S.J., Dessouky, M.I., 1977, Solving the Time/Cost Tradeoff Problem using the Minimum Cut Concept, Management Science, vol. 244, s. 393-400.
• Siemens, N., 1971, A Simple CPM Time-cost Tradeoff Algorithm, Management Science, vol. 176, s. 354-363.
• Sikora, W., 2012, Metoda wydłużania czynności w analizie czasowo-kosztowej przedsięwzięć, w: Sikora, W. (red.), Z prac Katedry Badań Operacyjnych, Wydawnictwo Uniwersytetu Ekonomicznego w Poznaniu, Poznań, s. 109-130.
• Trocki, M., Grucza, B., Ogonek, K., 2003, Zarządzanie projektami, Polskie Wydawnictwo Ekonomiczne, Warszawa.