CHƯƠNG 1 CƠ SỞ LÝ LUẬN VÀ Ý NGHĨA VẬN DỤNG CỦA LÝ THUYẾT XẾP HÀNG 1.1 Tổng quan về Lý thuyết xếp hàng: 1.1 Khái niệm: “Lý thuyết xếp hàng” - “Queueing Theory” hay còn gọi là “Lý thuyết phục vụ đám đông”, nghiên cứu các tính chất đặc trưng của mô hình toán liên quan đến hệ thống ngẫu nhiên như sau: có một hệ thống phục vụ và dòng khách hàng đến, trong đó các khách hàng tới hệ thống phải xếp hàng để đợi được phục vụ, khoảng thời gian đến của khách hàng, và khoảng thời gian phục vụ là những đại lượng ngẫu nhiên. Người nghiên cứu đầu tiên về Lý thuyết này là kỹ sư A. Erlang đã tìm cách tính toán số đường dây điện thoại tối ưu cho tổng đài điện thoại tại thành phố Copenhagen. Vào thời điểm bấy giờ, khi muốn thực hiện cuộc gọi, người ta phải cắm dây cắm vào một mạch điện dẫn tới tổng đài và chờ đợi.
Việc kết nối 2 đầu dây lại với nhau để thực hiện cuộc gọi sẽ được thực hiện thủ công bởi nhân viên trực tại tổng đài. Nhằm tiết kiệm lao động và cơ sở hạ tầng, Erlang muốn biết chính xác số đường dây tối thiểu cần thiết để tất cả các cuộc gọi đều được kết nối nhanh nhất. Nếu đối với các tổng đài nhỏ và cần chi phí thấp nhất, người ta chỉ trang bị 1 đường dây duy nhất và người ta phải xếp hàng rất lâu mới tới lượt cuộc gọi của họ được kết nối. Do đó, cần phải tính số đường dây ít nhất để tiết kiệm nhưng vẫn đảm bảo hàng nghìn người trong thành phố không phải chờ đợi quá lâu.
Để khắc phục điều đó, Erlang nghĩ ra một phương trình (còn được gọi là phương trình Erlang) nhằm tính ra được số cuộc gọi trung bình trong các giờ định trước và khoảng thời gian trung bình của mỗi cuộc gọi. Áp dụng phương trình của mình vào thí dụ đơn giản trên, tổng đài điện thoại Copenhagen đã tìm ra được rằng, nếu họ trang bị 7 đường dây thì 99% cuộc gọi sẽ được kết nối ngay lập tức tại bất cứ lúc nào. Vào LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 năm 1909, Erlang đã công bố phát hiện của ông và khai sinh ra một nhánh mới của toán học mang tên "Lý thuyết xếp hàng". Lý thuyết xếp hàng còn được gọi là ngẫu nhiên lý thuyết hệ thống dịch vụ, là thông qua các đối tượng dịch vụ và thời gian phục vụ cho việc xuất hiện của các nghiên cứu thống kê, kết quả của các chỉ số định lượng (thời gian chờ đợi, chiều dài hàng đợi, thời gian bận rộn…) của các quy luật thống kê, để cải thiện hệ thống dịch vụ hoặc tổ chức lại cấu trúc của các đối tượng được dịch vụ, làm cho hệ thống dịch vụ đáp ứng nhu cầu của khách hàng, nhưng cũng làm cho chi phí của các tổ chức kinh tế thấp nhất hoặc chỉ số nhất định tối ưu.
Lý thuyết xếp hàng được sử dụng rộng rãi trong các mạng máy tính, sản xuất, vận chuyển, hàng tồn kho. Nội dung của việc nghiên cứu Lý thuyết xếp hàng có ba khía cạnh: suy luận thống kê, dựa trên mô hình dữ liệu, hệ thống hành vi, tức là, số lượng các chỉ số và xếp hàng trên xác suất đều đặn, vấn đề tối ưu hóa hệ thống. Mục đích của nó là thiết kế phù hợp và hoạt động hiệu quả của các hệ thống dịch vụ khác nhau, để gặt hái những lợi ích tốt nhất.2 Các yếu tố đặc trưng của một hệ xếp hàng Một quá trình xếp hàng có thể mô tả đầy đủ qua các đặc trưng sau: 1.1 Kiểu dòng đến Dòng đến của các khách hàng mang tính ngẫu nhiên, ví dụ như dòng tàu đến cảng, dòng người chờ mua sắm, thanh toán, phục vụ. hoặc phương tiện (như tàu xe,…) hoặc cả những yêu cầu thông tin được xử lý (tự động hay không).
Do vậy chúng ta cần biết phân phối xác suất mô tả các khoảng thời gian giữa các lần đến của khách hàng. Phân phối xác suất này cho ta biết kiểu của dòng đến, thí dụ dòng chuẩn, dòng Poisson nghĩa là dòng đến kiểu phân phối chuẩn, hoặc phân phối Poisson. Trong Lý thuyết xác suất và thống kê, phân phối Poisson là một phân phối xác suất rời rạc. Nó khác với các phân phối xác suất rời rạc khác ở chỗ thông tin cho biết không phải là xác suất để một sự kiện xảy ra (thành công) trong một lần thử như trong phân phối Bernoulli, hay là số lần mà sự kiện đó xảy ra trong n lần thử LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 như trong phân phối nhị thức, mà chính là trung bình số lần xảy ra thành công của một sự kiện trong một khoảng thời gian nhất định.
Giá trị trung bình này được gọi là lamda, kí hiệu là λ. Dòng đến được gọi là ổn định nếu nó độc lập với thời gian, ngược lại là không ổn định nếu nó phụ thuộc vào thời gian. Ví dụ về dòng đến không ổn định như dòng hành khách mua vé tàu xe sẽ tập trung cao giờ cao điểm, vào dịp lễ Tết. Dòng Poisson có 3 tính chất sau: + Tính không hiệu quả: Dòng yêu cầu có tính không hiệu quả nghĩa là nếu xác suất xuất hiện một số yêu cầu nào đó trong một khoảng thời gian nhất định không phụ thuộc vào việc đã có bao nhiêu yêu cầu xuất hiện trước khoảng thời gian đó.
Nói cách khác, số yêu cầu xuất hiện trước và sau thời điểm t o nào đó không chịu ảnh hưởng qua lại lẫn nhau. + Tính đơn nhất: Dòng yêu cầu có tính chất đơn nhất có nghĩa là nếu xét trong khoảng thời gian khá bé thì biến cố “có nhiều hơn một yêu cầu xuất hiện” hầu như không xảy ra. Về mặt thời gian, chúng ta có thể xem dòng yêu cầu có tính chất đơn nhất nếu thời điểm xuất hiện các yêu cầu không trùng nhau. + Tính dừng (tính thuần nhất theo thời gian): Dòng yêu cầu có tính thuần nhất có nghĩa là: nếu xác suất xuất hiện k yêu cầu trong khoảng thời gian t chỉ phụ thuộc vào giá trị của t và của k chứ không phụ thuộc vào việc khoảng thời gian t này nằm ở vị trí nào trên dòng thời gian.
Điều này có nghĩa là với những khoảng thời gian t dài bằng nhau thì xác suất xuất hiện k yêu cầu như nhau. Nếu dòng vào là dòng tối giản thì: 𝑒 −𝑎 p k (t) = 𝑎𝑘 𝑘! Trong đó: - p k (t): là xác suất để trong khoảng thời gian t có k yêu cầu xuất hiện. - k: số yêu cầu xuất hiện trong khoảng thời gian quan sát t. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 - a: là số yêu cầu trung bình xuất hiện trong từng khoảng thời gian quan sát t.2 Kiểu hệ phục vụ Một hệ có thể chỉ phục vụ nhu cầu đơn lẻ hoặc cả gói nhu cầu của khách hàng.
Cũng có hệ nhiều khách hàng cùng được phục vụ bởi một người phục vụ, ví dụ máy tính với việc xử lý song hành, phục vụ hành khách trong vận tải, du lịch. Cũng như dòng đến, hệ phục vụ có thể là ổn định, nếu khả năng phục vụ của hệ không phụ thuộc vào thời gian, hoặc là không ổn định nếu nó phụ thuộc thời gian. Năng lực phục vụ của hệ có thể phụ thuộc vào dòng khách chờ, nếu có ta gọi hệ đó là hệ phụ thuộc trạng thái, nói chung một hệ có thể phục vụ nhanh hơn nếu hàng chờ có quy cũ và trật tự, ngược lại có thể gây ra rối.3 Quy tắc xếp hàng Quy tắc xếp hàng hay nguyên tắc phục vụ của hệ thống là cách thức nhận các yêu cầu vào các kênh phục vụ. Nguyên tắc phục vụ cho biết trường hợp nào thì yêu cầu được nhận vào phục vụ và cách thức phân bố các yêu cầu vào các kênh như thế nào.
Đồng thời nguyên tắc phục vụ cũng cho biết trong trường hợp nào yêu cầu bị từ chối hoặc phải chờ và giới hạn của thời gian chờ. Nói chung quy tắc xếp hàng chờ phục vụ là ai đến trước sẽ được phục vụ trước - FCFS. Tuy nhiên không phải quy tắc này luôn được áp dụng mà có thể có khách đến sau được phục vụ trước - LIFO, thường gặp ở hệ thống cung cấp vật tư khi mà dự trữ không có sẵn, nghĩa là khách phải chờ, khi đó hệ thống sẽ phục vụ khách kế tiếp (đến sau) hoặc như trong thang máy, người vào thang máy cuối cùng sẽ là người được ra khỏi thang máy trước. Quyền ưu tiên cũng giúp khách đến sau được phục vụ trước.
Có nhiều trường hợp quyền này còn buộc hệ phục vụ phải ngưng phục vụ khách hàng đang làm dang dở để phục vụ khách hàng có quyền ưu tiên này. Trong thực tế ví dụ bác sĩ đang khám bệnh cho bạn thì có bệnh nhân cấp cứu. Lúc đó bác sĩ sẽ yêu cầu bạn chờ và ưu tiên tới ca cấp cứu trước.4 Khả năng của hệ thống LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Có một số hệ thống vì kích thước của hệ không thể cho phép quá nhiều người chờ đợi, hoặc chỉ phục vụ được một số lượng khách hạn chế. Ta gọi đó là do kích thước của hệ hạn chế, nên chỉ chấp nhận một số lượng khách nhất định trong xếp hàng chờ.
Hiện tượng này rất thường gặp ở các phòng khám chữa bệnh, họ chỉ phục vụ một số bệnh nhân có hạn, và áp dụng cách phát số, nếu quá đông thì nhiều khách bị hết số, nghĩa là bị từ chối phục vụ.5 Số kênh phục vụ: Các kênh phục vụ được hiểu là những thiết bị kỹ thuật hoặc con người được tổ chức quản lý một cách thích hợp nhằm phục vụ các yêu cầu, các tín hiệu đến hệ thống. Chẳng hạn ở các trạm điện thoại tự động, kênh phục vụ là các đường dây liên lạc cùng các thiết bị kỹ thuật khác phục vụ cho việc đàm thoại. Một hệ thống phục vụ có thể có nhiều kênh phục vụ đồng thời. Những hệ thống này có thể có hai kiểu xếp hàng như một hàng chờ chung cho cả hệ hoặc nhiều hàng chờ cho từng kênh phục vụ.
Trường hợp có các hàng chờ cho từng kênh ta có thể xem như các hệ phục vụ song hành.6 Số pha (số giai đoạn): - Hệ thống một pha: là hệ thống mà khách hàng chỉ đi qua một nơi phục vụ xong việc sẽ ra khỏi hệ thống. - Hệ thống nhiều pha: là hệ thống mà khách hàng được phục vụ tại nhiều vị trí khác nhau tuần tự theo một thứ tự nhất định nào đó. Ví dụ: Khi đi khám bệnh: Lấy sổ khám đến phòng khám bệnh đến quầy nhận thuốc.