LÝ THUYẾT XẾP HÀNG: LỊCH SỬ, MÔ HÌNH, NÓ DÙNG ĐỂ LÀM GÌ VÀ VÍ DỤ - TOÁN HỌC - 2025

Các lý thuyết xếp hàng là một nhánh của toán học mà nghiên cứu các hiện tượng và hành vi trong dòng chờ đợi. Chúng được định nghĩa khi người dùng yêu cầu một dịch vụ nhất định quyết định đợi máy chủ được xử lý.

Nghiên cứu các yếu tố hiện diện trong các dòng chờ thuộc bất kỳ loại nào, cho dù chúng là yếu tố con người, xử lý dữ liệu hoặc hoạt động. Kết luận của ông luôn được ứng dụng trong các dây chuyền sản xuất, đăng ký và chế biến.

Phông chữ Pexels

Các giá trị của nó phục vụ trong việc tham số hóa các quá trình trước khi thực hiện chúng, đóng vai trò là yếu tố tổ chức chính để quản lý kế hoạch chính xác.

Lịch sử

Người chịu trách nhiệm chính cho sự phát triển của nó là nhà toán học người Đan Mạch Agner Kramp Erlang, người làm việc tại công ty viễn thông Copenhagen phone Exchange.

Agner ghi nhận nhu cầu ngày càng tăng trong hệ thống cung cấp dịch vụ điện thoại của công ty. Đó là lý do tại sao việc nghiên cứu các hiện tượng toán học có thể được định lượng trong hệ thống đường chờ bắt đầu.

Ấn phẩm chính thức đầu tiên của ông là một bài báo có tựa đề Lý thuyết xếp hàng, được xuất bản vào năm 1909. Trọng tâm của ông chủ yếu hướng đến vấn đề định cỡ đường dây và trung tâm chuyển mạch điện thoại cho dịch vụ cuộc gọi.

Mô hình và các yếu tố

Có nhiều mô hình hàng đợi khác nhau trong đó một số khía cạnh chịu trách nhiệm xác định và mô tả đặc điểm của từng hàng đợi. Trước khi xác định các mô hình, các phần tử tạo nên mọi mô hình hàng đợi được trình bày.

-Các dụng cụ

Nguồn gia nhập hoặc dân số tiềm năng

Đây là tập hợp những người có thể nộp đơn cho dịch vụ. Điều này áp dụng cho bất kỳ loại biến nào, từ người dùng con người đến tập hợp gói dữ liệu. Chúng được phân thành hữu hạn và vô hạn tùy thuộc vào bản chất của tập hợp.

Cái đuôi

Nó đề cập đến tập hợp các phần tử đã là một phần của hệ thống dịch vụ. Mà đã đồng ý đợi sự sẵn sàng của nhà điều hành. Họ đang trong trạng thái chờ đợi các giải pháp của hệ thống.

-Hệ thống đuôi

Nó được tạo thành từ bộ ba được hình thành bởi hàng đợi, cơ chế phục vụ và kỷ luật của hàng đợi. Nó cung cấp cấu trúc cho giao thức hệ thống, điều chỉnh các tiêu chí lựa chọn cho các phần tử trong hàng đợi.

- Cơ chế dịch vụ

Đó là quá trình mà dịch vụ được cung cấp cho mỗi người dùng.

-Khách hàng

Đó là bất kỳ yếu tố nào thuộc về dân số tiềm năng yêu cầu một dịch vụ. Điều quan trọng là phải biết tỷ lệ gia nhập của khách hàng, cũng như xác suất nguồn tạo ra họ.

-Queue dung lượng

Nó đề cập đến sức chứa tối đa của các mặt hàng có thể chờ được phục vụ. Nó có thể được coi là hữu hạn hoặc vô hạn, trong hầu hết các trường hợp là vô hạn theo tiêu chí của tính thực tiễn.

-Kỷ luật của hàng đợi

Nó là giao thức mà theo đó thứ tự mà khách hàng được phục vụ được xác định. Nó đóng vai trò như một kênh xử lý và đặt hàng cho người dùng, chịu trách nhiệm về việc sắp xếp và di chuyển của họ trong hàng đợi. Theo tiêu chí của bạn, nó có thể có nhiều loại khác nhau.

- FIFO: Từ viết tắt trong tiếng Anh First in first out, hay còn gọi là FCFS đến trước được phục vụ trước. Có nghĩa là, tương ứng, trước đến trước và đến trước sẽ được phục vụ. Cả hai hình thức đều biểu thị rằng khách hàng đầu tiên đến sẽ là người đầu tiên được phục vụ.

- LIFO: Cuối cùng ra trước còn được gọi là ngăn xếp hoặc LCFS đến cuối cùng được phân phối trước. Nơi khách hàng đến sau cùng được phục vụ trước.

- RSS: Lựa chọn ngẫu nhiên dịch vụ còn gọi là dịch vụ SIRO theo thứ tự ngẫu nhiên, trong đó khách hàng được lựa chọn theo tiêu chí ngẫu nhiên hoặc ngẫu nhiên.

Mô hình

Có 3 khía cạnh chi phối mô hình xếp hàng cần xem xét. Đây là những điều sau đây:

- Phân bổ thời gian giữa các lượt đến: đề cập đến tốc độ các đơn vị được thêm vào hàng đợi. Chúng là các giá trị hàm và phụ thuộc vào các biến khác nhau tùy thuộc vào bản chất của chúng.

- Phân phối thời gian phục vụ: thời gian máy chủ sử dụng để xử lý dịch vụ mà khách hàng yêu cầu. Nó thay đổi tùy theo số lượng hoạt động hoặc thủ tục được thiết lập.

2 khía cạnh này có thể nhận các giá trị sau:

M: phân phối lũy thừa hàm mũ (Markoviana).

D: Phân phối suy giảm (thời gian không đổi).

E _k : Phân phối Erlang với tham số hình dạng k.

G: Phân phối chung (phân phối bất kỳ).

- Số lượng máy chủ: Cổng dịch vụ mở và có sẵn để xử lý máy khách. Chúng rất cần thiết trong định nghĩa cấu trúc của mỗi mô hình xếp hàng.

Bằng cách này, các mô hình xếp hàng được xác định, đầu tiên lấy các chữ cái đầu bằng chữ cái viết hoa của phân phối thời gian đến và phân phối thời gian phục vụ. Cuối cùng, số lượng máy chủ được nghiên cứu.

Một ví dụ khá phổ biến là MM 1, đề cập đến kiểu phân phối thời gian đến và dịch vụ theo cấp số nhân, trong khi làm việc với một máy chủ duy nhất.

Các loại mô hình hàng đợi khác là MM s, MG 1, ME 1, DM 1, trong số những loại khác.

Các loại hệ thống xếp hàng

Có một số loại hệ thống xếp hàng trong đó nhiều biến số đóng vai trò là chỉ số của loại hệ thống được trình bày. Nhưng về cơ bản nó bị chi phối bởi số lượng hàng đợi và số lượng máy chủ. Cấu trúc tuyến tính mà người dùng phải chịu để có được dịch vụ cũng được áp dụng.

- Một hàng đợi và một máy chủ. Đây là cấu trúc thông thường, trong đó người dùng thông qua hệ thống đến sẽ vào hàng đợi, nơi sau khi hoàn thành việc chờ đợi của mình theo nguyên tắc của hàng đợi và được xử lý bởi máy chủ duy nhất.

- Một hàng đợi và nhiều máy chủ. Người dùng, vào cuối thời gian chờ của mình, có thể truy cập vào các máy chủ khác nhau có thể là máy chủ thực thi các quy trình giống nhau, cũng như chúng có thể là riêng tư cho các quy trình khác nhau.

- Nhiều hàng đợi và nhiều máy chủ. Cấu trúc có thể được phân chia cho các quy trình khác nhau hoặc phục vụ như một kênh rộng để đáp ứng nhu cầu cao về dịch vụ chung.

- Một hàng đợi với các máy chủ tuần tự. Người dùng trải qua các giai đoạn khác nhau. Họ vào và chiếm một vị trí trong hàng đợi, và khi được máy chủ đầu tiên phục vụ, họ chuyển sang một giai đoạn mới yêu cầu thực hiện trước đó trong dịch vụ đầu tiên.

Thuật ngữ

- λ: Biểu tượng này (Lambda) thể hiện trong lý thuyết xếp hàng giá trị mong đợi của đầu vào trong mỗi khoảng thời gian.

- 1 / λ: Tương ứng với giá trị mong đợi giữa các lần đến của mỗi người dùng vào hệ thống.

