Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tối ưu hóa việc áp dụng suy yếu một mạng lưới hoạt động dưới các sự cố
Tóm tắt
Trong bài báo này, chúng tôi xem xét một bài toán tối ưu liên quan đến việc suy yếu một mạng lưới hoạt động dưới một sự cố duy nhất. Một sự cố là một sự kiện có độ lớn và thời gian xảy ra ngẫu nhiên. Khi một sự cố xảy ra, thời gian thực hiện một hoạt động chưa bắt đầu — hoặc nói cách khác, chưa hoàn thành — có thể thay đổi. Chúng tôi xây dựng một chương trình quy hoạch hỗn hợp nguyên số ngẫu nhiên hai giai đoạn, trong đó thời gian của giai đoạn là ngẫu nhiên. Trong mô hình của chúng tôi, bài toán khôi phục là một chương trình quy hoạch hỗn hợp nguyên số. Chúng tôi chứng minh rằng bài toán này là NP-kho; và thông qua các ví dụ đơn giản, chúng tôi minh họa các tính chất khác biệt so với phiên bản xác định của bài toán. Việc đạt được một khoảng cách tối ưu tương đối chặt chẽ có thể yêu cầu một số lượng lớn mẫu trong phương pháp xấp xỉ trung bình mẫu, dẫn đến các trường hợp quy mô lớn mà việc giải quyết có chi phí tính toán cao. Do đó, chúng tôi phát triển một thuật toán phân nhánh và cắt giảm, trong đó việc phân nhánh không gian của các biến liên tục ở giai đoạn một và các xấp xỉ quy hoạch tuyến tính cho bài toán khôi phục được tăng cường tuần tự. Chúng tôi thử nghiệm thuật toán phân tách của mình với nhiều cải tiến và cho thấy nó có thể giảm đáng kể thời gian giải so với việc giải quyết bài toán trực tiếp.
Từ khóa
#tối ưu hóa #mạng lưới hoạt động #sự cố ngẫu nhiên #chương trình quy hoạch hỗn hợp nguyên số #NP-kho #thuật toán phân nhánh và cắt giảmTài liệu tham khảo
Aghaie, A., Mokhtari, H.: Ant colony optimization algorithm for stochastic project crashing problem in PERT networks using MC simulation. Int. J. Adv. Manuf. Technol. 45(11), 1051–1067 (2009)
Ahipasaoglu, S.D., Natarajan, K., Shi, D.: Distributionally robust project crashing with partial or no correlation information. Optimization-Online (2016). http://www.optimization-online.org/DB_FILE/2016/11/5715.pdf
Belotti, P., Cafieri, S., Lee, J., Liberti, L.: On feasibility based bounds tightening. Optimization-Online (2012). http://www.optimization-online.org/DB_FILE/2012/01/3325.pdf
Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34, 384–392 (1988)
Blazewicz, J., Lenstra, J.K., Kan, A.H.G.R.: Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math. 5(1), 11–24 (1983)
Bowman, R.A.: Stochastic gradient-based time-cost tradeoffs in PERT networks using simulation. Ann. Oper. Res. 53(1), 533–551 (1994)
Burt, J.M., Garman, M.B.: Conditional Monte Carlo: a simulation technique for stochastic network analysis. Manag. Sci. 18(3), 207–217 (1971)
Camm, J.D., Raturi, A.S., Tsubakitani, S.: Cutting big M down to size. Interfaces 20(5), 61–66 (1990)
Cardoen, B., Demeulemeester, E., Beliën, J.: Operating room planning and scheduling: a literature review. Eur. J. Oper. Res. 201(3), 921–932 (2010)
Carøe, C., Tind, J.: L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Program. 83(1–3), 451–464 (1998)
Chen, B., Küçükyavuz, S., Sen, S.: A computational study of the cutting plane tree algorithm for general mixed-integer linear programs. Oper. Res. Lett. 40(1), 15–19 (2012)
Chen, X., Sim, M., Sun, P., Zhang, J.: A linear decision-based approximation approach to stochastic programming. Oper. Res. 56(2), 344–357 (2008)
Coffrin, C., Hijazi, H.L., Van Hentenryck, P.: Strengthening convex relaxations with bound tightening for power network optimization. In: International Conference on Principles and Practice of Constraint Programming, pp. 39–57. Springer, Berlin (2015)
Cohen, I., Golany, B., Shtub, A.: The stochastic time-cost tradeoff problem: a robust optimization approach. Networks 49(2), 175–188 (2007)
Crow, E.L., Shimizu, K.: Lognormal Distributions: Theory and Applications. CRC Press, Amsterdam (1987)
De, P., Dunne, E.J., Ghosh, J.B., Wells, C.E.: Complexity of the discrete time-cost tradeoff problem for project networks. Oper. Res. 45(2), 302–306 (1997)
Demeulemeester, E., Herroelen, W.S.: Project Scheduling: A Research Handbook, vol. 49. Springer, Berlin (2006)
Demeulemeester, E., Vanhoucke, M., Herroelen, W.: RanGen: a random network generator for activity-on-the-node networks. J. Sched. 6(1), 17–38 (2003)
Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017)
Elmaghraby, S.E.: Activity Networks: Project Planning and Control by Network Models. Wiley, London (1977)
Fulkerson, D.R.: A network flow computation for project cost curves. Manag. Sci. 7(2), 167–178 (1961)
Gade, D., Küçükyavuz, S., Sen, S.: Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Program. 144(1–2), 39–64 (2014)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)
Gurobi Optimization, Inc.: Gurobi Optimizer Reference Manual (2016). http://www.gurobi.com
Hall, N.G., Sriskandarajah, C.: A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44(3), 510–525 (1996)
Hartmann, S., Kolisch, R.: Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127(2), 394–407 (2000)
Hellemo, L., Barton, P.I., Tomasgard, A.: Decision-dependent probabilities in stochastic programs with recourse. CMS 15(3–4), 369–395 (2018)
Jaselskis, E.J., Ashley, D.B.: Optimal allocation of project management resources for achieving success. J. Constr. Eng. Manag. 117(2), 321–340 (1991)
Ke, H.: A genetic algorithm-based optimizing approach for project time-cost trade-off with uncertain measure. J. Uncertain. Anal. Appl. 2(1), 8 (2014)
Kelly, J.E.: Critical-path planning and scheduling: mathematical basis. Oper. Res. 9(3), 296–320 (1961)
Kim, S., Boyd, S.P., Yun, S., Patil, D.D., Horowitz, M.A.: A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing. Optim. Eng. 8(4), 397–430 (2007)
Kim, S., Pasupathy, R., Henderson, S.G.: A guide to sample average approximation. In: Handbook of Simulation Optimization, pp. 207–243. Springer (2015)
Klotz, E., Newman, A.M.: Practical guidelines for solving difficult mixed integer linear programs. Surv. Oper. Res. Manag. Sci. 18(1–2), 18–32 (2013)
Kuhl, M.E., Tolentino-Peña, R.A.: A dynamic crashing method for project management using simulation-based optimization. In: Proceedings of the 40th Conference on Winter Simulation, pp. 2370–2376. Winter Simulation Conference (2008)
Lamas, P., Demeulemeester, E.: A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations. J. Sched. 19(4), 409–428 (2016)
Li, Z., Ierapetritou, M.: Process scheduling under uncertainty: review and challenges. Comput. Chem. Eng. 32(4–5), 715–727 (2008)
Magnanti, T.L., Wong, R.T.: Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Oper. Res. 29(3), 464–484 (1981)
Mak, W.K., Morton, D.P., Wood, R.K.: Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24(1), 47–56 (1999)
Malcolm, D.G., Roseboom, J.H., Clark, C.E., Fazar, W.: Application of a technique for research and development program evaluation. Oper. Res. 7(5), 646–669 (1959)
Möhring, R.H., Stork, F.: Linear preselective policies for stochastic project scheduling. Math. Methods Oper. Res. 52(3), 501–515 (2000)
Mullen, R.E.: The lognormal distribution of software failure rates: origin and evidence. In: Proceedings Ninth International Symposium on Software Reliability Engineering (Cat. No. 98TB100257), pp. 124–133 (1998)
Naderi, B., Zandieh, M., Fatemi Ghomi, S.M.T.: Scheduling job shop problems with sequence-dependent setup times. Int. J. Prod. Res. 47(21), 5959–5976 (2009)
Oberlender, G.D.: Project Management for Engineering and Construction, vol. 2. McGraw-Hill, New York (1993)
Philpott, A.B., Wahid, F., Bonnans, J.F.: MIDAS: a mixed integer dynamic approximation scheme. Math. Program. 181(1), 19–50 (2020)
Plambeck, E.L., Fu, B., Robinson, S.M., Suri, R.: Sample-path optimization of convex stochastic performance functions. Math. Program. 75(2), 137–176 (1996)
Project Management Institute: A guide to the project management body of knowledge: PMBOK guide. Project Management Institute, Newtown Square, Pennsylvania (2017)
Qi, Y., Sen, S.: The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Program. 161(1–2), 193–235 (2017)
Ross, S.M.: Stochastic Processes, vol. 2. Wiley, New York (1996)
Salmerón, J., Wood, R.K., Morton, D.P.: A stochastic program for optimizing military sealift subject to attack. Military Oper. Res. 14(2), 19–39 (2009)
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM (2009)
Söderlund, J.: Building theories of project management: past research, questions for the future. Int. J. Project Manag. 22(3), 183–191 (2004)
Srinivasan, S., Brooks, J.P., Wilson, J.H.: Batching-based approaches for optimized packing of jobs in the spatial scheduling problem, pp. 243–263. Springer, Cham (2015)
Sundar, K., Nagarajan, H., Misra, S., Lu, M., Coffrin, C., Bent, R.: Optimization-based bound tightening using a strengthened QC-relaxation of the optimal power flow problem. arXiv preprint arXiv:1809.04565 (2018)
Tonchia, S.: Industrial Project Management. Springer, Berlin (2018)
van Slyke, R.M.: Letter to the editor: Monte Carlo methods and the PERT problem. Oper. Res. 11(5), 839–860 (1963)
Wiesemann, W., Kuhn, D., Rustem, B.: Robust resource allocations in temporal networks. Math. Program. 135(1), 437–471 (2012)
Yang, H., Nagarajan, H.: Optimal power flow in distribution networks under stochastic N-1 disruptions. Electr. Power Syst. Res. 189, 106689 (2020)
Yu, G., Qi, X.: Disruption Management: Framework, Models and Applications. World Scientific (2004)
Yuan, W., Wang, J., Qiu, F., Chen, C., Kang, C., Zeng, B.: Robust optimization-based resilient distribution network planning against natural disasters. IEEE Trans. Smart Grid 7(6), 2817–2826 (2016)
Zou, J., Ahmed, S., Sun, X.A.: Stochastic dual dynamic integer programming. Math. Program. 175(1–2), 461–502 (2019)