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 tập trung trình bày về lý thuyết hàng đợi, các mô hình hàng đợi có thể sẽ liên quan đến bài toán hoạt động của một siêu thị. Chƣơng 2: Công cụ mô phỏng GPSS Luận văn tập trung trình bày về các công cụ mô phỏng GPSS các cách tiếp cận mô phỏng.
Quy trình mô phỏng bài toán thực tế bằng GPSS 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ị. Trình bày bài toán mô phỏng hoạt động của siêu thị cụ thể; bằng phƣơng pháp phân tích sử dụng lý thuyết hàng đợi. Áp dụng công cụ mô phỏng GPSS World và áp dụng quy trình mô phỏng hệ thống hàng đợi để giải quyết bài toán. Từ kết quả thu đƣợc đƣa ra so sánh và đánh giá hiệu quả của mô phỏng.
Kết luận Tóm lƣợc kết quả chính của luận văn, nêu lên các hạn chế của nghiên cứu từ đó định hƣớng phát triển trong thời gian tới. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1. LÝ THUYẾT HÀNG ĐỢI Chƣơng này tập trung trình bày các khái niệm liên quan đến lý thuyết hàng đợi. Đây là những kiến thức tổng quan, cơ bản nhất để phân tích và giải bài toán hàng đợi.1 Các khái niệm cơ bản 1.1 Biến ngẫu nhiên Trong hệ thống hàng đợi dễ dàng nhìn thấy 2 quá trình ngẫu nhiên độc lập: quá trình khách hàng xuất hiện ở đầu vào hệ thống và quá trình phục vụ khách hàng tại đầu ra của hệ thống.
Số lƣợng khách hàng tại một thời điểm đƣợc đặc trƣng bởi một biến ngẫu nhiên rời rạc. Tốc độ đến tại một thời điểm cũng nhƣ thời gian phục vụ đƣợc đặc trƣng bởi các biến ngẫu nhiên. Biến ngẫu nhiên đƣợc ký hiệu bởi X, Y có giá trị kỳ vọng E(X). Phƣơng sai: với độ lệch chuẩn.
Hệ số biến thiên là đại lƣợng mô tả mức độ biến động tƣơng đối của biến ngẫu nhiên. Tính hệ số biến thiên: 1.2 Phân phối sác xuất thƣờng gặp Mục tiêu của việc phân tích hàng đợi bằng lý thuyết là xây dựng mô hình chuyển trạng thái để xác định phân phối dựa vào xác suất ở đầu vào và phân phối xác suất ở đầu ra của hệ thống. Tốc độ đến và thời gian phục vụ đƣợc đặc trƣng bởi một phân phối xác suất. Các phân phối thƣờng gặp [2] hai đại lƣợng này đƣợc trình bày trong bảng 1.
1- Một số hàm phân phối thường gặp STT Viết tắt Tên Hàm phân phối Phân phối 1 M mũ Phân phối 2 Ek Erlang k f (t ) q j (1 e jt ) Phân phối j 1 3 Hk siêu bội Trong đó: μj >0, qj>0, j∈{1.k}, 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phân phối 5 G hình học Phân phối 6 Possion 1.1 Phân phối hình học (Geometric distribution) Là phân phối đặc trƣng cho số các biến cố sảy ra trong một khoảng thời gian cho trƣớc. Một biến ngẫu nhiên hình học [2 tr.18] với phân phối xác suất: Với phân phối này chúng ta có một số công thức sau 1.2 Phân phối Poisson (Poisson distribution) Là phân phối thƣờng gặp nhất trong các mô hình hàng đợi phân phối Poisson [6 tr.6-7] đƣợc đặc trƣng cho những quá trình đến và phục vụ hoàn toàn ngẫu nhiên, độc lập. Một biến phân phối Poisson với tham số có phân phối , n=0, 1, 2,… Trong đó: - là xác suất để trong khoảng thời gian τ có n yêu cầu xuất hiện; - n là số yêu cầu xuất hiện trong khoảng thời gian quan sát τ; - là số yêu cầu trung bình xuất hiện trong từng khoảng thời gian quan sát τ. Phân phối Poisson ta có: Biến ngẫu nhiên tuân có phân phối Poisson khi dòng đến có đủ các đặc điểm của quá trình Poisson.
Quá trình Poisson có 3 tính chất sau: Tính không hậu quả: Dòng yêu cầu có tính không hậu quả có nghĩa là: nếu xác suất xuất hiện một số yêu cầu nào đó trong một khoảng thời gian nhất định không phụ thuộc vào việc đã có bao nhiêu yêu cầu xuất hiện trƣớc khoảng thời gian đó. Hay nói khác, số yêu cầu xuất hiện trƣớc và sau thời điểm nào đó không chịu ảnh hƣởng qua lại lẫn nhau. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Tính đơn nhất Dòng yêu cầu có tính chất đơn nhất có nghĩa là: nếu xét trong khoảng thời gian khá bé thì biến cố “có nhiều hơn một yêu cầu xuất hiện” hầu nhƣ không xảy ra. Về mặt thời gian, chúng ta có thể xem dòng yêu cầu có tính chất đơn nhất nếu thời điểm xuất hiện các yêu cầu không trùng nhau.
Tính dừng (tính thuần nhất theo thời gian) Dòng yêu cầu có tính chất dừng có nghĩa là: nếu xác suất xuất hiện k yêu cầu trong khoảng thời gian τ chỉ phụ thuộc vào giá trị của τ và của k chứ không phụ thuộc vào việc khoảng thời gian τ này nằm ở vị trí nào trên dòng thời gian. Điều này có nghĩa là với những khoảng thời gian τ dài bằng nhau thì xác suất xuất hiện k yêu cầu nhƣ nhau.3 Phân phối mũ (Exponential Distributions) Mật độ của một phân phối mũ [2 tr.20]với tham số đƣợc cho bởi hàm , t>0. Có hàm phân phối xác suất: Với hàm phân phối này ta có một số công thức tính kỳ vọng và phƣơng sai nhƣ sau: 1.4 Phân phối Erlang (Erlang distribution) Một biến có một phân phối Erlang-k [9 tr.5] (k=1,2,…) với nếu X là tổng của E biến độc lập có phân phối mũ chung. Ký hiệu chung là hoặc ngắn gọn là.
Hàm phân phối xác suất bằng: Tham số đƣợc gọi là tham số quy mô (scale parameter), là tham số hình dạng (shape parameter) Một sơ đồ trạng thái của đƣợc biểu diễn bởi Hình 1.1 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.