Feasibility Regions and Critical-Path Uniqueness in Inverse Project Scheduling Using Multilayer Acyclic Digraph Models
Keywords:
Critical Path Method (CPM), multilayered acyclic digraph, project scheduling problem
Abstract
This paper examines an inverse project scheduling problem formulated using the Critical Path Method (CPM), in which one activity durations are unknown. The objective is to derive analytical conditions that ensure a given project duration is feasible and that a particular path becomes the unique critical path. The project workflow is represented as a multilayered acyclic digraph, which facilitates symbolic analysis of all critical path candidates. A numerical example is implemented in Python on a six-layer network with two nodes per inside layer and one unknown duration. From an initial set of 16 possible paths, only 4 remain after slack-based pruning, enabling symbolic characterization of the feasibility region. The findings contribute to a deeper understanding of structural conditions that guarantee critical path uniqueness in inverse project scheduling problems.
Downloads
Download data is not yet available.
References
[1] E. Kelley Jr. and M. R. Walker, “Critical path planning and scheduling,” in Proceedings of the Eastern Joint Computer Conference, Boston, MA, USA, 1959, pp. 160–173.
[2] D. G. Malcolm, J. H. Roseboom, C. E. Clark, and W. Fazar, “Application of a Technique for Research and Development Program Evaluation,” Oper Res, vol. 7, no. 5, pp. 646–669, 1959.
[3] D. R. Fulkerson, “A network flow computation for project cost curves,” Manage Sci, vol. 7, no. 2, pp. 167–179, 1961.
[4] J. J. Moder and C. R. Phillips, Project Management with CPM and PERT, 2nd ed. New York, NY: USA: Reinhold Publishing, 1964.
[5] W. A. Haga and K. A. Marold, “A Simulation Approach to the PERT/CPM Time-Cost Trade-Off Problem,” Project Management Journal, vol. 35, no. 2, pp. 31–37, Jun. 2004, doi: 10.1177/875697280403500205.
[6] E. Levner, V. Kats, P. Yan, and A. Che, “Fast Algorithm for High-Throughput Screening Scheduling Based on the PERT/CPM Project Management Technique,” Algorithms, vol. 17, no. 3, p. 127, Mar. 2024, doi: 10.3390/a17030127.
[7] F. W. Santoso, F. S. Handayani, and Setiono, “A Comparative Analysis of the CPM and PERT Methods in Project Time Management for a High-Rise Building Construction Project in Yogyakarta,” Sustainable Civil Building Management and Engineering Journal, vol. 2, no. 2, p. 13, May 2025, doi: 10.47134/scbmej.v2i2.3927.
[8] S. Aulia and H. Cipta, “Network Planning Analysis Using CPM and PERT Methods on Optimization of Time and Cost,” Sinkron, vol. 8, no. 1, pp. 171–177, Jan. 2023, doi: 10.33395/sinkron.v8i1.11961.
[9] B. N. Kurniawan and N. B. Mulyono, “Minimizing Delay in Construction Project at PT Freeport Indonesia using Crashing CPM-PERT Approach and Monte Carlo Simulation,” European Journal of Business and Management Research, vol. 9, no. 5, pp. 61–69, Sep. 2024, doi: 10.24018/ejbmr.2024.9.5.2448.
[10] R. T. Prasetyawidandi, R. N. Rachmadita, D. A. Utari, and L. E. Puspandari, “Analisis Optimasi Waktu dan Biaya Crashing Project Dengan Metode Critical Path dan Time Cost Trade Off Pada Proyek Pembangunan Galangan Kapal (Studi Kasus PT. Batam Expresindo Shipyard),” Jurnal Teknologi Maritim , vol. 5, no. 2, 2022.
[11] Y. F. Ryandre and G. Sarya, “EVALUASI WAKTU DAN BIAYA MENGGUNAKAN METODE CRITICAL PATH METHOD DAN CRASHING PADA PROYEK PEMBANGUNAN GEDUNG ARSIP TRENGGALEK,” Jurnal Taguchi : Jurnal Ilmiah Keilmuan Teknik dan Manajemen Industri , vol. 3, no. 2, pp. 1463–1473, 2023.
[12] A. M. C. A. Koster, J. Segschneider, and N. Ventsch, “Γ-robust optimization of project scheduling problems,” Comput Oper Res, vol. 161, p. 106453, Jan. 2024, doi: 10.1016/j.cor.2023.106453.
[13] M. Bold and M. Goerigk, “A faster exact method for solving the robust multi-mode resource-constrained project scheduling problem,” Operations Research Letters, vol. 50, no. 5, pp. 581–587, Sep. 2022, doi: 10.1016/j.orl.2022.08.003.
[14] N. Balouka and I. Cohen, “A robust optimization approach for the multi-mode resource-constrained project scheduling problem,” Eur J Oper Res, vol. 291, no. 2, pp. 457–470, Jun. 2021, doi: 10.1016/j.ejor.2019.09.052.
[15] W. Liu, L. Ge, C. Qu, and S. Yang, “Bi-objective Optimization for Resource-constrained Robust Construction Project Scheduling,” KSCE Journal of Civil Engineering, vol. 28, no. 1, pp. 15–28, Jan. 2024, doi: 10.1007/s12205-023-0633-8.
[16] M. Davari and E. Demeulemeester, “Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem,” Ann Oper Res, vol. 274, no. 1–2, pp. 187–210, Mar. 2019, doi: 10.1007/s10479-018-2899-7.
[17] Z. Chen, E. Demeulemeester, S. Bai, and Y. Guo, “Efficient priority rules for the stochastic resource-constrained project scheduling problem,” Eur J Oper Res, vol. 270, no. 3, pp. 957–967, Nov. 2018, doi: 10.1016/j.ejor.2018.04.025.
[18] J. Blázquez González, J. A. Barro, and E. Rubio Romero, “Construction project scheduling considering resource leveling and slack sensitivity,” Applied Sciences, vol. 11, no. 16, 2021.
[19] Y. Zhao, X. Hu, J. Wang, and N. Cui, “A robust multi-project scheduling problem under a resource dedication-transfer policy,” Ann Oper Res, vol. 337, no. 1, pp. 425–457, Jun. 2024, doi: 10.1007/s10479-024-05854-4.
[20] A. Andiyan, R. M. Putra, G. D. Rembulan, and H. Tannady, “Construction Project Evaluation Using CPM-Crashing, CPM-PERT and CCPM for Minimize Project Delays,” J Phys Conf Ser, vol. 1933, no. 1, p. 012096, Jun. 2021, doi: 10.1088/1742-6596/1933/1/012096.
[2] D. G. Malcolm, J. H. Roseboom, C. E. Clark, and W. Fazar, “Application of a Technique for Research and Development Program Evaluation,” Oper Res, vol. 7, no. 5, pp. 646–669, 1959.
[3] D. R. Fulkerson, “A network flow computation for project cost curves,” Manage Sci, vol. 7, no. 2, pp. 167–179, 1961.
[4] J. J. Moder and C. R. Phillips, Project Management with CPM and PERT, 2nd ed. New York, NY: USA: Reinhold Publishing, 1964.
[5] W. A. Haga and K. A. Marold, “A Simulation Approach to the PERT/CPM Time-Cost Trade-Off Problem,” Project Management Journal, vol. 35, no. 2, pp. 31–37, Jun. 2004, doi: 10.1177/875697280403500205.
[6] E. Levner, V. Kats, P. Yan, and A. Che, “Fast Algorithm for High-Throughput Screening Scheduling Based on the PERT/CPM Project Management Technique,” Algorithms, vol. 17, no. 3, p. 127, Mar. 2024, doi: 10.3390/a17030127.
[7] F. W. Santoso, F. S. Handayani, and Setiono, “A Comparative Analysis of the CPM and PERT Methods in Project Time Management for a High-Rise Building Construction Project in Yogyakarta,” Sustainable Civil Building Management and Engineering Journal, vol. 2, no. 2, p. 13, May 2025, doi: 10.47134/scbmej.v2i2.3927.
[8] S. Aulia and H. Cipta, “Network Planning Analysis Using CPM and PERT Methods on Optimization of Time and Cost,” Sinkron, vol. 8, no. 1, pp. 171–177, Jan. 2023, doi: 10.33395/sinkron.v8i1.11961.
[9] B. N. Kurniawan and N. B. Mulyono, “Minimizing Delay in Construction Project at PT Freeport Indonesia using Crashing CPM-PERT Approach and Monte Carlo Simulation,” European Journal of Business and Management Research, vol. 9, no. 5, pp. 61–69, Sep. 2024, doi: 10.24018/ejbmr.2024.9.5.2448.
[10] R. T. Prasetyawidandi, R. N. Rachmadita, D. A. Utari, and L. E. Puspandari, “Analisis Optimasi Waktu dan Biaya Crashing Project Dengan Metode Critical Path dan Time Cost Trade Off Pada Proyek Pembangunan Galangan Kapal (Studi Kasus PT. Batam Expresindo Shipyard),” Jurnal Teknologi Maritim , vol. 5, no. 2, 2022.
[11] Y. F. Ryandre and G. Sarya, “EVALUASI WAKTU DAN BIAYA MENGGUNAKAN METODE CRITICAL PATH METHOD DAN CRASHING PADA PROYEK PEMBANGUNAN GEDUNG ARSIP TRENGGALEK,” Jurnal Taguchi : Jurnal Ilmiah Keilmuan Teknik dan Manajemen Industri , vol. 3, no. 2, pp. 1463–1473, 2023.
[12] A. M. C. A. Koster, J. Segschneider, and N. Ventsch, “Γ-robust optimization of project scheduling problems,” Comput Oper Res, vol. 161, p. 106453, Jan. 2024, doi: 10.1016/j.cor.2023.106453.
[13] M. Bold and M. Goerigk, “A faster exact method for solving the robust multi-mode resource-constrained project scheduling problem,” Operations Research Letters, vol. 50, no. 5, pp. 581–587, Sep. 2022, doi: 10.1016/j.orl.2022.08.003.
[14] N. Balouka and I. Cohen, “A robust optimization approach for the multi-mode resource-constrained project scheduling problem,” Eur J Oper Res, vol. 291, no. 2, pp. 457–470, Jun. 2021, doi: 10.1016/j.ejor.2019.09.052.
[15] W. Liu, L. Ge, C. Qu, and S. Yang, “Bi-objective Optimization for Resource-constrained Robust Construction Project Scheduling,” KSCE Journal of Civil Engineering, vol. 28, no. 1, pp. 15–28, Jan. 2024, doi: 10.1007/s12205-023-0633-8.
[16] M. Davari and E. Demeulemeester, “Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem,” Ann Oper Res, vol. 274, no. 1–2, pp. 187–210, Mar. 2019, doi: 10.1007/s10479-018-2899-7.
[17] Z. Chen, E. Demeulemeester, S. Bai, and Y. Guo, “Efficient priority rules for the stochastic resource-constrained project scheduling problem,” Eur J Oper Res, vol. 270, no. 3, pp. 957–967, Nov. 2018, doi: 10.1016/j.ejor.2018.04.025.
[18] J. Blázquez González, J. A. Barro, and E. Rubio Romero, “Construction project scheduling considering resource leveling and slack sensitivity,” Applied Sciences, vol. 11, no. 16, 2021.
[19] Y. Zhao, X. Hu, J. Wang, and N. Cui, “A robust multi-project scheduling problem under a resource dedication-transfer policy,” Ann Oper Res, vol. 337, no. 1, pp. 425–457, Jun. 2024, doi: 10.1007/s10479-024-05854-4.
[20] A. Andiyan, R. M. Putra, G. D. Rembulan, and H. Tannady, “Construction Project Evaluation Using CPM-Crashing, CPM-PERT and CCPM for Minimize Project Delays,” J Phys Conf Ser, vol. 1933, no. 1, p. 012096, Jun. 2021, doi: 10.1088/1742-6596/1933/1/012096.
Published
2026-05-28
Section
Articles
Copyright (c) 2026 Robby Robby, Levina Michella, Yanuar Bhakti Wira Tama
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
