tư liệu Thuật toán nhánh cận giải câu hỏi lập lịch luồng các bước - Phan Thanh Toàn: 108 HNUE JOURNAL OF SCIENCE DOI: 10.18173/2354-1059.2018-0011 Natural Sciences 2018, Volume 63, Issue 3, pp. 108-116 This paper is available online at THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC Phan Thanh Toàn1, Đặng Quốc Hữu2 với Nguyễn cụ Lộc3 1Khoa Sư phạm Kĩ thuật, ngôi trường Đại học Sư Phạm thủ đô 2Trung tâm technology thông tin, trường Đại học thương mại dịch vụ 3Khoa công nghệ Thông tin, trường Đại học Sư phạm tp hà nội Tóm tắt. Điện toán đám mây là một môi trường thiên nhiên dịch vụ dựa vào nền tảng technology thông tin và truyền thông, phần đa tài nguyên trên hệ thống đều được cung cấp cho người sử dụng dưới dạng dịch vụ, và người sử dụng chỉ nên chi trả các tài nguyên thực dùng. Với sự ra đời của technology điện toán đám mây không ít các áp dụng trong lĩnh vực công nghệ thông tin đã tất cả những thay đổi căn bản, đưa từ dạng hỗ trợ sản phẩm đóng gói áp dụng riêng rẽ sang dạng hỗ trợ dịch vụ với được duy trì, quản lý bởi nhà cung cấp dịch vụ thông qua đó giả...


Bạn đang xem: Bài toán xếp lịch công việc

*

Xem thêm: Những Kiểu Tóc Cho Khuôn Mặt Tròn Cắt Tóc Gì, Mặt Tròn Để Tóc Gì

