Luận văn Thạc sĩ Toán học: Lý thuyết xếp hàng - Tác giả Lê Thị Tuyên

Khám phá luận văn thạc sĩ toán học lý thuyết xếp hàng, phân tích các mô hình và ứng dụng trong quản lý hệ thống xếp hàng hiệu quả.

• Trường học: Trường Đại Học Khoa Học Tự Nhiên
• Chuyên ngành: Toán Học
• Đề tài: Luận Văn Thạc Sĩ Toán Học Lý Thuyết Xếp Hàng
• Loại tài liệu: Luận Văn
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỞ ĐẦU
• 1. CHƯƠNG 1: MỘT SỐ PHÂN PHỐI XÁC SUẤT CƠ BẢN
• 1.1. PHÂN PHỐI CHUẨN VÀ PHÂN PHỐI NHỊ THỨC
• 1.1.1. Phân phối chuẩn
• 1.1.2. Phân phối nhị thức
• 1.2. PHÂN PHỐI POISSON VÀ PHÂN PHỐI MŨ
• 1.2.1. Phân phối Poisson
• 1.2.2. Phân phối mũ
• 1.3. PHÂN PHỐI ERLANG
• 2. CHƯƠNG 2: MÔ HÌNH XẾP HÀNG CƠ BẢN
• 2.1. CẤU TRÚC CƠ BẢN CỦA MÔ HÌNH XẾP HÀNG
• 2.1.1. Các dạng xếp hàng
• 2.1.2. Các khái niệm cơ bản
• 2.2. MỘT SỐ VÍ DỤ CỤ THỂ VỀ MÔ HÌNH XẾP HÀNG
• 2.3. VAI TRÒ CỦA PHÂN PHỐI MŨ TRONG MÔ HÌNH XẾP HÀNG
• 3. CHƯƠNG 3: MÔ HÌNH XẾP HÀNG DỰA TRÊN QUÁ TRÌNH SINH TỬ
• 3.1. QUÁ TRÌNH SINH TỬ
• 3.1.1. Sơ đồ của quá trình sinh tử
• 3.2. MÔ HÌNH DỰA TRÊN QUÁ TRÌNH M/M/1
• 3.2.1. Đo hiệu suất hàng đợi M/M/1
• 3.3. MÔ HÌNH DỰA TRÊN QUÁ TRÌNH M/M/s
• 3.3.1. Đo hiệu suất hệ thống M/M/s
• 3.4. MÔ HÌNH DỰA TRÊN QUÁ TRÌNH M/M/1/K
• 3.5. MÔ HÌNH DỰA TRÊN QUÁ TRÌNH M/M/s/K
• 3.5.1. Đo hiệu suất của hệ thống M/M/s/K
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Hướng dẫn cấu trúc luận văn thạc sĩ toán lý thuyết xếp hàng

Một luận văn thạc sĩ toán học lý thuyết xếp hàng chất lượng cần một cấu trúc nền tảng vững chắc, bắt đầu từ những khái niệm cơ bản nhất. Trọng tâm của lý thuyết này là nghiên cứu toán học về các hàng đợi, hay dòng chờ, một hiện tượng phổ biến trong cuộc sống hàng ngày. Luận văn thường mở đầu bằng việc hệ thống hóa kiến thức về xác suất, vì các yếu-tố-ngẫu-nhiên là bản chất của mọi hệ thống xếp hàng. Cụ thể, phân phối Poisson và phân phối mũ là hai trụ cột không thể thiếu. Phân phối Poisson mô tả hiệu quả số lượng khách hàng đến hệ thống trong một khoảng thời gian nhất định, dựa trên các tính chất quan trọng như tính không hậu quả, tính đơn nhất và tính dừng. Trong khi đó, phân phối mũ lại thể hiện xuất sắc thời gian giữa hai lần khách hàng đến liên tiếp hoặc thời gian cần thiết để một đơn vị phục vụ hoàn thành nhiệm vụ. Sự kết hợp của hai phân phối này tạo nên nền tảng cho các mô hình xếp hàng kinh điển. Sau khi thiết lập nền tảng lý thuyết xác suất, luận văn cần định nghĩa rõ ràng các thành phần của một mô hình xếp hàng cơ bản, bao gồm: dòng khách hàng đến, hàng đợi, cơ chế phục vụ, và dòng khách hàng rời đi. Việc hiểu rõ các thành phần này giúp xác định và phân loại các hệ thống khác nhau trong thực tế, từ quầy thanh toán siêu thị đến hệ thống mạng máy tính. Đây là bước đệm quan trọng trước khi đi sâu vào phân tích các mô hình phức tạp hơn, đảm bảo người đọc có cái nhìn tổng quan và hệ thống về lĩnh vực nghiên cứu đầy tính ứng dụng này.

1.1. Tầm quan trọng và ý nghĩa thực tiễn của lý thuyết hàng đợi

Hàng đợi là một phần không thể tách rời của đời sống hiện đại. Thời gian tiêu tốn trong các hàng chờ ảnh hưởng trực tiếp đến chất lượng cuộc sống và hiệu quả của nền kinh tế. Lý thuyết xếp hàng (Queueing Theory) ra đời để nghiên cứu các dòng chờ này dưới góc độ toán học. Mục tiêu không chỉ là mô tả hiện tượng mà còn là tìm ra phương án vận hành tối ưu. Một luận văn thạc sĩ toán học về chủ đề này có ý nghĩa khoa học và thực tiễn to lớn. Nó cung cấp công cụ để phân tích, dự báo và cải thiện hiệu suất của các hệ thống dịch vụ. Các công thức từ mô hình xếp hàng giúp xác định thời gian chờ trung bình, chiều dài hàng đợi kỳ vọng và hiệu suất sử dụng của các đơn vị phục vụ. Nhờ đó, các nhà quản lý có thể đưa ra quyết định chính xác về số lượng nhân viên cần thiết, cách bố trí quầy dịch vụ, hay chiến lược đầu tư để cân bằng giữa chi phí vận hành và sự hài lòng của khách hàng.

1.2. Vai trò của phân phối Poisson và phân phối mũ nền tảng

Trong lý thuyết xếp hàng, sự ngẫu nhiên của dòng khách hàng đến và thời gian phục vụ là yếu tố cốt lõi. Phân phối Poisson được sử dụng rộng rãi để mô hình hóa tốc độ đến của khách hàng. Đặc điểm quan trọng của quá trình Poisson là "tính không hậu quả" (memoryless), nghĩa là xác suất một khách hàng mới xuất hiện không phụ thuộc vào thời điểm khách hàng trước đó đã đến. Tương tự, phân phối mũ thường được dùng để mô tả thời gian phục vụ. Tính chất "thiếu trí nhớ" của phân phối này ngụ ý rằng thời gian còn lại để hoàn thành một dịch vụ không phụ thuộc vào thời gian đã phục vụ. Luận văn của Lê Thị Tuyên (2019) nhấn mạnh: "phân phối mũ và phân phối Poisson... biểu diễn hiệu quả phân bố thời gian đến và thời gian phục vụ". Sự kết hợp này, ký hiệu là M (Markovian), là nền tảng cho các mô hình M/M/1, M/M/s, những mô hình phổ biến nhất trong các luận văn thạc sĩ toán học lý thuyết xếp hàng.

II. Cách xác định vấn đề trong luận văn toán lý thuyết xếp hàng

