Preview

Труды Института системного программирования РАН

Расширенный поиск

Комплексный метод составления расписаний для сложных индустриальных программ с учетом пространственно-временных ограничений

https://doi.org/10.15514/ISPRAS-2014-26(1)-20

Полный текст:

Аннотация

Эффективное управление проектами предполагает использование развитых методов календарно-сетевого планирования и составления расписаний, которые позволяют определить сроки и последовательность выполнения работ для завершения проекта за минимальное время в рамках отведённых ресурсов. Традиционные методы поиска критических путей и ресурсного планирования полностью игнорируют пространственные факторы и не могут гарантировать достоверность подготавливаемых расписаний для сложных индустриальных программ. В данной статье рассматривается альтернативная постановка составления расписания, обобщающая традиционные задачи и принимающая во внимание пространственные факторы, связанные с перегруженностью рабочих пространств и нарушением естественной организации потока работ и ресурсов. Предлагается и исследуется метод решения поставленной задачи. Проведённые вычислительные эксперименты выявляют квазилинейную сложность метода, что делает возможным его применение к масштабным проектам. В то же время, метод достаточно эффективен с точки зрения генерации расписаний, близких к оптимальным, по крайней мере, на тестовых задачах.

Об авторах

В. А. Семенов
ИСП РАН
Россия


А. С. Аничкин
ИСП РАН
Россия


С. В. Морозов
ИСП РАН
Россия


О. А. Тарлапан
ИСП РАН
Россия


В. А. Золотов
ИСП РАН
Россия


Список литературы

1. Ahuja H. N.; Construction performance control by networks; John Wiley & Sons; New York; NY; 1976.

2. Bowers J. A.; Criticality in resource-constrained networks; Journal of the operational research society; 1995; No. 46(1); 80-91.

3. David E. W., Patterson J. H.; A comparison of heuristic and optimum solutions in resource-constrained project scheduling; Management science; 1975; No. 21(8); 944-955.

4. Hegazy T.; Optimization of resource allocation and leveling using genetic algorithms; Journal of construction engineering and management, ASCE; 1999; No. 125(3); 167-175.

5. Brooks G. N., White C. R.; An algorithm for finding optimal or near optimal solutions to the production scheduling problem; Journal of Industrial Engineering; 1966; Vol. 17.2; 173-186.

6. Gomory R. E.; An all integer programming algorithm; Industrial Scheduling, Prentice-Hall, New York, 1963.

7. Szwarg W.; Solutions of the akers-friedman scheduling problem; Operations Research; 1960; Vol. 8.6; 782-788.

8. Ashour S.; A Decomposition Approach for the Machine Scheduling Problem; University of Iowa; 1967.

9. Giffler B., Thompson G. L., Van Ness V.; Numerical experience with the linear and Monte-Carlo algorithms for solving production scheduling problems; Industrial Scheduling; 1963; Chapter 3.

10. Page E. S.; An approach to the scheduling of the N jobs on M machines; Journal of the Royal Statistical Society, B Series; 1961; Vol. 23(2); 484–492.

11. Kolisch R.; Efficient priority rules for the resource-constrained project scheduling problem; Journal of Operations Management; 1996; No. 14; 179-192.

12. Boctor F. F.; Some efficient multi-heuristic procedures for resource constrained project scheduling; European journal of operational research; 1990; No. 49, 3-13.

13. Siddesh K Pai, Preeti Verguese, Shweta Rai; Application of Line of Balance Scheduling Technique (LOBST) for a Real estate sector; International Journal of Science, Engineering and Technology Research (IJSETR); 2013; Vol. 2, Is. 1; 82-95.

14. Choo H. J., Tommelein I. D.; Space Scheduling Using Flow Analysis; Proceedings IGLC-7; 1999; 299-312.

15. Zouein P. P., Tommelein I. D.; Dynamic Layout Planning Using a Hybrid Incremental Solution Method; Journal of Construction Engineering and Management; 1999; No. 125(6); 400-408.

