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