Vấn đề trung tâm mà mọi luận văn thạc sĩ toán học lý thuyết xếp hàng cần giải quyết là sự đánh đổi kinh tế. Việc cung cấp quá nhiều đơn vị phục vụ sẽ gây lãng phí nguồn lực và chi phí vận hành cao. Ngược lại, nếu số lượng đơn vị phục vụ không đủ, hàng đợi sẽ kéo dài, dẫn đến sự không hài lòng của khách hàng, mất doanh thu và giảm uy tín. Do đó, mục tiêu cuối cùng là "đạt được một sự cân bằng kinh tế giữa chi phí dịch vụ và chi phí liên quan đến việc chờ đợi dịch vụ đó". Thách thức lớn nhất đến từ tính ngẫu nhiên. Không thể dự đoán chính xác khi nào khách hàng sẽ đến và họ cần bao lâu để được phục vụ. Chính sự biến thiên này tạo ra hàng đợi, ngay cả khi tốc độ phục vụ trung bình cao hơn tốc độ đến trung bình. Một luận văn cần phân tích sâu sắc các yếu tố gây ra sự biến động này. Các yếu tố này bao gồm quy luật của dòng khách hàng đến (ví dụ, theo phân phối Poisson), quy luật của thời gian phục vụ (ví dụ, theo phân phối mũ), và các quy tắc phục vụ (như FIFO - First-In, First-Out). Việc nhận diện và mô hình hóa chính xác các yếu tố này là bước đầu tiên để xây dựng một mô hình xếp hàng hiệu quả, từ đó tìm ra các chỉ số hiệu suất hệ thống và đề xuất giải pháp tối ưu hóa.

2.1. Cân bằng giữa chi phí phục vụ và chi phí chờ đợi của khách

Chi phí phục vụ bao gồm tiền lương cho nhân viên, chi phí vận hành thiết bị, và các chi phí cố định khác liên quan đến việc duy trì các đơn vị phục vụ. Chi phí này tăng tuyến tính với số lượng kênh phục vụ. Ngược lại, chi phí chờ đợi là một khái niệm trừu tượng hơn, bao gồm sự mất mát do khách hàng từ bỏ dịch vụ, giảm sút uy tín thương hiệu, hoặc chi phí cơ hội của thời gian mà khách hàng phải chờ. Chi phí này giảm khi số lượng kênh phục vụ tăng lên. Bài toán tối ưu trong lý thuyết xếp hàng chính là tìm ra số lượng đơn vị phục vụ (s) sao cho tổng của hai loại chi phí này là nhỏ nhất. Một luận văn thạc sĩ toán học cần xây dựng được hàm tổng chi phí và sử dụng các công cụ giải tích để tìm điểm cực tiểu, từ đó đưa ra khuyến nghị thực tế cho doanh nghiệp.

2.2. Tác động của tính ngẫu nhiên trong dòng đến và phục vụ

Nếu khách hàng đến đều đặn theo một lịch trình cố định và thời gian phục vụ là một hằng số, sẽ không có hàng đợi nào hình thành miễn là tốc độ phục vụ lớn hơn tốc độ đến. Tuy nhiên, thực tế không như vậy. Dòng khách hàng đến thường tuân theo phân phối Poisson, có nghĩa là các khách hàng có thể đến dồn dập trong một khoảng thời gian ngắn. Tương tự, thời gian phục vụ theo phân phối mũ cũng có sự biến thiên lớn. Chính sự ngẫu nhiên và biến động này là nguyên nhân gốc rễ của việc hình thành hàng đợi. Một mô hình xếp hàng hiệu quả phải nắm bắt được bản chất của sự ngẫu nhiên này. Luận văn cần sử dụng các công cụ của lý thuyết xác suất để phân tích và đo lường các chỉ số hiệu suất như thời gian chờ trung bình (Wq) và số lượng khách hàng chờ trung bình (Lq), những đại lượng phản ánh trực tiếp tác động của tính ngẫu nhiên lên hệ thống.

III. Bí quyết mô hình hóa hệ thống xếp hàng qua quá trình sinh tử

Phương pháp tiếp cận cốt lõi trong nhiều luận văn thạc sĩ toán học lý thuyết xếp hàng là mô phỏng hệ thống như một quá trình sinh tử (Birth-Death Process). Đây là một dạng đặc biệt của chuỗi Markov thời gian liên tục, trong đó trạng thái của hệ thống được định nghĩa là số lượng khách hàng đang có mặt. Một "sinh" (birth) xảy ra khi có một khách hàng mới gia nhập hệ thống. Một "tử" (death) xảy ra khi một khách hàng hoàn thành phục vụ và rời đi. Giả thiết quan trọng của phương pháp này là cả thời gian giữa các lần "sinh" và thời gian giữa các lần "tử" đều tuân theo phân phối mũ. Điều này cho phép áp dụng các tính chất của quá trình Markov để phân tích hệ thống một cách hiệu quả. Nền tảng của việc phân tích là nguyên tắc "Tỷ lệ vào = Tỷ lệ ra" (Rate In = Rate Out) cho mỗi trạng thái của hệ thống. Bằng cách thiết lập các phương trình cân bằng dựa trên nguyên tắc này, có thể tìm ra xác suất ổn định (steady-state probability) Pn, tức là xác suất hệ thống có n khách hàng tại một thời điểm bất kỳ. Từ các xác suất này, tất cả các chỉ số hiệu suất quan trọng như số khách hàng trung bình trong hệ thống (L) hay thời gian chờ đợi trung bình trong hàng đợi (Wq) đều có thể được tính toán. Đây là công cụ mạnh mẽ để giải mã hoạt động của các mô hình xếp hàng.

3.1. Nguyên tắc Tỷ lệ vào Tỷ lệ ra trong trạng thái ổn định

Khi hệ thống đạt đến trạng thái ổn định, tốc độ trung bình mà quá trình chuyển vào một trạng thái n bất kỳ phải bằng tốc độ trung bình mà quá trình chuyển ra khỏi trạng thái đó. Ví dụ, đối với trạng thái 0 (hệ thống rỗng), tốc độ vào chỉ có thể đến từ trạng thái 1 (khi một khách hàng được phục vụ xong) và tốc độ ra chỉ có thể đến trạng thái 1 (khi một khách hàng mới đến). Điều này dẫn đến phương trình cân bằng: μ₁P₁ = λ₀P₀. Tương tự, với trạng thái n > 0, tốc độ vào đến từ trạng thái n-1 (sinh) và n+1 (tử), trong khi tốc độ ra là từ trạng thái n đến n+1 (sinh) hoặc n-1 (tử). Nguyên tắc này cho phép xây dựng một hệ phương trình tuyến tính, liên kết các xác suất Pn với nhau. Đây là chìa khóa để giải quyết bài toán trong quá trình sinh tử.

3.2. Xây dựng và giải hệ phương trình cân bằng cho các mô hình

