Chương 1 – Giới thiệu Giới thiệu về bối cảnh nghiên cứu, mục tiêu, phạm vi nghiên cứu và phương pháp nghiên cứu, tóm lược các kết quả đạt được. Chương 2 - Tổng quan về lý thuyết hàng đợi Trình bày 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 hàng đợi (dòng vào, dòng ra, hàng đợi, kênh phục vụ), luật Little, các mô hình hàng đợi cơ bản và các thông số về hiệu suất của hệ thống. Chương 3 – Một số công cụ mô phỏng hệ thống hàng đợi Nêu lên các hướng tiếp cận mô phỏng: toán học, lập trình và sử dụng các công cụ mô phỏng có sẵn. Đồng thời, giới thiệu hai công cụ mô phỏng GPSS World, Petri-Nets và đưa ra một số so sánh, đánh giá hai công cụ này.
Chương 4 - Ứng dụng công cụ mô phỏng vào mô phỏng hệ thống hàng đợi thực tế Ứng dụng hai công cụ mô phỏng GPSS World và Petri-Nets vào mô phỏng hai bài toán thực tế về hệ thống hàng đợi ưu tiên và hệ thống hàng đợi không ưu tiên. Từ bài toán cụ thể đó: phân tích, tính toán, tiến hành mô phỏng và đánh giá kết quả thu được. Chương 5 - Kết luận Tóm lược kết quả chính của luận văn, rút ra kết luận và nêu định hướng phát triển trong thời gian tới. TIEU LUAN MOI download : skknchat@gmail.com 4 Chương 2 TỔNG QUAN VỀ LÝ THUYẾT HÀNG ĐỢI Chương này tập trung vào tìm hiểu tổng quan về lý thuyết hệ thống hàng đợi: giới thiệu về lý thuyết hàng đợi, vai trò và ứng dụng của lý thyết hàng đợi, các yếu tố của hệ thống hàng đợi gồm: dòng yêu cầu đầu vào, hàng đợi, kênh phục vụ, dòng yêu cầu đầu ra, các thông số mô tả về hệ thống; luật Little và một số mô hình hàng đợi cơ bản.
Vai trò của lý thuyết hàng đợi Lý thuyết hàng đợi là một nhánh của xác suất thống kê, được ứng dụng trong nhiều lĩnh vực khác nhau như: mạng truyền thông, các hệ thống máy tính, hệ thống nhà máy. Lý thuyết hàng đợi tập trung trả lời các câu hỏi như: trung bình thời gian đợi trong hàng đợi, trung bình thời gian phản hồi của hệ thống (thời gian đợi trong hàng đợi cộng thời gian phục vụ), nghĩa là sự sử dụng của các thiết bị phục vụ, phân phối số lượng khách hàng trong hàng đợi, phân phối khách hàng trong hệ thống. Một hệ thống hàng đợi có thể mô tả như sau: một trung tâm dịch vụ và một mật độ khách hàng. Thông thường, trung tâm phục vụ có thể chỉ phục vụ một giới hạn khách hàng, nếu khách hàng mới đến và các dịch vụ đã sử dụng hết, khách hàng này phải vào hàng đợi và đợi cho đến khi dịch vụ trở nên có sẵn hoặc ngay lập tức rời đi.
Vì vậy, 3 yếu tố chính của trung tâm dich vụ là: một mật độ khách hàng, các thiết bị phục vụ và hàng đợi. Khái quát về hệ thống hàng đợi Giới thiệu các thành phần của hệ thống hàng đợi: đầu vào, đầu ra, kênh phục vụ, nguyên tắc phục vụ, và các lý thuyết liên quan như hàm phân phối thời gian đến, hàm phân phối thời gian phục vụ, phục vụ ưu tiên hay không ưu tiên. Đồng thời, trình bày một số kết quả quan trọng của các hàng đợi cơ bản. Các thành phần cơ bản của một hệ thống hàng đợi Một hệ thống hàng đợi gồm các thành phần cơ bản [11] sau: - Tiến trình vào, tiến trình ra khỏi hệ thống (được coi như đầu vào và đầu ra của hệ thống hàng đợi) - Phân phối thời gian phục vụ - Số kênh phục vụ - Khả năng của hệ thống - Qui mô (kích thước) khách hàng - Nguyên tắc phục vụ TIEU LUAN MOI download : skknchat@gmail.
Nguyên tắc phục 2. Phân phối thời gian vụ phục vụ 1.Tiến trình vào Tiến trình ra 3. Số các kênh phục vụ 5. Qui mô khách hàng 4.
Khả năng của hệ thống Hình 2. Các thành phần cơ bản của một hệ thống hàng đợi Trong đó: Tiến trình vào Tiến trình vào (gọi tắt là dòng vào) là dòng các yêu cầu đến hệ thống hàng đợi, đòi hỏi thỏa mãn một yêu cầu nào đó được đặc trưng bởi tốc độ đến (arrival rate), ký hiệu là λ. Do dòng các yêu cầu đầu vào là một biến ngẫu nhiên, nó được đặc trưng bởi phân phối xác suất của hai lần đến liên tiếp của các khách hàng và được kí hiệu là A(t).1) Dòng vào này có thể tuân theo luật phân phối đều (D), hoặc luật phân phối mũ (M), hay luật phân phối Erlangian (Er). Tiến trình ra Tiến trình ra (gọi tắt là dòng ra) là dòng các yêu cầu ra khỏi hệ thống hàng đợi.
Được đặc trưng bởi tốc độ ra (departure rate), ký hiệu là µ. Phân phối thời gian phục vụ Ở đây thời gian phục vụ là độ dài thời gian mà khách hàng sử dụng các dịch vụ. Phân phối xác suất của nó được kí hiệu là B(𝓍).2) TIEU LUAN MOI download : skknchat@gmail.com 6 Số kênh phục vụ Kênh phục vụ bao gồm con người cùng với các thiết bị kĩ thuật hoạt động tại một vị trí nào đó. Thường được mô tả trong biến m.
Đặc điểm quan trọng nhất của kênh phục vụ là thời gian phục vụ 𝓍 n. Đó là thời gian kênh phục vụ phải tiêu phí để phục vụ khách hàng thứ n. Thời gian phục vụ cũng là một đại lượng ngẫu nhiên tuân theo một quy luật phân phối xác suất nào đó. Khả năng của hệ thống: gồm kích thước hàng đợi và khả năng phục vụ của các kênh phục vụ, kí hiệu: K.
Nguyên tắc phục vụ Mô tả thứ tự khách hàng được lấy ra khỏi hàng đợi và được phép vào sử dụng dịch vụ. Chẳng hạn, một số hàng đợi theo nguyên tắc phục vụ đến – trước – phục vụ - trước (first-come- first-serve viết tắt: FCFS), hay đến – sau – phục vụ - trước (last-come- first-serve viết tắt LCFS), hay thứ tự phục vụ ngẫu nhiên… Ngoài ra, khách hàng có thể được chia thành các nhóm với độ ưu tiên của mỗi nhóm khác nhau, đó là các hệ thống hàng đợi có ưu tiên. Các biến chính của một hệ thống hàng đợi Đối với một hệ thống hàng đợi chúng ta quan tâm đến các tham số đặc trưng được kí hiệu và định nghĩa [11, trang 29 ] như sau. Sn Cn Cn+1 Cn+2 Cn-1 Kênh phục vụ wn 𝓍n 𝓍 n+1 𝓍 n+2 Cn Thời gian Cn+1 Cn+2 Hàng đợi n n+1 n+2 t n+1 t n+2 Cn+1 Cn+2 Cn Hình 2.
Kí hiệu biểu đồ thời gian cho các hệ thống hàng đợi một kênh phục vụ Trong sơ đồ này: - Đường kẻ ngang dưới đại diện cho hàng đợi, đường kẻ ngang trên đại diện cho cơ sở dịch vụ hay kênh phục vụ. - Mũi tên hướng từ dưới lên chỉ vào đường kẻ ngang hàng đợi (hoặc kênh phục vụ) chỉ ra rằng một khách hàng đã vào hàng đợi (hoặc kênh phục vụ). TIEU LUAN MOI download : skknchat@gmail.com 7 - Mũi tên hướng từ đường kẻ ngang hàng đợi (hoặc kênh phục vụ) đi ra, chỉ ra rằng một khách hàng đã đi ra khỏi hàng đợi (hoặc kênh phục vụ). - Khách hàng Cn+1 đến trước khi khách hàng Cn vào dịch vụ và chỉ khi khách hàng Cn dời khỏi dịch vụ thì khách hàng Cn+1 mới vào dịch vụ (dĩ nhiên hai sự kiện này có thể xảy ra đồng thời).
- Khách hàng Cn+2 vào hệ thống và nhận thấy kênh phục vụ “rảnh” ngay lập tức xuyên qua hàng đợi vào ngay kênh phục vụ (wn+2=0). Ngoài ra, trong hệ thống hàng đợi chúng ta còn quan tâm đến các thông số khác như số khách hàng đến và rời khỏi hệ thống trong một khoảng thời gian, hay số khách hàng trung bình trong hệ thống, hoặc trong hàng đợi, hệ số sử dụng của hệ thống. Số khách hàng Thời gian t Hình 2. Biểu đồ số khách hàng đến và rời khỏi hệ thốngtheo thời gian Các tham số đặc trưng của hệ thống hàng đợi được tóm tắt trong bảng 2.1 dưới đây: Bảng 2.
Các tham số đặc trưng của hệ thống hàng đợi STT Ký hiệu Mô tả 1 Cn Khách hàng thứ n vào hệ thống 2 τn Thời điểm đến của khách hàng thứ n 3 tn Khoảng thời gian giữa khách hàng Cn-1 và Cn (tn= τn - τn-1 ) 4 ̃ ̃ 5 Wn Thời gian chờ trong hàng đợi của khách hàng thứ n 6 Thời gian hệ thống (thời gian đợi + thời gian phục vụ) của khách Sn hàng thứ n TIEU LUAN MOI download : skknchat@gmail.com 8 Sn=Wn+ 𝓍 n 7 Hàm phân phối xác suất thời gian giữa hai khách hàng liên tiếp An(t) (PDF) An(t)=P[tn≤t] 8 Giới hạn hàm phân phối xác suất [ ̃ ] ( ) A(t) Kí hiệu: An(t)A(t) 9 B(𝓍) Phân phối thời gian phục vụ 10 ( ) Số khách hàng đến trong khoảng thời gian (0,t) 11 ( ) Số khách hàng ra khỏi hệ thống trong khoảng thời gian (0,t) 12 Số khách hàng ở trong hệ thống tại thời điểm t N(t) ( ) ( ) ( ) 13 Nq(t) Số khách hàng trong hàng đợi tại thời điểm t 14 T Tổng thời gian phục vụ của toàn bộ hệ thống 15 λ Tốc độ đến (arrival rate) của khách hàng 16 µ Tốc độ phục vụ 17 ̅ thời gian trung bình sử dụng dịch vụ 18 Hệ số sử dụng hệ thống ρ ̅ { ̅ 19 pK xác suất có K khách hàng trong hệ thống ( ) Hệ thống ở trạng thái dừng (the system in the steady – state) khi 2. Kí hiệu Kendall A / B / m / K / n / D Các thành phần cơ bản của một hàng đợi được mô tả ngắn gọn trong kí hiệu Kendall[16, trang 14] có dạng: A / B / m / K / n / D. Ý nghĩa của các ký hiệu trong mô tả Kendall được trình bày trong bảng 2. TIEU LUAN MOI download : skknchat@gmail.
Các thành phần trong kí hiệu Kendall STT Ký hiệu Ý nghĩa Kí hiệu cho A(t) - hàm phân phối thời gian của hai khách hàng đến đến liên tiếp. A có thể nhận một trong các giá trị: M (phân phối mũ), 1 A D (phân phối đều), Er( phân phối Erlangian), G (phân phối chung), H (phân phối siêu mũ) Kí hiệu cho B(𝓍) - hàm phân phối thời gian phục vụ. B có có thể nhận một trong các giá trị: M (phân phối mũ), D (phân phối đều), 2 B Er( phân phối Erlangian), G (phân phối chung), H (phân phối siêu mũ) 3 m Số lượng kênh phục vụ Dung lượng của hệ thống, là số khách hàng lớn nhất mà hệ thống có 4 K thể phục vụ bao gồm cả khách hàng trong hàng đợi và khách hàng đang được phục vụ.