Mô hình xếp hàng

Mục đích của quá trình xếp hàng là để giải quyết các vấn đề tắc nghẽn, tối ưu hóa hiệu quả công việc; giảm thiểu thời gian chờ đợi hay bất tiện cho khách hàng; giúp tăng tốc độ sản xuất, và thậm chí là để tiết kiệm cuộc sống.
Nội dung trích xuất từ tài liệu:
Mô hình xếp hàngKhoa hoïc töï nhieân MÔ HÌNH XẾP HÀNG Lưu Thị Thu Huyền, Bùi Thị Thu Dung Khoa Toán – Công nghệ Trường Đại học Hùng Vương TÓM TẮT Mục đích của quá trình xếp hàng là để giải quyết các vấn đề tắc nghẽn, tối ưu hóa hiệu quả công việc; giảm thiểu thời gian chờ đợi hay bất tiện cho khách hàng; giúp tăng tốc độ sản xuất, và thậm chí là để tiết kiệm cuộc sống. Ở đây chúng tôi đã sử dụng lý thuyết xác suất vào nghiên cứu mô hình xếp hàng M/M/s (với hai trường hợp s=1 và s > 1), để tìm ra kỳ vọng - như là một tiêu chuẩn để đánh giá và đưa ra quyết định trong những tình huống cần lựa chọn những chiến lược khác nhau, và phương sai - đặc trưng cho mức độ rủi ro của các quyết định. Dựa vào tiêu chuẩn và dự đoán mức độ rủi ro chúng ta có thể lựa chọn được phương án tốt nhất. Từ khóa: Xếp hàng, mô hình đặc trưng của lý thuyết xếp hàng, hàng đợi M/M/1, hàng đợi M/M/s. 1. Mở đầu Trong một mô hình xếp hàng, khách hàng từ bên ngoài vào hệ thống và sử dụng khoảng thời giannào đó để nhận được sự phục vụ của hệ sau đó thì rời khỏi hệ. Điển hình cho mô hình này là trongquá trình lưu lại trong hệ thống, tức các khách hàng đến mà tất cả các trạm phục vụ đều bận thì kháchhàng đó phải ngồi chờ cho đến khi trạm rỗi, hiện tượng này xảy ra gọi là quá trình ngưng trệ hay quátrình chờ trong hàng. Hiện tượng xếp hàng có thể quan sát được trong thực tế ở những nơi mà vấn đềtắc nghẽn, quá tải còn tồn đọng, như trong các ngành kinh doanh, trong thông tin liên lạc, y tế, giaothông vận tải,... Người mua sắm chờ đợi trong hàng kiểm tra tại quầy thanh toán; khách hàng xếp hàngtại các ngân hàng, rạp chiếu phim, quán cafe hay trạm y tế; các mạch điện thoại xử lý các cuộc gọi đếntheo một trật tự,... Trong bài báo này chúng tôi chỉ xét đến những mô hình mà hiệu quả làm việc của các trạm là nhưnhau, và khách hàng chờ đợi trong một hàng. Các mô hình xếp hàng như vậy thường được đặc trưng bởi: *) Quá trình đến của khách hàng: Giả sử rằng khoảng thời gian giữa hai lần đến liên tiếp là đạilượng ngẫu nhiên có cùng phân phối. Trong thực tế quá trình đến của khách hàng tuân theo quá trìnhPoisson. Các khách hàng đến có thể đến từng người một hoặc đến theo từng nhóm. *) Hành vi của khách hàng: Khách hàng đến có thể kiên nhẫn chờ đợi trong một khoảng thời giandài để được phục vụ hoặc ngược lại có thể rời đi sau một khoảng thời gian chờ đợi. *) Thời gian phục vụ: Giả sử các khoảng thời gian phục vụ là các đại lượng ngẫu nhiên độc lập và cócùng phân phối. Cũng có khi thời gian phục vụ phụ thuộc vào độ dài hàng đợi, chẳng hạn tốc độ xử lýcông việc giảm đi khi mà khối lượng công việc đang chờ xử lý là quá lớn. *) Quy chế phục vụ: Khách hàng đến có thể được phục vụ từng người một hoặc từng nhóm một. Cócác quy tắc cơ bản sau: Đến trước phục vụ trước (FCFS: first come first server, FIFO: first in first out);đến sau phục vụ trước (LCFS: last come first server, LIFO: last in first out); thứ tự ngẫu nhiên; thứ tựưu tiên; chia công việc để xử lý. *) Khả năng xử lý: Hệ thống có thể phục vụ một người hay một nhóm người. *) Hàng đợi: Dung lượng hàng đợi có thể là hữu hạn hay vô hạn. Các yếu tố cần quan tâm cho một mô hình xếp hàng là: - Phân phối của thời gian chờ và thời gian trong hệ thống. Thời gian trong hệ thống là tổng của thờigian chờ trong hàng đợi và thời gian phục vụ. - Phân phối của số lượng khách hàng trong hệ. - Phân phối của các khoảng bận của dịch vụ (máy chủ). Đó là khoảng thời gian mà trong suốtkhoảng đó máy chủ làm việc liên tục. Ñaïi hoïc Huøng Vöông - Khoa hoïc Coâng ngheä 41 Khoa hoïc töï nhieân Trong thực hành ta thường quan tâm đến trung bình các đại lượng như: độ dài hàng đợi (số lượngtrung bình khách hàng trong hệ thống), thời gian chờ, thời gian phục vụ. 2. Phương pháp nghiên cứu Chúng tôi đã nghiên cứu tài liệu về xác suất và ứng dụng của nó trong mô hình xếp hàng, cụ thể làhàng đợi M/M/1 và hàng đợi M/M/s, dựa trên các nghiên cứu khởi đầu về lý thuyết xếp hàng của nhàtoán học người Đan Mạch Agner Krarup Erlang và dựa trên cách xây dựng mô hình xếp hàng trongtài liệu An Introduction to Stochastic processes and Their Applications của tác giả Chin Long Chiang. 3. Nội dung 3.1. Phương trình cân bằng của mô hình M/M/s Đây là mô hình có các đặc trưng sau: Có s trạm phục vụ; khách hàng mới đến tuân theo quá trìnhPoisson với tham số λ ; thời gian dịch vụ có phân phối mũ với tham số µ ; quy trình thực hiện: đếntrước phục vụ trước. Khi cả s trạm đang hoạt động tại thời điểm t thì xác suất để một trạm rỗi trong khoảng thời gian( t , t + ∆ ) là sµ∆ + 0(∆) Đặt X(t) là số khách hàng trong hệ tại thời điểm t, bao gồm những khách hàng đã và đang chờ tronghàng, với X (0) = i . Ta có xác suất chuyển: Pi ,k= (0, t ) Pr {= X (t ) k | = X (0) i}=k 0,1,... thỏa mãn các phương trình vi phân: d Pi ,0 (0, t ) =−λ Pi ,0 (0, t ) + µ Pi ,1 (0, t ) dt d Pi ,k (0, t ) =−(λ + k µ ) Pi ,k (0, t ) + λ Pi ,k −1 (0, t ) + (k + 1) µ Pi ,k +1 (0, t ), k = 1,..., s − 1 dt d Pi ,k (0, t ) =−(λ + s µ ) Pi ,k (0, t ) + λ Pi ,k −1 (0, t ) + s µ Pi ,k +1 (0, t ), k = s, s + 1,... (1) dt Định lý: Nếu tất cả các trạng thái trong một quá trình xếp hàng là liên thông với nhau thì giới hạnxác suất lim Pi ,k (0, t ) = Π k ; i, k = 0,1,... t →∞ tồn tại và nó không phụ thuộc vào thời gian ban đầu và trạng thái ban đầu i. Tổng các xác suất: ∑Π k =1; k (2) ...