Bạn đang xem ngôn từ tài liệu Thuật toán nhánh cận giải câu hỏi lập kế hoạch luồng các bước - Phan Thanh Toàn, để tải tài liệu về máy các bạn click vào nút download ở trên
hnue.edu.vn Thuật toán nhánh cận giải bài toán lập kế hoạch luồng công việc 109 các bước là nhỏ nhất. Đã có không ít công trình nghiên cứu và phân tích xem xét vụ việc này nhằm tối thiểu hóa các hàm mục tiêu không giống nhau như tổng bỏ ra phí, tổng thời hạn thực thi tại những máy chủ,... Nhưng chưa xuất hiện công trình nào giải quyết và xử lý bài toán cùng với hàm kim chỉ nam là thời hạn thực hiện (makespan). Bài xích báo này nhằm xử lý vấn đề đó. 2. Nội dung nghiên cứu và phân tích 2.1. Hầu hết công trình phân tích liên quan bài toán lập kế hoạch luồng công việc đã được chứng minh là thuộc lớp NP-Khó <5> nghĩa là thời gian để tìm ra giải mã tối ưu tăng rất cấp tốc theo kích thước dữ liệu đầu vào, vì chưng vậy đã có không ít công trình nghiên cứu nhằm kiếm tìm ra giải thuật đúng hoặc khoảng của việc này. N.S.Grigoreva <6> đã lời khuyên thuật toán lập lịch điều phối các tác vụ của luồng công việc vào thực hiện trên một khối hệ thống đa bộ vi xử lí nhằm mục đích cực tiểu hóa thời gian ngừng luồng công việc. Tác giả đã sử dụng kết hợp phương thức nhánh cận cùng kĩ thuật kiếm tìm kiếm nhị phân để tìm ra giải pháp xếp lịch bao gồm thời gian kết thúc luồng công việc là nhỏ dại nhất. Sadhasivam đã đề xuất thuật toán lập kế hoạch luồng công việc dựa trên sự cân bằng tải trong môi trường điện toán đám mây <7>. Thuật toán ko chỉ thỏa mãn nhu cầu các yêu mong từ người sử dụng mà còn hỗ trợ khả năng sử dụng tài nguyên một cách hiệu quả. Đây là thuật toán theo hướng nâng cao hiệu quả thương mại dịch vụ dựa bên trên Meta-heuristic. Những tác mang trong bài báo <8> đã khuyến nghị thuật toán EGA (Enhanced Genetic Algorithm) lập định kỳ bằng phương pháp di truyền. Vào công trình những tác giả thực hiện thuật toán Enhanced Max Min trong bước khởi tạo ra quần thể nhằm mục đích tìm ra những cá thể xuất sắc cho quá trình tiến hóa. Pandey <9> đã khuyến cáo thuật toán lập kế hoạch luồng công việc PSO Heuristic (Particle Swarm Optimization Heuristic – PSO_H) trong môi trường thiên nhiên điện toán đám mây dựa trên kế hoạch tối ưu bày đàn. Rajkumar đã khuyến cáo một thuật toán lập định kỳ phân cấp cho <10> và chuyển vào những tham số thương mại & dịch vụ khác nhau, chẳng hạn như thời hạn đáp ứng. Thuật toán áp dụng tham số này như một quyền ưu tiên nhằm lựa chọn những tác vụ lập lịch. Cao và những đồng nghiệp đã trình diễn thuật toán lập lịch dựa trên giải thuật ABC (Activity Based Costing) <11>. Thuật toán này gán mức ưu tiên cho từng tác vụ vào luồng các bước theo các tham số về thời gian, không gian, những tài nguyên và đưa ra phí, quá trình lập định kỳ sẽ thực hiện mức ưu tiên này nhằm quyết định các tác vụ được chọn trong quy trình lập lịch. Selvi và các cộng sự đã khuyến nghị thuật toán lập kế hoạch luồng các bước trong môi trường xung quanh điện toán lưới (Grid) <12>, vào công trình tác giả đã vận dụng thuật toán tiến hóa vi phân (DE) vào giải bài toán lập kế hoạch luồng quá trình trên môi trường xung quanh điện toán lưới nhằm cực tè thời gian dứt luồng các bước (makespan), trong công trình tác giả đã chỉ ra giá trị Makespan tìm kiếm được bởi thuật toán khuyến nghị là nhỏ hơn so với thuật toán PSO. Xu và các cộng sự đã khuyến nghị thuật toán COODE <13> (Current Optimum Opposition-based Differential Evolution) nhằm mục đích tìm giá chỉ trị tối ưu cho các hàm số dựa theo phương thức tiến hóa vi phân đối xứng, trong công trình tác giả đã lời khuyên công thức tìm điểm đối xứng của một điểm dựa theo giá bán trị tối ưu bây giờ nhằm biến đổi toán tử tự dưng biến trong phương pháp tiến hóa vi phân và người sáng tác đã đối chiếu thuật toán COODE với các thuật toán DE cùng ODE, công dụng đã đã cho thấy thuật toán khuyến nghị COODE giỏi hơn các thuật toán đối sánh. 2.2. Quy mô toán học vấn đề lập lịch luồng quá trình trong môi trường điện toán đám mây trả sử cần sắp xếp lịch biểu cho 1 luồng quá trình trong môi trường thiên nhiên đám mây với các giả thiết như sau: Phan Thanh Toàn, Đặng Quốc Hữu và Nguyễn nỗ lực Lộc 110 - Luồng các bước được biểu diễn bởi đồ thị G = (V, E), cùng với V là tập đỉnh của đồ vật thị, mỗi đỉnh biểu hiện cho một tác vụ. - T =T1, T2,,TM là tập các tác vụ, M là con số tác vụ của luồng công việc đang xét. - E là tập cạnh thể hiện mối quan hệ cha-con giữa những tác vụ. Cạnh (Ti, Tj)  E cho thấy thêm tác vụ Ti là thân phụ của tác vụ Tj, tài liệu đầu ra của Ti vẫn là tài liệu đầu vào mang đến tác vụ Tj (xem Hình 1). - Tập sever của đám mây kí hiệu là S = S1, S2,.,SN, N là số lượng máy công ty của đám mây. - mỗi tác vụ hoàn toàn có thể được thực hiện trên một máy chủ bất kì, máy chủ đó bắt buộc thực hiện toàn thể tác vụ từ đầu đến cuối. - cân nặng tính toán (Workload) của tác vụ Ti kí hiệu là Wi với đơn vị chức năng đo là flop (floating point operations: phép tính bên trên số thực lốt phảy động). Wi được cho trước (i = 1,2, M) - tốc độ tính toán của dòng sản phẩm chủ Si, đơn vị là MI/s (million instructions/second), được kí hiệu vì chưng P(Si), là quý giá được mang lại trước (i = 1,2, M) - giữa hai sever Si, Sj bất kỳ (1≤i,j≤N) gồm một con đường truyền với băng thông, đơn vị là Megabit/s, được biểu hiện bởi hàm hai biến đổi B() được định nghĩa như sau: B: S×S → R+ (Si,Sj) → B(Si,Sj) - mang thiết hàm băng thông B() thỏa mãn nhu cầu các điều kiện sau:  B(Si,Si) = ∞ : thời gian truyền trên chỗ bằng không  B(Si,Sj) = B(Sj,Si) : tốc độ truyền nhì chiều đều bằng nhau  cực hiếm B(Si,Sj) được đến trước (i,j). - cân nặng dữ liệu vì chưng tác vụ Ti chuyển tới tác vụ Tj, kí hiệu là Dij với đơn vị chức năng là Megabit, là giá bán trị mang lại trước (i,j). - Mỗi phương án xếp lịch tiến hành luồng các bước tương đương với cùng một hàm f() f : T → S Ti → f(Ti) trong các số ấy f(Ti) là trang bị chủ chịu trách nhiệm thực thi tác vụ Ti Biến quyết định và hàm kim chỉ nam  sử dụng biến nhị phân ; với trường hợp tác vụ Tk được thực hiện trên máy chủ Sj  phát triển thành biểu diễn cân nặng dữ liệu được truyền từ máy chủ Si đến máy chủ Sj mang lại tác vụ Tk nếu như  txcosti,j là ngân sách chi tiêu truyền một đơn vị dữ liệu từ sever Si cho Sj mang lại tác vụ Tk, nếu với  excostj biểu diễn chi phí sử dụng lắp thêm chủ tính toán Sj để tiến hành tác vụ Tk trường hợp  biểu diễn thời hạn thực hiện tại tác vụ Tk trên sever Sj nếu Hình 1: Đồ thị màn trình diễn một luồng các bước với 5 tác vụ 1 4 3 2 5 Thuật toán nhánh cận giải câu hỏi lập kế hoạch luồng các bước 111 Hàm kim chỉ nam kjkjjkjTkSjijikji xextimetexxttxdC  coscos,,,, C → min những điều kiện ràng buộc : (a) kT, jS ; ; trở nên nhị phân nhận giá trị 0 hoặc 1 (b) kT, i,jS ; ; khối lượng dữ liệu truyền giữa các tác vụ bảo đảm lớn hơn hoặc bằng 0 (c) kT ; ; tổng cân nặng dữ liệu truyền tới tác vụ Tk phải lớn hơn hoặc bằng 0 (d) i,jS ; ; giá thành truyền thông lớn hơn hoặc bởi 0 (e) kT, jS ; ; chi tiêu thực thi tác vụ to hơn hoặc bằng 0 (f) kT, jS ; ; thời hạn thực hiện tại tác vụ bảo đảm lớn hơn hoặc bởi 0 (g) ∑ ; đảm bảo mỗi tác vụ Tk chỉ được triển khai trên một thứ chủ xác minh (h) ∑ ; tổng trọng lượng dữ liệu được đưa tới tác vụ Tk (i) ∑ ∑ ; đảm bảo tính cân bằng giữa dữ liệu vào cùng ra của những tác vụ trong luồng các bước 2.3. Phương án đề xuất Nhánh cận là 1 trong những kĩ thuật chuyên chú có sử dụng hàm cận dưới nhằm mục đích cắt nhánh để giảm bớt không gian kiếm tìm kiếm trong quy trình duyệt. Thuật toán cẩn thận nhánh cận tất cả hai thủ tục chính:  Phân nhánh: phân hoạch tập các phương án ra thành các tập con với kích cỡ càng ngày càng nhỏ tuổi cho đến lúc thu được phân hoạch tập các phương án ra thành các tập con một phần tử  Tính cận: gửi ra phương pháp tính cận mang đến giá trị hàm phương châm của việc trên mỗi tập nhỏ trong phân hoạch của tập các phương án. Thuật toán nhánh cận đề xuất Biểu diễn lời giải Mỗi cách thực hiện xếp lịch được màn biểu diễn bởi một vector có độ dài ngay số tác vụ vào luồng công việc. Giá bán trị khớp ứng với mỗi vị trí i trong vector màn biểu diễn số hiệu máy chủ thực thi tác vụ i. Ví dụ: Xét luồng quá trình với 5 tác vụ T = T1, T2,,T5, tập máy chủ gồm 3 sản phẩm S = S1, S2, S3. Khi đó phương án xếp lịch (1,2,1,3,2) được biểu diễn như sau: T1 T2 T3 T4 T5 S1 S2 S1 S3 S2 Hàm tính cận dưới mang đến phương án thành phần Mỗi lời giải của bài toán là một trong những vector M chiều x = (x1, x2,,xM); với xi  S. Gọi cmin = minP(Si); iS; giá chỉ trị nhỏ dại nhất về năng lực thống kê giám sát trong số các máy nhà của khối hệ thống đám mây. Cận dưới cho phương án phần tử (x1, x2,,xL) tương xứng với việc bố trí tập L tác vụ TL =T1, T2,,TL tiến hành trên những máy chủ khớp ứng SL= (Sx1, Sx2,..,SxL). Lúc đó chi phí thực hiện tại của phương án thành phần là: kjkjjkjTkSjijikji xextimetexxttxdL coscos,,,, Phan Thanh Toàn, Đặng Quốc Hữu với Nguyễn gắng Lộc 112 Hàm cận dưới của phương án bộ phận (x1, x2,,xL) được xem theo công thức tiếp sau đây LTTkSjkjkjj xextimetexCkg,min cos)(  chứng minh: Ta tất cả ∑ ∑ ∑ = ∑ ∑ ∑ ( ) ∑ ( ) ∑ ∑ bởi vậy, g(k) là hàm cận bên dưới của lời giải phần tử cấp k. Thuật toán đề xuất Function cost(x1, x2,..,xM) begin return kjkjjkjTkSjijikji xextimetexxttxdLcoscos,,,, ; end; Procedure SchedulingBranch(k) begin for j:=1 to lớn M bởi if UCV(j,k) then begin a:=j; if i=M then Ghinhan; else if g(k)5144_11_toan_4651_2123671.pdf