Lập tiến độ dự án với việc tối ưu hóa chi phí và ràng buộc về thời gian được thiết lập thành bài toán quy hoạch tuyến tính

Nội dung text: Lập tiến độ dự án với việc tối ưu hóa chi phí và ràng buộc về thời gian được thiết lập thành bài toán quy hoạch tuyến tính

1. Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 31 5(48) (2021) 31-36 Project scheduling with cost minimization and time constraint formulated as a linear programming problem Lập tiến độ dự án với việc tối ưu hĩa chi phí và ràng buộc về thời gian được thiết lập thành bài tốn quy hoạch tuyến tính Hồng Nhật Đức1,2* Hoang Nhat Duca,b* aInstitute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam aViện Nghiên cứu và Phát triển Cơng nghệ Cao, Trường Đại học Duy Tân, Đà Nẵng, Việt Nam bFaculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam bKhoa Xây dựng, Trường Đại học Duy Tân, Đà Nẵng, Việt Nam (Ngày nhận bài: 28/8/2021, ngày phản biện xong: 07/10/2021, ngày chấp nhận đăng: 20/10/2021) Abstract In construction management, the task of optimizing a project schedule to achieve a minimal cost and meet a project deadline is very crucial. This study formulates this task as a linear programming problem and investigates the application of the open-source Google OR-Tools in solving such problem. A computer program has been constructed based on the formulated linear programming problem and developed with Microsoft Visual Studio and Google OR- Tools. This program has tested with a simplified project scheduling optimization task. Keywords: Construction management; project schedule optimization; linear programming; time-cost analysis. Tĩm tắt Trong quản lý xây dựng, nhiệm vụ tối ưu hĩa tiến độ dự án để đạt được chi phí tối thiểu và thỏa mãn thời gian hồn thành của dự án là rất quan trọng. Nghiên cứu của chúng tơi mơ hình hĩa vấn đề này như một bài tốn quy hoạch tuyến tính và nghiên cứu ứng dụng của cơng cụ mã nguồn mở Google OR-Tools trong việc giải quyết vấn đề này. Một chương trình tính tốn đã được xây dựng dựa trên bài tốn lập trình tuyến tính và phát triển bằng Microsoft Visual Studio kết hợp với Google OR-Tools. Chương trình này đã thử nghiệm với một bài tốn tối ưu hĩa tiến độ dự án đơn giản. Từ khĩa: Quản lý xây dựng; tối ưu hĩa tiến độ dự án; quy hoạch tuyến tính; phân tích thời gian-chi phí. 1. Introduction maintain schedules/costs with increasingly A project includes a set of activities with complex techniques, makes project their costs and durations. The construction management a highly challenging task [1-7]. industry, which is featured by constant changes Both owners and contractors have a great desire in the operational environment, pressures to of minimizing the project cost and satisfy the project schedule. The reason contractors have a *Corresponding Author: Hoang Nhat Duc; Faculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam; Institute of Research and Devolopment, Duy Tan University, 550000, Da Nang, Vietnam Email: hoangnhatduc@duytan.edu.vn
2. 32 Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 great risk of severe financial penalty for not 2. Problem formulation completing a project on time. Addition, project The project schedule optimization can be owners always wish to finish the project as formulated as the following optimization early as possible to put their facilities into problem [10-12]: operation. CS (1) In practice, a construction activity can be Minimize ii ii executed in several modes with different requirements of cost and time. A contractor can where Ci is the activity direct cost and  Si i i inspect the relationship between time and cost is the sum of the activity starting time. of each activity through cost/time estimation Subject to and historical records of similar activities performed in the past. A simple yet effective Sj – Si – Di ≥ 0  i, j FSSet (2) (3) approach of time-cost modeling is to express Cii  f( D ), i the relationship between them as a linear SN + DN ≤ TLimit (4) function. By doing so, the task of optimizing Herein, the objective function is a sum of the the project schedule with cost minimization and direct activity costs and activity start times. time constraint can be formulated as a linear FS is the set of activities with finish (i) – programming problem. Linear programming Set start (j) (FS) relationship. Eq. (3) describes the refers to a mathematical modeling approach linear relationship between activity time and within which a linear objective function is cost. The decision variables of the problems are either minimized or maximized when subjected activity start times (S ) and durations (D ). Eq. to a set of linear constraints [8]. i i (4) means that the finishing time of the last This problem structure is transparent and activity (activity N) must be less than a certain easy to understand and this linear optimization number (TLimit). problem is also easy to solve by existing open- source packages such as the Google OR-Tools. 3. Model application More importantly, the Google OR-Tools can be In this section of the article, a simple project used within the Microsoft Visual Studio with consisting of six activities with their duration C# programming language [9]. This fact means ranges and linear cost-time functions is used to that sophisticated schedule optimization demonstrate the linear programming software program based on the Google OR- formulation and solving with the employment Tools and Microsoft Visual Studio can be of the Google OR-Tools. This tool is quickly developed and used by project implemented within the Microsoft Visual managers. This study exploits the Studio and C# programming. Visual C# . NET aforementioned advantage of linear is a general purpose and multi-paradigm programming modeling, the Google OR-Tools, programming language that facilitates fast and the Microsoft Visual Studio with C# developments of computer software used for programming language to develop a computer solving problems in civil engineering [13-20]. program and tested it with a simplified project The project information with their duration scheduling optimization task. ranges and linear cost-time functions is shown in Table 1. The time relationships of activities are depicted in Fig. 1. Herein, S2, S3, S4, S5, S6,
3. Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 33 D1, D2, D3, D4, D5, and T6 are the decision S2 - S1 - D1 ≥ 0; S3 - S1 - D1 ≥ 0; S4 – S1 – D1 variables of the optimization problem. It is ≥ 0; S5 – S2 – D2 ≥ 0; noted that the activity 1’s start time S = 0. 2 S5 – S3 – D3 ≥ 0; S5 – S4 – D4 ≥ 0; S6 – S5 – The objective function of the problem is D ≥ 0; expressed as: 5 C1 = -30D1 + 500; C2 = -25D2 + 400; C3 = - Min. f = S2 + S3 + S4 + S5 + S6 + C1 + C2+ 10D3 + 600 C3+ C4+ C5+ C6 (5) C = -100D + 2000; C = -50D + 1500; C s.t. 4 4 5 5 6 = -10D6 + 300 S6 + D6 ≤ 18 Table 1. Project information Activity Predecessor Duration range Cost-time function 1 [1, 3] C = -30D + 500 2 1 [2, 4] C = -25D + 400 3 1 [3, 6] C = -10D + 600 4 1 [2, 5] C = -100D + 2000 5 2, 3, 4 [3, 5] C = -50D + 1500 6 5 [4, 7] C = -10D + 300 Fig. 1 Network diagram Fig. 2 Setting decision variables
4. 34 Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 Fig. 3 Setting problem constraints and objective function Fig. 4 Display problem results
5. Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 35 The code used for solving the (ii) The start time, duration, and finish time aforementioned optimization process is of each activity is as follows: demonstrated in Fig. 2 (Setting decision S1 = 0. D1 = 3. F1 = 3. S2 = 3. D2 = 4. F2 = 7. variables) and Fig. 3 (Setting problem S = 3. D = 5. F = 8. S = 3. D = 5. F = 8. constraints and objective function). The code 3 3 3 4 4 4 used for displaying the optimization results are S5 = 8. D5 = 5. F5 = 13. S6 = 13. D6 = 5. F6 = 18. shown in Fig. 4. The detailed optimized (iii) The project duration is 18 (day). schedule is reported in Table 2. The solution to (iv) The project cost is $4260. the problem of interest is as follows: (i) The objective function value is 4290. Table 2. Project scheduling results Optimal duration Activity Start time Finish time (day) 1 0 3 3 2 3 4 7 3 3 5 8 4 3 5 8 5 8 5 13 6 13 5 18 4. Concluding remarks Using Differential Evolution: A Comparative Study of Mutation Strategies," Advances in Civil This study develops a software program Engineering, vol. 2015, p. 8, 2015. based on linear programming, Google OR- [3] D. W. Halpin and B. A. Senior, Construction Management: Wiley, 4 edition, 2010. Tools, and Microsoft Visual Studio with C# to [4] J. Gordon and K. G. Lockyer, Project management perform construction project schedule and project network techniques: Pearson, 2005. optimization. The program is able to compute [5] K. N. Jha, Construction Project Management the project schedule automatically with a Theory and Practices: Pearson India, 2015. minimal activity cost and a total project [6] S. A. Mubarak, Construction Project Scheduling and Control: John Wiley & Sons, Inc., Hoboken, duration that satisfies a pre-specified time New Jersey, 2015. constraint. Future extensions of the current [7] L. Zhu, J. Lin, and Z.-J. Wang, "A discrete work may include the consideration of project oppositional multi-verse optimization algorithm for indirect cost and the integration the current multi-skill resource constrained project scheduling problem," Applied Soft Computing, vol. 85, p. linear programming formulation into other 105805, 2019/12/01/ 2019. sophisticated scheduling optimization models [8] N. Đ. Hồng, T. H. Vũ, L. T. Phan, and T. T. such as resource leveling [1, 21, 22], time-cost Nguyễn, "Ứng dụng phương pháp quy hoạch tuyến tính cho bài tốn tối ưu hĩa trong quản lý dự án xây trade-off [23-27], labor utilization [2, 28], etc. dựng," Tạp Chí Khoa Học và Cơng Nghệ, Đại Học References Duy Tân, vol. 2, pp. 89-95, 2017. [9] N.-D. Hoang, "Giải các bài tốn tối ưu hĩa tuyến [1] M.-Y. Cheng, D.-H. Tran, and N.-D. Hoang, "Fuzzy tính trong quản lý xây dựng với cơng cụ Google clustering chaotic-based differential evolution for OR-Tools và Microsoft Visual Studio (V1.3)," resource leveling in construction projects," Journal Technical Report TRLP7142021V1.3, Duy Tan of Civil Engineering and Management, vol. 23, pp. university, 113-124, 2017/01/02 2017. [2] N.-D. Hoang, Q.-L. Nguyen, and Q.-N. Pham, 8_Giai_cac_bai_toan_toi_uu_hoa_tuyen_tinh_tron "Optimizing Construction Project Labor Utilization g_quan_ly_xay_dung_voi_cong_cu_Google_OR-
6. 36 Hồng Nhật Đức / Tạp chí Khoa học và Cơng nghệ Đại học Duy Tân 5(48) (2021) 31-36 Tools_va_Microsoft_Visual_Studio (Last update Reality technology for safety training in the precast/ 07/17/2021), 2021. prestressed concrete industry," Applied Ergonomics, [10] N.-D. Hoang, "NIDE: A Novel Improved vol. 90, p. 103286, 2021/01/01/ 2021. Differential Evolution for Construction Project [20] N.-D. Hoang, "Image processing based automatic Crashing Optimization," Journal of Construction recognition of asphalt pavement patch using a Engineering, vol. 2014, p. 7, 2014. metaheuristic optimized machine learning [11] I.-T. Yang, "Using Elitist Particle Swarm approach," Advanced Engineering Informatics, vol. Optimization to Facilitate Bicriterion Time-Cost 40, pp. 110-120, 2019/04/01/ 2019. Trade-Off Analysis," Journal of Construction [21] I. Tarasov, A. Hạt, and O. Battạa, "Benders Engineering and Management, vol. 133, pp. 498- decomposition for a period-aggregated resource 505, 2007. leveling problem with variable job duration," [12] F. D. Akin, G. Polat, H. Turkoglu, and A. Damci, Computers & Operations Research, vol. 132, p. "A crashing-based time-cost trade-off model 105258, 2021/08/01/ 2021. considering quality cost and contract clauses," [22] G. Ulusoy and Ư. Hazır, "Resource Leveling and International Journal of Construction Management, Other Resource Management Problems," in An pp. 1-10, 2021. Introduction to Project Modeling and Planning, ed [13] H. Shafeek, H. A. Soltan, and M. H. Abdel-Aziz, Cham: Springer International Publishing, 2021, pp. "Corrosion monitoring in pipelines with a 251-280. computerized system," Alexandria Engineering [23] N. D. Hoang, "Automatic time-cost trade-off for Journal, vol. 60, pp. 5771-5778, 2021/12/01/ 2021. construction projects using evolutionary algorithm [14] Z. Xiang, A. Rashidi, and G. Ou, "Automated integrated into a scheduling software program Framework to Translate Rebar Spatial Information developed with .NET framework," DTU Journal of from GPR into BIM," Journal of Construction Science and Technology, vol. 3, pp. 3-8, 2020. Engineering and Management, vol. 147, p. [24] N. Đ. Hồng, Q. L. Nguyễn, and Q. N. Phạm, "Tối 04021120, 2021. ưu hĩa tiến độ và chi phí cho dự án xây dựng sử [15] T. Bi, F. Zhou, X. Yang, Y. Zhu, and X. Diao, dụng thuật tốn tiến hĩa vi phân," Tạp Chí Khoa "Research on the Construction of City Information Học và Cơng Nghệ, Đại Học Duy Tân, vol. 1, pp. Modelling Basic Platform Based on Multi-source 135–141, 2015. Data," IOP Conference Series: Earth and [25] M. ElMenshawy and M. Marzouk, "Automated BIM Environmental Science, vol. 693, p. 012021, schedule generation approach for solving time–cost 2021/03/01 2021. trade-off problems," Engineering, Construction and [16] E. M. Abdelkader, O. Moselhi, M. Marzouk, and T. Architectural Management, vol. ahead-of-print, Zayed, "Integrative Evolutionary-Based Method for 2021. Modeling and Optimizing Budget Assignment of [26] L. S. Tavassoli, R. Massah, A. Montazeri, M. Bridge Maintenance Priorities," Journal of Mirmozaffari, G.-J. Jiang, and H.-X. Chen, "A New Construction Engineering and Management, vol. Multiobjective Time-Cost Trade-Off for Scheduling 147, p. 04021100, 2021. Maintenance Problem in a Series-Parallel System," [17] Z. Liu, X. Gu, Q. Dong, S. Tu, and S. Li, "3D Mathematical Problems in Engineering, vol. 2021, Visualization of Airport Pavement Quality Based on p. 5583125, 2021/07/01 2021. BIM and WebGL Integration," Journal of [27] A. Dhawan, K. Sharma, and M. K. Trivedi, Transportation Engineering, Part B: Pavements, "Simulated Annealing-Based Time–Cost Trade-Off vol. 147, p. 04021024, 2021. Model for Construction Projects," Singapore, 2022, [18] H. Jain and V. H. Patankar, "Embedded system for pp. 33-43. ultrasonic imaging of under-water concrete [28] D. H. Jun and K. El-Rayes, "Optimizing the structures," Journal of Instrumentation, vol. 16, p. utilization of multiple labor shifts in construction P07049, 2021/07/01 2021. projects," Automation in Construction, vol. 19, pp. [19] S. Joshi, M. Hamilton, R. Warren, D. Faucett, W. 109-119, 2010/03/01/ 2010. Tian, Y. Wang, et al., "Implementing Virtual