Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật Toán Xấp Xỉ cho Lịch Trình Đa Bộ Xử Lý dưới Tình Huống Bất Định
Tóm tắt
Được thúc đẩy bởi các ứng dụng trong tính toán lưới và quản lý dự án, chúng tôi nghiên cứu lịch trình đa bộ xử lý trong các kịch bản mà có sự không chắc chắn trong việc thực hiện thành công các công việc khi được giao cho các bộ xử lý. Chúng tôi xem xét vấn đề lập lịch đa bộ xử lý dưới sự không chắc chắn, trong đó chúng tôi được cho n công việc đơn vị thời gian và m máy, một đồ thị có hướng và không vòng C thể hiện các phụ thuộc giữa các công việc, và đối với mỗi công việc j và máy i, xác suất p
ij
của việc hoàn thành thành công công việc j khi được lên lịch trên máy i trong bất kỳ bước cụ thể nào. Mục tiêu của vấn đề là tìm một lịch trình tối thiểu hóa thời gian hoàn thành kỳ vọng, tức là thời gian kỳ vọng mà tất cả các công việc được hoàn tất. Vấn đề lập lịch đa bộ xử lý dưới sự không chắc chắn được giới thiệu bởi Malewicz và được chứng minh là NP-hard ngay cả khi tất cả các công việc là độc lập. Trong bài báo này, chúng tôi giới thiệu các thuật toán xấp xỉ thời gian đa dạng cho vấn đề, cho các trường hợp đặc biệt của đồ thị C. Chúng tôi thu được một xấp xỉ O(log n) cho trường hợp các công việc độc lập, một xấp xỉ O(log mlog nlog (n+m)/log log (n+m)) khi C là một tập hợp các chuỗi không giao nhau, một xấp xỉ O(log mlog 2
n) khi C là một tập hợp các cây có hướng ra hoặc vào, và một xấp xỉ O(log mlog 2
nlog (n+m)/log log (n+m)) khi C là một khu rừng có hướng.
Từ khóa
#lịch trình đa bộ xử lý #bất định #xấp xỉ #đồ thị có hướng #NP-hardTài liệu tham khảo
Applegate, D., Cook, B.: A computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2), 149–156 (1991)
Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Nashua (1997)
Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–509 (1952)
Chudak, F., Shmoys, D.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30 (1999)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill, Cambridge (2001)
Crutchfield, C., Dzunic, Z., Fineman, J., Karger, D., Scott, J.: Improved approximations for multiprocessor scheduling under uncertainty. In: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, pp. 246–255 (2008)
Fernandez, A., Armacost, R., Pet-Edwards, J.: A model for the resource constrained project scheduling problem with stochastic task durations. In: 7th Industrial Engineering Research Conference Proceedings (1998)
Fernandez, A., Armacost, R., Pet-Edwards, J.: Understanding simulation solutions to resource constrained project scheduling problems with stochastic task durations. Eng. Manag. J. 10(4), 5–13 (1998)
Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure, 2nd edn. Morgan Kaufmann, San Francisco (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco (1979)
Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. (BSTJ) 45, 1563–1581 (1966)
Hall, L.: Approximation algorithms for scheduling. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems. PWS, Boston (1997)
Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. Eur. J. Oper. Res. 165(2), 289–306 (2005)
Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27, 713–721 (1956)
Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM J. Comput. 30 (2000)
Kumar, V., Marathe, M., Parthasarathy, S., Srinivasan, A.: Scheduling on unrelated machines under tree-like precedence constraints. In: International Workshop on Approximation Algorithms for Combinatorial Optimization (2005)
Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam (1991)
Leighton, F.T., Maggs, B.M., Rao, S.: Packet routing and job-shop scheduling in O (congestion + dilation) steps. Combinatorica 14(2), 167–186 (1994)
Lenstra, J., Shmoys, D., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46 (1990)
Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 25–34, San Diego, CA, USA (2007)
Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. Technical report, March 2007. arXiv:cs/0703100v1
Malewicz, G.: Parallel scheduling of complex dags under uncertainty. In: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 66–75, Las Vegas, Nevada, USA (2005)
Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs (2002)
Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988)
Raghavan, P., Thompson, C.: Provably good routing in graphs: Regular arrays. In: ACM Symposium on Theory of Computing (STOC) (1985)
Raghavan, P., Thompson, C.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987)
Schmidt, J., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8 (1995)
Schrijver, A.: Theory of Linear and Integer Programming. Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1986)
Shmoys, D., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23 (1994)
Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. Assoc. Comput. Mach. (JACM) 48(2), 206–242 (2001)
Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 589–590, Washington, DC, USA (2001)