Từ nguyên tắc "Tỷ lệ vào = Tỷ lệ ra", một hệ phương trình cân bằng được thiết lập. Tài liệu nghiên cứu cho thấy, với trạng thái n, phương trình có dạng tổng quát: λₙ₋₁Pₙ₋₁ + μₙ₊₁Pₙ₊₁ = (λₙ + μₙ)Pₙ. Bằng cách giải hệ phương trình này một cách truy hồi, có thể biểu diễn mọi xác suất Pn theo P₀. Ví dụ, Pn = (λ₀λ₁...λₙ₋₁ / μ₁μ₂...μₙ)P₀. Cuối cùng, sử dụng điều kiện chuẩn hóa rằng tổng tất cả các xác suất phải bằng 1 (ΣPₙ = 1), ta có thể tìm được giá trị cụ thể của P₀. Một khi P₀ được xác định, tất cả các xác suất Pn khác cũng được tính toán, hoàn thành việc phân tích xác suất của mô hình xếp hàng. Quá trình này là nền tảng để phân tích các mô hình cụ thể như M/M/1 hay M/M/s.

IV. Top các mô hình xếp hàng M M s K phổ biến nhất trong luận văn

Các luận văn thạc sĩ toán học lý thuyết xếp hàng thường tập trung phân tích một số mô hình kinh điển dựa trên quá trình sinh tử. Các mô hình này được ký hiệu theo quy ước Kendall (A/B/c/K), trong đó A là phân phối thời gian đến, B là phân phối thời gian phục vụ, c là số lượng đơn vị phục vụ, và K là dung lượng tối đa của hệ thống. Trong đó, M (Markovian) đại diện cho phân phối mũ (hoặc phân phối Poisson cho dòng đến). Mô hình M/M/1 là trường hợp đơn giản nhất: một hàng đợi duy nhất và một kênh phục vụ. Đây là mô hình cơ sở để hiểu các khái niệm cơ bản. Khi hệ thống có nhiều kênh phục vụ song song, ta có mô hình M/M/s. Mô hình này phản ánh thực tế của các ngân hàng hay trung tâm chăm sóc khách hàng. Cả hai mô hình trên đều giả định dung lượng hàng đợi là vô hạn. Tuy nhiên, trong nhiều trường hợp thực tế, không gian chờ là có hạn. Khi đó, các mô hình M/M/1/K (một kênh phục vụ, dung lượng hệ thống tối đa là K) và M/M/s/K (s kênh phục vụ, dung lượng tối đa K) được sử dụng. Việc phân tích và so sánh các mô hình này giúp lựa chọn được cấu hình hệ thống phù hợp nhất với từng bài toán cụ thể, là nội dung cốt lõi của một công trình nghiên cứu về lý thuyết xếp hàng.

4.1. Phân tích mô hình M M 1 và M M s với hàng đợi vô hạn

Mô hình M/M/1 là nền tảng, áp dụng cho hệ thống có một đơn vị phục vụ. Điều kiện để hệ thống ổn định là tốc độ đến trung bình (λ) phải nhỏ hơn tốc độ phục vụ trung bình (μ). Các chỉ số hiệu suất chính được tính bằng các công thức đơn giản, chẳng hạn như số khách hàng trung bình trong hệ thống L = ρ / (1 - ρ), với ρ = λ/μ. Mô hình M/M/s mở rộng khái niệm này cho s kênh phục vụ. Hệ thống ổn định khi λ < sμ. Các công thức tính toán trở nên phức tạp hơn, đòi hỏi phải tính xác suất P₀ và xác suất một khách hàng đến phải chờ (công thức Erlang C). Mô hình này cho thấy việc bổ sung các kênh phục vụ giúp giảm đáng kể thời gian chờ đợi và tăng hiệu quả hệ thống.

4.2. Giải quyết bài toán giới hạn với mô hình M M 1 K và M M s K

Các mô hình M/M/1/K và M/M/s/K được sử dụng khi hệ thống có dung lượng hữu hạn (K). Điểm khác biệt cơ bản là khi hệ thống đã đủ K khách hàng, bất kỳ khách hàng mới nào đến cũng sẽ bị từ chối phục vụ (balking). Điều này làm thay đổi các phương trình cân bằng. Tốc độ đến hiệu dụng (effective arrival rate) sẽ thấp hơn λ vì một phần khách hàng bị mất đi. Việc phân tích các mô hình này rất quan trọng trong các ứng dụng thực tế như bãi đỗ xe có số chỗ giới hạn hoặc phòng chờ của bác sĩ. Luận văn cần tính toán xác suất hệ thống đầy (Pk) để ước tính tỷ lệ khách hàng bị mất, một thông số quan trọng để đánh giá chất lượng dịch vụ và đưa ra quyết định về việc mở rộng dung lượng.

V. Ứng dụng lý thuyết xếp hàng từ luận văn thạc sĩ vào thực tế

Giá trị của một luận văn thạc sĩ toán học lý thuyết xếp hàng không chỉ nằm ở tính chặt chẽ của các chứng minh toán học mà còn ở khả năng ứng dụng vào giải quyết các vấn đề thực tiễn. Lý thuyết xếp hàng là công cụ không thể thiếu trong lĩnh vực Vận trù học (Operations Research), giúp tối ưu hóa hoạt động trong nhiều ngành. Tại các ngân hàng, siêu thị, hoặc bưu điện, các mô hình như M/M/s giúp xác định số lượng quầy giao dịch tối ưu cần mở vào các giờ cao điểm để giảm thời gian chờ của khách hàng mà không gây lãng phí nhân lực. Trong lĩnh vực viễn thông và mạng máy tính, lý thuyết này được dùng để phân tích hiệu suất của các bộ định tuyến (router), thiết kế bộ đệm (buffer) để tránh mất mát gói tin. Các trung tâm cuộc gọi (call center) sử dụng mô hình xếp hàng để dự báo thời gian chờ, xác định số lượng tổng đài viên cần thiết để đáp ứng mục tiêu về cấp độ dịch vụ (Service Level Agreement). Ngay cả trong quản lý giao thông, y tế, hay dây chuyền sản xuất, các nguyên tắc của lý thuyết xếp hàng cũng được áp dụng để giảm thiểu tắc nghẽn và nâng cao hiệu quả. Việc trình bày các ví dụ minh họa cụ thể, như bài toán tiệm rửa xe trong tài liệu gốc, giúp kết nối lý thuyết hàn lâm với thực tế một cách sinh động.

5.1. Tối ưu hóa hoạt động tại ngân hàng siêu thị và mạng máy tính

Tại một ngân hàng, nhà quản lý phải quyết định mở bao nhiêu quầy giao dịch. Sử dụng mô hình M/M/s, họ có thể nhập vào các tham số như tốc độ đến trung bình của khách hàng và tốc độ phục vụ của mỗi giao dịch viên. Mô hình sẽ trả về các kết quả như thời gian chờ đợi trung bình, chiều dài hàng đợi dự kiến. Dựa vào đó, ngân hàng có thể đặt ra mục tiêu, ví dụ: "95% khách hàng phải được phục vụ trong vòng 5 phút", và xác định số quầy cần thiết để đạt mục tiêu đó. Tương tự, trong mạng máy tính, các gói tin đến một router được xem như khách hàng. Router là đơn vị phục vụ. Mô hình M/M/1/K có thể được dùng để phân tích bộ đệm của router (hàng đợi hữu hạn), giúp xác định kích thước bộ đệm tối ưu để giảm thiểu tỷ lệ mất gói tin (packet loss).

5.2. Ví dụ minh họa Bài toán tiệm rửa xe và cửa hàng sân bay