- μ: Ký hiệu Mu tương ứng với số lượng khách hàng dự kiến ​​hoàn thành dịch vụ trên một đơn vị thời gian. Điều này áp dụng cho mọi máy chủ.

- 1 / μ: Thời gian phục vụ mà hệ thống mong đợi.

- ρ: Biểu tượng Rho biểu thị hệ số sử dụng của máy chủ. Nó được sử dụng để đo thời gian máy chủ bận xử lý người dùng.

ρ = λ / sμ

Nếu p> 1, hệ thống sẽ tạm thời, nó sẽ có xu hướng phát triển, bởi vì tỷ lệ tiện ích của máy chủ thấp hơn số lượng người dùng vào hệ thống.

Nếu p <1 hệ thống sẽ duy trì ổn định.

Lý thuyết là gì

Nó được tạo ra để tối ưu hóa quy trình cung cấp dịch vụ điện thoại. Điều này phân định mức độ hữu ích đối với các hiện tượng của các dòng chờ, nơi nó được tìm cách giảm giá trị thời gian và hủy bỏ bất kỳ loại quy trình làm lại hoặc dư thừa nào làm chậm quá trình của người dùng và người vận hành.

Phông chữ Pexels

Ở các cấp độ phức tạp hơn, trong đó các biến đầu vào và dịch vụ nhận các giá trị hỗn hợp, các phép tính được thực hiện ngoài lý thuyết xếp hàng gần như không thể tưởng tượng được. Các công thức được cung cấp bởi lý thuyết đã mở ra phép tính nâng cao trong nhánh này.

Các phần tử có trong công thức

- Pn: Giá trị đề cập đến xác suất "n" đơn vị nằm trong hệ thống.

- Lq: Độ dài của hàng đợi hoặc giá trị trung bình của những người dùng trong đó.

- Ls: Trung bình cộng của các đơn vị trong hệ thống.

- Wq: Tỷ lệ chờ trung bình trong hàng đợi.

- Ws: Tỷ lệ chờ trung bình trong hệ thống.

- _λ: Số lượng khách hàng trung bình sử dụng dịch vụ.

- Ws (t): Giá trị đề cập đến xác suất khách hàng còn lại nhiều hơn “t” đơn vị trong hệ thống.

- Wq (t): Giá trị đề cập đến xác suất khách hàng còn lại nhiều hơn “t” đơn vị trong hàng đợi.

Ví dụ

Cơ quan đăng ký có một máy chủ duy nhất để xử lý hộ chiếu của những người dùng đến. Trung bình mỗi giờ có 35 người dùng tham gia đăng ký. Máy chủ có khả năng phục vụ 45 người dùng mỗi giờ. Trước đây được biết rằng người dùng dành trung bình 5 phút trong hàng đợi.

Bạn muốn biết:

1. Thời gian trung bình mỗi người dùng dành cho hệ thống
2. Số lượng khách hàng trung bình trong hàng đợi

Chúng tôi có λ = 35/45 Khách hàng / phút

μ = 45/60 máy khách / phút

Wq = 5 phút

Phần A

Thời gian trung bình trong hệ thống có thể được tính bằng Ws

Ws = Wq + 1 / μ = 5 phút + 1,33 = 6,33 phút

Theo cách này, tổng thời gian mà người dùng sẽ ở trong hệ thống được xác định, trong đó 5 phút sẽ ở hàng đợi và 1,33 phút với máy chủ.

Phần b

Lq = λ x Wq

Lq = (0,78 phút khách hàng) x (5 phút) = 3,89 khách hàng

Có thể có nhiều hơn 3 khách hàng trong hàng đợi đồng thời.

Người giới thiệu

1. Quản lý hoạt động. Editorial Vértice, ngày 16 tháng 4. 2007
2. Lý thuyết về hàng đợi hoặc hàng đợi. Germán Alberto Córdoba Barahona. Pontificia Universidad Javeriana, 2002
3. Lý thuyết hệ thống giải quyết vấn đề. Roberto Sanchis Llopis. Các ấn phẩm của Universitat Jaume I, 2002
4. Phương pháp định lượng tổ chức công nghiệp II. Joan Baptista Fonollosa Guardiet, José María Sallán Laws, Albert Suñé Torrents. Đại học Politèc. từ Catalunya, 2009
5. Lý thuyết hàng tồn kho và ứng dụng của nó. Biên tập Pax-México, 1967