CÔNG CỤ GPSS CHO BÀI TOÁN MÔ PHỎNG CÁC HỆ THỐNG PHỤC VỤ ĐÁM ĐÔNG

- CÔNG CỤ GPSS CHO BÀI TOÁN MÔ PHỎNG.
- CÁC HỆ THỐNG PHỤC VỤ ĐÁM ĐÔNG.
- Tóm tắt Trong quá khứ có rất nhiều dự án xây dựng các hệ thống phục vụ phức tạp dựa trên các 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ả đó.
- Dựa trên “lý thuyết phục vụ đám đông.
- «Теория массавого обслуживания», việc tính toán và đưa ra các đặc tính của hệ thống không phải lúc nào cũng có thể thực hiện được, đặc biệt khi dữ liệu đầu vào của hàng chờ là các dự liệu ngẫu nhiên thì việc tính toán theo lý thuyết toán của các mô hình cũng có thể không đem lại sự thuyết phục, có thể có những đặc tính không thể tính được qua các mô hình, công thức toán, vì vậy yêu cầu mô phỏng mô hình toán của hệ trong một môi trường (ngôn ngữ) mô phỏng là một yêu cầu thiết thực, có tính thời sự cao.
- GPSS World (General Purpose Simulation System) là phần mềm dựa trên ngôn ngữ của máy tính mô phỏng (soft ware), sử dụng công cụ mô phỏng này có thể đặc tả và khảo sát được nhiều hệ thống với các loại kênh phục vụ khác nhau.
- Trong bài báo này, chúng tôi sẽ giới thiệu công cụ GPSS và đưa ra quy trình, cách thức dùng công cụ GPSS để xây dựng mô phỏng toán học các kênh phục vụ nói chung..
- Hiện trạng bài toán hệ thống phục vụ đám đông Lý thuyết phục vụ đám đông hay Lý thuyết hàng đợi, nghiên cứu quá trình phục vụ.
- Nó nghiên cứu những đặ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 (của khách hàng) [1].
- Những yêu cầu, thời gian phục vụ là những đại lượng ngẫu nhiên.
- Thành phần của một hệ thống phục vụ đám đông bao gồm: luồng các yêu cầu vào.
- máy phục vụ.
- phương pháp phục vụ.
- hàng đợi và phương pháp lựa chọn yêu cầu.
- luồng các yêu cầu ra.
- Việc giải quyết bài toán mô phỏng toán học các hệ thống phục vụ đám đông có thể tiến hành bằng các công thức toán học theo lý thuyết hàng đợi.
- mô phỏng bằng các ngôn ngữ lập trình thông thường như Pascal, C.
- tuy nhiên việc lập trình bằng các ngôn ngữ này rất phức tạp 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ì những lý do này, việc sử dụng các ngôn ngữ mô phỏng như Matlab, GPSS, PETRI Network [2-6]… là một vấn đề cần thiết và mang ý nghĩa khoa học thực sự, đặc biệt trong việc mô phỏng các hệ thống kênh phục vụ phức tạp như các hệ thống viễn thông, các hệ thống bán vé tự động, sân bay, giao thông.
- Ngôn ngữ mô phỏng GPSS.
- GPSS không dùng các bước nhảy theo thời gian mà dựa trên việc tạo ra các “giao dịch.
- Transaction có thể xem như là một “yêu cầu”, hay một “sự kiện” trong hệ thống phục vụ đám đông.
- Mỗi Transaction trong quá trình mô phỏng luôn thuộc vào một BLOCK xác định nào đó, nhưng hầu hết các BLOCK đều có thể chứa cùng lúc nhiều Transactions khác nhau.
- Mỗi Transaction dịch chuyển vào một BLOCK, sau đó đến BLOCK tiếp theo, cứ thể cho đến khi nó được xóa bỏ, tức là rơi vào trạng thái TERMINATED hoặc quá trình mô phỏng dừng.
- Thời gian Transaction lưu lại trong mỗi BLOCK là đại lượng ngẫu nhiên, được xác định bởi tính chất của hệ thống và trong GPSS cho phép sinh ra các đại lượng này theo các quy luật khác nhau.
- Ví dụ như thời gian để phục vụ một yêu cầu của khách hàng tại quầy thu ngân.
- thời gian để một máy bay thực hiện việc cất cánh trên đường băng… Để khởi tạo một Transaction trong GPSS sử dụng block GENERATE.
- A,B,C,D,E Tham biến A xác định khoảng thời gian trung bình xuất hiện một Transaction.
- Nếu như khoảng thời gian này là hằng số thì tham biên B không sử dụng, ngược lại sử dụng tham biến B để xác định độ thay đổi của khoảng thời gian này.
- tạo transaction sau mỗi khoảng thời gian ngẫu nhiên theo quy luật phân bố đều trong khoảng [60;140.
- GENERATE 1 ;cứ sau mỗi 1 tick thì có 1 “yêu cầu”- transaction ADVANCE 5 ;thực hiên trong 5 ticks sau khi chuyển sang block khác.
- yêu cầu được kết thúc.
- Facilities Facilities trong GPSS có thể được hiểu là các “thiết bị”, cơ sở vật chất của hệ thống như là các máy phục vụ…Trong quá trình mô phỏng, nếu Facility rỗi thì các transaction mới có thể sử dụng nó.
- Các Blocks được sử dụng để điều khiển việc sử dụng, quyền sử dụng và trạng thái của Facility gồm có.
- SEIZE dùng để yêu cầu sử dụng “thiết bị” hoặc là chờ đợi “thiết bị” được giải phóng để sử dụng.
- PREEMPT A,B,C,D,E – Transaction – “yêu cầu” hiện thời chiếm đoạt “thiết bị” và sử dụng, tên hoặc số hiệu của “thiết bị” được thiết lập ở tham biến A, việc chiếm đoạt có thể theo thứ tự ưu tiên nếu ở tham biến B của block này đưa vào giá trị PR;.
- VD: PREEMPT DUONGBANG, PR ;Đường băng tiếp nhận các máy bay theo sự ưu tiên;.
- FAVAIL – đưa “thiết bị” về trạng thái có thể làm việc;.
- Queues Là một thành phần rất quan trọng trong GPSS World, được dùng để lưu giữ thông tin trong quá trình xử lý các “yêu cầu.
- Đối với một Queue trong GPSS có 2 giai đoạn làm việc, “yêu cầu” được đưa vào một Queue và lấy “yêu cầu” từ Queue ra:.
- yêu cầu sử dụng Facility có tên là crew1.
- làm một cái gì đó trong một khoảng thời gian là 10 đơn vị.
- “yêu cầu” được đưa ra khỏi hàng đợi order.
- Thay vì sử dụng Block QUEUE để lưu giữ thông tin của các “yêu cầu” có thể sử dụng Blocks LINK/UNLINK.
- Các Block này cho phép thiết lập quy tắc ghi, sắp xếp các “yêu cầu” cũng như lấy chúng ra để xử lý: FIFO – “vào trước ra trước”, LIFO – “vào sau ra trước”, hoặc theo độ ưu tiên của các “yêu cầu”.
- đưa “yêu cầu” hiện thời vào vị trí cuối cùng của hàng đợi order..
- Built-in Probability Distributions Trong lý thuyết hàng đợi hay hệ thống phục vụ đám đông hầu hết các thông số như tần suất xuất hiện “yêu cầu”, thời gian phục vụ “yêu cầu”… đều là những đại lượng ngẫu nhiên.
- Một ưu điểm của GPSS World đó là có nhiều luồng sinh số ngẫu nhiên khác nhau và hỗ trợ sẵn các hàm cho phép tạo các số ngẫu nhiên theo các quy luật phân bố khác nhau như: Beta, Discrete Uniform, Exponential, Gamma, Poisson… Các hàm này thường được sử dụng trong các Blocks như GENERATE và ADVANCE.
- Ví dụ, để mô phỏng quá trình hạ cánh ở sân bay có tần suất trung bình 2 phút có một máy bay hạ cánh theo quy luật phân phối Exponential ta có thể sử dụng:.
- và như vậy các thời điểm hạ cánh sẽ được sinh ngẫu nhiên theo đúng quy luật phân phối từ luồng sinh số thứ nhất.
- Quy trình sử dụng GPSS để mô phỏng một hệ thống phục vụ đám đông Để mô phỏng một hệ thống phục vụ đám đông đầu tiên chúng ta cần cài đặt một công cụ cho phép xây dựng chương trình trên ngôn ngữ GPSS.
- trong bài báo này các tác giả sử dụng phiên bản này để mô phỏng các hệ thống phục vụ đám đông..
- Để mô phỏng một hệ thống phục vụ đám đông vào menu File và tạo một project mới, chọn New model, GPSS World sẽ tạo cho chúng ta một Model.
- Thực hiện viết code chương trình bằng ngôn ngữ GPSS cho hệ thống, thực thi lệnh Create Simulation từ menu Command để GPSS World tiến hành biên dịch codes và tạo một mô phỏng mới.
- Và lúc này ở menu Simulation Window sẽ xuất hiện các cửa sổ như: Blocks Window, Facilities Window, Plot Window, Queues Window… cho phép theo dõi quá trình mô phỏng và tính toán..
- Trong menu Command có các lệnh: START, STEP, HALT, CONTINUE để điều khiển quá trình mô phỏng.
- Khi quá trình mô phỏng kết thúc theo mặc định cửa sổ báo cáo kết quả REPORT sẽ xuất hiện..
- Xét bài toán mô phỏng hoạt động tại một sân bay.
- Ở một sân bay lớn, máy bay hạ cánh xuống đường băng (đường băng cất cánh và hạ cánh) với tần suất khoảng từ 10 ±5 phút.
- Nếu đường băng “tự do” thì máy bay sẽ nhận được sự đồng ý cho hạ cánh từ bên điều khiển không lưu, máy bay đó sẽ hạ cánh và mất đúng 2 phút cho việc hạ cánh.
- Còn nếu như đường băng “bận” (không tự do) thì máy bay phải bay tiếp theo một vòng tròn gần sân bay, và sẽ tiếp tục đòi hỏi hạ cánh xuống sân bay đó sau thời gian đúng 4 phút.
- Nếu như sau 5 vòng bay trên không liên tục, mà máy bay đó vẫn không nhận được sự đồng ý cho hạ cánh, thì máy bay đó sẽ bay sang một sân bay phụ.
- Tại sân bay đó, cứ trung bình từ 10±2 phút thì lại có một máy bay được cất cánh, nếu đường băng “tự do” thì máy bay đó sẽ cất cánh và mất đúng 2 phút cho việc cất cánh.
- Ở tại sân bay này, luôn luôn ưu tiên cho các máy bay cất cánh, như vậy trong trường hợp cùng một thời điểm có một máy bay muôn cất cánh và một bay muốn hạ cánh, thì đường băng sẽ đường dành cho máy bay cất cánh..
- Mô phỏng hoạt động của sân bay trong thời gian một ngày (24 giờ).
- Đếm số máy bay cất cánh được, số máy bay hạ cánh được, số máy bay phải thực hiện hạ cánh ở sân bay phụ.
- Tính hệ số sử dụng đường băng của sân bay đó.
- ;sigment 1 – Segment miêu tả cho máy bay hạ cánh ;DOWN.
- ;Xác lập tham số 1 cho kênh phục vụ tại thời điểm 0.
- ;để kiểm tra số vòng máy bay phải bay để chờ hạ cánh Again.
- ;Máy bay nhận thông báo từ đường băng.
- ;Nếu đường băng bận thì đi tới khối Busy.
- ;Đường băng tiếp nhận các máy bay theo sự ưu tiên.
- ;Thời gian bận của đường băng trong quá trình.
- ;phục vụ.
- ;Đường băng phục vụ máy bay hạ cánh.
- ;Giải phóng đường băng.
- ;Nếu tham số 1 của kênh phục vụ hiện tại bằng 5.
- ;bay hạ cánh sẽ bay sang sân bay phụ.
- ;Thời gian bay 1 vòng.
- ;Tăng số vòng bay đối với máy bay này.
- ;Đến lượt máy bay tiếp theo term.
- ;Máy bay sẽ bay sang sân bay phụ.
- ;sigment 2 – Đối với máy bay cất cánh.
- 8'=>12' có một máy bay cất cánh.
- ;Thời gian đường băng bận trong quá trình phục vụ.
- nghĩa là thời gian 1 ngày đêm tính.
- Kết quả mô phỏng nhận được ở file REPORT như sau:.
- Số lượng máy bay hạ cánh trong khoảng một ngày đêm : 146.
- Số lượng máy bay hạ cánh, mà phải thực hiện chuyến bay theo đường vòng : 28.
- Số lượng máy bay hạ cánh thành công trong thời gian một ngày đêm: 146.
- Số lượng máy bay hạ cánh không thành công trong khoảng một ngày đêm: 0.
- Số lượng máy bay cất cánh trong khoảng một ngày đêm: 142.
- Số lượng máy bay cất cánh thành công trong khoảng một ngày đêm: 142.
- Hệ số sử dụng của đường băng cho việc cất cánh- hạ cánh: 40 % Kết luận Trong bài báo này các tác giả đã nghiên cứu về lý thuyết hàng đợi và hệ thống phục vụ đám đông.
- ngôn ngữ mô phỏng GPSS và công cụ GPSS World trong bài toán mô phỏng hệ thống phục vụ đám đông.
- Dùng GPSS có thể tạo ra các “yêu cầu.
- Trong GPSS có các đối tượng tương ứng với các thành phần của một hệ thống phục vụ đám đông như: Transactions, Facilities, Queues… Để thực hiện ví dụ minh họa các tác giả đã sử dụng công cụ GPSS World tiến hành mô phỏng hoạt động của sân bay và tính toán các thông số đối với hệ thống phục vụ đám đông này.
- Kết quả thực nghiệm cho thấy, mô phỏng bài toán hệ thống phục vụ đám đông bằng công cụ GPSS World cùng cho ra một kết quả nhưng đơn giản và hiệu quả hơn nhiều so với việc tính toán lý thuyết cũng như lập trình mô phỏng bằng các ngôn ngữ lập trình như Pascal, C.
- GPSS cho phép quan sát quá trình mô phỏng một cách dễ dàng và trực quan thông qua các cửa sổ: Blocks Window, Facilities Window, Plot Window, Queues Window… Bằng ngôn ngữ mô phỏng GPSS và công cụ GPSS World hoàn toàn có thể tiến hành mô phỏng các hệ thống phục vụ đám đông phức tạp gồm nhiều nguồn yêu cầu, nhiều kênh phục vụ và các quy tắc phục vụ khác nhau…