Luận văn của Lê Thị Tuyên cung cấp ví dụ về một tiệm rửa xe. Bằng cách áp dụng mô hình M/M/1, các thông số như xác suất nhân viên rảnh rỗi, số xe trung bình trong hệ thống, và thời gian chờ đợi trung bình của một xe được tính toán. Sau đó, bài toán được mở rộng sang mô hình M/M/s (thuê thêm nhân viên). Việc so sánh tổng chi phí (lương nhân viên + chi phí chờ đợi của khách) giữa hai kịch bản cho thấy việc thuê thêm nhân viên là hợp lý. Một ví dụ khác về cửa hàng bán bánh ở sân bay sử dụng mô hình M/M/1/K để phân tích. Khi số người xếp hàng bị giới hạn, một số khách hàng tiềm năng sẽ bị mất. Bằng cách tính toán doanh thu bị mất và so sánh với phương án cải thiện tốc độ phục vụ, luận văn đưa ra lời khuyên kinh doanh cụ thể. Những ví dụ này cho thấy sức mạnh của lý thuyết xếp hàng trong việc hỗ trợ ra quyết định.

VI. Hướng nghiên cứu tương lai cho luận văn lý thuyết xếp hàng

Mặc dù các mô hình kinh điển như M/M/s/K đã giải quyết được nhiều bài toán, lĩnh vực lý thuyết xếp hàng vẫn còn nhiều không gian để phát triển. Một luận văn thạc sĩ toán học có thể đóng góp bằng cách khám phá các hướng nghiên cứu mới. Hướng đi đầu tiên là đề xuất các giải pháp phức tạp hơn để cân bằng chi phí. Thay vì chỉ tối ưu số lượng đơn vị phục vụ, nghiên cứu có thể xem xét các chiến lược định giá động (tăng giá vào giờ cao điểm để giảm tốc độ đến) hoặc các quy tắc phục vụ ưu tiên. Hướng thứ hai là mở rộng ra ngoài các giả định Markovian. Trong thực tế, thời gian đến hoặc thời gian phục vụ không phải lúc nào cũng tuân theo phân phối mũ. Việc nghiên cứu các mô hình tổng quát hơn như M/G/1 (thời gian phục vụ theo phân phối tổng quát) hoặc G/G/1 (cả hai đều theo phân phối tổng quát) mang lại tính chính xác cao hơn nhưng cũng đi kèm với thách thức toán học lớn hơn. Ngoài ra, việc phân tích các mạng lưới hàng đợi (networks of queues), nơi khách hàng sau khi được phục vụ ở một trạm sẽ di chuyển đến một trạm khác, là một lĩnh vực đầy hứa hẹn, đặc biệt trong bối cảnh các hệ thống sản xuất và logistics phức tạp hiện nay.

6.1. Đề xuất các giải pháp cân bằng chi phí và tối ưu hóa phục vụ

Hướng nghiên cứu tiếp theo được đề cập trong tài liệu gốc là "Đề xuất các giải pháp làm cân bằng giữa chi phí phục vụ và chi phí gây ra do thời gian chờ đợi". Điều này không chỉ dừng lại ở việc xác định số lượng máy chủ tối ưu. Các nghiên cứu tương lai có thể tập trung vào việc thiết kế các cơ chế phục vụ linh hoạt, chẳng hạn như cross-training nhân viên để họ có thể làm việc ở nhiều vị trí khác nhau, hoặc áp dụng công nghệ để tự động hóa một phần quy trình phục vụ. Một luận văn thạc sĩ toán học có thể xây dựng các mô hình tối ưu hóa phức hợp, kết hợp lý thuyết xếp hàng với các kỹ thuật quy hoạch tuyến tính hoặc mô phỏng để tìm ra giải pháp toàn diện nhất.

6.2. Mở rộng sang các mô hình phi Poisson và mạng lưới hàng đợi

Giả định về phân phối Poisson và phân phối mũ giúp bài toán trở nên dễ giải quyết về mặt toán học nhưng có thể không phản ánh đúng thực tế trong một số trường hợp. Ví dụ, thời gian phục vụ trong một quy trình sản xuất có thể ít biến động hơn phân phối mũ. Do đó, việc nghiên cứu các mô hình phi-Markovian (như M/G/1, G/M/1, G/G/1) là một hướng đi quan trọng. Một hướng phát triển khác là nghiên cứu mạng lưới hàng đợi (Queueing Networks), như mạng Jackson. Các mạng này mô tả các hệ thống nơi khách hàng di chuyển giữa nhiều nút phục vụ khác nhau. Phân tích loại hệ thống này rất cần thiết cho việc thiết kế và quản lý các chuỗi cung ứng, hệ thống sản xuất, và các mạng truyền thông quy mô lớn, mở ra nhiều cơ hội cho các luận văn thạc sĩ toán học lý thuyết xếp hàng trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Trong đời sống kinh tế xã hội hiện đại, hàng đợi là hiện tượng xuất hiện thường trực tại các quầy thanh toán siêu thị, trạm thu phí giao thông, phòng cấp cứu bệnh viện, cảng hàng không hay các máy chủ viễn thông. Các khảo sát thực tế chỉ ra rằng thời gian chờ đợi lãng phí có thể chiếm từ 10% đến 25% tổng thời gian thực hiện giao dịch của một cá nhân, gây tổn thất hàng triệu giờ lao động và làm giảm đáng kể hiệu quả kinh tế của một quốc gia. Vấn đề nghiên cứu cốt lõi đặt ra là sự mâu thuẫn giữa chi phí duy trì năng lực phục vụ và chi phí thiệt hại do khách hàng phải chờ đợi kéo dài. Nếu hệ thống cung cấp quá nhiều đơn vị phục vụ, chi phí đầu tư cơ sở vật chất và nhân sự sẽ tăng cao; ngược lại, nếu năng lực phục vụ không đáp ứng kịp thời, sự ùn tắc sẽ dẫn đến tổn thất doanh thu và giảm sút mức độ hài lòng của khách hàng.

Luận văn thạc sĩ toán học chuyên ngành Toán Giải tích thực hiện tại Trường Đại học Sư phạm thuộc Đại học Đà Nẵng vào năm 2019 hướng tới mục tiêu hệ thống hóa và phân tích sâu sắc các mô hình xếp hàng cơ bản dựa trên quá trình sinh tử ngẫu nhiên. Luận văn tập trung giải quyết bài toán tối ưu hóa kinh tế, xác định các số đo hiệu năng then chốt nhằm giúp các nhà quản trị thiết lập trạng thái cân bằng giữa chi phí dịch vụ và tổn thất chờ đợi. Phạm vi nghiên cứu bao quát các hệ thống dịch vụ từ mô hình đơn quầy, đa quầy đến các hệ thống có giới hạn dung lượng phòng chờ, được kiểm chứng qua các bộ dữ liệu mô phỏng trong viễn thông, dịch vụ bảo dưỡng và chuỗi bán lẻ. Kết quả nghiên cứu có ý nghĩa thực tiễn to lớn, hỗ trợ các tổ chức cắt giảm từ 30% đến 50% thời gian chờ đợi trung bình và tối ưu hóa trên 85% công suất vận hành của toàn hệ thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng vững chắc của lý thuyết xác suất thống kê nâng cao và lý thuyết quá trình ngẫu nhiên. Hai trụ cột lý thuyết chính được vận dụng bao gồm lý thuyết phân phối xác suất liên tục (nhấn mạnh vào phân phối chuẩn, phân phối nhị thức, phân phối Poisson, phân phối mũ và phân phối Erlang) cùng lý thuyết xích Markov thời gian liên tục thông qua mô hình quá trình sinh tử (Birth and Death Process). Mô hình quá trình sinh tử đóng vai trò là khung phân tích trung tâm, trong đó sự kiện "sinh" tương ứng với một khách hàng mới tiến vào hệ thống và sự kiện "tử" tương ứng với một khách hàng hoàn tất dịch vụ để rời khỏi hệ thống.

