Luận văn: Nghiên cứu bài toán hàng đợi có ưu tiên và ứng dụng mô phỏng

```json { "ai_description": "Luận văn thạc sĩ đi sâu vào nghiên cứu bài toán hàng đợi có ưu tiên, phân tích lý thuyết và ứng dụng mô phỏng thực tế. Khám phá

• Tác giả: Chu Mạnh Toàn
• Trường học: Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên cứu bài toán hàng đợi có ưu tiên và mô phỏng ứng dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan Khám phá Hàng Đợi Có Ưu Tiên và Nền Tảng Lý Thuyết Xếp Hàng Cơ Bản

Trong các hệ thống hiện đại, từ viễn thông đến y tế và sản xuất, việc quản lý tài nguyên và luồng công việc hiệu quả là yếu tố then chốt. Hàng đợi có ưu tiên (Priority Queueing) xuất hiện như một giải pháp mạnh mẽ để giải quyết bài toán này, cho phép các tác vụ quan trọng được xử lý trước, tối ưu hóa hiệu suất tổng thể của hệ thống. Nghiên cứu sâu rộng về mô hình này không chỉ giúp hiểu rõ cơ chế hoạt động mà còn mở ra nhiều ứng dụng thực tiễn quan trọng. Việc áp dụng các công cụ mô phỏng ứng dụng đóng vai trò thiết yếu trong việc phân tích và đánh giá hiệu quả của các thiết kế hệ thống hàng đợi phức tạp, đặc biệt là khi các phép tính toán học thuần túy gặp giới hạn. Phần này sẽ cung cấp cái nhìn tổng quan về hàng đợi có ưu tiên và các khái niệm nền tảng của lý thuyết xếp hàng, đặt cơ sở cho việc phân tích và mô phỏng chuyên sâu hơn.

1.1. Khái niệm cốt lõi Định nghĩa và phân loại hệ thống hàng đợi

Một hệ thống hàng đợi về cơ bản bao gồm các khách hàng đến, một hàng đợi chứa các khách hàng chờ đợi, và các bộ phục vụ. Khái niệm xếp hàng mô tả quá trình khách hàng chờ đợi được phục vụ khi tài nguyên không sẵn có ngay lập tức. Các yếu tố cơ bản của một hệ thống hàng đợi bao gồm nguồn khách hàng, luật đến, hàng đợi, luật phục vụ, và luật ra đi [6]. Việc phân loại Kendall (A/B/C/K/N) cung cấp một khung chuẩn để mô tả các mô hình lý thuyết xếp hàng dựa trên phân phối thời gian đến (A), phân phối thời gian phục vụ (B), số lượng kênh phục vụ (C), dung lượng hệ thống (K) và kích thước nguồn khách hàng (N). Hiểu rõ các thành phần này là bước đầu tiên để xây dựng và phân tích bất kỳ mô hình hàng đợi nào.

1.2. Nền tảng toán học Các mô hình lý thuyết xếp hàng cơ bản

Các mô hình lý thuyết xếp hàng kinh điển như M/M/1, M/M/n và M/M/n/n đóng vai trò nền tảng trong việc phân tích các hệ thống hàng đợi. Mô hình M/M/1 đại diện cho một hệ thống với tỷ lệ đến theo phân phối Poisson, thời gian phục vụ theo phân phối mũ và một bộ phục vụ. Mô hình M/M/n mở rộng với 'n' bộ phục vụ, trong khi M/M/n/n thêm giới hạn về dung lượng hệ thống, không cho phép hàng đợi. Việc phân tích các mô hình này thường dựa trên quá trình sinh tử (Birth-Death Process) để xác định xác suất trạng thái ổn định của hệ thống. Các kết quả từ lý thuyết xếp hàng cung cấp các công thức tính toán các số đo hiệu năng quan trọng như thời gian chờ trung bình, số lượng khách hàng trung bình trong hệ thống và độ chiếm dụng của bộ phục vụ [8].

1.3. Đặc điểm then chốt Cơ chế hoạt động của hàng đợi ưu tiên

Không giống như các hàng đợi thông thường theo nguyên tắc FIFO (First-In, First-Out), hàng đợi có ưu tiên cho phép các khách hàng hoặc tác vụ được phân loại và phục vụ dựa trên mức độ ưu tiên của chúng. Điều này có nghĩa là một khách hàng có ưu tiên cao hơn có thể được phục vụ trước một khách hàng đã chờ lâu hơn nhưng có ưu tiên thấp hơn. Cơ chế này đặc biệt quan trọng trong các môi trường mà một số tác vụ đòi hỏi phản hồi nhanh chóng hoặc có giá trị cao hơn. Các thuật toán lập lịch như FCFS (First Come First Served), SRT (Shortest Remaining Time), hay các kỹ thuật dựa trên mức độ ưu tiên cố định hoặc động đều được sử dụng để quản lý hàng đợi ưu tiên. Mục tiêu chính là tối ưu hóa hiệu năng hệ thống bằng cách đảm bảo các tác vụ quan trọng nhận được tài nguyên cần thiết một cách kịp thời [1].

II. Thách Thức Hiện Đại Tại Sao Cần Nghiên Cứu Hàng Đợi Có Ưu Tiên Trong Các Hệ Thống Phức Tạp

Trong bối cảnh công nghệ phát triển nhanh chóng, các hệ thống thực tế ngày càng trở nên phức tạp với vô số tác vụ đa dạng, mỗi tác vụ có mức độ quan trọng và yêu cầu về thời gian khác nhau. Điều này đặt ra những thách thức đáng kể trong việc thiết kế và quản lý hệ thống hàng đợi, đặc biệt là trong việc đảm bảo sự công bằng, hiệu quả và đáng tin cậy. Việc nghiên cứu hàng đợi có ưu tiên không còn là lựa chọn mà là yêu cầu bắt buộc để giải quyết những vấn đề này, từ việc điều phối lưu lượng mạng đến quản lý bệnh nhân trong bệnh viện. Các phương pháp toán học truyền thống thường không đủ để mô tả hoặc giải quyết hoàn toàn sự phức tạp và động lực học của các tình huống này, đòi hỏi một cách tiếp cận toàn diện hơn, kết hợp cả lý thuyết và thực nghiệm thông qua mô phỏng ứng dụng.

2.1. Hạn chế của phân tích toán học thuần túy trong bài toán hàng đợi

Mặc dù lý thuyết xếp hàng cung cấp các công cụ toán học mạnh mẽ để phân tích các hệ thống hàng đợi cơ bản, nhưng khi đối mặt với sự phức tạp của thực tế, như phân phối đến và phục vụ không theo quy luật thông thường, số lượng kênh phục vụ động, hoặc các chính sách ưu tiên phức tạp, việc sử dụng các công thức giải tích trở nên bất khả thi hoặc đòi hỏi những giả định không thực tế. Các mô hình hàng đợi có ưu tiên trong thế giới thực thường bao gồm nhiều loại khách hàng với các mức ưu tiên khác nhau, khả năng ngắt quãng phục vụ (preemption), và các điều kiện biên động. Trong những trường hợp này, việc tìm kiếm một giải pháp đóng (closed-form solution) gần như không thể, làm nổi bật sự cần thiết của các phương pháp khác như mô phỏng ứng dụng để thu được các số đo hiệu năng đáng tin cậy.

2.2. Sự cần thiết của hàng đợi ưu tiên trong quản lý tài nguyên

Trong nhiều lĩnh vực, khả năng phân loại và ưu tiên các tác vụ là tối quan trọng. Ví dụ, trong mạng viễn thông, các gói dữ liệu thoại hoặc video cần được ưu tiên hơn so với email để đảm bảo chất lượng dịch vụ (QoS). Trong một bệnh viện, bệnh nhân cấp cứu phải được khám trước những người chỉ cần kiểm tra định kỳ. Hàng đợi có ưu tiên giúp tối ưu hóa việc sử dụng tài nguyên hạn chế, giảm thiểu thời gian chờ đợi cho các tác vụ quan trọng và nâng cao sự hài lòng của người dùng. Việc triển khai hiệu quả hàng đợi có ưu tiên đòi hỏi sự hiểu biết sâu sắc về các chính sách lập lịch khác nhau và cách chúng ảnh hưởng đến hiệu năng hệ thống tổng thể.

2.3. Tối ưu hóa hiệu năng hệ thống thông qua quản lý ưu tiên

Mục tiêu cuối cùng của việc triển khai hàng đợi có ưu tiên là tối ưu hóa hiệu năng hệ thống. Điều này liên quan đến việc cân bằng giữa thời gian chờ đợi trung bình, tỷ lệ bỏ cuộc của khách hàng, và độ chiếm dụng của các bộ phục vụ. Một chính sách ưu tiên được thiết kế tốt có thể giảm đáng kể thời gian phản hồi cho các yêu cầu ưu tiên cao, đồng thời vẫn duy trì mức độ phục vụ chấp nhận được cho các yêu cầu ưu tiên thấp hơn. Tuy nhiên, việc thiết lập mức độ ưu tiên một cách không chính xác có thể dẫn đến việc các tác vụ ưu tiên thấp bị trì hoãn vô thời hạn, gây ra tắc nghẽn ở các bộ phận khác. Do đó, việc nghiên cứu hàng đợi có ưu tiên đòi hỏi sự phân tích cẩn thận và thử nghiệm thông qua mô phỏng ứng dụng để đạt được sự cân bằng tối ưu.

III. Phương Pháp Mới Hướng Dẫn Mô Phỏng Hàng Đợi Hiệu Quả Với Công Cụ Chuyên Dụng

Để vượt qua những hạn chế của phân tích toán học và thực sự hiểu được động lực phức tạp của hàng đợi có ưu tiên trong môi trường thực tế, mô phỏng ứng dụng trở thành một công cụ không thể thiếu. Phương pháp này cho phép các nhà nghiên cứu và kỹ sư tạo ra một mô hình ảo của hệ thống hàng đợi và quan sát cách nó hoạt động theo thời gian, thử nghiệm các kịch bản khác nhau mà không ảnh hưởng đến hệ thống thật. Trong số các công cụ mô phỏng, GPSS (General Purpose Simulation System) nổi bật như một ngôn ngữ mạnh mẽ được thiết kế đặc biệt cho các bài toán hàng đợi và các hệ thống sự kiện rời rạc. Việc nắm vững cách sử dụng GPSS là chìa khóa để triển khai các mô hình mô phỏng hàng đợi có ưu tiên một cách hiệu quả và thu được những hiểu biết sâu sắc về hiệu năng hệ thống.

3.1. Các hướng tiếp cận mô phỏng hàng đợi Ưu nhược điểm

Có hai hướng tiếp cận chính trong mô phỏng hàng đợi: mô phỏng sự kiện rời rạc (Discrete Event Simulation - DES) và mô phỏng dựa trên tác nhân (Agent-Based Simulation - ABS). DES tập trung vào các sự kiện xảy ra tại các điểm thời gian cụ thể, như sự kiện khách hàng đến hoặc kết thúc phục vụ. Nó đặc biệt phù hợp cho các bài toán hàng đợi truyền thống và là nền tảng của nhiều công cụ mô phỏng như GPSS. ABS lại mô hình hóa các thực thể độc lập (agents) và cách chúng tương tác với nhau và môi trường, phù hợp hơn cho các hệ thống phức tạp với hành vi emergent. Mỗi hướng tiếp cận có ưu điểm riêng: DES hiệu quả cho việc tính toán các số đo hiệu năng định lượng, trong khi ABS mạnh mẽ trong việc khám phá các hành vi động và tương tác phức tạp. Lựa chọn phương pháp phù hợp phụ thuộc vào mục tiêu nghiên cứu hàng đợi và đặc điểm của hệ thống.

3.2. Giới thiệu về GPSS World Ngôn ngữ mạnh mẽ cho mô phỏng ứng dụng

GPSS World là một ngôn ngữ mô phỏng sự kiện rời rạc được thiết kế để mô hình hóa các hệ thống phức tạp, đặc biệt là các hệ thống hàng đợi. Nó cung cấp một giao diện trực quan và các khối lệnh (blocks) dễ sử dụng để biểu diễn các thành phần của hệ thống như khách hàng (transactions), bộ phục vụ (facilities), và hàng đợi (queues). Một trong những điểm nổi bật của GPSS World là khả năng xử lý hàng đợi có ưu tiên thông qua các lệnh và thuộc tính ưu tiên tích hợp [4]. Ngôn ngữ này cho phép người dùng định nghĩa các luồng công việc, gán mức độ ưu tiên cho các tác vụ, và quan sát hành vi của hệ thống theo thời gian thực. Các kết quả mô phỏng từ GPSS World thường bao gồm các số đo hiệu năng chi tiết như thời gian chờ trung bình, số lượng khách hàng trung bình trong hàng đợi, và tỷ lệ sử dụng tài nguyên, giúp đánh giá và tối ưu hóa thiết kế hệ thống.

3.3. Cách hiện thực hóa hàng đợi có ưu tiên với GPSS World

Để hiện thực hóa hàng đợi có ưu tiên trong GPSS World, người dùng cần tận dụng khả năng gán thuộc tính ưu tiên (PRIORITY) cho các giao dịch (transactions). Khi các giao dịch tiến vào một khối QUEUE hoặc SEIZE, GPSS sẽ tự động xem xét mức độ ưu tiên của chúng. Các giao dịch có ưu tiên cao hơn sẽ được phục vụ trước, hoặc thậm chí có thể ngắt quãng (preempt) các giao dịch ưu tiên thấp hơn đang được phục vụ, tùy thuộc vào cấu hình của hệ thống. GPSS World cung cấp các lệnh như GENERATE để tạo ra các giao dịch với mức độ ưu tiên khác nhau, và các khối như SEIZE, RELEASE, ENTER, LEAVE để quản lý tài nguyên và hàng đợi. Việc này giúp dễ dàng mô phỏng ứng dụng các kịch bản phức tạp của hàng đợi ưu tiên, như trong các hệ thống bưu chính viễn thông hay quản lý luồng dữ liệu, cho phép phân tích tác động của các chính sách ưu tiên khác nhau lên hiệu năng hệ thống [2].

IV. Ứng Dụng Thực Tiễn Khám Phá Tiềm Năng Của Hàng Đợi Có Ưu Tiên Qua Các Bài Toán Minh Họa

Việc nghiên cứu hàng đợi có ưu tiên không chỉ dừng lại ở lý thuyết mà còn được minh chứng qua vô số ứng dụng thực tiễn trong nhiều lĩnh vực khác nhau. Từ việc quản lý lưu lượng giao thông đến tối ưu hóa dây chuyền sản xuất, khả năng phân bổ tài nguyên dựa trên mức độ quan trọng đã mang lại hiệu quả vượt trội. Phần này sẽ đi sâu vào việc trình bày và phân tích các bài toán hàng đợi cụ thể, bao gồm cả tình huống không ưu tiên và có ưu tiên, sử dụng công cụ GPSS World để minh họa cách mô phỏng ứng dụng giúp hiểu rõ hơn về hành vi của hệ thống. Thông qua những ví dụ này, giá trị của việc áp dụng hàng đợi có ưu tiên trong việc nâng cao hiệu năng hệ thống sẽ được làm nổi bật.

4.1. Phân tích bài toán hàng đợi không ưu tiên điển hình

Một bài toán hàng đợi không ưu tiên điển hình có thể được minh họa bằng một trạm dịch vụ khách hàng với một nhân viên duy nhất và một hàng đợi chung. Khách hàng đến theo một phân phối xác suất nhất định và được phục vụ theo nguyên tắc FCFS. Mục tiêu của mô phỏng ứng dụng là xác định các số đo hiệu năng như thời gian chờ trung bình, số lượng khách hàng trung bình trong hàng đợi, và tỷ lệ sử dụng của nhân viên phục vụ. Việc giải bài toán này bằng lý thuyết xếp hàng M/M/1 cung cấp một cơ sở so sánh. Sau đó, mô phỏng hàng đợi bằng GPSS World sẽ giúp xác nhận các kết quả lý thuyết và cung cấp những hiểu biết sâu sắc hơn về hành vi của hệ thống trong các kịch bản cụ thể, đặc biệt khi các giả định lý thuyết không được đáp ứng hoàn hảo.

4.2. Mô phỏng ứng dụng bài toán xếp hàng có ưu tiên với GPSS World

Một ví dụ thực tế về hàng đợi có ưu tiên là hệ thống cấp cứu tại bệnh viện, nơi bệnh nhân được phân loại theo mức độ nghiêm trọng và được phục vụ tương ứng. Bệnh nhân cấp cứu (ưu tiên cao) sẽ được khám trước bệnh nhân thông thường (ưu tiên thấp). Để mô phỏng ứng dụng bài toán này bằng GPSS World, các khách hàng (bệnh nhân) sẽ được tạo ra với các mức độ ưu tiên khác nhau (ví dụ: GENERATE 30,10,,,2 cho ưu tiên cao và GENERATE 5,2,,,1 cho ưu tiên thấp). Khối SEIZE sẽ tự động ưu tiên các giao dịch có mức độ ưu tiên cao hơn. Kết quả mô phỏng hàng đợi sẽ chỉ ra sự khác biệt rõ rệt về thời gian chờ và thời gian lưu lại trong hệ thống giữa các nhóm ưu tiên, làm nổi bật lợi ích của chính sách ưu tiên trong việc giảm thiểu thời gian phản hồi cho các trường hợp khẩn cấp. Việc này giúp đánh giá hiệu năng hệ thống và tối ưu hóa quản lý luồng dữ liệu của bệnh nhân.

4.3. Đánh giá và so sánh hiệu năng hệ thống

Sau khi thực hiện cả hai mô hình hàng đợi (không ưu tiên và có ưu tiên) bằng GPSS World, việc đánh giá và so sánh hiệu năng hệ thống là rất quan trọng. Các số đo hiệu năng chính bao gồm: thời gian chờ trung bình, thời gian lưu lại trong hệ thống trung bình, số lượng trung bình khách hàng trong hàng đợi, và độ chiếm dụng của các bộ phục vụ. So sánh các chỉ số này cho thấy rõ ràng lợi ích của việc áp dụng cơ chế ưu tiên: các khách hàng ưu tiên cao sẽ có thời gian chờ và thời gian lưu lại thấp hơn đáng kể, trong khi khách hàng ưu tiên thấp hơn có thể chịu một chút tăng lên về thời gian chờ, nhưng tổng thể hiệu năng hệ thống về mặt đáp ứng các yêu cầu quan trọng được cải thiện. Phân tích này hỗ trợ ra quyết định trong việc thiết kế và triển khai hàng đợi có ưu tiên trong thực tế, giúp tối ưu hóa tài nguyên và nâng cao chất lượng dịch vụ.

V. Kết Luận Tương Lai Của Nghiên Cứu Hàng Đợi Có Ưu Tiên và Tiềm Năng Mô Phỏng Ứng Dụng

Tổng kết lại, nghiên cứu hàng đợi có ưu tiên và việc áp dụng mô phỏng ứng dụng đã mở ra những cánh cửa mới trong việc hiểu và tối ưu hóa các hệ thống phức tạp trong nhiều ngành công nghiệp. Từ những nền tảng của lý thuyết xếp hàng đến sự tinh vi của các công cụ mô phỏng như GPSS World, khả năng giải quyết bài toán hàng đợi với các yêu cầu ưu tiên đã được nâng cao đáng kể. Mặc dù đã đạt được nhiều thành tựu, lĩnh vực này vẫn còn nhiều tiềm năng phát triển. Việc không ngừng cải tiến các mô hình, thuật toán và công cụ sẽ tiếp tục định hình cách chúng ta quản lý tài nguyên và luồng công việc trong tương lai, hướng tới các hệ thống thông minh hơn, linh hoạt hơn và hiệu quả hơn. Mô phỏng hàng đợi sẽ tiếp tục là một công cụ then chốt trong quá trình này.

5.1. Tóm tắt những điểm chính về hàng đợi có ưu tiên và mô phỏng

Bài viết đã làm rõ các khía cạnh quan trọng của hàng đợi có ưu tiên, bao gồm các đặc điểm, tính chất, cách thức hoạt động và những thách thức liên quan. Chúng ta đã xem xét các thuật toán lập lịch phổ biến như FCFS, SRT và cách chúng được áp dụng trong bối cảnh ưu tiên. Sự cần thiết của mô phỏng ứng dụng, đặc biệt là với công cụ GPSS World, đã được nhấn mạnh như một phương pháp hiệu quả để vượt qua giới hạn của phân tích toán học thuần túy. Thông qua các bài toán hàng đợi minh họa, lợi ích của việc triển khai hàng đợi có ưu tiên trong việc tối ưu hóa hiệu năng hệ thống và quản lý luồng dữ liệu đã được chứng minh rõ ràng. Những phân tích này cung cấp một cái nhìn toàn diện về tầm quan trọng của nghiên cứu hàng đợi có ưu tiên.

5.2. Xu hướng phát triển trong nghiên cứu hàng đợi có ưu tiên

Tương lai của nghiên cứu hàng đợi có ưu tiên dự kiến sẽ tập trung vào việc phát triển các mô hình phức tạp hơn, có khả năng xử lý các hệ thống động và tự thích nghi. Các xu hướng bao gồm việc tích hợp trí tuệ nhân tạo và học máy để dự đoán lưu lượng, tự động điều chỉnh mức độ ưu tiên và tối ưu hóa hiệu năng hệ thống theo thời gian thực. Ngoài ra, việc nghiên cứu các chính sách ưu tiên động (dynamic priority schemes) và cách chúng tương tác với các cơ chế cân bằng tải sẽ tiếp tục là trọng tâm. Sự phát triển của các công cụ mô phỏng ứng dụng tiên tiến hơn, có khả năng tích hợp dữ liệu lớn và trực quan hóa kết quả một cách sinh động, cũng sẽ đóng góp vào sự tiến bộ của lĩnh vực này, hỗ trợ việc tối ưu hóa tài nguyên trong các môi trường ngày càng phức tạp.

5.3. Tiềm năng của mô phỏng ứng dụng trong tương lai

Tiềm năng của mô phỏng ứng dụng trong tương lai là rất lớn. Với sự gia tăng về sức mạnh tính toán và khả năng xử lý dữ liệu, các mô hình mô phỏng hàng đợi sẽ trở nên chi tiết và chính xác hơn bao giờ hết. Chúng sẽ không chỉ được sử dụng để phân tích các bài toán hàng đợi đã biết mà còn để khám phá các kịch bản chưa từng có, thử nghiệm các ý tưởng đổi mới và dự đoán tác động của các thay đổi trong hệ thống hàng đợi trước khi chúng được triển khai thực tế. Việc tích hợp mô phỏng với các công nghệ như Digital Twin (Bản sao số) sẽ cho phép theo dõi và tối ưu hóa hệ thống trong thời gian thực, mang lại lợi ích to lớn cho việc quản lý luồng dữ liệu và tối ưu hóa tài nguyên trong mọi ngành nghề.

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

Chương 1 LÝ THUYẾT HÀNG ĐỢI 1. Các khái niệm cơ bản 1. Khái niệm xếp hàng Mô hình tổng quát của lý thuyết xếp hàng là khách hàng đến ở một thời điểm ngẫu nhiên nào đó và yêu cầu được phục vụ theo một loại nào đó. Giả thiết thời gian phục vụ có thể là ngẫu nhiên.

Nguồn vào Các khách hàng yêu cầu và tìm kiếm dịch vụ Quá trình đến Quá trình đến trung gian tn Độ Hàng đợi dài -Dung lượng: hàng Độ dài đợi Hữu hạn hoặc vô hạn hàng đợi - Quy tắc phục vụ: của hệ FIFO hoặc LIFO thống Phương tiện phục vụ Các khách hàng đã được phục vụ Đầu ra 4 Đặt tn là khoảng thời gian giữa 2 lần đến của khách hàng thứ n và thứ n+1. Ta giả định rằng tất cả các tn (n ≥ 1) là độc lập và có cùng phân bố. Vì vậy việc đến của 1 các khách hàng tạo thành 1 hàng kế tiếp nhau với tốc độ đến là  . Ta gọi quá E (t1 ) trình {tn, n=1,2,…} là quá trình đến.

Khách hàng đến hệ thống yêu cầu các server của hệ thống phục vụ. Ta giả sử rằng khách hàng thứ n cần một thời gian phục vụ là sn (n ≥ 1), tất cả các sn độc lập và có cùng phân bố. Quá trình tn ; n  1, 2,. được gọi là quá trình phục vụ. Ta cũng giả thiết rằng các thời gian đến trung gian độc lập với thời gian phục vụ.

Quá trình xếp hàng được phân loại dựa vào các tiêu chí sau:   1) Phân bố của quá trình đến (input process) là lq  t  t 0 2) Phân bố của thời gian phục vụ (service distribution) sn ; n  1, 2,. 3) Nguyên tắc phục vụ: Các khách hàng đến được sắp xếp vào hàng đợi đến lượt được phục vụ. Để đơn giản ta giả thiết chỉ có một hàng. Tuy nhiên trong nhiều trường hợp có thể mở rộng cho nhiều hàng cùng hoạt động song song. Nếu độ dài hàng có đặt ngưỡng thì các đơn vị đến hàng khi hàng đầy vượt ngưỡng sẽ bị loại.

Các khách hàng được chọn để phục vụ theo nguyên tắc "đến trước phục vụ trước" (FIFO), nghĩa là phục vụ cho khách nào đứng đầu hàng. 4) Cơ cấu phục vụ: Một phương tiện phục vụ bao gồm một hay nhiều Server. Các Server có thể kết nối thành chuỗi vì thế mỗi yêu cầu phục vụ được phục vụ theo nhiều cách hoặc lần lượt hoặc song song. Các yếu tố cơ bản của hệ thống hàng đợi [6] Hệ thống hàng đợi tổng quát được minh hoạ như hình sau: Input Output Hàng KÊNH PHỤC VỤ Dòng tín hiệu đến chờ Dòng tín hiệu ra Hình 1.1 Hệ thống hàng đợi 5 Các yếu tố cơ bản của hệ thống hàng đợi bao gồm:  Bố trí vật lí của hệ thống Hệ thống hàng đợi có một số dạng bố trí vật lí (phisical layout) như minh họa dưới đây: Single Channel – Single Server (Một kênh phục vụ, một loại dịch vụ) Single Channel – Multi Server (Một kênh phục vụ, nhiều loại dịch vụ) Dịch vụ 1 Dịch vụ 2 Dịch vụ 3 Multi Channel – Single Server (Nhiều kênh phục vụ, một loại dịch vụ) Multi Channel – Multi Server (Nhiều kênh phục vụ, nhiều loại dịch vụ) Dịch vụ 1 Dịch vụ 2 Hình1.2 Các dạng hệ thống hàng đợi Các kênh phục vụ được hiểu là những thiết bị kĩ thuật hoặc con người hoặc những tổ hợp các thiết bị kĩ thuật và 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.  Nguyên tắc phục vụ Nguyên tắc phục vụ (hay nội quy) 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ế 6 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ờ.

Một số nguyên tắc phục vụ thường được áp dụng trong các hệ thống hàng đợi là FIFO (First in first out), LIFO (Last in first out), FCFS (First come first serve), có ưu tiên, không ưu tiên,.  Các phân phối xác suất của các dòng tín hiệu, dòng phục vụ Số tín hiệu đến trong một khoảng thời gian cũng như thời gian phục vụ từng tín hiệu nói chung là những biến ngẫu nhiên, và do đó, chúng tuân theo các quy luật phân phối xác suất. Các quy luật phân phối xác suất này được thiết lập căn cứ các số liệu thực nghiệm thu thập từ các quan sát, thí nghiệm, hay từ cơ sở dữ liệu sẵn có. Đối với dòng tín hiệu đầu vào, thông thường chúng ta giả sử rằng số tín hiệu đến trong vòng một khoảng thời gian nào đó được ấn định trước (1 phút, 3 phút, 5 phút, 30 phút,.) tuân theo luật phân phối Poisson P().

Ở đây, tham số  đặc trưng cho số tín hiệu đến (trung bình) trong khoảng thời gian trên. Ví dụ, số khách vào siêu thị (trung bình) là 100 người trong 1 giờ. Có nghĩa là, số khách vào siêu thị là biến ngẫu nhiên X có phân phối Poisson với  = 100. Hoặc, với số cuộc gọi (trung bình) đến tổng đài trong vòng 1 phút là 3 (tín hiệu) thì có X ~ P(3).

Một cách chính xác hơn, trong những trường hợp trên, ta có dòng tín hiệu đến là dòng Poisson dừng (còn gọi là dòng tối giản) với các tính chất trên sau: Tính không hậu quả: Một dòng tín hiệu có tính không hậu quả nếu xác suất xuất hiện một số tín hiệ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 tín hiệu đã xuất hiện và xuất hiện như thế nào trước khoảng thời gian đó. Tính đơn nhất: Dòng tín hiệu có tính đơn nhất nếu xét trong khoảng thời gian khá bé thì sự kiện “có nhiều hơn một tín hiệu xuất hiện” hầu như không xảy ra. Về mặt thời gian ta có thể xem dòng tín hiệu có tính đơn nhất nếu thời điểm xuất hiện các tín hiệu không trùng nhau. 7 Tính dừng: Dòng tín hiệu có tính dừng nếu xác suất xuất hiện một số tín hiệu nào đó trong khoảng thời gian  chỉ phụ thuộc vào độ dài của  chứ không phụ thuộc vào điểm khởi đầu của .

Phân tích hàng đợi Có các phương pháp phân tích hàng đợi như sau  Phân tích giải tích  Quá trình mô phỏng  Cả hai phương pháp trên Phương pháp giải tích để giải mô hình hàng đợi gồm các bước sau: Bước 1: Phân tích hệ thống, chủ yếu là phân tích bản chất của dòng yêu cầu / tín hiệu đến và các trạng thái của hệ thống. Bước 2: Thiết lập hệ phương trình trạng thái cho các xác suất trạng thái (xác suất để hệ thống ở một trạng thái nào đó tại thời điểm t). Bước 3: Giải hệ phương trình để tìm các xác suất trạng thái. Từ đó thiết lập các mối quan hệ giữa các chỉ tiêu cần phân tích.

Bước 4: Tính toán, phân tích các chỉ tiêu, trên cơ sở đó đưa ra các nhận xét và các quyết định. Phương pháp giải tích thường sử dụng các giả thiết rất chặt chẽ của Toán học về các đặc trưng của hệ thống, vì vậy nó có một số hạn chế nhất định khi giải các bài toán thực tế. Trong khi đó, phương pháp mô phỏng/mô phỏng ngẫu nhiên để giải mô hình hàng đợi được áp dụng cho các bài toán dịch vụ đám đông không giải được bằng công cụ giải tích, nhất là những bài toán liên quan đến hệ thống lớn, bất ổn định, hàm chứa nhiều yếu tố ngẫu nhiên, không tuân theo các giả thiết quá chặt chẽ của Toán học. Trong nhiều trường hợp phương pháp mô phỏng cho ta tiết kiệm được thời gian và chi phí nghiên cứu.

Tuy phương pháp mô phỏng chỉ tạo ra các phương án đủ tốt để đánh giá hoạt động của hệ thống chứ không đưa ra được kĩ thuật tìm lời giải tốt nhất. Các bước cần tiến hành khi áp dụng phương pháp mô phỏng bao gồm: 8 Bước 1: Xác định bài toán hay hệ thống hàng đợi cần mô phỏng và mô hình mô phỏng. Bước 2: Đo và thu thập số liệu cần thiết cần thiết để khảo sát thống kê các số đặc trưng / các yếu tố cơ bản của mô hình. Bước 3: Chạy mô phỏng kiểm chứng (test simulation) mô hình và so sánh kết quả kiểm chứng với các kết quả đã biết được trong thực tế.

Phân tích kết quả chạy mô phỏng kiểm chứng, nếu cần thì phải sửa lại phương án đã được đánh giá qua chạy mô phỏng. Bước 4: Chạy mô phỏng để kiểm chứng phương án cuối cùng và kiểm tra tính đúng đắn của mọi kết luận về hệ thống thực tế được rút ra sau khi chạy mô phỏng. Triển khai hoạt động của hệ thống hàng đợi dựa trên phương án tìm được. Từ những phân tích trên đây có thể thấy Lí thuyết xếp hàng còn gọi là Lí thuyết hệ phục vụ công cộng hay Lí thuyết hệ dịch vụ đám đông là lĩnh vực rất quan trọng của Toán ứng dụng / Vận trù học.

Nhiều bài toán thực tế trong các lĩnh vực hệ thống dịch vụ, kĩ thuật, … đã được giải quyết thành công nhờ áp dụng phương pháp mô phỏng mô hình hàng đợi. Kết quả phân tích (về phía khách hàng) • Thời gian xếp hàng (trễ hàng đợi) • Tổng trễ (bao gồm trễ hàng đợi và trễ phục vụ) • Số lượng khách hàng trong hàng đợi • Số lượng khách hàng trong hệ thống (gồm khách hàng chờ và khách hàng đang được phục vụ) • Xác suất nghẽn mạng (khi kích thước bộ đệm hữu hạn) • Xác suất chờ để phục vụ Kết quả phân tích (về phía người phục vụ) • Khả năng sử dụng server • Khả năng sử dụng bộ đệm • Lợi ích thu được (thông số dịch vụ và các xem xét về kinh tế) • Lợi ích bị mất (thông số dịch vụ và các xem xét về kinh tế) 9 Ta phân tích hàng đợi sau: Hình 1.