Chương 1: Cơ sở lý thuyết về hệ thống hàng đợi Chương này tập trung vào tìm hiểu cơ sở lý thuyết về hệ thống hàng đợi: các đặc điểm của hệ thống, các yếu tố của hệ thống gồm có 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… và tìm hiểu về quá trình Markov và trạng thái của hệ thống phục vụ… 1.1 Mô tả về hệ thống hàng đợi Chúng ta làm quen với một ví dụ về hệ thống hàng đợi [2, 12, 18] (hay còn gọi là hệ thống phục vụ đám đông) như hình vẽ 1. 1 Ví dụ về hệ thống hàng đợi, hay còn gọi là hệ thống phục vụ đám đông. Trong mô hình này, chúng ta quan sát thấy có yếu tố khách đến, khách bỏ đi (do không có thời gian chờ đợi, hoặc các lý do khác), khách xếp hàng chờ tới lượt mình được phục vụ, các máy phục vụ, và khách hàng đã được phục vụ xong, rời khỏi hệ thống phục vụ trên. Các yếu tố này có thể tóm lược sơ bộ gồm các thành phần trong bảng 1: Bảng 1: Các yếu tố cấu thành một hệ thống phục vụ đám đông STT Tên yếu tố Giải thích 1 Dòng các yêu cầu Khách hàng gọi điện thoại đến một tổng đài giải đáp (Call đầu vào Center), các xe ô tô đi vào bãi đậu xe, các máy bay hạ cánh xuống một phi trường… 2 Hệ thống phục vụ Là các máy phục vụ nhằm đáp ứng yêu cầu ứng với từng loại đầu vào cụ thể ở trên, trong hệ thống phục vụ có hàng chờ, tại đó, khách hàng xếp hàng chờ đến lượt mình được phục vụ.
Hệ thống phục vụ có các máy phục vụ và chúng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 hoạt động theo những quy luật, nguyên tắc phục vụ nào? 3 Các máy phục vụ Các máy điện thoại bàn và nhân viên trong một Call Center, đường băng tại sân bay, vị trí trong bãi đậu xe… 4 Dòng các yêu cầu Là các yêu cầu đã được phục vụ sau khi đi ra khỏi hệ thống đầu ra phục vụ ở trên Về bản chất, khi xuất hiện các yêu cầu vượt quá khả năng đáp ứng của một dịch vụ nào đó tại một thời điểm nào đó, hàng đợi sẽ xuất hiện. Sự chờ đợi (nhanh hay chậm để được đáp ứng yêu cầu) phụ thuộc mạnh vào số lượng kênh phục vụ của hệ thống, cũng như quy tắc phục vụ của hệ thống.1 Mô hình hóa một hệ thống hàng đợi Chúng ta có thể mô hình đơn giản cho một hệ thống hàng đợi trong hình 1. 2 Mô hình hóa các yếu tố của một hệ thống hàng đợi Các thông số mô tả liên quan đến hệ thống hàng đợi gồm có: Bảng 2: Các tham số đặc trưng trong hệ thống hàng đợi STT Ký hiệu Nội dung 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 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ụ.
Lưu ý: λ < µ 4 Nq(t) Hàng chờ, đặc trưng bởi số lượng khe để phục vụ cho xếp hàng 5 Wi Thời gian xếp hàng của khách hàng thứ i trong hàng chờ 6 Ns(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 vụ 9 T Tổng thời gian phục vụ của toàn bộ hệ thống Có nhiều nguyên tắc phục vụ, hoặc nguyên tắc xếp hàng. Chúng ta lấy ví dụ đơn giản nhất khi xếp hàng là: Ai đến trước phục vụ trước – First In, First Out. Khi đó, Tổng thời gian trễ Ti của khách hàng thứ i sẽ là tổng của thời gian xếp hàng Wi và thời gian phục vụ τi. Chúng ta có: Ti = W i + τ i (1.2 Quan điểm về hiệu suất của hệ thống hàng đợi Có hai quan điểm về vấn đề này [2] Nếu nhìn ở góc độ khách hàng, chúng ta đã biết tốc độ đến (arrival rate) là λ, và có một số khách hàng bỏ đi, với tốc độ bỏ đi là λb.
Khi đó chúng ta sẽ tính hiệu suất hệ thống (theo góc độ dòng yêu cầu đầu vào, hay góc độ khách hàng): η1 = λb/ λ (1.2) Nếu nhìn ở góc độ phân bố tài nguyên trong hệ thống, hiệu suất hệ thống tính theo tỉ lệ thời gian mà mỗi máy phục vụ có thể thực hiện được, và tốc độ mà mỗi khách hàng được phục vụ. Khi đó hiệu suất hệ thống là một hàm số của N(t) và Nq(t): η2 = λ - λb = f(N(t), Nq(t)) (1.3 Công thức Little Thời gian phục vụ là một đại lượng ngẫu nhiên, chúng ta khó có thể đo được. Tuy nhiên, nhìn tổng thể, thời gian phục vụ trung bình là một yếu tố rất quan trọng, đem lại nhiều ý nghĩa để đánh giá hiệu suất hoạt động của hệ thống hàng đợi. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Công thức Litte phát biểu rằng: Hệ thống hàng đợi đạt được trạng thái dừng khi mà Trung bình các khách hàng trong hệ thống bằng Tốc độ đến trung bình nhân với Thời gian phục vụ trung bình trong hệ thống hàng đợi đó.4) Khi đó, chúng ta suy ra các hệ quả sau: E[Nq(t)] = λtb E[W] (1.5) Trung bình khách hàng chờ đợi và Thời gian chờ đợi trung bình 1- p0 = E[Ns(t)] = λtb E[τ] (1.4 Hệ thống hàng đợi theo cách viết của Kendall và các phân phối liên quan Theo Kendall [3,13,14], mô tả ngắn gọn về hệ thống hàng đợi có dạng như sau: A/B/m/K (1.8) Các ký hiệu trong mô tả Kendall được trình bày trong bảng 3: Bảng 3: Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi STT Ký hiệu Ý nghĩa 1 A Phân phối xác suất của thời gian đến 2 B Phân phối xác suất của thời gian phục vụ.
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ờ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Chi tiết hơn, với ký hiệu X là biến ngẫu nhiên của phân phối xác suất và E[X] là kỳ vọng , hoặc giá trị trung bình của X, chúng ta nói về các phân phối xác suất [8, 20] liên quan đến yếu tố A và B trong bảng 4: Bảng 4: Các phân phối xác suất liên quan đến A và B trong mô tả Kendall STT Viết Phân phối Hàm phân phối Ghi tắt chú xác suất 1 M Phân phối mũ, X không F x 1 e x , λ là hệ số kỳ vọng (1.10) E[X] = k/ λ F x 1 , λ là hệ j 0 j! số kỳ vọng, k là pha, x ≥ 0, 3 Hk Phân phối siêu lũy thừa, k jx (1.12) gian vào và thời gian phục vụ là hằng số F(x)= 0, nếu x ˂ a a là một thời điểm nào đó cố định 5 G Phân phối tổng quát 6 GI Phân phối tổng quát với Đặc trưng bởi chuỗi Markov hoặc quá các thời gian vào hệ thống trình Possion, sẽ trình bày kỹ hơn về hoặc thời gian phục vụ chuỗi này sau độc lập nhau. 7 PH Phân phối pha Đặc trưng bởi chuỗi Markov, sẽ trình bày kỹ hơn về chuỗi này sau 1.2 Các yếu tố của hệ thống phục vụ Các yếu tố của hệ thống phục vụ [1], gồm có: 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, và các cách phục vụ (quy luật phục vụ ). Chúng ta sẽ xét từng yếu tố cụ thể đã liệt kê trong bảng 1.1 Dòng yêu cầu đầu vào Dòng yêu cầu đầu vào (gọi tắt là dòng vào) là dòng các yêu cầu đến hệ thống phục vụ, đòi hỏi được thỏa mãn một yêu cầu nào đó.
Đặc trưng rõ nét nhất của dòng vào là tốc độ đến (arrival rate), ký hiệu là λ. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Chúng ta thấy rằng, dòng các yêu cầu đầu vào là một yếu tố xuất hiện ngẫu nhiên, chúng có thể ít, có thể nhiều tùy theo thời điểm đến, nó có đặc trưng bởi một số phân bố xác suất nào đó (xem bảng 1. Trong luận văn này, chúng ta tập trung xét hai loại dòng yêu cầu đầu vào thông dụng nhất là: Dòng vào tiền định, đặc trưng bởi phân phối tất định D Dòng vào Possion, tuân theo phân phối Possion Một số ví dụ về dòng yêu cầu đầu vào: Khách hàng xếp hàng tại quầy thu ngân trong siêu thị, các xe ô tô chờ xếp hàng vào bãi, các máy bay chờ để cất cánh… Dòng vào tiền định Dòng vào tiền định là dòng vào trong đó các yêu cầu đến hệ thống phục vụ tại các thời điểm cách đều nhau một khoảng a. Dòng vào tiền định là một đại lượng ngẫu nhiên có hàm phân bố xác suất theo phân phối D: F(x) = 1, nếu x ≥ a (1.13) F(x) = 0, nếu x < a Dòng vào Poisson Dòng vào Poisson là dòng yêu cầu đi đến hệ thống, dòng vào này tuân theo luật phân phối Poisson với N(t) là số các biến cố xảy ra trong khoảng thời gian [0, t] N(t) là quá trình ngẫu nhiên liên tục, không giảm theo thời gian.15) x( Dt ) a t, t ! Trong đó a(t, Dt) là số trung bình các yêu cầu xuất hiện từ t đến Dt.
- Dòng vào Poisson dừng: Là dòng vào mà xác suất trong khoảng thời gian Dt, kể từ thời điểm t, có x yêu cầu xuất hiện, không phụ thuộc vào t, nghĩa là: e t (1. t)x ! Trong đó, λo là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian (cường độ dòng yêu cầu). Nói cách khác là mật độ dòng yêu cầu không đổi. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Nếu t là khoảng thời gian giữa lần xuất hiện các yêu cầu liên tiếp, thì t là một đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là t có hàm phân bố xác suất và hàm mật độ như sau: F t 1 e ot (1.2 Hàng đợi Hàng đợi (Queue) là tập hợp các yêu cầu sắp xếp theo một nguyên tắc nào đó để chờ đợi đến lượt được vào phục vụ trong hệ thống.
Trong hàng đợi ta có thể giới hạn hoặc không giới hạn số lượng khách chờ.