16. Thabet W. Y., Beliveau Y. J.; HVLS: Horizontal and Vertical Logic Scheduling for Multistory Projects; Journal of Construction Engineering and Management; 1994; No. 120(4); 875-892.

17. Yeoh K. W., David K. H. Chua; Mitigating Workspace Congestion: A Genetic Algorithm Approach; EPPM 2012 Conference; 2012; 107-118.

18. Thabet W. Y., Beliveau Y. J.; Modeling Work Space to Schedule Repetitive Floors in Multistory Buildings; Journal of Construction Engineering and Management; 1994; No. 120(1); 96-116.

19. Ellips M., Davoud S.; Classic and Heuristic Approaches in Robot Motion Planning - A Chronological Review; Proceedings of world academy of science, engineering and technology 23; 2007; 101-106.

20. Kolisch R., Sprechrr A., Drexl A.; Characterization and generation of a general class of resource-constrained project scheduling problems; Management Science; 1995; No. 41(10); 1693-1703.

21. Lavalle S. M.; Planning algorithms; Cambridge University Press; UK; 2006.

22. Chua D., Yeoh K., Song Y.; Quantification of spatial temporal congestion in Four-dimensional computer-aided design; Journal of Construction Engineering and Management; 2010; Vol. 136, No. 6; 641-649.

23. Chavada R., Dawood N., Kassem M.; Construction workspace management: the development and application of a novel nD planning approach and tool; Journal of Information Technology in Construction; 2012; Vol. 17; 213-236.

24. Kolisch R.; Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation; Journal of Operations Management; 1996; No. 90; 320-333.

25. Semenov V.A., Kazakov K.A., Zolotov V.A., Jones H., Jones S., Combined strategy for efficient collision detection in 4D planning applications. // In Computing in Civil and Building Engineering, Proceedings of the International Conference, W. Tizani (Editor), 2010, Nottingham, UK, Nottingham University Press, p. 31-39, ISBN 978-1-907284-60-1.

26. Semenov V.A., Kazakov K.A., Morozov S.V., Tarlapan O.A., Zolotov V.A., Dengenis T., 4D modeling of large industrial projects using spatio-temporal decomposition. // eWork and eBusiness in Architecture, Engineering and Construction, eds. K. Menzel and R. Scherer, CRC Press, Taylor & Francis Group,London, UK, 2010, pp. 89-95.

27. Semenov V.A., Kazakov K. A, Zolotov V. A., Virtual Construction: 4D Planning and Validation; Proceedings of the XI International Conference on Construction Applications of Virtual Reality; 2011; 135-142.

28. Semenov V.A., Zolotov V.A., Kazakov K.A., Spatio-temporal validation of construction projects against path conflicts; Proceedings of 12th Conference on Construction Applications of Virtual Reality, National Taiwan University Press; 2012; 542-551.

29. Semenov V.A., Anichkin A.S., Morozov S.V., Tarlapan O.A., Zolotov V. A., Visual Planning and Scheduling of Industrial Projects with Spatial Factors; Proceedings of 20th ISPE International Conference on Concurrent Engineering, eds. C. Bil, J. Mo, J. Stjepandic, IOS Press, Melbourne, Australia, ISBN 978-1-61499-301-8; 2013; 343-352.


Для цитирования:


Семенов В.А., Аничкин А.С., Морозов С.В., Тарлапан О.А., Золотов В.А. Комплексный метод составления расписаний для сложных индустриальных программ с учетом пространственно-временных ограничений. Труды Института системного программирования РАН. 2014;26(1):457-482. https://doi.org/10.15514/ISPRAS-2014-26(1)-20

For citation:


Semenov V.A., Anichkin A.S., Morozov S.V., Tarlapan O.A., Zolotov V.A. Effective Method For Scheduling Complex Industrial Programs Under Spatio-Temporal Constraints. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(1):457-482. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(1)-20

Просмотров: 75


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)