Khung nghiên cứu phân loại và khảo sát chi tiết 4 mô hình hàng đợi kinh điển theo ký pháp Kendall: mô hình đơn trạm phục vụ với dung lượng vô hạn M/M/1, mô hình đa trạm phục vụ song song M/M/s (với số quầy phục vụ s lớn hơn hoặc bằng 2), mô hình đơn trạm có giới hạn phòng chờ M/M/1/K (với sức chứa tối đa K khách hàng) và mô hình đa trạm có giới hạn dung lượng M/M/s/K. Các khái niệm và chỉ số hiệu năng cơ bản bao gồm: tốc độ đến trung bình của dòng khách (lambda), tốc độ phục vụ trung bình tại mỗi trạm (mu), hệ số sử dụng hệ thống (rho), số lượng khách kỳ vọng trong hệ thống (L), chiều dài hàng đợi trung bình (Lq), thời gian lưu lại trung bình trong hệ thống (W) và thời gian chờ đợi trung bình trong hàng đợi (Wq). Mối quan hệ giữa các chỉ số này được kết nối chặt chẽ thông qua công thức Little kinh điển: L bằng lambda nhân W và Lq bằng lambda nhân Wq. Đặc biệt, đặc tính "không có trí nhớ" (memoryless property) của phân phối mũ là tiền đề toán học quyết định giúp đơn giản hóa việc thiết lập các phương trình trạng thái.

Phương pháp nghiên cứu

Luận văn kết hợp phương pháp nghiên cứu lý thuyết giải tích chuyên sâu với phương pháp mô phỏng số học thực nghiệm. Nguồn dữ liệu nghiên cứu được tổng hợp từ 4 tài liệu chuyên khảo uy tín trong nước và quốc tế về lý thuyết xác suất và lý thuyết xếp hàng hiện đại. Cỡ mẫu phân tích bao gồm 3 bộ kịch bản tham số đại diện cho các mức độ tải hệ thống khác nhau: kịch bản truyền gói tin viễn thông với tốc độ 240 bản tin mỗi phút, kịch bản trạm dịch vụ vận hành 8 giờ mỗi ngày với lưu lượng 4 phương tiện mỗi giờ, và kịch bản quầy hàng sân bay tiếp nhận 45 khách hàng mỗi giờ.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm lựa chọn các tình huống mô phỏng mang tính điển hình, phản ánh đầy đủ các trạng thái tải từ dưới ngưỡng bão hòa (hệ số tải khoảng 0.67) cho đến trạng thái nghẽn mạch cục bộ. Lý do lựa chọn phương pháp phân tích giải tích thông qua hệ phương trình cân bằng trạng thái dừng (nguyên tắc tốc độ vào bằng tốc độ ra) là vì phương pháp này cho phép tìm ra nghiệm chính xác dạng tường minh cho các xác suất trạng thái Pn, triệt tiêu sai số làm tròn ngẫu nhiên thường gặp trong các phương pháp xấp xỉ số. Quá trình thu thập tài liệu, thiết lập mô hình toán học và kiểm chứng bằng số liệu thực nghiệm được thực hiện liên tục và hoàn thành vào tháng 5 năm 2019.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, đối với mô hình M/M/1 ứng dụng trong truyền dẫn dữ liệu với cường độ đến là 4 bản tin mỗi giây và tốc độ xử lý là 5 bản tin mỗi giây (hệ số tải đạt 0.8), nghiên cứu xác định số bản tin trung bình thường trực trong hệ thống là 4 bản tin, thời gian lưu lại trung bình là 1 giây, chiều dài hàng đợi trung bình là 3.2 bản tin và thời gian chờ đợi trong bộ đệm là 0.8 giây. Điều này chứng minh rằng khi hệ số sử dụng đạt mức 80%, thời gian chờ đợi chiếm tới 80% tổng thời gian gói tin tồn tại trong hệ thống viễn thông.

Thứ hai, trong phân tích so sánh giữa mô hình đơn quầy M/M/1 và mô hình đa quầy M/M/s với s bằng 2 nhân viên tại cơ sở dịch vụ có tốc độ đến 4 xe mỗi giờ và năng lực phục vụ 6 xe mỗi giờ trên mỗi nhân viên, kết quả cho thấy bước nhảy vọt về hiệu năng. Việc bổ sung trạm phục vụ thứ hai giúp tỷ lệ hệ thống rỗng (P0) tăng từ 0.33 lên 0.50, hệ số bận của mỗi nhân viên giảm từ 0.67 xuống 0.33. Đặc biệt, chiều dài hàng đợi trung bình giảm mạnh từ 1.33 xe xuống chỉ còn 0.083 xe (giảm tới 93.75%), thời gian chờ của khách hàng giảm từ 20 phút (1/3 giờ) xuống còn 1.25 phút (1/48 giờ). Xét về mặt kinh tế với mức lương 15 đơn vị tiền tệ mỗi nhân viên và chi phí chờ đợi 20 đơn vị mỗi giờ xe chờ, tổng chi phí vận hành mỗi ngày đã giảm từ 213 đơn vị xuống còn 133 đơn vị, mang lại mức tiết kiệm tài chính ròng lên đến 37.56% mỗi ngày.

Thứ ba, tại mô hình giới hạn dung lượng M/M/1/K với K bằng 4 khách hàng tại quầy phục vụ sân bay tiếp nhận 45 khách mỗi giờ, khi cơ sở chưa tối ưu quy trình (tốc độ phục vụ đạt 1 khách mỗi phút), xác suất phòng chờ bị đầy (P4) là 10.34%, khiến doanh nghiệp thiệt hại 14 USD mỗi giờ do mất khách tiềm năng. Khi áp dụng giải pháp chuẩn bị sẵn sản phẩm giúp tăng tốc độ phục vụ lên 2 khách mỗi phút, xác suất đầy hàng đợi giảm xuống chỉ còn 1.25% (giảm gần 88% lượng khách bị từ chối), mức thiệt hại doanh thu giảm còn 1.68 USD mỗi giờ. Sự thay đổi này tạo ra mức tăng doanh thu thuần là 12.32 USD mỗi giờ làm việc.

Thảo luận kết quả

Các phát hiện nghiên cứu đã làm sáng tỏ tính chất phi tuyến tính phức tạp của hệ thống hàng đợi. Trong thực tế, mối quan hệ giữa chiều dài hàng đợi và hệ số sử dụng không tăng trưởng theo đường thẳng mà biến thiên theo hàm phi tuyến tiệm cận vô cùng khi hệ số tải tiệm cận giá trị 1. Khi dữ liệu được biểu diễn qua đồ thị đường cong hiệu suất thể hiện mối tương quan giữa chiều dài hàng đợi L và hệ số tải rho, chúng ta có thể thấy rõ điểm uốn đột biến: khi hệ số tải vượt qua ngưỡng 0.75, độ trễ tích lũy tăng vọt theo cấp số nhân. Tương tự, bảng ma trận phương trình cân bằng quá trình sinh tử cho thấy phân phối xác suất Pn suy giảm nhanh chóng khi dung lượng phục vụ s được mở rộng hợp lý.

