Nghiên Cứu Công Cụ Mô Phỏng GPSS Và Petri Net Cho Bài Toán Hệ Thống Hàng Đợi

• Tác giả: Lê Xuân Hiếu
• Người hướng dẫn: TS. Lê Quang Minh
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên Cứu Mô Phỏng Hệ Thống Hàng Đợi Bằng GPSS Và Petri Net
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: Thái Nguyên

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ HỆ THỐNG HÀNG ĐỢI
• 1.1. Vai trò của hệ thống hàng đợi
• 1.2. Mô tả hệ thống hàng đợi
• 1.3. Mô hình hóa một hệ thống hàng đợi
• 1.4. Công thức Little
• 1.5. Hệ thống hàng đợi theo cách viết của Kendall và các phân phối liên quan
• 1.6. Các yếu tố của hệ thống hàng đợi
• 1.6.1. Dòng yêu cầu đầu vào
• 1.6.2. Kênh phục vụ
• 1.6.3. Dòng yêu cầu đầu ra
• 1.6.4. Các quy luật hoạt động của hệ thống phục vụ
• 1.6.5. Trạng thái hệ thống phục vụ
• 1.6.5.1. Định nghĩa về trạng thái của hệ thống phục vụ
• 1.6.5.2. Quá trình thay đổi trạng thái của hệ thống phục vụ
• 1.6.5.3. Qui tắc thiết lập hệ phương trình trạng thái
• 2. CHƯƠNG 2: CÁC CÔNG CỤ MÔ PHỎNG BÀI TOÁN HÀNG ĐỢI
• 2.1. Quy trình chung của việc phân tích, mô phỏng hệ thống hàng đợi
• 2.2. Một số ngôn ngữ lập trình bậc cao dùng để giải quyết bài toán hàng đợi
• 2.2.1. Ngôn ngữ lập trình Matlab
• 2.2.2. Ngôn ngữ lập trình Java
• 2.2.3. Ngôn ngữ lập trình C++ và bộ công cụ Visual Studio
• 2.3. Ngôn ngữ mô phỏng GPSS và công cụ GPSS World
• 2.3.1. Giới thiệu về ngôn ngữ GPSS
• 2.3.2. Sự ra đời của ngôn ngữ GPSS
• 2.3.3. Những ưu điểm của ngôn ngữ GPSS
• 2.3.4. Các ứng dụng của công cụ mô phỏng GPSS World
• 2.3.5. GPSS World Student Version
• 2.4. Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net
• 2.4.1. Các khái niệm cơ bản về Petri-net
• 2.4.2. Mô tả toán học về Petri-net
• 2.4.3. Một số thuộc tính của Petri-net
• 2.4.4. Một số công cụ sử dụng ngôn ngữ Petri-net
• 2.4.5. Ứng dụng của mạng Petri-net
• 2.4.6. So sánh giữa P/T net và GPSS
• 3. CHƯƠNG 3: SỬ DỤNG GPSS VÀ PETRI NET TRONG BÀI TOÁN MÔ PHỎNG HỆ THỐNG HÀNG ĐỢI
• 3.1. Mô phỏng bài toán hàng đợi không ưu tiên
• 3.1.1. Phát biểu bài toán
• 3.1.2. Phân tích bài toán
• 3.1.3. Phân tích kết quả của bài toán bằng lý thuyết hàng đợi
• 3.1.4. Mô phỏng bài toán bằng công cụ GPSS WORLD
• 3.1.5. Mô phỏng bài toán bằng mô hình mạng Petri
• 3.2. Mô phỏng bài toán hàng đợi có ưu tiên
• 3.2.1. Phát biểu bài toán
• 3.2.2. Phân tích bài toán
• 3.2.3. Phân tích kết quả bài toán bằng lý thuyết hàng đợi
• 3.2.4. Mô phỏng bài toán bằng GPSS World
• 3.2.5. Mô phỏng bài toán bằng mô hình mạng Petri
• 3.2.6. Đánh giá các kết quả mô phỏng
• KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO

