Khoa học quản lý ứng dụng - Chương 7: Lý thuyết hàng đợi (sắp hàng) - Huỳnh Đỗ Bảo Châu

2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 1 CHƯƠNG 7 LÝ THUYẾT HÀNG ĐỢI (SẮP HÀNG) 1 TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOA HỌC QUẢN LÝ ỨNG DỤNG GV. ThS. Huỳnh Đỗ Bảo Châu ĐẶT VẤN ĐỀ  Tại cửa hàng có 1 quầy tính tiền.  Có nhiều khách hàng cần tính tiền  Khách hàng xếp hàng tại quầy tính tiền tạo thành hàng đợi. 2 GV. Huỳnh Đỗ Bảo Châu Waiting lines ĐẶT VẤN ĐỀ GV. Huỳnh Đỗ Bảo Châu3  Chờ đợi, xếp hàng là một vấn đề thường gặp trong cuộc sống hằng ngày.  Khách hàng chờ đợi mua sắm, hoặc sử dụng dịch vụ,  Trong sản xuất, nguyên liệu chờ sản xuất, máy móc chờ được sử dụng,  Máy bay chờ để đáp, cất cánh   Tốn thời gian  Thời gian là một nguồn tài nguyên có giá trị, giảm thời gian chờ đợi là một vấn đề quan trọng cần phân tích. ĐẶT VẤN ĐỀ GV. Huỳnh Đỗ Bảo Châu4  Các công ty, NCC dịch vụ nghĩ ra cách giảm thời gian chờ đợi  Tăng năng lực dịch vụ Vd: tăng số máy móc, tăng nhân viên phục vụ, tăng quầy phục vụ,  Tăng chi phí đầu tư  Cơ sở phân tích hàng đợi là mối quan hệ giữa chi phí cải thiện dịch vụ và các chi phí nếu khách hàng phải chờ đợi.  KẾT QUẢ PHÂN TÍCH HÀNG ĐỢI LÀ MỘT XÁC SUẤT 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 2 Nội dung chính 1. Các chi phí của hàng đợi 2. Các đặc tính của hệ thống hàng đợi 3. Các mô hình bài toán hàng đợi 5 GV. Huỳnh Đỗ Bảo Châu Giới thiệu GV. Huỳnh Đỗ Bảo Châu6  Nghiên cứu về hàng đợi còn được gọi là Lý thuyết sắp hàng, là 1 trong những kỹ thuật phân tích định lượng được sử dụng từ lâu.  Ba thành phần cơ bản của quá trình sắp hàng:  Lượng khách đến (arrivals)  Phương tiện phục vụ (service facilities)  Dòng chờ thực sự (actual waiting line)  Các mô hình phân tích hàng đợi có thể giúp các nhà quản lý đánh giá chi phí và hiệu quả của hệ thống phục vụ. Giới thiệu GV. Huỳnh Đỗ Bảo Châu7  Các vấn đề sẽ được xem xét đối với hàng đợi:  Chi phí của hàng đợi  Đặc tính của hàng đợi  Các giả thiết toán học cơ bản được sử dụng để phát triển các mô hình hàng đợi  Các phương trình cần thiết để tính toán các đặc tính vận hành của hệ thống phục vụ  Các ví dụ minh họa 1. Các chi phí của hàng đợi GV. Huỳnh Đỗ Bảo Châu8 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 3 VẤN ĐỀ BÀI TOÁN GV. Huỳnh Đỗ Bảo Châu9  Xác định mức độ phục vụ lý tưởng của công ty cần cung cấp để thỏa mãn nhu cầu cho khách hàng. Giảm chi phí chờ đợi cho khách hàng Tăng chi phí phục vụ của công ty Trạm xăng cần xác định có bao nhiêu máy bơm xăng để phục vụ khách hàng ??? Chi phí cần xem xét GV. Huỳnh Đỗ Bảo Châu10  ĐÁNH ĐỔI: CHI PHÍ DỊCH VỤ vs PHỤC VỤ TỐT NHẤT Tổng chi phí kỳ vọng (total expected cost) = Chi phí phục vụ (service) + Chi phí chờ đợi (waiting) Mức độ phục vụ tối ưu = Min (Tổng chi phí kỳ vọng) Chi phí chờ đợi có thể phản ảnh qua số lượng sản phẩm mà khách hàng không sản xuất được do phải dùng thời gian lẽ ra làm việc thay vì sắp hàng. Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu11  Bài toán công ty vận tải đường sông Sài Gòn.  Mỗi ca làm việc (12 giờ) sẽ có 5 tàu cập bến để bốc hàng.  Tàu nằm chờ bốc dỡ hàng tốn 1000$/giờ.  Nếu có 1 đội bốc dỡ, 1 tàu đợi 7h để được bốc dỡ Nếu có 2 đội bốc dỡ, 1 tàu đợi 4h để được bốc dỡ Nếu có 3 đội bốc dỡ, 1 tàu đợi 3h để được bốc dỡ Nếu có 4 đội bốc dỡ, 1 tàu đợi 2h để được bốc dỡ  Thù lao trả cho 1 đội bốc dỡ trong 1 ca là 6000$/đội  Cần bao nhiêu đội bốc dỡ hàng là hợp lý ? Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu12 Hạng mục Số đội bốc dỡ 1 2 3 4 Số tàu đến TB mỗi ca – a Thời gian chờ TB (giờ) – b Tổng thời gian các tàu chờ mỗi ca (giờ) – a*b = c Chi phí chờ bốc dỡ mỗi giờ ($) – d  Chi phí chờ đợi các tàu mỗi ca – c*d = e Chi phí phục vụ (lương trả đội bốc dỡ) – f Tổng chi phí kỳ vọng – e+f 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 4 2. Các đặc tính của hệ thống hàng đợi GV. Huỳnh Đỗ Bảo Châu14 Các đặc tính của khách đến GV. Huỳnh Đỗ Bảo Châu15  Số lượng khách đến  Vô hạn  Hữu hạn  Dạng của lượng khách đến: được xem là ngẫu nhiên  Hành vi của khách đến:  Giả định phổ biến: khách hàng có tính kiên nhẫn, sẽ chờ đến lúc được phục vụ mà không chuyển chỗ giữa các hàng.  Thực tế, khách hàng có thể:  Từ chối sắp hàng khi thấy hàng quá dài  Bỏ về khi thấy sắp hàng chờ quá lâu  Sự cần thiết của lý thuyết hàng đợi được yêu cầu bởi nhóm khách hàng này. Các đặc tính của dòng chờ GV. Huỳnh Đỗ Bảo Châu16  Chiều dài dòng chờ:  Hữu hạn  Vô hạn: là giả định sử dụng trong các mô hình hàng đợi  Sử dụng quy luật sắp hàng: FIFO. Các đặc tính của phương tiện phục vụ GV. Huỳnh Đỗ Bảo Châu17  Cấu hình hệ thống phục vụ  Số kênh phục vụ  HT một kênh  HT nhiều kênh  Số giai đoạn  HT một giai đoạn  HT nhiều giai đoạn 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 5 Các đặc tính của phương tiện phục vụ (tt) GV. Huỳnh Đỗ Bảo Châu18  Dạng thời gian phục vụ:  Không đổi: thời gian cần có để phục vụ cho mỗi khách hàng là như nhau.  Ngẫu nhiên (tương tự dạng lượng khách đến): được xem như tuân theo phân phối xác suất dạng số mũ âm μ ∶ số lượng khách TB được phục vụ 1 đvị thời gian P Thời gian phục vụ ൒ X đvị thời gian ൌ eିஜ୶ 3. Các mô hình bài toán hàng đợi MÔ HÌNH SẮP HÀNG 1 KÊNH GV. Huỳnh Đỗ Bảo Châu19 - Lượng khách hàng đến tuân theo phân phối Poisson - Thời gian phục vụ tuân theo Hàm mũ Các giả thiết của mô hình GV. Huỳnh Đỗ Bảo Châu20 1. Lượng khách đến được phục vụ theo nguyên tắc FIFO 2. Tất cả khách đều chờ, bất kể chiều dài hàng đợi, không có khách bỏ về hoặc từ chối sắp hàng. 3. KH đến sau không phụ thuộc KH đến trước, nhưng số lượng TB của KH đến không đổi theo thời gian. 4. Lượng KH đến tuân theo phân phối Poisson, được xem như vô hạn. 5. Thời gian phục vụ thay đổi và độc lập theo từng KH, nhưng thời gian TB cho mỗi KH xem như đã biết. 6. Thời gian phục vụ tuân theo phân phối Hàm mũ. 7. Tỷ lệ phục vụ TB > Tỷ lệ KH đến TB Các đặc tính vận hành chính của mô hình GV. Huỳnh Đỗ Bảo Châu21  Tỷ lệ sử dụng  Thời gian TB chờ đợi trong hệ thống và trong hàng đợi.  Số lượng khách TB trong hệ thống và trong hàng đợi.  Xác suất của số lượng KH khác nhau trong hệ thống. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 6 Các phương trình tính toán GV. Huỳnh Đỗ Bảo Châu22   = số lượng KH đến TB trong 1 đơn vị thời gian   = số lượng KH được phục vụ trong 1 đvị thời gian   >  1. L = Số lượng KH TB trong hệ thống = Số lượng KH trong hàng + Số lượng KH đang được phục vụ ܮ ൌ ߣ ߤ െ ߣ 2. W = Thời gian TB mà 1 KH phải mất trong hệ thống = Thời gian sắp hàng + Thời gian được phục vụ ܹ ൌ 1 ߤ െ ߣ ൌ ܮ ߣ GV. Huỳnh Đỗ Bảo Châu23 3. ࡸࢗ = Số lượng khách TB trong hàng đợi ܮ௤ ൌ ߣଶ ߤሺߤ െ ߣሻ 4. ࢃࢗ = Thời gian TB mà 1 KH phải mất để sắp hàng ௤ܹ ൌ ߣ ߤሺߤ െ ߣሻ 5. U = Hệ số sử dụng đối với hệ thống r = xác suất sử dụng thiết bị phục vụ ܷ ൌ ߣ ߤ 6. ࡼ૙ = Tỷ lệ thời gian không sử dụng = xác suất để hệ thống không có khách hàng trong hàng đợi phục vụ ଴ܲ ൌ 1 െ ߣ ߤ Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu24  Cửa hàng Fast Market  Số lượng khách hàng đến quầy thanh toán trung bình là 24 KH/giờ  Số lượng KH thanh toán được là 30KH/giờ Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu25  ଴ܲ ൌ 1 െ ఒ ఓ =  ܮ ൌ ఒ ఓିఒ =  ܮ௤ ൌ ఒమ ఓሺఓିఒሻ =  ܹ ൌ ఒ ఓିఒ ൌ ௅ ఒ =  ௤ܹ ൌ ఒ ఓሺఓିఒሻ =  ܷ ൌ ఒ ఓ 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 7 3. Các mô hình bài toán hàng đợi MÔ HÌNH SẮP HÀNG NHIỀU KÊNH GV. Huỳnh Đỗ Bảo Châu26 - Lượng khách hàng đến tuân theo phân phối Poisson - Thời gian phục vụ tuân theo Hàm mũ Các phương trình tính toán GV. Huỳnh Đỗ Bảo Châu27   = số lượng KH đến TB trong 1 đơn vị thời gian   = số lượng KH TB được phục vụ trong 1 đvị thời gian ở mỗi kênh phục vụ  c = số lượng kênh phục vụ  c = tỷ lệ phục vụ hiệu quả trung bình cho hệ thống,  c >  GV. Huỳnh Đỗ Bảo Châu28 ࡼ૙ = Tỷ lệ thời gian không sử dụng = xác suất để hệ thống không có khách hàng trong hàng đợi phục vụ ௢ܲ ൌ 1 ∑ 1݊! ߣ ߤ ௡ ௡ୀ௖ିଵ ௡ୀ଴ ൅ 1 ܿ! ߣ ߤ ௖ ܿߤ ܿߤ െ ߣ ࡼ࢔ = xác suất để hệ thống có n khách hàng trong hàng đợi phục vụ ௡ܲ ൌ 1 ܿ! ܿ௡ିଶ ߣ ߤ ௡ ଴ܲ ݊ếݑ ݊ ൐ ܿ ௡ܲ ൌ 1 ݊ ߣ ߤ ௡ ଴ܲ ݊ếݑ ݊ ൑ ܿ GV. Huỳnh Đỗ Bảo Châu29 L = Số lượng KH TB trong hệ thống = Số lượng KH trong hàng + Số lượng KH đang được phục vụ ܮ ൌ ߣߤ ߣ ߤ ௖ ܿ െ 1 ! ሺܿߤ െ ߣሻଶ ଴ܲ ൅ ߣ ߤ W = Thời gian TB mà 1 KH phải mất trong hệ thống = Thời gian sắp hàng + Thời gian được phục vụ ܹ ൌ ܮ ߣ ࡸࢗ = Số lượng khách TB trong hàng đợi ܮ௤ ൌ ܮ െ ߣ ߤ ࢃࢗ = Thời gian TB mà 1 KH phải mất để sắp hàng ௤ܹ ൌ ܹ െ 1 ߤ ൌ ܮ௤ ߣ 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 8 GV. Huỳnh Đỗ Bảo Châu30 ࡼ࢝= Xác suất tất cả các kênh phục vụ đều bận = Xác suất 1 khách hàng trong hàng đợi của hệ thống phải chờ được phục vụ. ௪ܲ ൌ 1 ܿ! ߣ ߤ ௖ ܿߤ ܿߤ െ ߣ ଴ܲ U = Hệ số sử dụng đối với hệ thống r = xác suất sử dụng thiết bị phục vụ ܷ ൌ ߣ ܿߤ Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu31  Bưu điện US  Số lượng khách hàng đến bưu điện để gửi hàng trung bình là 10 KH/giờ  Số lượng KH được phục vụ bởi 1 nhân viên bưu điện là 4 KH/giờ  Bưu điện duy trì 3 quầy phục vụ. Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu32 ௢ܲ ൌ ଵ ∑ భ ೙! ഊ ഋ ೙ ೙స೎షభ ೙సబ ା భ ೎! ഊ ഋ ೎ ೎ഋ ೎ഋషഊ = ܮ ൌ ఒఓ ഊ ഋ ೎ ௖ିଵ !ሺ௖ఓିఒሻమ ଴ܲ ൅ ఒ ఓ = ܮ௤ ൌ ܮ െ ఒ ఓ = ܹ ൌ ௅ ఒ = ௤ܹ ൌ ܹ െ ଵ ఓ ൌ ௅೜ ఒ = ܷ ൌ ఒ ௖ఓ = 3. Các mô hình bài toán hàng đợi MÔ HÌNH THỜI GIAN ĐỢI LÀ HẰNG SỐ GV. Huỳnh Đỗ Bảo Châu33 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 9 Các phương trình tính toán GV. Huỳnh Đỗ Bảo Châu34   = số lượng KH đến TB trong 1 đơn vị thời gian   = số lượng KH được phục vụ trong 1 đvị thời gian   >  1. ࡸࢗ = Chiều dài trung bình của hàng đợi ܮ௤ ൌ ߣଶ 2ߤሺߤ െ ߣሻ 2. ࢃࢗ = Thời gian TB phải mất để sắp hàng ௤ܹ ൌ ߣ 2ߤሺߤ െ ߣሻ GV. Huỳnh Đỗ Bảo Châu35 3. L = Số lượng KH TB trong hệ thống ܮ ൌ ܮ௤ ൅ ߣ ߤ 4. W = Thời gian TB mà 1 KH phải mất trong hệ thống ܹ ൌ ௤ܹ ൅ 1 ߤ 5. U = Hệ số sử dụng đối với hệ thống r ܷ ൌ ߣ ߤ 6. ࡼ૙ = Tỷ lệ thời gian không sử dụng ଴ܲ ൌ 1 െ ߣ ߤ 3. Các mô hình bài toán hàng đợi MÔ HÌNH LƯỢNG KHÁCH ĐẾN HỮU HẠN GV. Huỳnh Đỗ Bảo Châu36 Các giả thiết của mô hình GV. Huỳnh Đỗ Bảo Châu37  Chỉ có 1 kênh phục vụ  Lượng khách đến hữu hạn  Lượng khách hàng đến tuân theo phân phối Poisson  Thời gian phục vụ tuân theo Hàm mũ  Lượng khách đến được phục vụ theo nguyên tắc FIFO 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 10 Các phương trình tính toán GV. Huỳnh Đỗ Bảo Châu38   = số lượng KH đến TB trong 1 đơn vị thời gian   = số lượng KH được phục vụ trong 1 đvị thời gian  N = cỡ của lượng khách đến ࡼ૙ = Tỷ lệ thời gian không sử dụng = xác suất để hệ thống không có khách hàng trong hàng đợi phục vụ P଴ ൌ 1 ∑ ܰ! ܰ െ ݊ ! ߣ ߤ ௡ ே ௡ୀ଴ ࡼ࢔ = xác suất để hệ thống có n khách hàng trong hàng đợi phục vụ ௡ܲ ൌ ܰ! ܰ െ ݊ ! ߣ ߤ ௡ ଴ܲ , với n ൌ 1, 2, 3,N GV. Huỳnh Đỗ Bảo Châu39 ࡸࢗ = chiều dài trung bình của hàng đợi ܮ௤ ൌ ܰ െ ߣ ൅ ߤ ߣ 1 െ ଴ܲ L = lượng khách hàng trung bình trong hệ thống ܮ ൌ ܮ௤ ൅ ሺ1 െ ଴ܲሻ ࢃࢗ = Thời gian sắp hàng trung bình ௤ܹ ൌ ܮ௤ ሺܰ െ ܮሻߣ W = Thời gian chờ TB trong hệ thống ܹ ൌ ௤ܹ ൅ 1 ߤ 4. Ảnh hưởng qua lại của hoạt động và quyết định quản lý GV. Huỳnh Đỗ Bảo Châu40 Tình huống 1: Bổ sung nhân viên GV. Huỳnh Đỗ Bảo Châu41  Sử dụng Ví dụ minh họa tại slide 24  Bổ sung các dữ kiện:  Việc tăng thêm 1 nhân viên phục vụ sẽ làm tăng 150$/tuần cho chi phí của cửa hàng  Qua nghiên cứu, nhà quản lý thấy rằng cứ giảm đi 1 phút khách hàng phải chờ trong hàng đợi, cửa hàng sẽ tránh được sự thất thoát doanh số là 75$/tuần  Nếu tăng thêm 1 nhân viên mới thì tỷ lệ khách hàng được phục vụ trong sẽ tăng lên là 40 KH/giờ 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 11 Tình huống 1 (tt) GV. Huỳnh Đỗ Bảo Châu42 Bài toán được tính lại:  ଴ܲ ൌ 1 െ ఒ ఓ =  ܮ ൌ ఒ ఓିఒ =  ܮ௤ ൌ ఒమ ఓሺఓିఒሻ =  ܹ ൌ ఒ ఓିఒ ൌ ௅ ఒ =  ௤ܹ ൌ ఒ ఓሺఓିఒሻ =  ܷ ൌ ఒ ఓ Nhận xét GV. Huỳnh Đỗ Bảo Châu43  Số lượng khách hàng đến quầy là 24 KH/giờ  Mỗi 2.5 phút có 1 KH đến  Với bài toán trước khi tăng 1 nhân viên:  KH phải chờ _____ phút trong quầy để được thanh toán  KH tốn tất cả ______ phút để xếp hàng & thanh toán  Với bài toán sau khi tăng 1 nhân viên:  KH phải chờ _____ phút trong quầy để được thanh toán  Tiết kiệm _____ phút  Tiết kiệm ___* 75$ = _____$/tuần  So với chi phí trả cho nhân viên 150$/tuần, cửa hàng được lợi:  ________$ - 150$ = _______ $/tuần  Với sự tiết kiệm chi phí này, giải pháp thêm 1 nhân viên sẽ khả thi hơn trước đó. Tình huống 2: Bổ sung quầy tính tiền GV. Huỳnh Đỗ Bảo Châu44  Sử dụng Ví dụ minh họa tại slide 24  Bổ sung các dữ kiện:  Nhà quản lý sẽ đầu tư thêm 1 quầy tính tiền mới với chi phí dự án này là 6000$.  Tốn thêm 200$/tuần cho 1 người tính tiền.  Qua nghiên cứu, nhà quản lý thấy rằng cứ giảm đi 1 phút khách hàng phải chờ trong hàng đợi, cửa hàng sẽ tránh được sự thất thoát doanh số là 75$/tuần  Giả định lượng khách xếp hàng sẽ chia đều cho 2 quầy.  Các tỷ lệ phục vụ mới là:  Số lượng khách hàng đến quầy thanh toán trung bình là 12 KH/giờ  Số lượng KH thanh toán được là 30KH/giờ Tình huống 2 (tt) GV. Huỳnh Đỗ Bảo Châu45 Bài toán được tính lại:  ଴ܲ ൌ 1 െ ఒ ఓ =  ܮ ൌ ఒ ఓିఒ =  ܮ௤ ൌ ఒమ ఓሺఓିఒሻ =  ܹ ൌ ఒ ఓିఒ ൌ ௅ ఒ =  ௤ܹ ൌ ఒ ఓሺఓିఒሻ =  ܷ ൌ ఒ ఓ 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 12 Nhận xét GV. Huỳnh Đỗ Bảo Châu46  Với bài toán trước khi tăng 1 quầy tính tiền:  KH phải chờ _____ phút trong quầy để được thanh toán  KH tốn tất cả ______ phút để xếp hàng & thanh toán  Với bài toán sau khi tăng 1 quầy tính tiền:  KH phải chờ _____ phút trong quầy để được thanh toán  Tiết kiệm _____ phút  Tiết kiệm ___* 75$ = _____$/tuần  So với chi phí trả cho thủ quỹ 200$/tuần, cửa hàng được lợi:  ________$ - 200$ = _______ $/tuần  Số tiền tiết kiệm này sẽ dùng để bù đắp cho chi phí đầu tư ban đầu  ଺଴଴଴$ _____$ ൌ ______ݐݑầ݊  So với tình huống 1, sau khi đã bù đắp chi phí đầu tư dự án, tình huống 2 giúp tiết kiệm nhiều hơn ______$ Tóm tắt giữa các tính huống GV. Huỳnh Đỗ Bảo Châu47 HẾT CHƯƠNG 7 48 GV. Huỳnh Đỗ Bảo Châu