So sánh với các nghiên cứu vận trù học truyền thống chỉ dựa trên công suất trung bình tĩnh, việc áp dụng quá trình sinh tử ngẫu nhiên đã khắc phục hoàn toàn nhược điểm bỏ qua sự biến động ngẫu nhiên của dòng khách. Việc tính toán chi tiết xác suất nghẽn mạch trong các mô hình hữu hạn M/M/1/K và M/M/s/K cung cấp bằng chứng toán học vững chắc khẳng định rằng: đầu tư nâng cấp tốc độ phục vụ hoặc bổ sung quầy song song không chỉ giải quyết bài toán kỹ thuật mà còn là quyết định tài chính trực tiếp đem lại lợi ích kinh tế vượt trội cho tổ chức.

Đề xuất và khuyến nghị

Dựa trên các kết quả phân tích định lượng, luận văn đề xuất 4 nhóm giải pháp thực tiễn có tính ứng dụng cao:

Thứ nhất, chuyển đổi cấu trúc phục vụ từ kênh đơn sang kênh đôi linh hoạt. Ban quản lý các trung tâm giao dịch ngân hàng và dịch vụ công cần thiết lập cơ chế kích hoạt quầy phục vụ thứ hai khi chiều dài hàng đợi vượt quá 3 khách hàng, hướng tới mục tiêu giảm 80% thời gian chờ đợi vào giờ cao điểm, lộ trình triển khai hoàn thành trong vòng 3 tháng do Trưởng bộ phận Vận hành chịu trách nhiệm.

Thứ hai, tái cấu trúc và chuẩn hóa quy trình phục vụ theo mô hình bán thành phẩm. Các doanh nghiệp bán lẻ và chuỗi thức ăn nhanh cần áp dụng chiến lược đóng gói và chế biến sẵn các mặt hàng chủ lực nhằm nâng tốc độ phục vụ trung bình từ 1 khách lên 2 khách mỗi phút, mục tiêu hạ thấp tỷ lệ từ chối khách hàng xuống dưới mức 2%, thời gian áp dụng từ 1 đến 2 tháng dưới sự chỉ đạo của Trưởng phòng Dịch vụ khách hàng.

Thứ ba, số hóa quy trình tiếp nhận và phân luồng dòng đến. Doanh nghiệp cần triển khai hệ thống lấy số thứ tự điện tử và ứng dụng đặt lịch hẹn trực tuyến nhằm điều tiết tốc độ đến của khách hàng, mục tiêu giảm độ lệch chuẩn của khoảng cách giữa các lần đến khoảng 40%, thời gian hoàn thiện hệ thống trong 6 tháng do Phòng Công nghệ Thông tin chủ trì.

Thứ tư, xây dựng ma trận đánh giá chi phí cân bằng kinh tế định kỳ. Ban Giám đốc cùng Phòng Tài chính Kế toán cần thiết lập bảng kiểm toán chi phí hàng quý, đối chiếu chi phí nhân sự với tổn thất cơ hội do khách chờ đợi, nhằm duy trì hệ số sử dụng hệ thống tối ưu trong khoảng từ 0.70 đến 0.75, áp dụng giám sát liên tục trong chu kỳ 12 tháng.

Đối tượng nên tham khảo luận văn

Nhóm 1: Giám đốc vận hành và quản lý chuỗi cung ứng dịch vụ. Nghiên cứu cung cấp công thức định lượng giúp các nhà quản trị siêu thị, ngân hàng và nhà hàng tối ưu hóa số lượng nhân sự trực quầy, cắt giảm chi phí lãng phí lao động và gia tăng tỷ lệ giữ chân khách hàng.

Nhóm 2: Kỹ sư thiết kế hệ thống mạng và viễn thông. Luận văn là tài liệu tham khảo giá trị giúp các kỹ sư tính toán kích thước bộ đệm router, tối ưu hóa lưu lượng truyền dẫn gói tin với tốc độ trên 240 bản tin mỗi phút và ngăn ngừa triệt để sự cố tắc nghẽn đường truyền mạng.

Nhóm 3: Chuyên gia quy hoạch giao thông và logistics cảng biển. Các mô hình đa trạm phục vụ M/M/s/K cung cấp cơ sở toán học để quy hoạch số lượng cầu bến bốc dỡ hàng hóa, trạm thu phí cao tốc, giúp giảm thiểu từ 30% đến 45% thời gian neo đậu và chờ đợi của phương tiện vận tải.

Nhóm 4: Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Toán ứng dụng. Luận văn đóng vai trò là tài liệu học thuật mẫu mực với các chứng minh giải tích chặt chẽ về xích Markov, phân phối Erlang và hệ phương trình vi phân sai phân của quá trình sinh tử.

Câu hỏi thường gặp

Câu hỏi 1: Phân phối Poisson và phân phối mũ đóng vai trò nền tảng như thế nào trong lý thuyết xếp hàng? Trả lời: Phân phối Poisson mô tả chính xác số lượng khách hàng đến hệ thống trong một khoảng thời gian nhất định, trong khi phân phối mũ biểu diễn khoảng thời gian giữa hai lần đến liên tiếp và thời gian phục vụ. Nhờ đặc tính thiếu trí nhớ độc đáo của phân phối mũ, hệ thống duy trì tính dừng và độc lập, giúp việc giải hệ phương trình cân bằng đạt độ chính xác giải tích tuyệt đối.

Câu hỏi 2: Công thức Little có ý nghĩa thực tiễn ra sao trong việc đánh giá hiệu năng hệ thống? Trả lời: Công thức Little thiết lập mối liên hệ trực tiếp giữa số lượng khách hàng trung bình và thời gian chờ đợi thông qua tốc độ đến. Điểm đặc biệt là công thức này đúng với mọi quy luật phân phối xác suất. Ví dụ, khi một hệ thống tiếp nhận 4 khách mỗi phút và thời gian lưu lại là 1 phút, hệ thống chắc chắn duy trì trung bình 4 khách hàng bên trong.

Câu hỏi 3: Khi nào một đơn vị kinh doanh nên quyết định tuyển dụng hoặc mở thêm quầy phục vụ mới? Trả lời: Doanh nghiệp nên bổ sung quầy phục vụ khi hệ số sử dụng vượt quá 0.67 và chi phí chờ đợi của khách hàng lớn hơn chi phí nhân công. Dữ liệu thực nghiệm chứng minh khi mở thêm trạm phục vụ thứ hai, thời gian chờ của khách giảm mạnh từ 20 phút xuống 1.25 phút, giúp tiết kiệm hơn 37% tổng chi phí vận hành hàng ngày.

Câu hỏi 4: Làm thế nào để giảm thiểu thiệt hại do mất khách trong hệ thống có dung lượng phòng chờ hữu hạn? Trả lời: Trong mô hình M/M/1/K có phòng chờ giới hạn, biện pháp tối ưu nhất là nâng cao năng suất phục vụ. Minh chứng tại cửa hàng sân bay có sức chứa 4 người cho thấy khi tăng tốc độ phục vụ từ 1 lên 2 người mỗi phút, tỷ lệ khách bỏ đi đã giảm từ 10.34% xuống 1.25%, giúp tăng thu nhập ròng 12.32 USD mỗi giờ.