I. Tổng Quan Mô Phỏng Hệ Thống Hàng Đợi GPSS Petri Net

Trong thực tế, rất nhiều hệ thống được hình thành từ các yêu cầu ngẫu nhiên. Các hệ thống như xếp hàng mua vé, thanh toán ở siêu thị, máy bay cất cánh, mạng máy tính đều là hệ thống hàng đợi. Vận hành và tính toán đặc trưng của hệ thống hàng đợi rất quan trọng. Mô hình toán học giúp giảm chi phí. Đặc tả hệ thống hàng đợi dự báo kết quả quan trọng. Mô hình mô phỏng cần đảm bảo quá trình làm việc của các phần tử, logic và quy tắc tương tác. Sử dụng các ngôn ngữ lập trình truyền thống để xây dựng mô hình mô phỏng rất phức tạp. Do đó, cần các ngôn ngữ mô phỏng chuyên dụng như GPSS và Petri Net. Hiện nay, các phương pháp đánh giá, mô phỏng được sử dụng rộng rãi là mô hình hóa, mô hình hàng đợi, mạng Petri, GPSS, đồ thị và mô hình lai ghép. "Việc xây dựng mô hình toán học cho mỗi hệ thống là rất cần thiết để giảm chi phí tối đa cho các hoạt động đặc tả nó."

1.1. Giới Thiệu Lý Thuyết Hàng Đợi và Ứng Dụng

Lý thuyết hàng đợi được ứng dụng rộng rãi trong nhiều lĩnh vực như viễn thông, hàng không, đường sắt, kiểm soát giao thông, đánh giá hiệu năng hệ thống máy tính, y tế... Nghiên cứu đảm bảo hiệu quả của hệ thống hàng đợi là mục đích của lý thuyết hàng đợi. Các khách hàng phải dùng chung tài nguyên, chờ đợi, đôi khi bị từ chối phục vụ. Các nghiên cứu cần đảm bảo tính hiệu quả và tối ưu của hệ thống.

1.2. Khái Niệm Cơ Bản về Mô Hình Hàng Đợi

Mô hình hàng đợi bao gồm: khách đến, khách bỏ đi, khách xếp hàng, máy phục vụ, khách rời khỏi hệ thống. Các yếu tố này tóm lược thành dòng yêu cầu đầu vào, hệ thống phục vụ, các máy phục vụ và dòng các yêu cầu đầu ra. Hàng đợi xuất hiện khi vượt quá khả năng đáp ứng của dịch vụ. Thời gian chờ phụ thuộc vào số lượng kênh phục vụ và quy tắc phục vụ của hệ thống.

II. Thách Thức Phân Tích Hiệu Năng Hệ Thống Hàng Đợi Phức Tạp

Việc phân tích hiệu năng hệ thống hàng đợi phức tạp là một thách thức lớn. Các hệ thống hàng đợi có quy mô lớn, nhiều yếu tố ảnh hưởng lẫn nhau. Tính toán các đặc trưng của hệ thống để tư vấn cho nhà quản lý là cần thiết. Việc đặc tả và tính toán một số đặc điểm của hệ thống hàng đợi có thể đem lại các kết quả dự báo quan trọng cho hệ thống. Do tính chất của hệ thống, quy mô của hệ thống có thể là những yếu tố ảnh hưởng đến việc lựa chọn công cụ. Chính vì vậy, yêu cầu lựa chọn, so sánh, đánh giá các công cụ mô phỏng là một đề tài mang ý nghĩa khoa học và thực tiễn cao.

2.1. Các Yếu Tố Ảnh Hưởng Đến Hiệu Năng Hàng Đợi

Thời gian chờ đợi phụ thuộc vào số lượng giao dịch, số kênh cung ứng dịch vụ, thời gian phục vụ. Các yếu tố như dòng vào, dòng ra, số lượng máy chủ, quy tắc hàng đợi ảnh hưởng lớn đến hiệu suất hệ thống. Phân tích các yếu tố giúp tối ưu hóa hoạt động của hệ thống.

