Effective Method For Scheduling Complex Industrial Programs Under Spatio-Temporal Constraints

Effective project management implies the use of advanced planning and scheduling methods that allow to determine the feasible sequences of activities and to complete a project on time and on budget. Traditional scheduling tools like fundamental Critical Path Method (CPM) and various methods for Resource Constrained Project Scheduling Problem (RCPSP) and Time Constrained Project Scheduling Problem (TCPSP) have many shortcomings for the construction projects where spatial factor plays critically important role. Previously taken attempts to interpret space as a specific resource were successful for particular problems of line-of-balance scheduling, space scheduling, dynamic layout planning, horizontal and vertical logic scheduling, workspace congestion mitigating, scheduling multiple projects with movable resources, spatial scheduling of repeated and grouped activities, motion planning. However, none of these methods considers the spatio-temporal requirements in a holistic framework of generic RCPSP problem and provides feasible results accounting for workspace and workflow factors. In the paper we start with the classical RCPSP statement and then present mathematically strong formalization of the extended generalized problem taking into account workspace congestion and workflow disturbance constraints specified in practically meaningful and computationally constructive ways. For the generalized RCPSP problem an effective scheduling method is proposed. The method tends to minimize the project makespan while satisfying timing constraints and precedence relations, not exceeding resource utilization limits, avoiding workspace congestion and keeping workflows continuous. The method reuses so-called serial scheduling scheme and provides for additional computational routines and heuristic priority rules to generate feasible schedules satisfying all the imposed requirements. In order to evaluate the method, benchmark sets are proposed and investigated. Advantages of the method and prospects for its application to industrial needs are outlined in the paper too.

planning and scheduling, resource-constrained project scheduling problem, priority rules, 4D modeling, workspace management

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

2. Bowers J. A. Criticality in resource-constrained networks. Journal of the operational research society, vol. 46, no. 1, 1995, p.p. 80–91.

3. David E. W., Patterson J. H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Management science, vol. 21, no. 8, 1975, pp. 944–955.

4. Hegazy T. Optimization of resource allocation and leveling using genetic algorithms. Journal of construction engineering and management, ASCE, vol. 125, no. 3, 1999, p.p. 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, vol. 17, no. 2, 1966, pp. 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, vol. 8, no. 6, 1960, pp. 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, vol. 23, no. 2, 1961, pp. 484–492.

11. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, vol.14, 1996, pp. 179–192.

12. Boctor F. F. Some efficient multi-heuristic procedures for resource constrained project scheduling. European journal of operational research, vol. 49, 1990, pp. 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), vol.2, no. 1, 2013, pp. 82–95.

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

15. Zouein P. P., Tommelein I. D. Dynamic Layout Planning Using a Hybrid Incremental Solution Method. Journal of Construction Engineering and Management, vol. 125, no. 6, 1999, pp. 400–408.

16. Thabet W. Y., Beliveau Y. J. HVLS: Horizontal and Vertical Logic Scheduling for Multistory Projects. Journal of Construction Engineering and Management, vol. 120, no. 4, 1994, pp. 875–892.

17. Yeoh K. W., David K. H. Chua. Mitigating Workspace Congestion: A Genetic Algorithm Approach. Proceedings EPPM 2012 Conference, 2012, pp. 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, vol. 120, no. 1, 1994, pp. 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, vol. 23, 2007, pp. 101–106.

20. Kolisch R., Sprechrr A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, vol. 41, no. 10, 1995, pp. 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, vol. 136, no. 6, 2010, pp. 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, vol. 17, 2012, pp. 213–236.

24. Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. Journal of Operations Management, vol. 90, 1996, pp. 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. Computing in Civil and Building Engineering, Proceedings of the International Conference, 2010, p.p. 31–39.

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, 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, pp. 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, 2012, pp. 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, 2013, pp. 343–352.