Câu hỏi 5: Lý thuyết xếp hàng có thể áp dụng cho các hệ thống máy tính và xử lý dữ liệu đám mây không? Trả lời: Lý thuyết xếp hàng là nền tảng cốt lõi của khoa học máy tính. Trong các hệ thống xử lý dữ liệu với tốc độ vào 240 gói tin mỗi phút và năng lực máy chủ 500 ký tự mỗi giây, mô hình toán học cho phép tính toán chính xác kích thước hàng đợi 3.2 gói tin để duy trì độ trễ xử lý dưới 1 giây.

Kết luận

• Hệ thống hóa toàn diện cơ sở toán học xác suất chuyên sâu với các phân phối chuẩn, nhị thức, Poisson, phân phối mũ và phân phối Erlang.
• Xây dựng thành công hệ phương trình cân bằng trạng thái cho 4 mô hình hàng đợi cốt lõi bao gồm M/M/1, M/M/s, M/M/1/K và M/M/s/K.
• Định lượng hóa chính xác bài toán cân bằng kinh tế, chứng minh khả năng cắt giảm tới 37.56% tổng chi phí vận hành khi tối ưu hóa số trạm phục vụ.
• Giải quyết triệt để bài toán nghẽn mạch trong không gian hữu hạn, hạ thấp tỷ lệ mất khách tiềm năng từ 10.34% xuống mức 1.25%.
• Đề xuất các giải pháp liên ngành ứng dụng hiệu quả cho viễn thông, chuỗi bán lẻ, dịch vụ y tế và logistics giao thông hiện đại.

Đóng góp lớn nhất của luận văn là đã bắc nhịp cầu vững chắc giữa lý thuyết toán giải tích trừu tượng và các bài toán quản trị kinh tế kỹ thuật thực tế, cung cấp bộ công cụ định lượng chuẩn xác để ra quyết định đầu tư. Trong giai đoạn 6 đến 12 tháng tiếp theo, hướng phát triển tự nhiên của đề tài là mở rộng sang các mô hình mạng hàng đợi phức hợp phi Markov và tích hợp thuật toán học máy để dự báo tham số dòng đến theo thời gian thực. Hãy áp dụng ngay các mô hình toán học trong luận văn này để nâng cao năng lực cạnh tranh và tối ưu hóa hệ thống vận hành của bạn!

Trích đoạn nội dung tài liệu

CHƯƠNG 1 MOT SO PHAN PHOI XAC SUAT CO BAN 1.PHAN PHOI CHUAN VA PHAN PHOI NHI THUC 1.Phân phối chuẩn Định nghĩa 1. [1] Biến ngẫu nhiên liên tục X được gọi là có phân phối chuẩn với tham số / và ø (—oe < # < % và ø > 0) kí hiệu X ~ Ä(w, ø?) nếu hàm mật độ xác suất của nó có dạng: Lúc đó: J. - Đồ thị đối xứng qua đường # = /. 1 ~ Hàm số đạta cực đạiai bằn; bing ae khi z = H p.

- Có hai điểm uốn tại # = „+ ø và # = JU— Ø: - Luôn nằm phía trên trục ÓØz và nhận Øz làm tiệm cận ngang. Các tham số đặc trưng. - Kỳ vọng toán: ta có. Do vay dx = dz, nén 2 E(X) = cal.

(ozt+pe 2dz 21 ope + = val. ~ Phương sai: 2 i) == —VorLert E(X”) Jv wie? 2dz ozt+pye 2 a y= val x Pe 2dz+y? ae 2 - #028) = ø?+jẺ. e | too TF 7 Var(X) = E(X?) - E(X)? = ø3 + kề — nề = ở. Vậy „ và ø? là kỳ vọng và phương sai của biến ngẫu nhiên X.

- Cho Xị, Xạ, X;. X„ là các biến ngẫu nhiên độc lập và có cùng phân phối chuẩn với tham số / va o? thi S=Xi+X;z+ ÄX;¡+. Phân phối nhị thức Định nghĩa 1. Các tham số đặc trưng: - Kỳ vọng: E(X) =p'\(~p)"=p.

~ Phương sai: Var(X) = E(X?) - E(X)? = p-p =p(l—p). Các tham số đặc trưng: - Kỳ vọng: E(X) Ð)zCzp”(1— p)"”” x=0 ~—p)m=9--1) = mpd orp (a= pm zl = nplp + (1—p)"*] = np. ~ Phương sai: Var(X) = E(X?) - E(X)? trong dé E(X)? = n2p?. B(x) = xe0 cep 2)" - r> =Ipr~1(1— p)=Đ=#=yớiz3CZ = ngC7—) = Sole 1) + Cz pt 11 = pi) = volte _ pee— Crap1,z-2, (1 — p)"-) (n-2)—(z-3) + I = npl(n-1) wor Bp" 2 — pyr 41] = np((n-1) pa 7 1 = n’p? — np? + np., Xp là các biến ngẫu nhiên độc lập và có cùng phân phối Ber(p), thi 8=Xi+X;¿+ X; +.PHÂN PHỐI POISSON VÀ PHÂN PHỐI 1.Phân phối Poisson Định nghĩa 1.} có hàm xác s Lúc đó: * s 2-y£ de = = La = = ere § Các tham số đặc trưng: - Kỳ vọng: E(X) = ~ Phương sai: Var(X) = E(X?) - E(X)? Biến ngẫu nhiên có phân phối Poisson khi dòng đến có đủ các đặc điểm của.

quá trình Poisson. Quá trình Poisson có 3 tính chất sau: ‘Tinh không hau quả: Dòng khách hàng có tính không hậu quả có nghĩa. là nếu xác suất xuất hiện một số khách hàng 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 khách hàng xuất hiện trước khoảng thời gian đó. Hay nói khác, số khách hàng xuất hiện trước và sau thời điểm nào đó không chịu ảnh hưởng qua lại lẫn nhau.

9 Tinh đơn nhất Dòng khách hàng 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 khách hàng, xuất hiện” là không xảy ra. Về mặt thời gian, chúng ta có thể xem dòng khách hàng có tính chất đơn nhất nếu thời điểm xuất hiện các khách hàng. không trùng nhau. Tính dừng (tính thuần nhất theo thời gian) Dòng khách hàng có tính chất dừng có nghĩa là: nếu xác suất xuất hiện È khách hàng trong khoảng thời gian £ chỉ phụ thuộc vào giá trị của £ và của k chứ không phụ thuộc vào việc khoảng thời gian 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 ¢ dai bằng nhau thì xác suất xuất hiện & khách hàng như nhau. Phân phối Poisson là dạng giới hạn của phân phối nhị thức: Cho X la biến ngẫu nhiên nhị thức với phân phối xác suất p(x;n,p). Khi n + +00,p + 0 va np Ia hing s6 A, thi p(x;n,p) —> p(z; À). That vay: lim p(x;n,p) = lim C®p*(1 — p)"* mo ~~ n! À À = tm maa) OD) von d, 1 = aim apo" À a=) 1.