2.2. Giới Hạn Của Phương Pháp Phân Tích Truyền Thống

Phương pháp phân tích truyền thống gặp khó khăn khi xử lý hệ thống phức tạp. Các phương pháp này thường đơn giản hóa mô hình, bỏ qua các yếu tố ngẫu nhiên. Việc xây dựng mô hình mô phỏng bằng cách sử dụng các ngôn ngữ lập trình truyền thống là khá phức tạp, khó khăn do khi lập trình, chúng ta phải quản lý các sự kiện theo một mô hình nhiều sự kiện xảy ra đồng thời (song song) với việc xây dựng các hàm tạo ngẫu nhiên các sự kiện (random) cũng không hề đơn giản, chính vì vậy đã xuất hiện các ngôn ngữ mô phỏng chuyên dụng.

III. Phương Pháp Mô Phỏng GPSS World và Mạng Petri

Để giải quyết các thách thức trên, việc sử dụng các công cụ mô phỏng như GPSS World và mạng Petri là cần thiết. GPSS (General Purpose Simulation System) là ngôn ngữ mô phỏng chuyên dụng. Mạng Petri là mô hình toán học để mô tả hệ thống. Cả hai công cụ này đều có ưu điểm riêng, phù hợp với các loại bài toán khác nhau. Hiện nay có một số phương pháp đánh giá, mô phỏng được sử dụng rộng rãi và có hiệu quả trên thực tế là phương pháp mô hình hoá và các mô hình được sử dụng hiện nay là mô hình hàng đợi, mạng Petri, General Purpose Simulation System (GPSS), đồ thị, và các mô hình lai ghép.

3.1. Ưu Điểm và Ứng Dụng của GPSS World Trong Mô Phỏng

GPSS World là công cụ mạnh mẽ để mô phỏng hệ thống rời rạc. Nó cung cấp cú pháp đơn giản, dễ học và sử dụng. Nó được sử dụng rộng rãi trong mô phỏng hệ thống sản xuất, hệ thống dịch vụ, và quản lý hàng đợi. "Hiện nay có một số phương pháp đánh giá, mô phỏng được sử dụng rộng rãi và có hiệu quả trên thực tế là phương pháp mô hình hoá và các mô hình được sử dụng hiện nay là mô hình hàng đợi, mạng Petri, General Purpose Simulation System (GPSS), đồ thị, và các mô hình lai ghép."

3.2. Mô Hình Hóa Bằng Mạng Petri Khái Niệm và Ưu Điểm

Mạng Petri là mô hình toán học trực quan để mô tả hệ thống đồng thời. Nó có khả năng mô tả các trạng thái, sự kiện và mối quan hệ giữa chúng. Mạng Petri được sử dụng trong mô hình hóa hệ thống điều khiển, hệ thống nhúng và hệ thống sản xuất linh hoạt. Các khái niệm cơ bản về Petri-net . Mô tả toán học về Petri-net.

3.3. So Sánh GPSS và Petri Net Lựa Chọn Công Cụ Phù Hợp

GPSS phù hợp với hệ thống rời rạc, hướng sự kiện. Petri Net phù hợp với hệ thống đồng thời, hướng trạng thái. Lựa chọn công cụ phụ thuộc vào tính chất của hệ thống và mục tiêu của mô phỏng. Mạng Petri có tính trực quan hơn, nhưng GPSS có nhiều tính năng hỗ trợ mô phỏng hơn.

IV. Ứng Dụng Thực Tế Mô Phỏng Hàng Đợi Với GPSS và Petri Net

Để minh họa, luận văn này áp dụng GPSS và Petri Net vào hai bài toán cụ thể. Bài toán hàng đợi không ưu tiên (mô phỏng điều khiển xe cẩu). Bài toán hàng đợi có ưu tiên (mô phỏng hệ thống điều khiển đường băng sân bay). So sánh kết quả tính toán theo lý thuyết với kết quả mô phỏng. Điều này giúp đánh giá ưu nhược điểm của mỗi công cụ trong thực tế.

