Tài liệu Nghiên cứu và sử dụng công cụ general purpose simulation system trong bài toán mô phỏng hàng đợi

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG NGHIÊN CỨU VÀ SỬ DỤNG CÔNG CỤ GENERAL PURPOSE SIMULATION SYSTEM TRONG BÀI TOÁN MÔ PHỎNG HÀNG ĐỢI Thái Nguyên - 2012 ĐẠI HỌC THÁI NGUYÊN NGHIÊN CỨU VÀ SỬ DỤNG CÔNG CỤ GENERAL PURPOSE SIMULATION SYSTEM TRONG BÀI TOÁN MÔ PHỎNG HÀNG ĐỢI Chuyên ngành: Mã số: 60 48 01 TS. Lê Quang Minh Thái Nguyên - 2012 i LỜI CAM KẾT Tôi xin cam đoan Luận văn là do tôi thực hiện, được hoàn thành trên cơ sở tìm kiếm, nghiên cứu, tổng hợp phần lý thuyết và các phương pháp kĩ thuật được trình bày bằng văn bản trong nước và trên thế giới. Mọi tài liệu tham khảo đều được nêu ở phần của Luận văn. Luận văn này là mới và không sao chép nguyên bản từ bất kì một nguồn tài liệu nào khác. Nếu có gì sai sót, tôi xin chịu mọi trách nhiệm./. HỌC VIÊN Nguyễn Ngọc Thanh ii MỤC LỤC MỞ ĐẦU ....................................................................................................................1 Chƣơng 1:...................................................................................................................4 CƠ SỞ LÝ THUYẾT VỀ HỆ THỐNG HÀNG ĐỢI .............................................4 1.1. Mô tả hệ thống phục vụ ....................................................................... 4 1.2. Các yếu tố của hệ thống phục vụ ........................................................ 6 1.2.1. Cường độ dòng vào ....................................................................... 7 1.2.1.1. Cường độ dòng vào tiền định ............................................... 7 1.2.1.2. Cường độ dòng vào Poisson ................................................. 7 1.2.2. Hàng chờ (Queue) ........................................................................ 8 1.2.3. Kênh phục vụ ................................................................................ 8 1.2.4. Dòng ra.......................................................................................... 9 1.2.5. Nguyên tắc phục vụ của hệ thống dịch vụ ................................ 10 1.3. Trạng thái hệ thống phục vụ ............................................................. 10 1.3.1. Định nghĩa ................................................................................... 10 1.3.2. Quá trình thay đổi trạng thái của hệ thống phục vụ ................ 11 1.3.3. Sơ đồ trạng thái ............................................................................ 11 1.3.4. Qui tắc thiết lập hệ phương trình trạng thái ............................. 12 Chƣơng 2:.................................................................................................................14 HIỆN TRẠNG MỘT SỐ CÔNG CỤ MÔ PHỎNG BÀI TOÁN HÀNG ĐỢI ..14 2.1. Ngôn ngữ mô phỏng GPSS và công cụ GPSS World...................... 15 2.1.1. Giới thiệu về ngôn ngữ GPSS .................................................... 15 2.1.2. Sự ra đời của ngôn ngữ GPSS ................................................... 15 2.1.3. Những ưu điểm của ngôn ngữ GPSS ........................................ 16 2.1.4. Các ứng dụng của công cụ mô phỏng GPSS World ................. 17 2.2. Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net............ 19 2.2.1. Các khái niệm cơ bản về Petri-net ............................................. 19 2.2.2. Mô tả toán học về Petri-net ........................................................ 21 2.2.3. Một số thuộc tính của Petri-net ................................................. 22 2.2.4. Một số công cụ sử dụng ngôn ngữ Petri-net ............................. 23 2.2.5. Ứng dụng của mạng Petri-net ................................................... 24 iii 2.3. Ngôn ngữ lập trình Matlab ............................................................... 24 2.4. Ngôn ngữ lập trình Java .................................................................... 25 2.5. Ngôn ngữ lập trình C++ và bộ công cụ Visual Studio.net.............. 26 Chƣơng 3:.................................................................................................................28 NGHIÊN CỨU VỀ NGÔN NGỮ GPSS VÀ CÔNG CỤ GPSS WORLD .........28 3.1. Tổng quan về GPSS ........................................................................... 28 3.2. Thao tác lệnh của GPSS .................................................................... 31 3.3. Các đối tƣợng trong GPSS ................................................................ 32 3.4. Block cơ bản trong GPSS .................................................................. 34 3.4.1. Block làm việc với Transactions ................................................ 36 3.4.2. Facilities ...................................................................................... 39 3.4.3. Queue .......................................................................................... 40 3.4.4. Các Blocks dùng để điều khiển dịch chuyển của Transactions41 3.4.5. Phân phối xác suất nội tại (Built-in Probability Distributions)41 3.5. GPSS World Student Version ........................................................... 42 Chƣơng 4:.................................................................................................................45 SỬ DỤNG NGÔN NGỮ GPSS VÀO BÀI TOÁN THỰC TẾ ............................45 4.1. Quy trình ứng dụng GPSS mô phỏng hệ thống phục vụ đám đông ..................................................................................................................... 45 4.2. Bài toán................................................................................................ 46 4.2.1. Bài toán 1: ................................................................................... 46 4.2.1.1. Phân tích bài toán .............................................................. 46 4.2.1.2. Giải bài toán ...................................................................... 49 4.2.1.3. Mô hình GPSS World......................................................... 50 4.2.2. Bài toán 2: ................................................................................... 57 4.2.2.1. Phân tích bài toán .............................................................. 57 4.2.2.2. Giải bài toán ...................................................................... 60 4.2.2.3. Mô hình GPSS WORLD ..................................................... 61 ................................................................................65 2. Kiến .................................................................................................. 65 ................................................................................................ 66 TÀI LIỆU THAM KHẢO ......................................................................................67 iv DANH MỤC CÁC Kí hiệu CHỮ VIẾT TẮT Diễn giải CEC Current Events Chain FEC Future Events Chain GPSS General Purpose Simulation System WoPeD TAPAAL Workflow Petri-net Designer Tool for Verification of Timed-Arc Petri-nets v DANH MỤC CÁC BẢNG, BIỂU Trang Bảng 1. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS với T = 480 phút 53 Bảng 2. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS với T = 3360 phút 56 63 vi DANH MỤC CÁC HÌNH Trang Hình 1.1: Mô hình cơ bản của hệ thống phục vụ 4 Hình 1.2: Mô tả hệ thống phục vụ đám đông 5 Hình 1.3: Sơ đồ trạng thái của hệ thống phục vụ 12 Hình 2.1: Minh họa cửa sổ làm việc của GPSS World 16 Hình 2.2: Ví dụ về Petri-net 20 Hình 2.3: Minh họa tính tiếp cận của Petri-net 22 Hình 2.4: Minh họa tính bất tử của Petri-net 23 Hình 2.5: Minh họa tính không có đường bao giới hạn của Petri-net 23 Hình 2.6: Minh họa tính bảo thủ của Petri-net 23 Hình 2.7: Minh họa công cụ Netlab tích hợp trên nền tảng Matlab 24 Hình 2.8: Minh họa Applet: The Petri - Net - Simulator chạy trên nền Java 25 Hình 2.9: Minh họa công cụ YASPER phát triển trên công nghệ .Net 26 Hình 3.1. Một hệ phục vụ đám đông đơn giản 35 Hình 3.2: Cửa sổ Untitled Model 1 với Model của hệ phục vụ đám đông đơn kênh hở Hình 3.3: Ví dụ một cửa sổ Block Window 36 43 Hình 3.4: Ví dụ về một cửa sổ REPORT 43 Hình 4.1: Điều kiện bài toán 47 Hình 4.2: Cấu trúc mô hình phân tích 47 Hình 4.3: huật toán hoạt động của mô hình mô phỏng 48 Hình 4.4: Điều kiện bài toán 58 Hình 4.5: Cấu trúc mô hình phân tích 58 Hình 4.6: huật toán hoạt động của mô hình mô phỏng 59 1 MỞ ĐẦU Những năm gần đây, việc ứng dụng công nghệ thông tin vào các hoạt động trong đời sống, xã hội là rất cần thiết. Trong thực tế, chúng ta bắt gặp rất nhiều các hệ thống được thiết lập bởi các yêu cầu (của khách hàng), trong đó các thời điểm xuất hiện được xem như một đại lượng ngẫu nhiên, còn nhu cầu được đặc trưng bằng khối lượng các công việc phải làm để phục vụ, thứ tự ưu tiên trước sau, thời gian hoàn thành công việc và toàn bộ công việc. Đó là những hệ thống như: Mạng điện thoại, mạng máy tính, hệ thống phục vụ sử dụng phòng máy thực hành, hệ thống các quầy thu ngân trong siêu thị, hệ thống bán vé tự động, sân bay,... Những hệ thống này được biết đến với tên gọi hệ thống phục vụ đám đông (hay hệ thống hàng đợi) [1]. Nhìn chung các hệ thống phục vụ đám đông là hệ thống phức tạp, việc vận hành và tính toán các đặc trưng của hệ thống để tư vấn cho nhà quản lý là một vấn đề hết sức cần thiết. Trong quá khứ, có rất nhiều dự án xây dựng hệ thống phục vụ phức tạp dựa trên hàng chờ (Queue) không thành công vì đã không đặc tả được chính xác bài toán thực tiễn. Việc xây dựng mô hình toán học cho mỗi hệ thống là rất cần thiết để giảm chi phí tối đa cho các hoạt động đặc tả nó. Khi đó tính chất đầy đủ của các mô hình mô phỏng cần đạt được việc mô phỏng quá trình làm việc của mỗi phần tử trong hệ thống với việc đảm bảo logic, quy tắc của sự tương tác và phát triển của chúng, cả trong không gian và trong thời gian. Các câu hỏi được đặt ra là: Làm thế nào để mô phỏng một hệ thống phức tạp dưới dạng đơn giản nhưng chính xác? Phương pháp nào là khả thi nhất, tối ưu nhất ? Có rất nhiều phương pháp đã được đưa ra để giải quyết bài toán trên như: Tính toán bằng các công thức toán học, xây dựng hệ thống phục vụ bằng các ngôn ngữ lập trình (Pascal, C++,…), mô phỏng bằng các công cụ mô phỏng (Matlab, Petri Network, …). Để xây dựng 2 mô hình mô phỏng bằng cách sử dụng các ngôn ngữ lập trình truyền thống là khá phức tạp, khó khăn do khi lập trình chúng ta phải quản lý các sự kiện theo một mô hình nhiều sự kiện xảy ra đồng thời (song song) với việc xây dựng hàm tạo ngẫu nhiên các sự kiện (random) cũng không hề đơn giản, chính vì vậy đã xuất hiện ngôn ngữ mô phỏng chuyên dụng. Một trong những ngôn ngữ chuyên dụng mô phỏng hệ thống phức tạp, rời rạc hiệu quả và phổ biến nhất hiện nay là General Purpose Simulation System (GPSS) [4], ngôn ngữ này thuộc về lớp ngôn ngữ hướng vấn đề. Lĩnh vực áp dụng chính của GPSS là hệ thống phục vụ đám đông. Đối tượng của ngôn ngữ này được sử dụng tương tự như: Thành phần chuẩn của một hệ thống phục vụ đám đông; các yêu cầu, thiết bị phục vụ, hàng đợi, … Tập hợp đầy đủ thành phần như vậy cho phép xây dựng các mô phỏng phức tạp trong khi đảm bảo những thuật ngữ thông thường của hệ thống phục vụ đám đông. Trên thế giới nói chung và ở Liên bang Nga nói riêng, việc nghiên cứu và ứng dụng của GPSS rất phổ biến và phát triển. Tuy nhiên việc triển khai và ứng dụng công cụ mô phỏng GPSS trong giải quyết các bài toán hệ thống phục vụ đám đông là rất mới ở Việt Nam. Trên cơ sở nghiên cứu đã có, luận văn đã dựa trên định hướng xây dựng mô phỏng hệ thống phục vụ đám đông và sử dụng công cụ GPSS vào Bài toán phân phối sử dụng trong phòng máy thực hành của một trường đại học . Luận văn gồm 4 chương với nội dung được mô tả sơ bộ dưới đây: Chƣơng 1. Cơ sở lý thuyết về hệ thống hàng đợi: Cơ sở lý thuyết phục vụ đám đông bao gồm các mô tả về một hệ thống phục vụ nói chung như: các yếu tố của hệ thống phục vụ ( dòng vào, dòng ra, hàng chờ, kênh phục vụ), trạng thái của hệ thống (quá trình thay đổi trạng thái của hệ thống phục vụ, sơ đồ trạng thái, quy tắc thiết lập hệ phương trình trạng thái). 3 Chƣơng 2. Một số công cụ mô phỏng các bài toán hàng đợi: Giới thiệu tổng quan một số công cụ mô phỏng được sử dụng trong thực tế để giải quyết các bài toán hàng đợi, như: Ngôn ngữ mô phỏng GPSS và công cụ GPSS World; Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net; Ngôn ngữ lập trình Matlab; Ngôn ngữ lập trình Java; Ngôn ngữ lập trình C++ và bộ công cụ Visual Studio.NET. Chƣơng 3. Nghiên cứu về ngôn ngữ GPSS và công cụ GPSS World: Mô tả chi tiết về ngôn ngữ mô phỏng GPSS bao gồm định nghĩa, khái niệm cũng như cấu trúc thành phần. Nội dung chính của chương đề cập cấu trúc của một thao tác lệnh, các đối tượng (đối tượng động, đối tượng điều hành, đối tượng thuộc về thiết bị, đối tượng tĩnh, đối tượng hỗ trợ tính toán, đối tượng phục vụ lưu trữ, đối tượng nhóm) và các Block cơ bản trong GPSS. Chương này cũng giới thiệu một trong những công cụ phổ biến hỗ trợ thao tác với ngôn ngữ công cụ GPSS World. Chƣơng 4. Sử dụng ngôn ngữ GPSS vào bài toán thực tế: Chương này tập trung vào việc giới thiệu bài toán phân phối trong sử dụng phòng máy thực hành ặc tả quy . trình chung sử dụng GPSS để mô phỏng một hệ thống phục vụ đám đông, cách tiếp cận giải quyết bài toán thông qua Kết luận: Tóm lược nội dung chính của phát triển trong thời gian tới. GPSS World. và nêu định hướng 4 Chƣơng 1: CƠ SỞ LÝ THUYẾT VỀ HỆ THỐNG HÀNG ĐỢI Chủ đề chính của luận văn là áp dụng ngôn ngữ GPSS vào bài toán hệ thống phục vụ đám đông. Chương này tập trung vào cơ sở lý thuyết phục vụ đám đông (hay lý thuyết hàng đợi), mô tả hệ thống, các yếu tố của hệ thống như: dòng vào, hàng chờ, kênh phục vụ, dòng ra, … và trạng thái hệ thống. 1.1. Mô tả hệ thống phục vụ Một hệ thống phục vụ điển hình được biết đến với mô hình được mô tả ở hình 1.1 [9-12] Hình 1.1: Mô hình cơ bản của hệ thống phục vụ Trong đó: - Dòng các yêu cầu vào: Các yêu cầu được phục vụ và không được phục vụ - Hệ thống phục vụ: Bao gồm các máy phục vụ - Máy phục vụ: Các kênh phục vụ - Dòng yêu cầu ra: Các yêu cầu được phục vụ 5 Chi tiết về hệ thống phục vụ sẽ được trình bày cụ thể trong phần 1.2. Trong các hệ thống phục vụ, hàng đợi xuất hiện bất cứ lúc nào khi nhu cầu hiện tại đối với dịch vụ vượt quá khả năng cung ứng dịch vụ tại thời điểm đó. Thời gian một yêu cầu đến phải chờ đợi phụ thuộc vào một số yếu tố như: Số lượng giao dịch trong hệ thống, số kênh giao dịch cung ứng dịch vụ tại thời điểm đó và thời gian phục vụ cho mỗi yêu cầu đến. Ta có thể sử dụng một trong hai phương pháp “hộp đen” hoặc phương pháp “hộp trắng” để mô tả một hệ thống phục vụ đám đông. Trong Luận văn này, chúng ta sẽ mô tả hệ thống phục vụ đám đông bằng phương pháp “hộp đen” [2]. Hình 1.2: Mô tả hệ thống phục vụ đám đông Một hệ thống phục vụ đám đông có thể được ký hiệu theo Kendall [2,3] dưới dạng: A|B|m|n. Trong đó: A: Phân phối của thời gian vào. B: Phân phối thời gian phục vụ. m: Số máy phục vụ. n: Số chỗ trong hàng đợi. A, B có thể nhận một trong các phân phối sau: λ: Cường độ xuất hiện của sự kiện đầu vào µ: Cường độ phục vụ của kênh phục vụ - M: Phân phối mũ [15] có hàm phân phối: 6 F x x 1 e (1.1) Trong đó: F(x): Hàm phân bố của phân phối mũ - Ek: Phân phối Erlang k pha [15] có hàm phân phối: k 1 F x 1 e j 0 x ( x) j j! (1.2) Phân phối Erlang là trường hợp đặc biệt của phân phối Gamma với tham số hình dạng là số nguyên, được phát triển để dự đoán các thời gian đợi trong các hệ thống hàng đợi. Trong đó: - Hk: Phân phối siêu lũy thừa [15] với hàm phân phối: k F x q j (1 e jx ) x ≥0 (1.3) j 1 Với: F(x): Hàm phân bố của phân phối mũ - D: Phân phối tất định (Deterministic distribution), tức thời gian vào và thời gian phục vụ là hằng số. Hàm phân phối của phân phối này: 1, nếu x ≥ x0 F (x) = (1.4) 0, nếu x < x0 - G: Phân phối tổng quát (General distribution) - GI: Phân phối tổng quát với các thời gian vào hệ thống hoặc thời gian phục vụ độc lập nhau [2]. 1.2. Các yếu tố của hệ thống phục vụ 7 Một hệ thống phục vụ, dù ở qui mô nào, tính chất hoạt động ra sao, đều được đặc trưng bởi các yếu tố chủ yếu sau: 1.2.1. Cường độ dòng vào Cường độ dòng vào là dòng các yêu cầu đến hệ thống phục vụ, đòi hỏi được thỏa mãn một yêu cầu nào đó. Ví dụ: Khách hàng xếp hàng tại quầy bán vé xem phim, các container chờ để được dỡ hàng, các máy bay chờ để cất cánh ,… Tại các thời điểm khác nhau, các yêu cầu đến hệ thống phục vụ một cách ngẫu nhiên nên các dòng yêu cầu là những đại lượng ngẫu nhiên, tuân theo một luật phân bố xác suất nào đó, do vậy có nhiều loại dòng vào. Trong luận văn này, ta chỉ tập trung vào hai loại dòng yêu cầu quan trọng, thường gặp nhất ở mọi hệ thống phục vụ, đó là: Cường độ dòng vào tiền định và dòng vào Poisson. 1.2.1.1. Cường độ dòng vào tiền định Cường độ dòng vào tiền định là dòng vào trong đó yêu cầu đến hệ thống phục vụ tại các thời điểm cách đều nhau một khoảng a, là một đại lượng ngẫu nhiên có hàm phân bố xác suất là: 0, nếu x < a F (x) = (1.5) 1, nếu x ≥ a 1.2.1.2. Cường độ dòng vào Poisson vào Poisson là dòng yêu cầu đến hệ thống tuân theo luật phân phối Poisson. dòng vào Poisson được chia làm hai loại: - vào Poisson không dừng: Là dòng vào mà xác suất xuất hiện x yêu cầu trong khoảng thời gian Dt, kể từ thời điểm t, phụ thuộc vào t, nghĩa là: 8 a (t , e x ( Dt ) t) ! a t, t x (1.6) Trong đó: a(t, Dt) là số trung bình yêu cầu xuất hiện từ t đến Dt. - vào Poisson dừng: Là dòng vào mà xác suất trong khoảng thời gian Dt, kể từ thời điểm t, có x yêu cầu xuất hiện, không phụ thuộc vào t, nghĩa là: x( Dt ) t e ! ( . t)x (1.7) Trong đó: λ là cường độ xuất hiện của dòng yêu cầu. Nếu t là khoảng thời gian giữa lần xuất hiện các yêu cầu liên tiếp, thì t là một đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là t có hàm phân bố xác suất dạng: F t 1 e t (1.8) Và hàm mật độ xác suất là: f(t) = λe-λt 1.2.2. Hàng (1.9) (Queue) Hàng chờ là tập hợp các yêu cầu sắp xếp theo một nguyên tắc nào đó để chờ được vào phục vụ trong hệ thống. Trong hàng đợi ta có thể giới hạn hoặc không giới hạn số lượng khách chờ. 1.2.3. Kênh phục vụ Kênh phục vụ là toàn bộ các thiết bị kĩ thuật, con người hoặc một tổ hợp các thiết bị kĩ thuật có cùng công nghệ tương ứng mà hệ thống sử dụng để phục vụ yêu cầu khách hàng. Ví dụ về một số dạng kênh phục vụ như: Đường băng sân bay, kênh đường điện thoại, quầy bán vé, … Đặc trưng quan trọng nhất của kênh phục vụ là thời gian phục vụ. Đó là thời gian mỗi kênh phải tiêu phí để phục vụ một yêu cầu. Thời gian phục vụ 9 là một đại lượng ngẫu nhiên tuân theo một quy luật xác suất nào đó. Các dòng yêu cầu được phục vụ trong kênh phục vụ gọi là “dòng phục vụ”. Khi dòng yêu cầu được phục vụ trên các kênh phục vụ (dòng phục vụ) là tối giản thì khoảng thời gian giữa các lần xuất hiện liên tiếp các yêu cầu là một đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là đại lượng ngẫu nhiên có phân bố xác suất dạng: F (t) = 1- e –μt (1.10) Và hàm mật độ xác suất có dạng: f(t) = μe –μt (1.11) Trong đó: μ: Là cường độ phục vụ của kênh phục vụ. F(t): Hàm phân bố xác suất. f(t): Hàm mật độ xác suất. Khoảng thời gian giữa lần xuất hiện liên tiếp các yêu cầu trong dòng phục vụ của mỗi kênh chính là khoảng thời gian kênh đó phục vụ xong từng yêu cầu, nghĩa là thời gian phục vụ của kênh. Nếu dòng phục vụ trên mỗi kênh là dòng tối giản thì thời gian phục vụ của kênh đó là đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là có hàm phân phối xác suất và mật độ xác suất dạng (1.10), (1.11). 1.2.4. Dòng ra Dòng ra là dòng yêu cầu đi ra khỏi hệ thống, bao gồm các yêu cầu đã được phục vụ và các yêu cầu chưa được phục vụ. - Dòng yêu cầu ra đã được phục vụ: Đó là những yêu cầu đã được phục vụ ở mỗi kênh, nếu dòng đó là tối giản thì nó có một vai trò rất lớn trong hệ thống dịch vụ. Người ta đã chứng minh được rằng: Nếu dòng vào là tối giản thì dòng ra được phục vụ tại mỗi kênh sẽ là dòng xấp xỉ tối giản. 10 - Dòng yêu cầu ra không được phục vụ: Đây là bộ phận yêu cầu đến hệ thống nhưng không được phục vụ vì một lí do nào đó. 1.2.5. Nguyên tắc phục vụ của hệ thống dịch vụ Nguyên tắc phục vụ của hệ thống dịch vụ là cách thức nhận các yêu cầu vào phục vụ của hệ thống đó và các quy định khác đối với yêu cầu. Nó chỉ ra: - Trong trường hợp nào thì yêu cầu được nhận vào phục vụ - Cách thức bố trí các yêu cầu vào các kênh phục vụ - Khi nào và trong trường hợp nào thì yêu cầu bị từ chối hoặc phải chờ - Cách thức hình thành hàng chờ của các yêu cầu Các yếu tố của phương pháp phục vụ như: tần suất phục vụ, lựa chọn máy phục vụ… Các phương pháp phục vụ bao gồm: FCFS: First Come First Served (yêu cầu nào đến trước phục vụ trước), LCFS: Last Come First Served (yêu cầu đến sau được phục vụ trước), SIRO: Service In Random Order (phục vụ các yêu cầu theo thứ tự ngẫu nhiên), PS: Processor Shared (chia sẻ bộ vi xử lý), IS: Infinitive Server (nguyên mẫu máy chủ), Static priorities (ưu tiên cố định), Dynamic priorities (ưu tiên không cố định), Preemption (chế độ thay đổi phục vụ). 1.3. Trạng thái hệ thống phục vụ 1.3.1. Định nghĩa Trạng thái của hệ thống phục vụ, ký hiệu là xk(t), là khả năng kết hợp dòng vào và dòng ra của hệ thống ở một thời điểm nhất định. Theo nghĩa đó thì trạng thái của hệ thống phục vụ tại thời điểm t chính là tình huống mà trong hệ thống có k yêu cầu được phục vụ, hay nói cách khác hệ thống đang có k kênh phục vụ đang bận (đang làm việc) và do đó có (n-k) kênh được rỗi (không làm việc). Hệ thống phục vụ đang ở trạng thái nào đó là một quá trình ngẫu nhiên, quá trình này tuân theo một luật phân phối xác suất nào đó. Nên khả năng xuất hiện 11 một trong các trạng thái xk(t) (k = 0,1,2,...) nào đó tại thời điểm t, có xác suất là một giá trị xác định Pk(t). 1.3.2. Quá trình thay đổi trạng thái của hệ thống phục vụ Trong quá trình hoạt động, hệ thống phục vụ chuyển từ trạng thái này sang trạng thái khác dưới tác động của cường độ dòng vào và cường độ dòng phục vụ. Xác suất của quá trình đó được gọi là xác suất chuyển trạng thái. Nguyên nhân gây ra sự chuyển trạng thái là do tác động của cường độ dòng vào và cường độ dòng phục vụ, số kênh bận và số yêu cầu trong hệ thống thay đổi, tức là dưới tác động của cường độ dòng phục vụ μ(t) và cường độ dòng vào λi(t) tại thời điểm t, hệ thống sẽ biến đổi từ trạng thái này sang trạng thái khác. 1.3.3. Sơ đồ trạng thái Sơ đồ trạng thái của hệ thống được dùng để diễn tả quá trình thay đổi trạng thái của hệ thống phục vụ. Sơ đồ trạng thái là tập hợp các mũi tên, hình vẽ, diễn tả quá trình biến đổi trạng thái của hệ thống phục vụ, trong đó mũi tên nối liền các trạng thái mô tả bước chuyển từ trạng thái này sang trạng thái khác, hình chữ nhật biểu diễn trạng thái của hệ thống. Tham số ghi trên mũi tên biểu thị tác động của cường độ dòng biến cố kéo trạng thái dịch chuyển theo hướng mũi tên. 02 X0 01 10 12 X1 23 X2 X3 32 21 31 12 Hình 1.3: Sơ đồ trạng thái của hệ thống phục vụ 1.3.4. Qui tắc thiết lập hệ phương trình trạng thái Căn cứ vào sơ đồ trạng thái, ta thiết lập quan hệ giữa xác suất xuất hiện tác nhân gây ra sự biến đổi trạng thái đó. Mối trạng thái xk(t): Pk(t), với quan hệ này được hiển thị bởi phương trình toán học chứa xác suất Pk(t) và cường độ dòng chuyển trạng thái của hệ thống. - Nội dung quy tắc: Đạo hàm bậc nhất theo thời gian của xác suất xuất hiện trạng thái xk(t), Pk(t), bằng tổng đại số của một số hữu hạn số hạng, số các số hạng này bằng số mũi tên nối liền trạng thái xk(t), với trạng thái xj(t) khác, trong đó số số hạng mang dấu (+) tương ứng với số mũi tên hướng từ xj(t) về xk(t) ; số số hạng mang dấu (-) tương ứng với số mũi tên hướng từ xk(t) sang xj(t). Mỗi số hạng có giá trị bằng tích giữa cường độ của dòng biến cố hướng theo mũi tên và xác suất xuất hiện trạng thái mà mũi tên xuất phát. - Hệ phƣơng trình trạng thái: d 'k t k t jk dt t . t (1.12) j k (k=0,1,2,…,n) Với điều kiện: j j k t k j k t 1 (1.13)