ĐẠ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ênngà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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠ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ôngnghệthông tin Chuyênngành: Kỹthuậtphầnmềm Mãsố: 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TIẾN SĨ LÊ QUANG MINH HàNội - 2017 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu do chính tôi thực hiện trên cơ sở tìm kiếm, thu thập, nghiên cứu, tổng hợp trình bày bằng văn bản. Các tài liệu tham khảo đều đƣợc nêu ở phần cuối của luận văn. Các số liệu, kết quả nêu trong luận văn là trung thực 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 hoàn toàn chịu trách nhiệm. HỌC VIÊN NGUYỄN THU THỦY 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC LỜI CAM ĐOAN .2 DANH MỤC HÌNH VẼ .4 DANH MỤC CÁC BẢNG .5 Chƣơng 1: LÝ THUYẾT HÀNG ĐỢI .1 Các khái niệm cơ bản .1 Biến ngẫu nhiên.2 Phân phối sác xuất thƣờng gặp .3 Khái niệm hàng đợi và lý thuyết hàng đợi .5 Định nghĩa các độ đo hiệu suất .2 Một số mô hình hàng đợi cơ bản .1 Hệ thống một kênh phục vụ M/M/1 .2 Hệ thống đa kênh phục vụ M/M/c.3 Hệ thống hàng đợi có thời gian phục vụ chính xác (M/D/1) .4 Hệ thống hàng đợi giới hạn kích thƣớc M/M/c/K.3 Các điều kiện để bài toán có thể giải đƣợc bằng lý thuyết .4 Phƣơng pháp giải quyết bài toán bằng lý thuyết hàng đợi.24 Chƣơng 2: CÔNG CỤ MÔ PHỎNG GPSS WORLD.1 Cách tiếp cận mô phỏng .2 Hiện trạng một số công cụ mô phỏng chuyên dụng .3 Giới thiệu về GPSS World .1 Đặc điểm nổi bật của ngôn ngữ GPSS World .2 Một số khái niệm trong GPSS World .3 Các thực thể trong GPSS .4 Cú pháp lệnh GPSS .5 Các khối cơ bản trong GPSS .6 Một số hàm thƣ viện.7 Cài đặt và sử dụng GPSS World Student Version .4 Hàng đợi có ƣu tiên Priority Queueing .42 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.5 Các bƣớc mô phỏng bài toán trên GPSS World .44 CHƢƠNG 3: ỨNG DỤNG LÝ THUYẾT HÀNG ĐỢI VÀ CÔNG CỤ MÔ PHỎNG VÀO BÀI TOÁN HÀNG ĐỢI SIÊU THỊ .1 Một số quan sát về hàng đợi siêu thị.2 Bài toán xếp hàng gồm 1 phase phục vụ .1 Phát biểu bài toán .2 Phân tích bài toán bằng lý thuyết hàng đợi.3 Mô phỏng bài toán bằng công cụ mô phỏng .3 Bài toán xếp hàng nhiều phase phục vụ .1 Phát biểu bài toán .2 Phân tích bài toán bằng lý thuyết hàng đợi .3 Mô phỏng bài toán bằng công cụ mô phỏng .70 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC HÌNH VẼ Hình 1. 1- Sơ đồ chuyển trạng thái của phân phối Erlang-k với biến quy mô là . 2- Thành phần cơ bản của hàng đợi . 3 - Mô hình hàng đợi M/M/1 . 4- Mô hình hàng đợi M/M/1 . 5 - Sơ đồ chuyển trạng thái của hàng đợi M/M/1 . 6- Mô hình hàng đợi M/M/c . 7 - Sơ đồ chuyển trạng thái hàng đợi M/M/c . 8- Mô hình hàng đơi M/M/c/K . 9 - Sơ đồ chuyển trạng thái mô hình hàng đợi M/M/c/K . 1 - Mô tả chƣơng trình mô phỏng bằng GPSS . 2- Một segment điển hình . 3- Mô hình một chƣơng trình mô phỏng hệ thống hàng đợi đơn giản . 4- Cách lấy yêu cầu của hàng đợi Priority Queueing . 7- Quy trình mô phỏng . 1- Đồ thị sác xuất số khách hàng trong hệ thống . 2- Mô hình thuật toán giải bài toán bãi đậu xe . 3- Mã nguồn mô phỏng bài toán bãi đỗ xe . 4- Báo cáo thu đƣợc khi chạy mô phỏng . 5- Mô tả mô hình hoạt động của siêu thị . 6- Mô hình thuật toán hoạt động của siêu thị .61 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC BẢNG Bảng 1. 1- Một số hàm phân phối thƣờng gặp . 2 - Một số tham số của hàng đợi . 3-Một số mô hình hàng đợi cơ bản . 1- Một số Block cơ bản làm việc với giao tác . 2- Một số khối làm việc với thực thể thiết bị . 3 Một số khối cơ bản điều khiển dịch chuyển của giao tác . 1- Kết quả mô phỏng với thời gian 8h . Kết quả mô phỏng với thời gian khác nhau . 3- Bảng so sánh độ lệch giữa mô phỏng và tính toán từ lý thuyết của lƣợng xe đƣợc phục vụ . 4- Kết quả tính toán hàng đợi gửi xe ô tô . 5-Bảng kết quả tính toán hàng đợi bãi gửi xe máy . 6- Kết quả tính toán hàng đợi giỏ hàng trong 8h . 7- Kết quả tính toán hàng đợi xe đẩy trong 8h. 8 – Kết quả mô phỏng hoạt động của siêu thị .66 Tƣơng tự cách tiến hành với mô hình bài toán bãi gửi xe, thực hiện thay đổi thời gian mô phỏng bằng cách cài đặt lại biến thời gian v_time_work lần lƣợt bằng các giá trị: 16*60*60, 24*60*60, 40*60*60, 80*60*60 sau đó chạy mô phỏng. Đem so sánh kết quả từng trƣờng hợp với lý thuyết. 9 đƣa ra so sánh thời gian phục vụ của các quầy phục vụ với thời gian trung bình tính toán từ lý thuyết (225 giây). Bảng so sánh thời gian thanh toán trung bình .68 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LỜI MỞ ĐẦU Hàng đợi ảnh hƣởng đến nhiều mặt trong cuộc sống thực tế cũng nhƣ lĩnh vực kỹ thuật. Trong hoạt động xã hội, hàng đợi là điều không mong muốn của các hệ thống phục vụ đám đông, từ thực tế đó các nhà quản lý luôn mong muốn đánh giá đƣợc hiệu quả hệ thống dịch vụ của họ để cải tiến chất lƣợng phục vụ, giảm chi phí vô ích. Trong các hoạt động sản xuất kinh doanh cũng nhƣ đời sống hàng ngày đều tồn tại những hệ thống phục vụ nhƣ: Bến cảng, khách sạn, nhà hàng, trạm điện thoại, cửa hàng bán xăng dầu. Trong các hệ thống ấy thƣờng diễn ra 2 quá trình: Quá trình nảy sinh các yêu cầu và quá trình phục vụ các yêu cầu. Tuy nhiên, trong quá trình hoạt động của hệ thống do nhiều nguyên nhân khác nhau thƣờng dẫn đến các tình trạng: - Khả năng phục vụ của hệ thống không đáp ứng yêu cầu dẫn đến kết quả là một số yêu cầu không được phục vụ hoặc phải chờ đợi để được phục vụ. - Khả năng phục vụ của hệ thống vượt quá yêu cầu dẫn đến kết quả là hệ thống không sử dụng hết năng lực về lao động, vật tư, thiết bị. Cả hai tình trạng trên đều gây nên thiệt hại về mặt kinh tế nói chung. Vì vậy bài toán đặt ra là phân tích bản chất của các quá trình diễn ra trong hệ thống và thiết lập mối quan hệ về lƣợng giữa các đặc trƣng của các quá trình ấy. Trên cơ sở các mối liên hệ đã đƣợc xây dựng và các số liệu thu thập đƣợc từ hệ thống, tính toán, phân tích và đƣa ra quyết định nhằm điều khiển hệ thống hoạt động có hiệu quả. Để trả lời cho những câu hỏi về hàng đợi, chúng ta có 2 phƣơng pháp cơ bản để phân tích là phƣơng pháp phân tích bằng lý thuyết hàng đợi (hay còn gọi là phƣơng pháp giải tích) và mô phỏng hàng đợi. Lý do dùng 2 phƣơng pháp thay vì chỉ dùng một phƣơng pháp là: phân tích bằng lý thuyết chỉ khả thi với các hệ thống hàng đợi đơn giản nhƣ hàng đợi đơn, hệ thống với những đặc điểm riêng về quy tắc đến và phân phối thời gian dịch vụ (phân phối Possion hay Normal); hầu hết hệ thống phức tạp đều cần sử dụng mô phỏng, nhƣ hệ thống cần quan sát dữ liệu thật hoặc phụ thuộc vào yếu tố thời gian, sẽ khó phân tích bằng lý thuyết. Trên thực tế, mỗi hệ thống phục vụ đám đông có tính đặc thù riêng và cần đƣợc phân tích kỹ lƣỡng bằng mô hình toán học cũng nhƣ mô phỏng. Mô phỏng tính toán là phƣơng pháp xem xét thông tin về hành vi của hệ thống. Khi phân tích hiệu suất của hàng đợi, chúng ta cần tìn hiểu, thiết kế và điều khiển năng lực của hệ thống phục vụ và quyết định khi nào mở hay đóng dịch vụ. Sử dụng thông tin ƣớc lƣợng giá trị lãng phí, xác định đƣợc hạn chế của dịch vụ taị mỗi thời điểm xác định để có giá trị lãng phí nhỏ nhất (giá trị dịch vụ + thời gian chờ đợi) 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Có nhiều cách để mô phỏng hàng đợi nhƣ: xây dựng giải thuật và triển khai bằng ngôn ngữ lập trình; Mô phỏng bằng các công cụ chuyên nghiệp nhƣ (Petri Nets, MatLab, GPSS, NS2,…). Công cụ mô phỏng cần sinh ngẫu nhiên sự kiện và quản lý vòng đời của sự kiện theo thời gian và mô phỏng vận hành của của hệ thống, vì vậy sử dụng công cụ lập trình để triển khai thuật toán tốn khá nhiều thời gian. Công cụ mô phỏng sự kiện rời rạc của IBM phát triển vào khoảng thập niên 1960 - General Purpose Simulation System (viết tắt là GPSS) là công cụ đƣợc lựa chọn để giới thiệu và sử dụng trong luận văn này. Vấn đề nghiên cứu và ứng dụng ngôn ngữ mô phỏng GPSS tại Liên bang Nga, cũng nhƣ một số quốc gia phát triển khác không còn xa lạ [1]. Ở Việt Nam, việc ứng dụng GPSS cũng đã đƣợc đề cập tới ở một số công trình, luận văn khoa học; tuy nhiên việc áp dụng GPSS để mô phỏng chƣa áp dụng theo một phƣơng pháp có tính tổng quát. Trên cơ sở các nghiên cứu về phƣơng pháp giải bài toán hệ thống phục vụ đám đông, luận văn đã tập trung vào các mục tiêu sau: Luận văn tập trung nghiên cứu về một số kiến thức cơ bản trong “ Lý thuyết hàng đợi”, các mô hình hàng đợi, công cụ mô phỏng hàng đợi là GPSS. Đề xuất quy trình xây dựng mô phỏng bằng GPSS và vận dụng để giải quyết bài toán xếp hàng tại siêu thị có thành phần ƣu tiên và không ƣu tiên. Luận văn đƣợc trình bày trong ba chƣơng với nội dung chính của mỗi chƣơng nhƣ sau Chƣơng 1: Lý thuyết hàng đợi.
Luận văn thạc sĩ VNU-UET: Nghiên cứu lý thuyết hàng đợi mô phỏng siêu thị
Luận văn thạc sĩ VNU UET nghiên cứu ứng dụng lý thuyết hàng đợi trong mô phỏng hoạt động siêu thị, mang lại giải pháp tối ưu cho quản lý.
Trường đại học
Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà NộiChuyên ngành
Công Nghệ Thông TinNgười đăng
Ẩn danhThể loại
Luận văn thạc sĩPhí lưu trữ
30 PointMục lục chi tiết
THÔNG TIN CHI TIẾT
Tác giả: Nguyễn Thu Thủy
Người hướng dẫn: Tiến Sĩ Lê Quang Minh
Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
Chuyên ngành: Công Nghệ Thông Tin
Đề tài: 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ị
Loại tài liệu: Luận văn thạc sĩ
Năm xuất bản: 2017
Địa điểm: Hà Nội
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