- Nghiên cứu về hệ thống hàng đợi và xây dựng chương trình mô phỏng mô hình trên công cụ. - mô phỏng GPSS. - Abstract: Trình bày cơ sở lý thuyết về hệ thống hàng đợi: đưa ra cơ sở lý thuyết về hệ thống hàng đợi, bao gồm: các yếu tố của hệ thống phục vụ (dòng vào, dòng ra, hàng chờ, kênh phục vụ), các quá trình Markov và trạng thái của hệ thống. - Với sự phát triển của khoa học máy tính, phương pháp mô phỏng chứng tỏ những khả năng tốt cho việc giải bài toán hàng đợi, ngoài phương pháp toán học thuần túy có thể tìm ra lời giải của bài toán hàng đợi khi dựa vào hệ phương trình trạng thái với các điều kiện ban đầu.. - Nghiên cứu hiện trạng một số công cụ mô phỏng các bài toán hàng đợi: giới thiệu một số ngôn ngữ, công cụ mô phỏng được sử dụng để giải quyết các bài toán hàng đợi.. - Tìm hiểu qua về ngôn ngữ đặc tả P/T net, và ngôn ngữ General Purpose Simulation System – GPSS, tiến hành so sánh, đánh giá hai ngôn ngữ đó. - GPSS có ưu điểm hơn P/T net khi giải bài toán hàng đợi bằng phương pháp mô phỏng. - Tìm hiểu về ngôn ngữ GPSS và công cụ GPSS World: đề cập cụ thể, chi tiết về cấu trúc của một thao tác lệnh, các đối tượng và các khối (block) cơ bản trong GPSS. - Trình bày các bước tiến hành mô phỏng một bài toán hàng đợi khi sử dụng phương pháp mô phỏng qua công cụ GPSS World. - Áp dụng ngôn ngữ GPSS vào bài toán thực tế: bài toán đánh giá hoạt động của tổng đài điện thoại, và đánh giá hoạt động của một phòng xử lý thông tin tại nơi làm việc.. - Mô hình hàng đợi. - Ngôn ngữ GPSS Content. - Cơ sở lý thuyết về hệ thống hàng đợi. - Chương 1 đưa ra cơ sở lý thuyết về hệ thống hàng đợi, bao gồm: các yếu tố của hệ thống phục vụ (dòng vào, dòng ra, hàng chờ, kênh phục vụ), các quá trình Markov và trạng thái của hệ thống. - Với sự phát triển của khoa học máy tính, phương pháp mô phỏng chứng tỏ những khả năng tốt cho việc giải bài toán hàng đợi, ngoài phương pháp toán học thuần túy mà chúng ta có thể tìm ra lời giải của bài toán hàng đợi khi dựa vào hệ phương trình trạng thái với các điều kiện ban đầu.. - Các mô hình hàng đợi trong thực tế rất đa dạng, ví vụ như bãi đỗ xe, quán ăn, nhà ga, sân bay… Từ thực tế, chúng ta lập ra mô hình toán học của hệ thống hàng đợi.. - 1 Mô hình hóa các yếu tố của một hệ thống hàng đợi. - Bảng 1: Các tham số đặc trưng trong hệ thống hàng đợi STT Ký. - 1 N(t) Số khách hàng ở trong hệ thống tại thời điểm t.. - 2 λ Dòng yêu cầu đầu vào, đặc trưng bởi tốc độ đến (arrival rate) của khách hàng. - 3 µ Dòng yêu cầu đầu ra, là các yêu cầu đã được và không được phục vụ, đặc trưng bởi tốc độ tối đa phục vụ. - µ 4 N q (t) Hàng chờ, đặc trưng bởi số lượng khe để. - phục vụ cho xếp hàng. - 5 W i Thời gian xếp hàng của khách hàng thứ i trong hàng chờ. - 6 N s (t) Kênh phục vụ và các cách phục vụ, đặc trưng bởi số lượng kênh, cụ thể có c kênh, cũng có nghĩa là đang có c khách hàng đang được phục vụ. - 7 τ i Thời gian phục vụ với khách hàng thứ i 8 τ Thời gian phục vụ trên tất cả các máy phục. - 9 T Tổng thời gian phục vụ của toàn bộ hệ thống. - Chương 1 cũng đề cập tới biểu diễn toán học của hệ thống hàng đợi theo Kendall. - Bảng 2: Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi. - 3 m Số lượng máy phục vụ.. - 4 K Dung lượng của hệ thống, là số khách hàng lớn nhất có mặt mà hệ thống phục vụ được, có tính đến cả khách hàng đang chờ. - Chương 1 trình bày về các quá trình Markov, một kiến thức nền quan trọng của bài toán hàng đợi, và đưa ra công thức Chapman – Kolmogorov liên quan đến xác suất trạng thái của hệ thống và tốc độ dịch chuyển từ trạng thái i sang trạng thái j nào đó cho một chuỗi Markov với thời gian liên tục, được mô tả như sau:. - Tỉ suất để quá trình X(t) sống ở trạng thái i là. - Khi X(t) nhảy từ trạng thái i sang trạng thái j khả năng xảy ra biến cố đó là. - Tốc độ mà quá trình X(t) nhảy từ trạng thái i sang trạng thái j được tính bằng. - Khi đó, chúng ta thiết lập được hệ phương trình vi phân Chapman – Kolmogorov. - 2 Mô tả sự chuyển trạng thái của chuỗi Markov. - Để giải được hệ phương trình (1.30), chúng ta cần biết rõ các điều kiện ban đầu p j (0) =0, p i (0)=1 với mọi i#j. - j Đây là phương trình trạng thái của hệ thống.. - Chương 2: Hiện trạng một số công cụ mô phỏng các bài toán hàng đợi.. - Chương này giới thiệu một số ngôn ngữ, công cụ mô phỏng được sử dụng để giải quyết các bài toán hàng đợi. - Chúng ta sẽ tìm hiểu qua về ngôn ngữ đặc tả P/T net, và ngôn ngữ General. - Purpose Simulation System – GPSS, tiến hành so sánh, đánh giá hai ngôn ngữ đó. - GPSS có ưu điểm hơn P/T net khi chúng ta giải bài toán hàng đợi bằng phương pháp mô phỏng.. - Đầu tiên, chương 2 đề cập đến ngôn ngữ đặc tả Petri nets, gồm khái niệm, mô tả toán học, các đặc trưng của chúng.. - là trạng thái và sự nhảy trạng thái, biểu thị bởi hình chữ nhật hoặc ô vuông, kí hiệu là trạng thái T. - là các đường dẫn trực tiếp liên kết giữa các vị trí P và các trạng thái T. - Tiếp theo, chương 2 đề cập sơ qua ngôn ngữ GPSS, ra đời tại IBM với điểm mạnh là quản lý theo các BLOCK và các TRANSACTION, cùng với ngôn ngữ lập trình bậc cao Matlab, ngôn ngữ lập trình Java, bộ công cụ lập trình Visual Studio.net, và tiến hành so sánh sơ qua về P/T net và GPSS.. - Chương 3 Tìm hiểu về ngôn ngữ GPSS và công cụ GPSS World. - Chương này đề cập cụ thể, chi tiết về cấu trúc của một thao tác lệnh, các đối tượng và các khối (block) cơ bản trong GPSS. - Đồng thời, chương 3 trình bày các bước tiến hành mô phỏng một bài toán hàng đợi khi sử dụng phương pháp mô phỏng qua công cụ GPSS World.. - Các thao tác lệnh – blocks (gọi tắt là BLOCK) đảm bảo logic chức năng hoạt động của mô hình. - Các thao tác khai báo, định nghĩa đối tượng dùng để xác định các tham biến của các đối tượng nào đó trong GPSS. - Ví dụ của các tham biến có thể là số kênh phục vụ trong hệ đa kênh, số hàng và số cột của ma trận…. - Các thao tác lệnh điều khiển dùng để kiểm soát và điều khiển quá trình mô phỏng (mô hình được vận hành).. - Các thao tác lệnh vận hành cho phép điều khiển hoạt động của môi trường tích hợp GPSS/PC. - Đây là các thao tác hoạt động trên phần mềm, sao cho nội dung của chương trình ( source code) được chạy tốt để ra kết quả.. - GPSS có 7 nhóm đối tượng làm việc:. - Đối tượng động: là các transactions, bản chất là nguyên mẫu của “yêu cầu” trong thuật ngữ của hệ thống phục vụ đám đông.. - Đối tượng điều hành: Đối tượng điều hành (Block Entities) của GPSS còn được gọi là các khối (Blocks) tương ứng với thực thi lệnh – blocks của chương trình nguồn và cũng thiết lập logic các hoạt động của mô hình bằng cách đưa ra các chỉ thị đối với các Transactions: sẽ đi tới đâu và làm gì tiếp theo.... - Đối tượng thuộc về thiết bị: Đối tượng thuộc về thiết bị (Facility Entities) tương tự như các máy phục vụ và các thiết bị khác của hệ thống thực.. - Đối tượng tĩnh: Các đối tượng tĩnh được sử dụng để thu thập và xử lý các dữ liệu thống kê về hoạt động của mô hình: Queue Entities và Table Entities.. - Đối tượng tính toán: Function và Variable. - Đối tượng lưu trữ: Các đối tượng kiểu này gồm có Savevalue Entities, Matrix Entities.. - Đối tượng nhóm: Các đối tượng thuộc nhóm gồm có Numeric Group Entities. - Chương 3 đề cập sâu vào Transaction với các đặc trưng liên quan đến chuỗi sự kiện và thiết lập các bước giải bài toán hàng đợi dựa trên công cụ mô phỏng GPSS.. - Transaction là các đối tượng động trong GPSS với tập các thuộc tính, các thuộc tính này được gọi là các Parameters. - Một transaction đơn lẻ có thể bao gồm vài thực thể riêng, giống như là nhiều người “được phục vụ” bởi một thang máy. - Transaction có thể xem như là một “yêu cầu”, hay một “sự kiện” trong hệ thống phục vụ đám đông.. - Áp dụng ngôn ngữ GPSS vào bài toán thực tế. - Bài toán đánh giá hoạt động của một phòng xử lý thông tin tại nơi làm việc. - Qua đó, chúng ta thấy được một phần nào đó hiệu quả hoạt động của hai đối tượng mà chúng ta khảo sát.. - Luận văn tập trung làm rõ việc giải bài toán hàng đợi qua ngôn ngữ mô phỏng GPSS. - Đưa ra Cở sở lý thuyết về hệ thống hàng đợi: Mô hình, tham số, các quy luật liên quan đến trạng thái của hệ thống hàng đợi.. - Tìm hiểu qua về ngôn ngữ đặc tả P/T net mô tả các hệ thống phân tán.. - Nghiên cứu ngôn ngữ mô phỏng GPSS: các định nghĩa, cấu trúc của ngôn ngữ GPSS. - Làm việc trên công cụ GPSS World dành cho sinh viên.. - Xây dựng các bước phân tích, mô phỏng hệ thống hàng đợi.. - Áp dụng ngôn ngữ GPSS vào bài toán thực tiễn, và so sánh với kết quả tính toán trên lý thuyết.. - Chưa tìm hiểu được hết tất cả các ứng dụng của ngôn ngữ mô phỏng GPSS trong các bài toán thực tiễn.. - Chỉ làm việc trên công cụ GPSS World dành cho sinh viên, nên kết quả chưa có sự so sánh với các phiên bản GPSS khác.. - [1] Lê Quang Minh, Phan Đăng Khoa, “Công cụ GPSS cho bài toán mô phỏng các hệ thống phục vụ đám đông”, Báo cáo tổng hợp đề tài cấp ĐHQGHN, Viện Công nghệ thông tin – Đại học Quốc Gia Hà Nội, 2010.. - GPSS – Getting Started, University of London, 2005.