CHƯƠNG 1. TỔNG QUAN VỀ LÝ THUYẾT XẾP HÀNG 1.1 Lịch sử lý thuyết xếp hàng Lịch sử lý thuyết xếp hàng đã có từ hơn một trăm năm trước. “Waiting Times and Number of Calls” của Johannsen xuất bản năm 1907 (được in lại trên tạp chí Post Office Electrical Engineers Journal, London, tháng 10 năm 1910) dường như là bài báo đầu tiên nói về chủ đề này, nhưng phương pháp được sử dụng trong bài báo này không chính xác về mặt toán học [6]. Hai năm sau đó, nghiên cứu có tầm quan trọng trong lịch sử lý thuyết xếp hàng được đưa ra bởi Agner Krarup Erlang (1/1/1878 – 3/2/1929) – một nhà toán học, nhà thống kê và kỹ sư người Đan Mạch.
Trong rất nhiều tài liệu hiện có, Erlang được giới thiệu là người đầu tiên đưa ra nghiên cứu về lý thuyết xếp hàng. Vào năm 1909 ông đã xuất bản cuốn sách “The Theory of Probabilities and Telephone Conversations”, [11], giới thiệu cho thế giới khái niệm về lý thuyết xếp hàng qua điện thoại. Trong các công trình sau này, ông nhận thấy rằng hệ thống điện thoại thường được đặc trưng bởi (1) đầu vào Poisson, thời gian giữ (dịch vụ) theo cấp số nhân và nhiều kênh (máy chủ), hoặc (2) đầu vào Poisson, thời gian giữ không đổi và một kênh duy nhất [5]. Năm 1917, ông xuất bản công trình quan trọng nhất của mình [12], “Solution of some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges”, [13] chứa các công thức cổ điển của ông về mất cuộc gọi và thời gian chờ.
Và một bài báo đặc biệt của ông cũng cần đề cập đến là “On the Rational Determination of the Number of Circuits” (Brockmeyer và cộng sự), trong đó, lần đầu tiên giải quyết vấn đề tối ưu hóa trong lý thuyết xếp hàng. Nghiên cứu của Erlang đã thu hút sự quan tâm của nhiều nhà toán học khác, những người đã mở rộng công việc của ông. Molina xuất bản bài báo của mình “Application of the Theory of Probability to Telephone Trunking Problems”, nghiên cứu này được tiếp nối một năm sau đó bởi cuốn sách Probability and Its Engineering Uses của Thornton Fry, mở rộng phần lớn công trình trước đó của Erlang. Vào đầu những năm 1930, Felix Pollaczek đã thực hiện một số công việc tiên phong hơn nữa về đầu vào Poisson, đầu ra tùy ý và các vấn đề đơn và đa kênh.
Các nghiên cứu bổ sung được thực hiện vào thời điểm đó ở Nga bởi Kolmogorov và Khintchine, ở Pháp bởi Crommelin, và ở Thụy Điển bởi Palm. Công việc về lý thuyết xếp hàng lấy đà khá chậm trong những ngày đầu của nó, nhưng đã tăng tốc vào những năm 1950, và đã có rất nhiều nghiên cứu được phát triển kể từ đó [5]. Một người đóng góp quan trọng khác cho lý thuyết xếp hàng là David George Kendall (D. Trong bài báo này, ông đề cập đến một “hệ thống xếp hàng đơn giản” (simple queueing system).
Mặc dù trước đó đã có một số lượng lớn các bài báo về chủ đề này, tuy nhiên nghiên cứu của D.G Kendall dã đưa ra một cách tiếp cận có hệ thống và toán học đối với vấn đề của hàng đợi (queue) hay dòng chờ (waiting line). Kendall giới thiệu bộ ký hiệu xếp hàng loại A/B/C. Tiếp sau những công trình mang tính khởi đầu, lý thuyết xếp hàng đã được phát triển thêm cho đến ngày nay và các khía cạnh khác nhau của lý thuyết xếp hàng đã được nhiều tác giả thảo luận, đến nỗi nó đã tạo ra rất nhiều bài báo đánh giá trong nhiều năm, ví dụ như Saaty (1966), Bhat (1969), Koenigsberg (1982), Bitran và Dasu (1992), Medhi (1997), Worthington (2009), Mandelbaum và Hlynka (2009), Wang và cộng sự (2010), C. Lakshmi và Appa Iyer (2013).2 Một số khái niệm cơ bản 1.1 Biến ngẫu nhiên “Trong hệ thống xếp hàng dễ dàng nhìn thấy hai quá trình ngẫu nhiên độc lập: quá trình khách hàng xuất hiện ở đầu vào hệ thống và quá trình phục vụ khách hàng tại đầu ra của hệ thống.
Số lượng khách hàng tại một thời điểm được đặc trưng bởi một biến ngẫu nhiên rời rạc. Tốc độ đến tại một thời điểm cũng như thời gian phục vụ được đặc trưng bởi các biến ngẫu nhiên” [25]. Quá trình ngẫu nhiên là một sự kiện hoặc thử nghiệm có kết quả ngẫu nhiên. Ví dụ: lăn một con súc sắc, chọn bóng bingo,.
Đó là thứ mà không thể dự đoán chính xác một kết quả; có thể có một loạt các khả năng để tính toán xác suất của một kết quả cụ thể. Biến ngẫu nhiên là một loại biến trong thống kê mà các giá trị có thể có của nó phụ thuộc vào kết quả của một hiện tượng ngẫu nhiên nhất định. Vì một biến ngẫu nhiên có thể nhận các giá trị khác nhau, nên nó thường được gắn nhãn bằng một chữ cái (ví dụ: biến “X”). Mỗi biến có một hàm phân phối xác suất cụ thể (một hàm toán học biểu thị xác suất xuất hiện của tất cả các kết quả có thể xảy ra).
Nói một cách cụ thể, biến ngẫu nhiên là một biến có giá trị không xác định hoặc một hàm chỉ định giá trị cho mỗi kết quả của một thử nghiệm [26]. Các biến ngẫu nhiên có các đặc điểm và hành vi riêng biệt [26]: ▪ Các biến ngẫu nhiên được ký hiệu bằng chữ in hoa. ▪ Các biến ngẫu nhiên được liên kết với các quá trình ngẫu nhiên. ▪ Các biến ngẫu nhiên cung cấp các con số cho kết quả của các sự kiện ngẫu nhiên.
15 Hình 1-1 Phân loại biến ngẫu nhiên Nguồn: Tác giả đề xuất Các biến ngẫu nhiên có thể được chia làm hai loại là biến ngẫu nhiên rời rạc, là các biến có giá trị cụ thể; hoặc biến ngẫu nhiên liên tục, là các biến có thể có bất kỳ giá trị nào trong một phạm vi liên tục. Bảng 1-1 Phân loại biến ngẫu nhiên Biến ngẫu nhiên rời rạc Biến ngẫu nhiên liên tục Số lượng giá trị có thể đếm được Số lượng giá trị có thể có là vô hạn Xác suất của mỗi giá trị từ 0 đến 1 Xác suất của mỗi giá trị khác biệt là 0 Tổng tất cả các xác suất = 1. Các Diện tích dưới đường cong (tức tích biến ngẫu nhiên rời rạc với hàm phân không xác định) là 1. Khi 𝑓𝑋 là khối lượng xác suất 𝑚(𝑥) = pdf của 𝑋, ta có : 𝑃(𝑋 = 𝑥) có ∞ ∫ 𝑓𝑋 (𝑥)𝑑 (𝑥) = 1 ∑ 𝑚 (𝑥 ) = 1 −∞ 𝑥 Nguồn : B.
Kjos-Hanssen and S.2 Hàng đợi Hàng đợi được định nghĩa là tập hợp khách hàng được hệ thống hóa để chờ đợi đến lượt được phục vụ bởi nhà cung cấp dịch vụ hoặc trạm dịch vụ. Phương pháp sắp xếp và quản lý những khách hàng như vậy một cách có tổ chức và được xác định rõ ràng được gọi là xếp hàng [28]. Xếp hàng chờ đợi là một hoạt động phổ biến trong cuộc sống hàng ngày và thường xảy ra khi nhu cầu về dịch vụ vượt quá khả năng cung cấp dịch vụ hiện có hoặc khi cơ sở dịch vụ không đầy đủ. Việc xếp hàng dài tại một cơ sở dịch vụ dẫn đến việc tích lũy số lượng khách hàng, do đó thời gian phục vụ ngày càng dài hơn [29].
Các hàng đợi có thể được giải quyết bằng [30]: lý thuyết xếp hàng phân tích (analytical queuing theory), các gói mô phỏng chuyên dụng (dedicated simulation packages) và mô phỏng bằng bảng tính (spreadsheet simulation).3 Lý thuyết xếp hàng Lý thuyết xếp hàng là một nghiên cứu toán học về các dòng chờ hoặc hàng đợi, liên quan đến việc mô hình hóa và phân tích toán học các hệ thống phục vụ các nhu cầu ngẫu nhiên. Lý thuyết xếp hàng thường được coi là một nhánh của vận trù học (OR – Operation Research) vì các mô hình xếp hàng thường được sử dụng trong kinh doanh để đưa ra quyết định về các nguồn lực cần thiết để cung cấp dịch vụ cho khách hàng (theo Stewart, 2009). Lý thuyết xếp hàng được sử dụng rộng rãi để hiểu hành vi của hệ thống xếp hàng nhằm dự đoán, kiểm soát và tối ưu hóa kết quả hoạt động của doanh nghiệp. Đó là một khía cạnh rất quan trọng của việc quản lý thành công hệ thống phục vụ đám đông.
Do đó, không thể đánh giá thấp tầm quan trọng của lý thuyết xếp hàng. Một trong những phần cơ bản của lý thuyết xếp hàng là đánh giá kết quả hoạt động của một hệ thống (theo Kumar, Vij, và Kumar, 2015). Theo Kenton (2019), lý thuyết xếp hàng là một nghiên cứu toán học về sự tắc nghẽn và sự chậm trễ của việc xếp hàng chờ đợi. Nó kiểm tra mọi thành phần của hàng chờ đợi để được phục vụ, bao gồm quá trình đến, quá trình dịch vụ, số lượng máy chủ, số lượng vị trí hệ thống và số lượng khách hàng có thể là cá nhân, gói thông tin, phương tiện, v.
Các ứng dụng thực tế của lý thuyết xếp hàng bao gồm một loạt các ứng dụng như cách cung cấp dịch vụ khách hàng nhanh hơn, cải thiện luồng giao thông, vận chuyển hiệu quả các đơn đặt hàng từ nhà kho và thiết kế hệ thống viễn thông từ mạng dữ liệu đến trung tâm cuộc gọi. Chowdhury (2013) cho rằng lý thuyết xếp hàng là một trong những lý thuyết lâu đời nhất và phổ biến nhất trong các kỹ thuật phân tích định lượng thường được sử dụng và là một nghiên cứu quan trọng trong xã hội hiện đại. Lý thuyết xếp hàng đi sâu phân tích ba quá trình ngẫu nhiên gắn liền với nhau theo trình tự: khách hàng đi đến hệ thống với mật độ ngẫu nhiên ở cuối hàng chờ (Back of the Queue); khách hàng chờ trước khi được phục vụ (Waiting in the Queue); khách hàng được phục vụ với thời lượng ngẫu nhiên ở đầu hàng chờ (Front of the Queue). Nó sử dụng các mô hình xếp hàng để đại diện cho các loại hệ thống xếp hàng khác nhau phát sinh trong thực tế.3 Các yếu tố đặc trưng của hệ thống xếp hàng Hệ thống xếp hàng là một mô hình có cấu trúc gồm những người hoặc khách hàng đến và tham gia vào hàng đợi để chờ dịch vụ.
Sau khi khách hàng nhận được dịch vụ, họ sẽ thoát khỏi hệ thống [34]. Các yếu tố quan trọng của hệ thống xếp hàng là khách hàng và máy chủ. Chúng có nhiều dạng khác nhau trong các lĩnh vực ứng dụng khác nhau. Thuật ngữ khách hàng có thể đề cập đến con người, máy 17 móc, xe tải, bệnh nhân, pallet, máy bay, e-mail, đơn đặt hàng hoặc quần áo bẩn – bất cứ thứ gì đến cơ sở và yêu cầu dịch vụ.