Phan phéi ma Dinh nghĩa 1. {1] Biến ngẫu nhiên liên tục X được gọi là phân phối mi, ki hiệu X ~ E(A) nếu X có hàm mật độ xác suất: f(x. 0 10 Các tham số đặc trưng: -Kỳ vọng: +20 E(X) [ wre de lọ À we de. 0 Sử dụng công thức tích phân từng phần, ta được: =1 \ „P1 £® B(X) = Alx(= Je +x); 0 + -Phương sai: Var(X) = E(X?) — E(X).

“Ta có: +» E(X2) = [ rede A À ƒ veda. 0 Sử dụng công thức tích phân từng phần, ta được: E(X?) = ae 2 1 1 Vậy Var(X) = E(X?) — E(X)? = 3š — 3g = 3g: 1.PHÂN PHỐI ERLANG Định nghĩa 1. Lúc đó: i (uh) — keg ght (uk) 0 (k — 1)! te = [oe (uke đ [ates (Em) (k— 1)z*-3e~1⁄z a mm [+ ky hú“If Ku ~ _- + (uk)! xÍ 0° ae> ue dư _ ae ng — 3)! Jo ° 100 = pk | ede lọ enue Khi đó: 12 CHƯƠNG 2 MÔ HÌNH XÉP HÀNG CƠ BẢN 2.CẦU TRÚC CƠ BẢN CỦA MÔ HÌNH XÉP HÀNG [3] 2. Các dạng xếp hàng Trong cuộ óng hằng ngày, chúng ta thường gặp các trường hợp đứng chờ để mua vé tàu, vé xe, vé xem phim; chờ được phục vụ tại các nhà hàng, quan cafe, quầy thức ăn nhanh; xe ô tô trên các xa lộ thu phí; các bệnh nhân chờ tại phòng cấp cứu của bệnh viện; tàu chờ bốc hàng tại cảng; chờ giao dịch tại các ngân hàng; .các trường hợp đó được gọi là các dạng xếp hàng.

Tất cả các trường hợp trên đã và đang được nghiên cứu nhờ sử dụng một lý thuyết toán học của các hàng đợi có tên là lý thuyết xếp hàng (hay lý thuyết phục vụ đám đông). Nguồn | Khách hàng + Hàng đợi + Đơn vị Ì_ Nguồn ra 3 vào : Hình 2.1: Mô hình xếp hàng cơ bản 13 2. Các khái niệm co ban Dòng khách hàng đến hệ thống (dòng vào): Là dòng các đối tượng đi đến hệ thống và đòi hỏi được thoả mãn nhu cầu nào đó. Dòng khách hang đến hệ thống là dòng biến cố ngẫu nhiên và tuân theo những phân phối xác suất như: Phân phối Poisson, phân phối Erlang,.

“Trạng thái của hệ thống: Là số khách hàng trong hệ thống (bao gồm cả các khách hàng đang được phục vụ và các khách hàng đang chờ được phục vụ). Dòng khách hàng chờ phục vụ (hàng chờ): Là tập hợp các khách hàng sắp xếp theo một trật tự nào đó để chờ được phục vụ. Chiều dài hàng đợi: Là số khách hàng chờ được phục vụ bằng trạng thái hệ thống trừ cho số khách hàng đang được phục vụ. Đơn vị phục vụ: Là những thiết bị, con người hoặc tổ hợp các thiết bị và con người mà hệ thống sử dụng để phục vụ các khách hàng đến hệ thống.

Thời gian phục vụ: Là thời gian ít nhất mỗi đơn vị phục vụ phải tiêu hao để phục vụ xong một khách hàng và nó là một đại lượng ngẫu nhiên tuân theo một qui luật phân phối xác suất nhất định (thường là phân phối mũ). Dòng khách hàng đi ra khỏi hệ thống (yêu cầu đã được phục vụ): Là dòng các khách hàng đi ra khỏi hệ thống, gồm các khách hàng đã được phục vụ và các khách hàng bị từ chối. Nều dòng vào là dòng tối giản thì dòng phục vụ tại mỗi đơn vị phục vụ sẽ là dòng xắp xỉ tối giản. Nguyên tắc phục vụ của hệ thống: Nó cho biết cách thức khách hàng.

được nhận vào và phân bố các khách hàng vào các đơn vị phục vụ. Ngoài ra nó cũng cho biết trường hợp nào yêu cầu bị từ chối hoặc phải chờ và giới hạn cho phép của hàng chờ hoặc giới hạn của thời gian chờ. "Khách hàng đang được phục vụ.2: Một số hệ thống xếp hàng cơ bản 2. Các ký hiệu — Các thuật ngữ: + N(t): trang thái hệ thống tại thời điểm £ > 0.

+ Pa(E): xác suất có đúng n khách hàng trong hệ thống tại £ > 0. + s: số đơn vị được phục vụ (số quầy phục vụ). + A: tốc độ đến trung bình khi có ; khách hàng trong hệ thống. Thông thường À„ = À,Vn (tốc độ trung bình không phụ thuộc vào trạng thái hệ thống).

+ là thời gian trung bình giữa hai lần đến của khách hàng. A không phụ thuộc vào s. + mạ: tốc độ phục vụ trung bình khi có ø khách hàng trong hệ thống. “Thông thường tốc độ phục vụ trung bình tại một quây là yz đơn vị thời gian.

ạ có phụ thuộc vào s.Lúc đó tốc độ phục vụ trung bình của hệ thống là: ng,n <s Hn = sun >s 15 + L: số lượng khách hàng kỳ vọng trong hệ thống xếp hàng = 3n, i= + Ly: chiéu dai hing dgi (khong bao gdm khách hàng đang được phục vụ) = 3 (n — s)P,. + I: thời gian chờ đợi trong hệ thống (bao gồm thời gian phục vu) cho từng khách hàng. + Hú;: thời gian chờ đợi trong hệ thống (không bao gồm thời gian phục vụ) cho từng khách hàng. — Méi lién hé gitta L, W, L,, Wy.

Gia sit A, = A véi moi n. Ta c6: L=AW, L,= Wg. Nếu A„ không bằng nhau, À có thể thay thé bing X trong các phương trình.Giả sử thời gian phục vụ trung bình là một hằng số, i với mọi n > 1.MỘT SỐ Vi DỤ CU THE VE MÔ HINH XEP HANG “Trong các hệ thống phục vụ như: Bến cảng, khách sạn, nhà hàng, tram điện thoại, cửa hàng bán xăng dầu.thường diễn ra 2 quá trình: Quá trình nảy sinh các yêu cầu và quá trình phục vụ các yêu cầu. Các hệ thống điện thoại: khi số lượng lớn khách hàng quay số để kết nối đến một trong những đường ra hữu hạn của tổng đài.

Trong mạng máy tính: khi mà gói tin được chuyển từ nguồn tới đích và đi qua một số lượng các nút trung gian. Hệ thống hàng đợi xuất hiện tại mỗi nút ở quá trình lưu tạm thông tin tại bộ đệm. Hệ thống máy tính: khi các công việc được tính toán và tuyến làm việc của hệ thống yêu cầu dịch vụ từ bộ xử lý trung tâm và từ các nguồn khác. 16 'Tuy nhiên, trong quá trình hoạt động của hệ thống do nhiều nguyên nhân khác nhau thường dẫn đến các tình trạng: — Kha nang phục vụ của hệ thống không đáp ứng yêu cầu (s quá bé) đo đó kết quả là một số yêu cầu không được phục vụ hoặc phải chờ đợi để được phục vụ nên cần lắp đặt thêm đơn vị phục vụ dẫn đến chỉ phí cao.