Tóm tắt Luận văn Thạc sĩ ngành Công nghệ thông tin: Nghiên cứu và ứng dụng lý thuyết hàng đợi trong bài toán mô phỏng hoạt động một siêu thị

nội dung Luận văn trình bày 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. Ngoài cách tiếp cận bằng lý thuyết hàng đợi, luận văn tập trung nghiên cứu hiện trạng một số công cụ mô phỏng các bài toán hàng đợi: Giới thiệu ngôn ngữ, công cụ mô phỏng GPSS World và sử dụng để giải quyết bài toán hàng đợi thực tế.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận văn Thạc sĩ ngành Công nghệ thông tin: Nghiên cứu và ứng dụng lý thuyết hàng đợi trong bài toán mô phỏng hoạt động một siêu thị ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THU THỦY NGHIÊN CỨU VÀ ỨNG DỤNG LÝ THUYẾT HÀNG ĐỢI TRONG BÀI TOÁN MÔ PHỎNG HOẠT ĐỘNG MỘT SIÊU THỊ Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2017 1 Nghiên cứu và ứng dụng lý thuyết hàng đợi trong bài toán mô phỏng hoạt động một siêu thị Nguyễn Thu Thủy Trường Đại học Công nghệ Luận văn Thạc sĩ ngành: Kỹ thuật phần mềm, mã số: 60480103 Người hướng dẫn: TS. Lê Quang Minh Năm bảo vệ: 2017 Tổng quan: Trình bày 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. Ngoài cách tiếp cận bằng lý thuyết hàng đợi, luận văn tập trung nghiên cứu hiện trạng một số công cụ mô phỏng các bài toán hàng đợi: giới thiệu ngôn ngữ, công cụ mô phỏng GPSS World và sử dụng để giải quyết bài toán hàng đợi thực tế.Về ngôn ngữ GPSS và công cụ GPSS World: đề 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. 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ế: mô phỏng hoạt động hàng đợi đơn giản là bãi đỗ xe tại siêu thị, và mô phỏng hoạt 2 động của hệ thống dịch vụ phức tạp với nhiều phase phục vụ được cung cấp tại siêu thị từ gửi xe, giỏ hàng tới khi thanh toán và rời hệ thống. Từ khóa: Hàng đợi; Mô hình hàng đợi; Ngôn ngữ GPSS. Nội dung TÓM TẮT LUẬN VĂN THẠC SỸ Chương I: Lý thuyết hàng đợi Chương 1 tập trung trình bày về lý thuyết hàng đợi bao gồm: các khái niệm cơ bản như biến ngẫu nhiên, các phân phối xác suất thường gặp, khái niệm hàng đợi và các đặc điểm của hàng đợi; Ký hiệu Kendall và định nghĩa các biến cần quan tâm khi giải quyết bài toán hàng đợi; từ những khái niệm cơ bản đã nêu, phần 2 của chương giới thiệu một số hàng đợi cơ bản thường thấy, phân tích chi tiết quá trình chuyển trạng thái và công thức tính hiệu suất của từng mô hình hàng đợi. Hàng đợi (hay dòng chờ) là một dòng đợi dịch vụ. Yêu cầu được phục vụ từ khách hàng sinh ra theo thời gian thông qua 1 nguồn đầu vào. Khách hàng sẽ phải chờ trong hàng đợi đến lượt được phục vụ. Khách rời khỏi hệ thống sau khi đã được phục vụ. Các thành phần cơ bản và đặc điểm của hàng đợi được trình bày trong hình 1.2. 3 Hình 1. 1- Thành phần cơ bản của hàng đợi Mô hình hàng đợi trong thực tế rất đa dạng, trong đó cần kể đến một số mô hình trình bày trong bảng 1.3 Bảng 1. 1-Một số mô hình hàng đợi cơ bản Tên hàng đơi Số kênh phục vụ Số bước phục vụ Hệ thống đơn hàng M/M/1 Hệ thống đa hàng M/M/c Hệ thống hàng đợi có thời gian phục vụ chính 1 1 c (c>1) 1 1 1 Phân Phân phối Kích phối tín thời gian thước hiệu phục vụ của đến dòng đến Luật Luật phân Không phân phối mũ giới phối mũ hạn Possion Luật phân Không phối mũ giới hạn Possion Luật phân Không phối mũ giới hạn 4 Nguyê n tắc phục vụ FIFO FIFO FIFO xác (M/D/1) Hệ thống hàng đợi M/M/c/K c(c>1 ) 1 Possion Luật phân Giới phối mũ hạn FIFO Với mỗi mô hình có những đặc trưng và hiệu suất khác nhau. Tuy nhiên có những mô hình phức tạp rất khó để giải được bằng lý thuyết toán học. Để bài toán giải được bằng lý thuyết cần đáp ứng một số điều kiện sau: Điều kiện 1: Dòng vào của hệ thống phải là dòng tối giản hoặc xấp xỉ tối giản. Điều kiện 2: Khoảng thời gian (T) giữa 2 lần xuất hiện liên tiếp các yêu cầu là đại lượng ngẫu nhiên tuân theo qui luật hàm số mũ. Như vậy, hàm mật độ xác suất có dạng: (1.1) ( ) = Và hàm phân phối xác suất có dạng ( ) = 1 − (1.2) Với λ là cường độ dòng vào, đó là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian. Điều kiện 3: Thời gian phục vụ của các kênh cũng là đại lượng ngẫu nhiên tuân theo qui luật hàm số mũ. Như vậy, hàm mật độ xác suất có dạng ( ) = Và hàm phân phối xác suất có dạng ( ) = 1 − Với μ là năng suất phục vụ của các kênh, đó là số yêu cầu được phục vụ tính bình quân trên một đơn vị thời gian. Phương pháp giải quyết bài toán bằng lý thuyết có đường lối chung bao gồm các bước: 5