Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi.

- Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- LÊ VĂN ÚY NGHIÊN CỨU VÀ SỬ DỤNG CÔNG CỤ GPSS TRONG BÀI TOÁN MÔ PHỎNG HÀNG ĐỢI Chuyên ngành : Kỹ thuật Máy tình và Truyền thông LUẬN VĂN THẠC SĨ KỸ THUẬT KỸ THUẬT MÁY TÍNH VÀ TRUYỀN THÔNG NGƢỜI HƢỚNG DẪN KHOA HỌC: TS.
- LÃ THẾ VINH Hà Nội – Năm 2015 Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 2 Lời cảm ơn Đầu tiên, em xin bày tỏ lòng biết ơn sâu sắc nhất tới Tiến sĩ Lã Thế Vinh đã tận tình hƣớng dẫn em trong suốt quá trình thực hiện luận văn này.
- Em xin chân thành cảm ơn các giảng viên Viện Công Nghệ Thông Tin và Truyền Thông, Đại học Bách Khoa Hà Nội đã giúp đỡ giảng dạy và tạo những điều kiện tốt nhất để em học tập và nghiên cứu chƣơng trình Sau Đại học tại đây.
- Học viên Lê Văn Úy Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 3 Tóm tắt nội dung Lý thuyết hệ thống phục vụ đám đông, hay lý thuyết hàng đợi (Queueing theory.
- nghiên cứu các đặc điểm đặc trƣng và xác định các tính chất của hệ thống đƣợc thiết lập bởi các yêu cầu [1], với mục tiêu tìm ra cách phục vụ tối ƣu nhất.
- Các hệ thống này thƣờng là những mô hình của các hệ thống phục vụ đám đông có trong thực tế nhƣ: mạng máy tính, mạng điện thoại, dây chuyền sản xuất, phi trƣờng, bãi đậu xe,…Phƣơng pháp mô phỏng cho phép chúng ta tìm hiểu về chúng một cách tốt nhất.
- Luận văn này tập trung nghiên cứu, tổng hợp, làm rõ cơ sở lý thuyết cho hệ thống phục vụ đám đông và sử dụng công cụ mô phỏng GPSS World vào bài toán cụ thể.
- Luận văn trình bày các khái niệm, đặc điểm của ngôn ngữ mô phỏng GPSS, đƣa ra các bƣớc xây dựng bài toán mô phỏng hệ thống phục vụ đám đông trên ngôn ngữ GPSS khi biết đƣợc các thông tin đầu vào.
- Từ bài toán cụ thể, luận văn này đã làm các phân tích, tính toán, tiến hành mô phỏng và đánh giá kết quả thu đƣợc.
- Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 4 Lời cam kết 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ƣớc và trên thế giới.
- Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 5 MỤC LỤC LỜI CẢM ƠN.
- 10 CHƢƠNG 1: CƠ SỞ LÝ THUYẾT VỀ HỆ THỐNG HÀNG ĐỢI.
- 12 1.1 MÔ TẢ VỀ HỆ THỐNG HÀNG ĐỢI.
- 12 1.1.1 Mô hình hóa một hệ thống hàng đợi.
- 13 1.1.2 Quan điểm về hiệu suất của hệ thống hàng đợi.
- 15 1.1.4 Hệ thống hàng đợi theo cách viết của Kendall và các phân phối liên quan.
- 16 1.2 CÁC YẾU TỐ CỦA HỆ THỐNG PHỤC VỤ.
- 17 1.2.1 Dòng yêu cầu đầu vào.
- 17 1.2.2 Hàng đợi.
- 19 1.2.3 Kênh phục vụ.
- 19 1.2.4 Dòng yêu cầu đầu ra.
- 20 1.2.5 Các quy luật hoạt động của hệ thống phục vụ.
- 20 1.3 TRẠNG THÁI CỦA HỆ THỐNG PHỤC VỤ.
- 21 1.3.2 Định nghĩa về trạng thái của hệ thống phục vụ.
- 23 1.3.3 Quá trình thay đổi trạng thái của hệ thống phục vụ.
- 23 1.4 MỘT SỐ KẾT QUẢ TỔNG HỢP VỀ HỆ THỐNG HÀNG ĐỢI KINH ĐIỂN M/M/1.
- 27 CHƢƠNG 2: GIỚI THIỆU NGÔN NGỮ MÔ PHỎNG GPSS (GENERAL PURPOSE SIMULATION SYSTEM.
- 29 2.1 GIỚI THIỆU VỀ NGÔN NGỮ GPSS.
- 29 2.2 SỰ RA ĐỜI CỦA NGÔN NGỮ GPSS.
- 29 2.3 NHỮNG ƢU ĐIỂM CỦA NGÔN NGỮ GPSS.
- 30 Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 6 2.4 CÁC ỨNG DỤNG CỦA CÔNG CỤ MÔ PHỎNG GPSS WORLD.
- 32 CHƢƠNG 3: TÌM HIỂU VỀ NGÔN NGỮ GPSS VÀ CÔNG CỤ MÔ PHỎNG GPSS WORLD.
- 42 3.4 CÁC BƢỚC PHÂN TÍCH VÀ MÔ PHỎNG BÀI TOÁN TRÊN GPSS WORLD.
- 44 CHƢƠNG 4: ÁP DỤNG NGÔN NGỮ MÔ PHỎNG VÀO BÀI TOÁN THỰC TẾ.
- 45 4.1.1 Phân tích bài toán.
- 45 4.1.1.1 Phân tích các biến trong bài toán.
- 45 4.1.1.2 Mô hình luồng thông tin đi vào hệ thống.
- 54 4.2.1 Phân tích bài toán.
- 54 4.2.2 Giải bài toán.
- 57 4.2.3 Mô hình GPSS World.
- 75 Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 7 Bảng các ký hiệu và chữ viết tắt Ký hiệu Tiếng Anh Giải thích theo tiếng Việt CEC Current Event Chain Chuỗi sự kiện hiện tại GPSS General Purpose Simulation System Ngôn ngữ mô phỏng hệ thống GPSS GPSS/PC General Purpose Simulation System/Personal Computer Môi trƣờng lập trình cho ngôn ngữ GPSS FEC Future Event Chain Chuỗi sự kiện tƣơng lai Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 8 Danh sách các hình vẽ Hình 1.1: Ví dụ về hệ thống hàng đợi, hay còn gọi là hệ thống phục vụ đám đông.
- 12 Hình 1.2: Mô hình hóa các yếu tố của một hệ thống hàng đợi.
- 13 Hình 1.3: Mô tả sự chuyển trạng thái của chuỗi Markov.
- 25 Hình 1.4: Sơ đồ trạng thái của hệ thống phục vụ.
- 25 Hình 1.5: Minh họa hoạt động của hệ M/M/1.
- 30 Hình 3.1: Một hệ phục vụ đám đông đơn giản.
- 43 Hình 3.2: Minh họa mô hình của hệ phục vụ đám đông đơn kênh hở.
- 46 Hình 4.2: Cấu trúc mô hình phân tích.
- 53 Hình 4.6: Điều kiện bài toán.
- 55 Hình 4.7: Cấu trúc mô hình phân tích.
- 55 Hình 4.8: Thuật toán hoạt động của mô hình mô phỏng.
- 56 Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 9 Danh sách các bảng biểu Bảng 1: Các yếu tố cấu thành một hệ thống phục vụ đám đông.
- 12 Bảng 2: Các tham số đặc trưng trong hệ thống hàng đợi.
- 14 Bảng 3: Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi.
- 16 Bảng 5: Một số phương pháp phục vụ áp dụng trong lý thuyết hàng đợi.
- 73 Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 10 Mở đầu Ngày nay, khoa học và công nghệ đƣợc ứng dụng vào các hoạt động trong đời sống, xã hội rất nhiều.
- Trong đó, chúng ta gặp nhiều hệ thống đƣợc xây dựng lên dựa vào các yêu cầu đầu vào.
- Đó là những hệ thống nhƣ: mạng điện thoại, mạng máy tính, bãi đậu xe, phi trƣờng.
- Các hệ thống này đƣợc gọi là hệ thống phục vụ đám đông (hay hệ thống hàng đợi) [1,2,7].
- Trên thực tế, các hệ phục vụ đám đông có đặc thù phức tạp, và việc tƣ vấn cho các nhà quản lý, nhà hoạch định chính sách về các hệ này là hết sức cần thiết sao cho khi hệ thống đƣợc đƣa vào sử dụng phải đạt hiệu suất cao nhất có thể.
- Chúng ta cần xây dựng mô hình toán học cho từng hệ thống.
- mô tả quá trình làm việc của các thành phần trong hệ thống.
- sự tƣơng tác qua lại giữa chúng theo thời gian, và trong không gian để giảm chi phí tối đa cho các hoạt động đặc tả hệ thống.
- Vấn đề ở đây là: Cần có sự đơn giản hóa nhưng chính xác các đặc điểm của hệ thống phục vụ đám đông dưới dạng mô hình.
- Để giải bài toán trên nhƣ, chúng ta có thể: tìm kiếm và giải quyết bằng các mô hình toán học, dùng tìm ra các giải thuật và dùng các ngôn ngữ lập trình (C.
- mô phỏng bằng các công cụ mô phỏng (Java, Matlab, P/T Net…) Mô phỏng hệ thố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 vì 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.
- Chính vì vậy đã xuất hiện các ngôn ngữ mô phỏng chuyên dụng.
- Ngôn ngữ lập trình GPSS (General Purpose Simulation System) [4], thuộc loại ngôn ngữ lập trình hƣớng đối tƣợng, một ngôn ngữ mô phỏng các hệ thống phức tạp rời rạc.
- GPSS dự đoán các hành vi trong tƣơng lai của các hệ thống phục vụ đám đông .
- Các đối tƣợng của ngôn ngữ Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 11 này đƣợc sử dụng tƣơng tự nhƣ các thành phần chuẩn của một hệ thống phục vụ đám đông.
- nhƣ là các yêu cầu, các thiết bị phục vụ, hàng đợi… Tập hợp đầy đủ các 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.
- Vấn đề nghiên cứu và ứng dụng ngôn ngữ mô phỏng GPSS rất phổ biến và phát triển tại Liên bang Nga cũng nhƣ một số quốc gia khác.
- Trên cơ sở các nghiên cứu đã có, luận văn giới thiệu ví dụ thực tế: đánh giá hoạt động tại một đơn vị xử lý thông tin và hoạt động của phòng máy thực hành nơi tôi làm việc.
- Bài toán sử dụng luồng thông tin đầu vào là các đại lƣợng ngẫu nhiên và không có sự ƣu tiên.
- Cơ sở lý thuyết về hệ thống hàng đợi: đƣa ra cơ sở lý thuyết về hệ thống hàng đợi, bao gồm: 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ụ), các quá trình Markov và trạng thái của hệ thống.
- Với sự phát triển của khoa học máy tính, phƣơng pháp mô phỏng chứng tỏ những khả năng tốt cho việc giải bài toán hàng đợi, ngoài phƣơng pháp toán học thuần túy mà chúng ta có thể tìm ra lời giải của bài toán hàng đợi khi dựa vào hệ phƣơng trình trạng thái với các điều kiện ban đầu.
- Giới thiệu ngôn ngữ mô phỏng GPSS (General Purpose Simulation System): Phần này giới thiệu sơ lƣợc về ngôn ngữ GPSS, một ngôn ngữ mô phỏng chuyên dụng với các khái niệm, đặc trƣng.
- Tìm hiểu về ngôn ngữ GPSS và công cụ GPSS World: Chƣơng này đề cập cụ thể, chi tiết về cấu trúc của một thao tác lệnh, các đối tƣợng và các khối (block) cơ bản trong GPSS.
- Đồng thời, chƣơng 3 trình bày các bƣớc tiến hành mô phỏng một bài toán hàng đợi khi sử dụng phƣơng pháp mô phỏng qua công cụ GPSS World.
- Áp dụng ngôn ngữ GPSS vào bài toán thực tế: đánh giá hoạt động tại một đơn vị xử lý thông tin, và hoạt động của phòng máy thực hành nơi tôi làm việc.
- Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 12 Chƣơng 1: Cơ sở lý thuyết về hệ thống hàng đợi Chƣơng này tập trung vào tìm hiểu cơ sở lý thuyết về hệ thống hàng đợi: các đặc điểm của hệ thống, các yếu tố của hệ thống gồm có dòng yêu cầu đầu vào, hàng chờ, kênh phục vụ, dòng yêu cầu đầu ra, các thông số mô tả về hệ thống… và tìm hiểu về quá trình Markov và trạng thái của hệ thống phục vụ… 1.1 Mô tả về hệ thống hàng đợi Chúng ta làm quen với một ví dụ về hệ thống hàng đợi hay còn gọi là hệ thống phục vụ đám đông) nhƣ hình vẽ 1.1: Hình 1.1: Ví dụ về hệ thống hàng đợi, hay còn gọi là hệ thống phục vụ đám đông.
- Trong mô hình này, chúng ta quan sát thấy có yếu tố khách đến, khách bỏ đi (do không có thời gian chờ đợi, hoặc các lý do khác), khách xếp hàng chờ tới lƣợt mình đƣợc phục vụ, các máy phục vụ, và khách hàng đã đƣợc phục vụ xong, rời khỏi hệ thống phục vụ trên.
- Các yếu tố này có thể tóm lƣợc sơ bộ gồm các thành phần trong bảng 1: Bảng 1: Các yếu tố cấu thành một hệ thống phục vụ đám đông STT Tên yếu tố Giải thích 1 Dòng các yêu cầu đầu vào Khách hàng gọi điện thoại đến một tổng đài giải đáp (Call Center), các xe ô tô đi vào bãi đậu xe, các máy bay hạ cánh Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 13 xuống một phi trƣờng… 2 Hệ thống phục vụ Là các máy phục vụ nhằm đáp ứng yêu cầu ứng với từng loại đầu vào cụ thể ở trên, trong hệ thống phục vụ có hàng chờ, tại đó, khách hàng xếp hàng chờ đến lƣợt mình đƣợc phục vụ.
- Hệ thống phục vụ có các máy phục vụ và chúng hoạt động theo những quy luật, nguyên tắc phục vụ nào? 3 Các máy phục vụ Các máy điện thoại bàn và nhân viên trong một Call Center, đƣờng băng tại sân bay, vị trí trong bãi đậu xe… 4 Dòng các yêu cầu đầu ra Là các yêu cầu đã đƣợc phục vụ sau khi đi ra khỏi hệ thống phục vụ ở trên Về bản chất, khi xuất hiện các yêu cầu vƣợt quá khả năng đáp ứng của một dịch vụ nào đó tại một thời điểm nào đó, hàng đợi sẽ xuất hiện.
- Sự chờ đợi (nhanh hay chậm để đƣợc đáp ứng yêu cầu) phụ thuộc mạnh vào số lƣợng kênh phục vụ của hệ thống, cũng nhƣ quy tắc phục vụ của hệ thống.
- 1.1.1 Mô hình hóa một hệ thống hàng đợi Chúng ta có thể mô hình đơn giản cho một hệ thống hàng đợi trong hình 1.2 : Hình 1.2: Mô hình hóa các yếu tố của một hệ thống hàng đợi Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 14 Các thông số mô tả liên quan đến hệ thống hàng đợi gồm có: Bảng 2: Các tham số đặc trưng trong hệ thống hàng đợi STT Ký hiệu Nội dung 1 N(t) Số khách hàng ở trong hệ thống tại thời điểm t.
- 2 λ Dòng yêu cầu đầu vào, đặc trƣng bởi tốc độ đến (arrival rate) của khách hàng 3 µ Dòng yêu cầu đầu ra, là các yêu cầu đã đƣợc và không đƣợc phục vụ, đặc trƣng bởi tốc độ tối đa phục vụ.
- Lƣu ý: λ < µ 4 Nq(t) Hàng chờ, đặc trƣng bởi số lƣợng khe để phục vụ cho xếp hàng 5 Wi Thời gian xếp hàng của khách hàng thứ i trong hàng chờ 6 Ns(t) Kênh phục vụ và các cách phục vụ, đặc trƣng bởi số lƣợng kênh, cụ thể có c kênh, cũng có nghĩa là đang có c khách hàng đang đƣợc phục vụ 7 τi Thời gian phục vụ với khách hàng thứ i 8 τ Thời gian phục vụ trên tất cả các máy phục vụ 9 T Tổng thời gian phục vụ của toàn bộ hệ thống Có nhiều nguyên tắc phục vụ, hoặc nguyên tắc xếp hàng.
- Chúng ta lấy ví dụ đơn giản nhất khi xếp hàng là: Ai đến trƣớc phục vụ trƣớc – First In, First Out.
- Khi đó, Tổng thời gian trễ Ti của khách hàng thứ i sẽ là tổng của thời gian xếp hàng Wi và thời gian phục vụ τi.
- Chúng ta có: Ti = Wi + τi Quan điểm về hiệu suất của hệ thống hàng đợi Có hai quan điểm về vấn đề này [2] Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 15 Nếu nhìn ở góc độ khách hàng, chúng ta đã biết tốc độ đến (arrival rate) là λ, và khách hàng đƣợc phục vụ, với tốc độ phục vụ là λs.
- Khi đó chúng ta sẽ tính hiệu suất hệ thống chính là tốc độ phục vụ chia cho tốc độ đến hệ thống: η1 = λs/ λ (1.2) Nếu nhìn ở góc độ phân bố tài nguyên trong hệ thống, hiệu suất hệ thống tính theo hiệu của tốc độ đến và tốc độ bỏ đi: Khi đó hiệu suất hệ thống là một hàm số của N(t) và Nq(t): η2 = λ - λb = f(N(t), Nq(t Công thức Little Thời gian phục vụ là một đại lƣợng ngẫu nhiên, chúng ta khó có thể đo đƣợc.
- Tuy nhiên, nhìn tổng thể, thời gian phục vụ trung bình là một yếu tố rất quan trọng, đem lại nhiều ý nghĩa để đánh giá hiệu suất hoạt động của hệ thống hàng đợi.
- Công thức Litte phát biểu rằng: Hệ thống hàng đợi đạt được trạng thái dừng khi mà Số lượng trung bình các khách hàng trong hệ thống bằng Tốc độ đến trung bình nhân với Thời gian phục vụ trung bình trong hệ thống hàng đợi đó.
- Số lƣợng trung bình khách hàng đƣợc phục vụ tại thời điểm t (1.5) E[Ns(t.
- đây là xác suất trạng thái dừng của hệ thống khi có khách hàng.
- Hiệu suất sử dụng (hay hệ số tải) của một hệ phục vụ có c máy phục vụ: (1.6) Đề tài: Nghiên cứu và sử dụng công cụ GPSS trong bài toán mô phỏng hàng đợi 16 ρ = λtb E[τ]/ c Hệ thống hàng đợi theo cách viết của Kendall và các phân phối liên quan Theo Kendall [3,8,9], mô tả ngắn gọn về hệ thống hàng đợi có dạng nhƣ sau: A/B/m/K (1.8) Các ký hiệu trong mô tả Kendall đƣợc trình bày trong bảng 3: Bảng 3: Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi STT Ký hiệu Ý nghĩa 1 A Phân phối xác suất của thời gian đến 2 B Phân phối xác suất của thời gian phục vụ.
- 3 m Số lƣợng máy phục vụ.
- 4 K Dung lƣợng của hệ thống, là số khách hàng lớn nhất có mặt mà hệ thống phục vụ đƣợc, có tính đến cả khách hàng đang chờ Chi tiết hơn, với ký hiệu X là biến ngẫu nhiên của phân phối xác suất và E[X] là kỳ vọng , hoặc giá trị trung bình của X, chúng ta nói về các phân phối xác suất [6, 11] liên quan đến yếu tố A và B trong bảng 4: Bảng 4: Các phân phối xác suất liên quan đến A và B trong mô tả Kendall STT Viết tắt Phân phối xác suất Hàm phân phối Ghi chú 1 M Phân phối mũ, X không nhớ, E[X]= 1/λ  xexF1, λ là hệ số kỳ vọng và x Ek Phân phối Erlang k pha, E[X

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt