Алгоритм пошуку часу завершення складного проекту
Ключові слова:
складна система, мережевий графік, критичний шлях, алгоритм мінімізації часуАнотація
Постановка проблеми. Розглядається задача мінімізації часу побудови складної системи, яка складається з множини підсистем. Такі задачі виникають на виробництві, в будівництві, управлінні, інформатиці та інших прикладних галузях. Побудова системи передбачає послідовну побудову її підсистем, що складаються з безлічі елементів. Ці елементи в задані моменти часу надходять на вхід системи. Відомий технологічний маршрут кожного елемента і кожної підсистеми, що включає задану кількість елементів, а також час обробки кожного елемента і підсистеми. Побудова складної системи подається у вигляді мережевого графіка, який визначає послідовність її побудови. Цей мережевий графік у даному випадку являє собою дерево дуг, основою якого є час завершення побудови складної системи. При заданих моментах надходження елементів системи та їх складання в підсистеми, мінімальний час побудови системи дорівнює критичному шляху даного мережевого графіка. Для його знаходження необхідно визначити час завершення кожної підсистеми. Цей час залежить від часу готовності всіх елементів підсистеми для її складання. Час критичного шляху може бути зменшений за допомогою усунення очікувань на ділянках складання підсистем. Мінімізація очікувань дозволяє отримати критичний шлях мінімальної довжини. Існують такі моменти часу надходження елементів складної системи на вході мережевого графіка, для яких сумарне очікування елементів та їх підсистем на кожному пункті складання буде мінімальним. Визначення таких моментів надходження на вхід системи необхідно починати з кінця мережевого графіка. Зменшення часу завершення складання системи тягне за собою зменшення часу надходження складових її елементів. Це зменшення тягне за собою зменшення часу надходження елементів підсистеми на попередній пункт складання. Таке проходження мережевого графіка від кінця до початку зі зміною часів надходження елементів підсистем дозволяє мінімізувати очікування початку складання підсистем на кожній ділянці. Це досягається за допомогою визначення оптимальних часів надходження елементів на вході мережевого графіка. Після виконаних змін критичний шлях необхідно перерахувати і тільки в тому випадку, якщо його значення не буде змінено, буде знайдене мінімальний час побудови складної системи. Для реалізації даного алгоритму обчислення мінімального часу побудови складної системи розроблено комп'ютерну програму та проведено числові експерименти, які підтверджують ефективність даного алгоритму.
Посилання
Korbut A.A. and Finkelshteyn Yu.Yu. Diskretnoe programmirovanie [Discrete programming]. Moskow: Nauka, 1969, 368 p. (in Russian).
Kosolap A.I. Metody global'noy optimizatsii [Methods of global optimization]. Dnepropetrovsk: Nauka i obrazovanie, 2013, 316 p. (in Russian).
Kosolap A.I. Global'naya optimizatsiya. Metod tochnoy kvadratichnoy regulyarizatsii [Globaloptimisation. A method of exact quadraticregularization]. Dnepropetrovsk: PGASA, 2015, 164 p. (in Russian).
Kuzin B.I. Optimal'noe kalendarnoe planirovanie na potochnykh liniyakh i predmetnykh uchastkakh [Optimal schedul- ing on production lines and subject areas]. Leningrad: LGU, 1969, 167 p. (in Russian).
Koffman E.G. ed. Teoriya raspisaniy i vychislitel'nye mashiny [Scheduling theory and computers]. Moskow: Nauka, 1984, 336 p. (in Russian).
Baker K.R. and Trietsch D. Principles ofsequencing andscheduling. Hoboken, New Jersey: A John Wiley& Sons, 2009, 510 p.
Brucker P. Scheduling algorithms. 5th еd. Berlin, Heidelberg, New York: Springer, 2007, 377 p.
Horst R. and Tuy H. Global Optimization. Deterministic Approaches. 3rd ed. Berlin, Heidelberg, New York: Springer, 1996, 727 p.
Johnson S.M. Optimal two and three stage production schedules with setup times included. Naval research logistics quarterly, 1954, vol. 1, pp. 61-68.
Pinedo M.L. Scheduling : theory, algorithms, and systems; fourth edition. 4th ed. Berlin, Heidelberg, New York: Springer, 2012, 696 p.
Scholz D. Deterministic globaloptimization. Geometric branch-and-bound methods and their applications. Berlin, Heidelberg, New York: Springer, 2010, 153 p.
Uher T. and Adam S. Zantis. Programmingand schedulingtechniques. 2nd ed. Kensington: NewSouth Publishing, 2011, 285 p.
Zhou J., Love P.E.D., Wang X., Teo K.L., Irani Z. A review of methods and algorithms for optimizing construction scheduling. Journal of the Operational Research Society. 2013, vol. 64, pp. 1091-1105.
##submission.downloads##
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство роботи та передають журналу право першої публікації на умовах ліцензії Creative Commons Attribution License, яка дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право самостійно укладати додаткові угоди щодо неексклюзивного розповсюдження наукової роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу передбачає можливість розміщення авторами рукопису в мережі Інтернет (наприклад, у електронних сховищах інформації або на веб-сайтах), оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на динаміці цитування опублікованої роботи (див. The Effect of Open Access).
Договір про передачу авторського права
