Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ Đ I H C THÁI σGUYÊσ TR NGăĐ IăH CăCỌNGăNGH ăTHỌNGăTINăVÀăTRUY NăTHỌNG LêăXuânăHi u NGHIÊN C U CỌNGăC ăMỌăPH NGăGPSSăVÀăPETRIăNETă CHOăBÀIăTOÁNăH ăTH NGăHÀNGăĐ I LU NăVĔNăTH CăSĨăKHOAăH CăMÁYăTệNH Thái Nguyên - 2013 Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ Đ I H C THÁI NGUYÊN TR NGăĐ IăH CăCỌNGăNGH ăTHỌNGăTINăVÀăTRUY NăTHỌNG LêăXuânăHi u NGHIÊN C U CỌNGăC ăMỌăPH NGăGPSSăVÀăPETRIăNETă CHOăBÀIăTOÁNăH ăTH NGăHÀNGăĐ I Chuyên ngành: Khoa h c máy tính Mã số: 60 48 01 LU NăVĔNăTH CăSĨăKHOAăH CăMÁYăTệNH σG IH σG D σ KHτA H C TS. Lê Quang Minh Thái Nguyên - 2013 Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ L IăCAMăĐOAN Tôi xin cam đoan luận văn này là do tôi thực hiện đ ợc hoàn thành trên cơ s tìm kiếm, thu thập, 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 tham khảo đều đ ợc nêu c và trên thế gi i. M i tài liệu phần cuối c a luận văn. Luận văn này hoàn toàn 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 LêăXuânăHi u Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ i M CăL C Đ TăV NăĐ ........................................................................................................ 1 Ch ơngă1.ăT NGăQUANăV ăH TH NGăHÀNGăĐ I .................................. 3 1.1. Vai trò c a hệ thống hàng đợi. ......................................................................... 3 1.2. Mô tả hệ thống hàng đợi................................................................................... 3 1.2.1. Mô hình hóa một hệ thống hàng đợi ..................................................... 5 1.2.2. Công th c Little ..................................................................................... 7 1.2.3. Hệ thống hàng đợi theo cách viết c a Kendall và các phân phối liên quan ................................................................................................................. 7 1.3. Các yếu tố c a hệ thống hàng đợi. ................................................................. 10 1.3.1. Dòng yêu cầu đầu vào ......................................................................... 10 1.3.2. Hàng đợi .............................................................................................. 12 1.3.3. Kênh phục vụ ....................................................................................... 12 1.3.4. Dòng yêu cầu đầu ra ........................................................................... 13 1.3.5 Các quy luật hoạt động c a hệ thống phục vụ ..................................... 13 1.4. Tr ng thái hệ thống phục vụ........................................................................... 15 1.4.1. Định nghĩa về trạng thái c a hệ thống phục vụ .................................. 15 1.4.2. Quá trình thay đổi trạng thái c a hệ thống phục vụ .............................. 15 1.4.3. Sơ đồ trạng thái .................................................................................... 16 1.4.4. Qui tắc thiết lập hệ phương trình trạng thái ....................................... 16 Ch ơngă2.ăCÁCăCỌNGăC ăMỌăPH NGăBÀIăTOÁNăHÀNGăĐ I ............. 19 2.1. Quy trình chung c a việc phân tích, mô phỏng hệ thống hàng đợi ............... 19 2.2. M t số ngôn ngữ lập trình bậc cao dùng để giải quyết bài toán hàng đợi ..... 20 2.2.1. Ngôn ngữ lập trình Matlab ................................................................. 20 2.2.2. Ngôn ngữ lập trình Java ..................................................................... 21 2.2.3. Ngôn ngữ lập trình C++ và bộ công cụ Visual Studio.net ................. 22 2.3. σgôn ngữ mô phỏng GPSS và công cụ GPSS World .................................... 23 2.3.1. Giới thiệu về ngôn ngữ GPSS ............................................................... 23 2.3.2. Sự ra đời c a ngôn ngữ GPSS ............................................................. 24 Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ ii 2.3.3. Những ưu điểm c a ngôn ngữ GPSS ..................................................... 25 2.3.4. Các ng dụng c a công cụ mô phỏng GPSS World .............................. 26 2.3.5. GPSS World Student Version .............................................................. 28 2.4. Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net............................ 29 2.4.1. Các khái niệm cơ bản về Petri-net ...................................................... 29 2.4.2. Mô tả toán học về Petri-net ................................................................. 31 2.4.3. Một số thuộc tính c a Petri-net........................................................... 32 2.4.4. Một số công cụ sử dụng ngôn ngữ Petri-net ....................................... 33 2.4.5. ng dụng c a mạng Petri-net ............................................................. 34 2.5. So sánh giữa P/T net và GPSS ...................................................................... 34 Ch ơngă3.ăS ăD NGăGPSSăVÀăPETRIăNET ................................................. 36 TRONGăBÀIăTOÁNăMỌăPH NGăH ăTH NGăHÀNGăĐ I ....................... 36 3.1. Mô phỏng bài toán hàng đợi không u tiên ................................................... 36 3.1.1. Phát biểu bài toán. .............................................................................. 36 3.1.2. Phân tích bài toán ............................................................................... 37 3.1.3. Phân tích kết quả c a bài toán bằng lý thuyết hàng đợi..................... 37 3.1.4. Mô phỏng bài toán bằng công cụ GPSS WORLD .............................. 39 3.1.5. Mô phỏng bài toán bằng mô hình mạng Petri .................................... 43 3.2. Mô phỏng bài toán hàng đợi có u tiên. ........................................................ 51 3.2.1 Phát biểu bài toán ............................................................................... 51 3.2.2. Phân tích bài toán ............................................................................... 52 3.2.3. Phân tích kết quả bài toán bằng lý thuyết hàng đợi ........................... 54 3.2.4. Mô phỏng bài toán bằng GPSS World ................................................ 55 3.2.5. Mô phỏng bài toán bằng mô hình mạng Petri .................................... 59 3.3. Đánh giá các kết quả mô phỏng ..................................................................... 64 K TăLU NăVÀăKI NăNGH ............................................................................ 66 TÀIăLI UăTHAMăKH O .................................................................................. 68 Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ iii DANHăM CăCÁCăKụăHI U,ăCH ăVI TăT T Kýăhi u CEC GPSS GPSS/PC FEC PABX P/T net Ti ngăAnh Current Event Chain General Purpose Simulation System General Purpose Simulation System/Personal Computer Future Event Chain Private Automatic Branch Exchange Place/ Transition Network Số hóa b i trung tâm h c liệu Gi iăthíchătheoăti ngăVi t Chuỗi sự kiện hiện t i σgôn ngữ mô phỏng hệ thống GPSS Môi tr ng lập trình cho ngôn ngữ GPSS Chuỗi sự kiện t ơng lai Tổng đài liên l c dành cho m t tổ ch c, đơn v đ c lập M t lo i ngôn ngữ mô tả toán h c, dựa trên lý thuyết về tập hợp http://www.lrc.tnu.edu.vn/ iv DANHăM CăCÁCăB NGăBI U Bảng 1.1 Các yếu tố cấu thành hàng đợi Bảng 1.2 Các tham số đặc tr ng trong hệ thống hàng đợi Bảng 1.3 Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi Bảng 1.4 Các phân phối xác suất liên quan đến A và B trong mô tả Kendall Bảng 1.5 M t số ph ơng pháp phục vụ áp dụng trong lý thuyết hàng đợi Bảng 2.1 So sánh giữa Petri σet và GPSS Bảng 3.1 Th i gian ch T1 v trí P1 Bảng 3.2 Th i gian ch Tx-T8 v trí P12 Bảng 3.3 Th i gian ch T5 v trí P7 Bảng 3.4 Th i gian ch T5 v trí P8 Bảng 3.5 Kết quả phân tích hàng ch T Bảng 3.6 Kết quả phân tích v trí các đỉnh P Bảng 3.7 Th i gian ch T1 v trí P1 (Khi T1 thay đổi) Bảng 3.8 Th i gian ch T5 v trí P7 (Khi T5 thay đổi) Bảng 3.9 Th i gian ch T6 v trí P8 (Khi T6 thay đổi) Bảng 3.10 Kết quả phân tích hàng ch T khi T1,T5,T6 thay đổi Bảng 3.11 Kết quả phân tích v trí các đỉnh P khi T1,T5,T6 thay đổi Bảng 3.12 So sánh kết quả tính toán theo lý thuyết v i tính toán trong GPSS và Petri Net Bảng 3.13 So sánh kết quả tính toán theo lý thuyết v i tính toán trong GPSS v = 1.440 phút Bảng 3.14 Th i gian ch T1 v trí P1 Bảng 3.15 Th i gian ch T2 v trí P2 Bảng 3.16 Kết quả phân tích hàng ch T Bảng 3.17 Kết quả phân tích v trí các đỉnh P Bảng 3.18 So sánh kết quả tính toán theo lý thuyết v i tính toán trong GPSS và Petri Net Bảng 3.1λ So sánh kết quả tính toán theo lý thuyết v i tính toán trong GPSS và Petri σet theo th i gian Số hóa b i trung tâm h c liệu Trang 4 6 8 9 14 34 45 45 46 46 47 47 48 49 49 50 50 51 58 60 61 62 62 63 64 http://www.lrc.tnu.edu.vn/ v DANHăM CăCÁCăHỊNH VẼ Trang Hình 1.1 Mô hình cơ bản c a hệ thống hàng đợi (hay hệ thống phục vụ đám đông) 3 Hình 1.2 Mô hình hóa các yếu tố c a m t hệ thống hàng đợi 5 Hình 1.3 Mô tả hệ thống đợi 7 Hình 1.4 Sơ đồ tr ng thái c a hệ thống phục vụ 16 Hình 2.1 Minh h a công cụ σetlab tích hợp trên nền tảng Matlab 21 Hình 2.2 Minh h a Appletμ The Petri - Net - Simulator ch y trên nền Java 22 Hình 2.3 Minh h a công cụ YASPER phát triển trên công nghệ .σet 23 Hình 2.4 Minh h a cửa sổ làm việc c a GPSS World 25 Hình 2.5 Ví dụ về m t cửa sổ REPτRT GPSS World Student Version 29 Hình 2.6 Ví dụ Petri-net 30 Hình 2.7 Minh h a tính tiếp cận c a Petri-net 32 Hình 2.8 Minh h a tính bất tử c a Petri-net 33 Hình 2.9 Minh h a tính không có đ 33 ng bao gi i h n c a Petri-Net Hình 2.10 Minh h a tính bảo th c a Petri-net 33 Hình 3.1 Mô phỏng điều kiện bài toán xe c u trên thực tế 37 Hình 3.2 Mô phỏng điều kiện bài toán xe c u theo toán h c 37 Hình 3.3 Sơ đồ khối thuật toán bài toán xe c u 39 Hình 3.4 Mô hình bài toán xe c u theo m ng Petri 43 Hình 3.5 Điều kiện bài toán mô phỏng mô hình hệ thống điều khiển đ ng băng sân bay 52 Hình 3.6 Sơ đồ thuật toán bài toán mô phỏng mô hình hệ thống điều khiển đ ng băng sân bay 53 Hình 3.7 Mô hình hàng đợi theo d ng M/M/1 bài toán mô phỏng mô hình hệ thống điều khiển đ ng băng sân bay 54 Hình 3.8 Mô hình hóa bằng m ng Petri bài toán mô phỏng mô hình hệ thống điều khiển đ ng băng sân bay 60 Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ 1 Đ TăV NăĐ 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 μ Xếp hàng mua vé vào r p hát, xếp hàng thanh toán tiền quầy thu ngân bưi đậu xe, phi tr siêu th , máy bay cất cánh (h cánh), m ng máy tính, ng… Những hệ thống này đ ợc g i là hệ thống hàng đợi (hay hệ thống phục vụ đám đông)[1],[3],[6],12]. Nhìn chung các hệ thống hàng đợi là các 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. 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ó. Việc đặc tả và tính toán m t số đặc điểm c a hệ thống hàng đợi có thể đem l i các kết quả dự báo quan tr ng cho hệ thống. 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 các 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. Để xây dựng 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 các 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 các ngôn ngữ mô phỏng chuyên dụng. Hiện nay có m t số ph ơng pháp đánh giá, mô phỏng đ ợc sử dụng r ng rưi và có hiệu quả trên thực tế là ph ơng pháp mô hình hoá và các mô hình đ ợc sử dụng hiện nay là mô hình hàng đợi, m ng Petri, General Purpose Simulation System (GPSS), đồ th , và các mô hình lai ghép... Trong đó mô hình hàng đợi là m t mô hình đơn giản và tỏ ra có hiệu quả trong thực tế. Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/ 2 V i nhu cầu cần mô phỏng hệ thống hàng đợi, việc áp dụng cách tiệp cận cũng nh công cụ mô phỏng nào là m t vấn đề quan tr ng do tính chất c a hệ thống, quy mô c a hệ thống có thể là những yếu tố ảnh h ng đến việc lựa ch n công cụ. Chính vì vậy, yêu cầu lựa ch n, so sánh, đánh giá các công cụ mô phỏng là m t đề tài mang ý nghĩa khoa h c và thực tiễn cao. V i lý do đó, tôi lựa ch n đề tài “Nghiên c u công cụ mô phỏng GPSS và Petri Net cho bài toán hệ thống hàng đợi“ cho luận văn tốt nghiệp th c sỹ c a mình. Luận văn gồm 3 ch ơng v i n i dung đ ợc mô tả tóm l ợc nh sauμ Ch ơngă1.ăT ngăquanăv ăh ăth ngăhàngăđ i: σ i dung ch ơng 1 đ a ra vai trò c a hệ thống hàng đợi; tập trung vào cơ s lý thuyết hàng đợi (lý thuyết phục vụ đám đông) bao gồm các mô tả về m t hệ thống hàng đợi nói chung nh μ Các yếu tố c a hệ thống hàng đợi (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). Ch ơngă2.ăCácăcôngăc ămôăph ngăbàiătoánăhàngăđ i: Cách tiếp cận cho việc mô phỏng bài toán hàng đợi bằng m t số ngôn ngữ lập trình bậc cao nh Java, Matlab, C++… và các ngôn ngữ đặc tả ,công cụ mô phỏng chuyên dụng GPSS, Petri Net. Nghiên c u kỹ cách áp dụng công cụ mô phỏng GPSS và Petri Net cho bài toán hàng đợi. Đ a ra so sánh đặc điểm, ng dụng giữa công cụ GPSS và Petri Net. Chương 3. Sử dụng GPSS và Petri Net trong bài toán mô phỏng hệ thống hàng đợi: Áp dụng công cụ mô phỏng GPSS và Petri Net vào 2 bài toán hàng đợi cụ thểμ Bài toán hàng đợi không u tiên (bài toán mô phỏng điều khiển xe c u) và bài toán hàng đợi có u tiên (bài toán mô phỏng hệ thống điều khiển hệ thống đ ng băng sân bay). So sánh kết quả tính toán theo lý thuyết v i kết quả mô phỏng trên GPSS và Petri Net theo th i gian. Từ các kết quả mô phỏng đ ợc trình bày trong luận văn đ a ra so sánh, khuyến cáo khi sử dụng 2 công cụ mô phỏng GPSS và Petri Net khi áp dụng vào bài toán cụ thể. K tălu n: Tóm l ợc n i dung chính c a luận văn và nêu đ nh h ng phát triển trong th i gian t i. Số hóa b i trung tâm h c liệu http://www.lrc.tnu.edu.vn/