Thông qua việc mô hình hóa và sử dụng tiêu chuẩn về thứ tự của otomat khoảng, các tác giả đề xuất thuật toán lập lịch và thực nghiệm cho thấy có kết quả tốt về thời gian hoàn thành các công việc so với các phương pháp truyền thống như FIFO (hàng đợi tự nhiên), hàng đợi công việc với tiêu chuẩn hoàn thành nhanh trước (tiếp cận tham lam), hoàn thành lâu trước (tiếp cận an toàn) không đồng bộ. | Journal of Computer Science and Cybernetics, , (2011), 218–228 DURATION AUTOMATON IN SCHEDULING PROGRAMS FOR A CLUSTER COMPUTER SYSTEM∗ BUI VU ANH Faculty of Mathematics, Mechanics and Informatics VNU University of Science Tóm t t. Lập lịch tối ưu cho các công việc chạy trên các máy, trong trường hợp tổng quát, là một bài toán khó và không có thuật toán thực hiện trong thời gian đa thức. Các giải pháp tối ưu và xấp xỉ tối ưu chỉ giải quyết cho các trường hợp riêng với các ràng buộc hạn chế. Thuật toán lập lịch trên 1 và 2 máy được công bố ở [4, 16] được xem như những khởi đầu. Trong [16], tác giả giải bài toán công việc quá hạn có tính đến thời gian chuẩn bị. [4] giải bài toán công việc đến hạn trên trường hợp hai máy, và có thể mở rộng cho trường hợp 3 máy với một số điều kiện trên công việc. Các tác giả khác cũng xem xét các bài toán lập lịch ở các trường hợp riêng như trong [5, 8, 17]. Bài báo ứng dụng mô hình otomat khoảng (Duration Automaton - DA) [1, 2] giải quyết bài toán lập lịch động cho các công việc với thời gian xử lý không chắc chắn trên máy tính ghép cụm - hệ thống gồm nhiều máy tính (nốt tính toán) phối hợp làm việc với nhau. Chúng tôi xét cụm máy tính trong hai trường hợp: các máy giống nhau và khác nhau về cấu hình (tài nguyên của máy tính, một cách hình thức được quy về cấu hình, thể hiện qua thời gian xử lý công việc). Do không biết trước thời gian hoàn thành mỗi công việc, các thuật toán tối ưu đã có sẽ không được áp dụng một cách hiệu quả. Thông qua việc mô hình hóa và sử dụng tiêu chuẩn về thứ tự của otomat khoảng, chúng tôi đề xuất thuật toán lập lịch và thực nghiệm cho thấy có kết quả tốt về thời gian hoàn thành các công việc so với các phương pháp truyền thống như FIFO (hàng đợi tự nhiên), hàng đợi công việc với tiêu chuẩn hoàn thành nhanh trước (tiếp cận tham lam), hoàn thành lâu trước (tiếp cận an toàn) không đồng bộ. Abstract. Optimal schedule for works running on machines, in a general case, is a hard problem and there is no .