4.1. Mô Phỏng Bài Toán Xe Cẩu Không Ưu Tiên bằng GPSS và Petri Net

Bài toán xe cẩu mô phỏng quá trình xếp dỡ hàng hóa tại bãi. Sử dụng GPSS và Petri Net để mô phỏng các hoạt động của xe cẩu, thời gian chờ đợi, và hiệu suất làm việc. Kết quả mô phỏng được so sánh với lý thuyết hàng đợi để đánh giá tính chính xác. "Mô phỏng bài toán hàng đợi không ưu tiên . Phát biểu bài toán. Phân tích bài toán . Phân tích kết quả của bài toán bằng lý thuyết hàng đợi. Mô phỏng bài toán bằng công cụ GPSS WORLD . Mô phỏng bài toán bằng mô hình mạng Petri ."

4.2. Mô Phỏng Hệ Thống Điều Khiển Đường Băng Sân Bay Ưu Tiên

Bài toán hệ thống điều khiển đường băng mô phỏng quá trình cất cánh và hạ cánh của máy bay. Ưu tiên được gán cho các máy bay khẩn cấp hoặc máy bay lớn. GPSS và Petri Net được sử dụng để mô phỏng hệ thống, đánh giá thời gian chờ đợi và hiệu quả điều khiển. "Bài toán hàng đợi có ưu tiên.1 Phát biểu bài toán . Phân tích bài toán . Phân tích kết quả bài toán bằng lý thuyết hàng đợi . Mô phỏng bài toán bằng GPSS World . Mô phỏng bài toán bằng mô hình mạng Petri ."

4.3. Đánh Giá và So Sánh Kết Quả Mô Phỏng Từ GPSS và Petri Net

So sánh kết quả mô phỏng từ GPSS và Petri Net để xác định ưu điểm và nhược điểm của mỗi công cụ. GPSS thường dễ sử dụng hơn cho các hệ thống lớn và phức tạp. Petri Net trực quan hơn và phù hợp cho các hệ thống nhỏ và trung bình. "So sánh kết quả tính toán theo lý thuyết với kết quả mô phỏng trên GPSS và Petri Net theo thời gian."

V. Kết Luận Tối Ưu Hóa Hệ Thống Hàng Đợi Bằng Mô Phỏng

Luận văn đã nghiên cứu mô phỏng hệ thống hàng đợi bằng GPSS và Petri Net. Kết quả cho thấy cả hai công cụ đều có thể được sử dụng để tối ưu hóa hệ thống hàng đợi. Việc lựa chọn công cụ phù hợp phụ thuộc vào tính chất của hệ thống và mục tiêu của mô phỏng. Kết quả mô phỏng giúp nhà quản lý đưa ra quyết định tốt hơn về thiết kế và vận hành hệ thống.

5.1. Tổng Kết Ưu Nhược Điểm của GPSS và Petri Net Trong Mô Phỏng

GPSS: Mạnh mẽ, dễ sử dụng cho hệ thống lớn, nhưng ít trực quan. Petri Net: Trực quan, dễ hiểu, nhưng khó sử dụng cho hệ thống phức tạp. Cần cân nhắc kỹ trước khi lựa chọn công cụ. Dựa trên các kết quả mô phỏng được trình bày trong luận văn đưa ra so sánh, khuyến cáo khi sử dụng 2 công cụ mô phỏng GPSS và Petri Net khi áp dụng vào bài toán cụ thể.

5.2. Hướng Phát Triển Tiếp Theo Trong Nghiên Cứu Mô Phỏng

Nghiên cứu các mô hình lai ghép giữa GPSS và Petri Net để tận dụng ưu điểm của cả hai. Phát triển các công cụ mô phỏng trực quan, dễ sử dụng hơn. Ứng dụng các kỹ thuật trí tuệ nhân tạo để tự động hóa quá trình mô phỏng và tối ưu hóa hệ thống. Tóm lược nội dung chính của luận văn và nêu định hướng phát triển trong thời gian tới.