Mở đầu Giới thiệu về 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 Chương này đư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ụ), luật Little, các quá trình Markov và trạng thái của hệ thống, nghiên cứu một số mô hình hàng đợi cơ bản và một số phân phối xác suất quan trọng. Chương 3 – Nghiên cứu công cụ mô phỏng hệ thống hàng đợi Nêu các hướng tiếp cận mô phỏng: lập trình truyền thống và các công cụ mô phỏng có sẵn, trong đó tập trung vào công cụ GPSS World. 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 công cụ mô phỏng GPSS World vào bài toán thực tế: Bài toán mô phỏng hoạt động kiểm soát xuất nhập cảnh của cửa khẩu sân bay quốc tế Nội Bài.
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 và nêu định hướng phát triển trong thời gian tới. TIEU LUAN MOI download : skknchat@gmail.com 10 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ý thuyết hàng đợi, các yếu tố của hệ thống hàng đợi bao gồm: dòng yêu cầu đầu vào, hàng chờ, kênh phục vụ, dòng yêu cầu đầu ra, các thông số mô tả về hệ thống; công thức Kendall, luật Little, một số mô hình hàng đợi cơ bản và một số phân phối xác suất quan trọng. Vai trò của lý thuyết hàng đợi.
Lý thuyết hàng đợi chủ yếu được nhìn nhận như là một nhánh của lý thuyết xác suất ứng dụng, được ứng dụng trong rất nhiều lĩnh vực khác nhau như viễn thông, máy tính, dịch vụ, sản xuất, kiểm soát XNC,. Lý thuyết hàng đợi còn được biết đến với các tên gọi khác như lý thuyết giao thông, lý thuyết xếp hàng, lý thuyết giải quyết tắc nghẽn, lý thuyết phục vụ đám đông hay lý thuyết của các hệ thống dịch vụ ngẫu nhiên thống kê [4, tr. 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 lượng khách hàng đến yêu cầu được phục vụ. 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 có 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 sẵn sàng.
Do đó, chúng ta có thể xác định 3 yếu tố chính của một trung tâm dịch vụ là: lượng khách hàng, các thiết bị phục vụ và hàng đợi. Các trung tâm dịch vụ có thể được bố trí theo mô hình mạng, một khách hàng có thể đi qua một vài trung tâm dịch vụ theo một đường nào đó. Lý thuyết hàng đợi tập trung trả lời các câu hỏi như: thời gian đợi trung bình trong hàng đợi, thời gian phản hồi trung bình của hệ thống (thời gian trong hàng đợi cộng với thời gian phục vụ), hiệu suất trung bình sử dụng các thiết bị phục vụ, phân bố số lượng khách hàng trong hàng đợi và trong hệ thống,. Các thông số này thường được tính toán bằng phương pháp thống kê, trong đó khoảng thời gian khách hàng đến hay thời gian phục vụ được coi là các đại lượng ngẫu nhiên [10, tr.
Khái quát về hệ thống hàng đợi Giới thiệu về các thành phần của hệ thống hàng đợi như đầ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 bố thời gian đến và thời gian phục vụ, phục vụ ưu tiên, không ưu tiên. Đồng thời đưa ra một số kết quả quan trọng của một số 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 [5, tr.30-4] sau: TIEU LUAN MOI download : skknchat@gmail.com 11 - Tiến trình vào, ra khỏi hệ thống - Phân phối thời gian phục vụ - Số các kênh phục vụ - Khả năng của hệ thống (trong hàng chờ và trong quá trình được phục vụ) - Qui mô (kích thước) khách hàng - Nguyên tắc phục vụ 6. Nguyên tắc phục vụ 2.
Phân phối thời gian 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.1 Các thành phần cơ bản của một hệ thống hàng đợi Các khách hàng đến trung tâm dịch vụ theo một phân phối ngẫu nhiên.
Khả năng phục vụ của hệ thống có thể bao gồm một hay nhiều kênh phục vụ, mỗi một kênh có thể phục vụ một khách hàng tại một thời điểm, thời gian phục vụ một khách hàng cũng là ngẫu nhiên. Chúng ta giả sử: Quy mô khách hàng là vô hạn, khách hàng thứ n ký hiệu là Cn đến tại thời điểm τn. Khoảng thời gian tn giữa hai khách hàng đến được định nghĩa là tn= τn - τn-1. Chúng ta giả sử khoảng thời gian tn là ngẫu nhiên độc lập, nghĩa là chúng không phụ thuộc lẫn nhau và tất cả các tn đều phát sinh theo cùng một phân phối với hàm phân phối là A(t) = Pr[tn ≤ t] và hàm 𝑑𝐴 𝑡 mật độ xác suất tương ứng là 𝑎 𝑡 = 𝑑𝑡 Thời gian phục vụ cho khách hàng Cn là xn cũng là ngẫu nhiên độc lập với hàm phân phối là B(t) và hàm mật độ xác suất tương ứng b(t).
Các hệ thống hàng đợi không chỉ khác nhau về phân phối xác suất đến và thời gian phục vụ mà còn có thể khác nhau ở số lượng kênh phục vụ, kích thước hàng đợi (hữu hạn hay vô hạn), nguyên tắc phục vụ,. Một số nguyên tắc phục vụ phổ biến bao gồm: FIFO/FCFS (First In First Out/First Come First Served - đến trước phục vụ TIEU LUAN MOI download : skknchat@gmail.com 12 trước), LIFO/LCFS (Last in First Out/Last Come First Served - đến sau phục vụ trước), SIRO (Service In Random Order - phục vụ theo thứ tự ngẫu nhiên), PNPN (Priority service - phục vụ theo thứ tự ưu tiên), PS (Processor Sharing – chia sẻ bộ xử lý), Round Robin (phục vụ quay vòng),. Các tham số đặc trưng của một hệ thống hàng đợi Các tham số đặc trưng trong 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 trong 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 (Cn) 3 tn Khoảng thời gian giữa khách hàng Cn-1 và Cn (tn= τn - τn-1 ) 4 𝑡 𝑡 ≜ lim 𝑡𝑛 𝑛→∞ 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 chờ + thời gian phục vụ) của khách Sn hàng thứ n 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 - probability density function) ( 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 TIEU LUAN MOI download : skknchat@gmail.com 13 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 ρ 𝜆𝑥 𝑛ế𝑢 𝑐ó 1 𝑘ê𝑛 𝑝ụ𝑐 𝑣ụ 𝜌 = 𝜆𝑥 𝑛ế𝑢 𝑐ó 𝑚 𝑘ê𝑛 𝑝ụ𝑐 𝑣ụ 𝑚 19 pK xác suất có K khách hàng trong hệ thống 2.
Kí hiệu Kendall A / B / m / K / n / D David George Kendall (15/01/1918 – 23/10/2007) là nhà toán học và thống kê học người Anh. Ông là người đầu tiên đưa ra ký hiệu dùng để mô tả các thành phần cơ bản của một hàng đợi [9, tr. Ý nghĩa của các ký hiệu trong mô tả Kendall được trình bày trong bảng 2.2: Các thành phần trong kí hiệu Kendall STT Ký hiệu Ý nghĩa 1 A Kí hiệu cho A(t) - hàm phân phối thời gian của các lần đến liên tiếp. 2 B Kí hiệu cho B(𝓍) - hàm phân phối thời gian phục vụ.
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 có mặt trong hệ 4 K thống, bao gồm cả số khách hàng đang được phục vụ. 5 n Kích thước khách hàng (population size). Nguyên tắc phục vụ.
Nếu trong ký hiệu không nêu tham số này thì 6 D ngầm định nguyên tắc phục vụ là FIFO. Thông thường A và B có thể nhận các giá trị là [5, tr. TIEU LUAN MOI download : skknchat@gmail.com 14 Sau đây là bảng các hàm phân phối xác suất của A và B [10, tr.3: Một số hàm phân phối xác suất trong ký hiệu Kendall STT Viết Hàm phân phối tắt 1 M A(t ) 1 e t , và a(t ) e t , với λ>0 k 1 (kt ) j 2 Ek At 1 e kt , k ≥ 1 là pha, µ>0 j 0 j! k A(t ) q j (1 e jt ) 3 Hk j 1 𝑘 Trong đó: μj >0, qj>0, j∈{1.k}, 𝑗 =1 𝑞𝑗 = 1 Chúng ta thường quan tâm đến các giải pháp để đạt được trạng thái cân bằng (steady state), nghĩa là sau một thời gian hoạt động lâu dài, hệ thống có xu hướng đạt đến một trạng thái cân bằng, ví dụ như phân phối khách hàng của hệ thống không thay đổi. Điều này phân biệt rõ với trạng thái nhất thời (transient state), trạng thái có được khi chúng ta khảo sát phản hồi của hệ thống với các sự kiện khác nhau trong một khoảng thời gian ngắn [10, tr.