Luận văn thạc sĩ về ứng dụng khoa học máy tính trong quản lý cửa hàng thức ăn nhanh

• Tác giả: Nguyễn Kim Ngân
• Người hướng dẫn: TS. Huỳnh Tường Nguyên
• Trường học: Đại học Bách Khoa - ĐHQG - HCM
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Hỗ trợ quản lý cửa hàng thức ăn nhanh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thành phố Hồ Chí Minh

• LỜI CÁM ƠN
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Lý do chọn đề tài
• 1.2. Mục đích nghiên cứu
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Cấu trúc của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VỀ BÀI TOÁN LẬP LỊCH
• 2.1. Mô tả bài toán
• 2.2. Một số khái niệm liên quan đến công việc
• 2.3. Một số khái niệm liên quan đến kết quả lập lịch
• 2.4. Phân loại bài toán lập lịch
• 2.5. Đặc điểm công việc
• 2.6. Môi trường máy
• 3. CHƯƠNG 3: CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 3.1. Bài toán Og||Cmax
• 3.1.1. Mô tả bài toán
• 3.1.2. Giải thuật đề xuất
• 3.1.3. Giải thuật xấp xỉ
• 4. CHƯƠNG 4: ĐẶC TẢ VÀ MÔ HÌNH HÓA BÀI TOÁN
• 4.1. Đặc tả bài toán
• 4.2. Định dạng nhập - xuất
• 4.3. Mô hình hóa bài toán
• 4.3.1. Hàm mục tiêu (Objective function)
• 5. CHƯƠNG 5: ĐỀ XUẤT GIẢI THUẬT CHO BÀI TOÁN
• 5.1. Sắp xếp các máy
• 5.2. Phân loại khách hàng dựa theo yêu cầu
• 5.3. Cấu trúc dữ liệu
• 5.3.1. Đối tượng Machine
• 5.3.2. Đối tượng Customer
• 5.3.3. Danh sách các máy
• 5.3.4. Danh sách khách hàng
• 5.3.5. Mảng chứa các danh sách khách hàng
• 5.4. Giải thuật MTF (MaxTimeFirst)
• 5.5. Giải thuật MSF (MaxSumFirst)
• 5.6. Ví dụ minh họa
• 6. CHƯƠNG 6: ĐÁNH GIÁ THỰC NGHIỆM
• 6.1. Môi trường thực nghiệm
• 6.2. Dữ liệu thử nghiệm sinh ra do mô phỏng
• 6.3. Cách đánh giá kết quả
• 6.4. Kết quả thực nghiệm
• 7. CHƯƠNG 7: TỔNG KẾT
• 7.1. Kết luận
• 7.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO

I. Giới thiệu

Bài viết này tập trung vào việc hỗ trợ quản lý cửa hàng thức ăn nhanh thông qua ứng dụng của khoa học máy tính. Trong bối cảnh dịch vụ ăn uống ngày càng phát triển, việc tối ưu hóa quy trình phục vụ khách hàng trở nên cần thiết. Quản lý cửa hàng không chỉ đơn thuần là việc điều hành mà còn bao gồm việc sử dụng công nghệ để nâng cao hiệu quả hoạt động. Mục tiêu chính của nghiên cứu là xây dựng một mô hình toán học cho bài toán lập lịch trong cửa hàng thức ăn nhanh, từ đó đề xuất các giải pháp công nghệ nhằm cải thiện quy trình phục vụ và giảm thiểu thời gian chờ đợi của khách hàng.

1.1 Lý do chọn đề tài

Lập lịch là một phần quan trọng trong quản lý cửa hàng thức ăn nhanh. Với sự gia tăng nhu cầu tiêu dùng, các cửa hàng cần phải tối ưu hóa quy trình phục vụ để đáp ứng nhanh chóng và hiệu quả. Việc áp dụng công nghệ thông tin vào quản lý giúp các nhà quản lý có thể đưa ra quyết định chính xác hơn, từ đó nâng cao trải nghiệm của khách hàng. Nghiên cứu này sẽ giúp các nhà quản lý hiểu rõ hơn về cách thức lập lịch và ứng dụng của nó trong thực tiễn.

II. Cơ sở lý thuyết về bài toán lập lịch

Chương này trình bày các khái niệm cơ bản về lập lịch trong quản lý cửa hàng thức ăn nhanh. Lập lịch có thể được định nghĩa là quá trình phân bổ thời gian cho các công việc trên các máy móc nhằm tối ưu hóa thời gian hoàn thành. Các khái niệm như thời gian xử lý, deadline và trọng số sẽ được phân tích. Việc hiểu rõ các khái niệm này là cần thiết để xây dựng mô hình toán học cho bài toán lập lịch. Các bài toán lập lịch có thể được phân loại thành nhiều dạng khác nhau, từ các máy chuyên dụng đến các máy song song, mỗi loại đều có những đặc điểm và yêu cầu riêng.

2.1 Mô tả bài toán

Bài toán lập lịch trong cửa hàng thức ăn nhanh thường liên quan đến việc phân bổ công việc cho các máy chế biến thức ăn. Mỗi công việc có thể có thời gian xử lý khác nhau và cần được hoàn thành trong một khoảng thời gian nhất định. Mục tiêu là tối thiểu hóa thời gian phục vụ khách hàng, từ đó nâng cao sự hài lòng của họ. Việc áp dụng các giải thuật tối ưu sẽ giúp giảm thiểu thời gian chờ đợi và nâng cao hiệu quả hoạt động của cửa hàng.

III. Công trình nghiên cứu liên quan

Nghiên cứu trước đây đã chỉ ra rằng việc áp dụng khoa học máy tính vào quản lý cửa hàng có thể mang lại nhiều lợi ích. Các công trình nghiên cứu đã phát triển nhiều mô hình và giải thuật khác nhau để giải quyết bài toán lập lịch. Những nghiên cứu này không chỉ giúp cải thiện quy trình phục vụ mà còn cung cấp cái nhìn sâu sắc về cách thức hoạt động của các cửa hàng thức ăn nhanh. Việc phân tích các công trình này sẽ giúp xác định các phương pháp hiệu quả nhất cho việc lập lịch trong cửa hàng.

3.1 Phân tích các giải thuật

Các giải thuật được đề xuất trong các nghiên cứu trước đây bao gồm các phương pháp tối ưu hóa như Gurobi Solver và các giải thuật heuristic. Những giải thuật này đã được áp dụng thành công trong nhiều tình huống thực tế, giúp giảm thiểu thời gian phục vụ và nâng cao hiệu quả hoạt động. Việc so sánh hiệu quả giữa các giải thuật sẽ cung cấp thông tin quý giá cho các nhà quản lý trong việc lựa chọn phương pháp phù hợp nhất cho cửa hàng của họ.

IV. Đề xuất giải pháp công nghệ

Dựa trên các phân tích và nghiên cứu trước đây, bài viết đề xuất một số giải pháp công nghệ nhằm hỗ trợ quản lý cửa hàng thức ăn nhanh. Các giải pháp này bao gồm việc phát triển phần mềm quản lý tích hợp, cho phép theo dõi và tối ưu hóa quy trình phục vụ. Việc sử dụng ứng dụng di động cũng sẽ giúp khách hàng đặt hàng và thanh toán nhanh chóng, từ đó giảm thiểu thời gian chờ đợi. Những giải pháp này không chỉ giúp nâng cao hiệu quả hoạt động mà còn cải thiện trải nghiệm của khách hàng.

4.1 Phát triển phần mềm quản lý

Phần mềm quản lý sẽ giúp các nhà quản lý theo dõi tình hình hoạt động của cửa hàng theo thời gian thực. Các tính năng như lập lịch tự động, phân tích dữ liệu và báo cáo sẽ giúp tối ưu hóa quy trình phục vụ. Việc áp dụng công nghệ này sẽ giúp giảm thiểu sai sót và nâng cao hiệu quả làm việc của nhân viên, từ đó cải thiện chất lượng dịch vụ.

Tổng quan nghiên cứu

Trong bối cảnh ngành dịch vụ ăn uống phát triển mạnh mẽ, đặc biệt là các cửa hàng thức ăn nhanh, việc tối ưu hóa quy trình vận hành nhằm nâng cao chất lượng phục vụ và giảm thiểu thời gian chờ đợi của khách hàng trở thành một vấn đề cấp thiết. Theo ước tính, các chuỗi cửa hàng thức ăn nhanh như McDonald’s, KFC, Pizza Hut đã đầu tư mạnh mẽ vào thị trường Việt Nam, tạo ra áp lực cạnh tranh lớn về hiệu quả quản lý và vận hành. Luận văn tập trung nghiên cứu bài toán lập lịch cho cửa hàng thức ăn nhanh với mô hình các máy chế biến chuyên dụng song song và một nhân viên phục vụ duy nhất (single server), trong đó thời gian thực thi của các máy là cố định. Mục tiêu chính là tối thiểu hóa thời gian hoàn thành toàn bộ yêu cầu của khách hàng (makespan), từ đó nâng cao hiệu quả phục vụ và sự hài lòng của khách hàng.

Phạm vi nghiên cứu được giới hạn trong khoảng thời gian từ năm 2014 đến 2015, tại các cửa hàng thức ăn nhanh có cấu trúc tương tự mô hình nghiên cứu, với dữ liệu đầu vào được mô phỏng dựa trên phân phối Poisson cho thời gian xử lý và số lượng yêu cầu. Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp các giải pháp lập lịch tối ưu hoặc gần tối ưu, giúp nhà quản lý đưa ra quyết định điều hành hiệu quả, giảm thiểu thời gian phục vụ và tăng năng suất hoạt động của cửa hàng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết lập lịch (scheduling theory), trong đó bài toán được mô hình hóa theo dạng bài toán lập lịch trên các máy chuyên dụng song song với một server duy nhất. Các khái niệm chính bao gồm:

• Máy chuyên dụng song song (Parallel Dedicated Machines): Mỗi máy chỉ thực hiện được một loại công việc nhất định, hoạt động song song nhưng độc lập.
• Server đơn (Single Server): Một nhân viên phục vụ chịu trách nhiệm khởi động máy và cung cấp nguyên liệu, chỉ có thể phục vụ một máy tại một thời điểm.
• Makespan (Cmax): Thời gian hoàn thành muộn nhất trong toàn bộ hệ thống, là hàm mục tiêu cần tối thiểu hóa.
• Giải thuật heuristic: Các phương pháp xấp xỉ nhằm tìm lời giải khả thi trong thời gian ngắn, bao gồm giải thuật MaxTimeFirst (MTF) và MaxSumFirst (MSF).

Ngoài ra, luận văn tham khảo các mô hình toán học và thuật toán đã được phát triển trong các công trình nghiên cứu về bài toán lập lịch Open Shop, Flow Shop và các bài toán lập lịch có server đơn, đặc biệt là các công trình của P. Brucker và Celia A. Strusevich.

Phương pháp nghiên cứu

Nguồn dữ liệu được tạo ra bằng phương pháp mô phỏng ngẫu nhiên dựa trên phân phối Poisson cho các tham số thời gian xử lý máy, công suất máy và số lượng yêu cầu của khách hàng. Cỡ mẫu bao gồm các bộ dữ liệu với số lượng máy từ 2 đến 5 và số lượng khách hàng từ 10 đến 200, mỗi trường hợp được thử nghiệm 10 lần để đảm bảo tính đại diện.

Phương pháp phân tích bao gồm:

• Xây dựng mô hình toán học dạng Mixed Integer Linear Programming (MILP) cho bài toán lập lịch.
• Giải bài toán bằng phần mềm Gurobi Solver để tìm nghiệm tối ưu hoặc gần tối ưu.
• Đề xuất và triển khai hai giải thuật heuristic MTF và MSF nhằm giảm thời gian tính toán.
• So sánh kết quả về giá trị mục tiêu và thời gian thực thi giữa các giải thuật và Gurobi Solver.
• Timeline nghiên cứu kéo dài từ tháng 7/2014 đến tháng 5/2015, bao gồm các giai đoạn xây dựng mô hình, phát triển giải thuật, thực nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của mô hình toán học và Gurobi Solver:
   Gurobi Solver có thể tìm ra nghiệm tối ưu cho các trường hợp nhỏ với số máy 2-3 và số khách hàng dưới 20 trong thời gian dưới 900 giây. Tuy nhiên, khi số máy tăng lên 4-5 hoặc số khách hàng vượt quá 20, thời gian giải quyết tăng theo hàm mũ, nhiều trường hợp không tìm được nghiệm tối ưu trong thời gian giới hạn.

2. Hiệu suất giải thuật MTF và MSF:
   Hai giải thuật heuristic MTF và MSF luôn cho ra lời giải khả thi trong mọi trường hợp thử nghiệm. Trong tổng số 240 trường hợp, MTF cho kết quả tốt hơn MSF trong khoảng 79% trường hợp, với 51% kết quả của MTF đạt bằng hoặc gần bằng chặn dưới của hàm mục tiêu, trong khi MSF đạt tỷ lệ 33%.

3. So sánh giá trị mục tiêu:
   Giá trị nghiệm trung bình của MTF và MSF gần với giá trị tối ưu hoặc chặn dưới, đặc biệt với số máy từ 2 đến 3 và số khách hàng dưới 50. Khi số máy và số khách hàng tăng, độ lệch so với nghiệm tối ưu có xu hướng tăng nhẹ nhưng vẫn nằm trong giới hạn chấp nhận được.

4. Thời gian thực thi:
   Thời gian thực thi của MTF và MSF thấp hơn đáng kể so với Gurobi Solver, đặc biệt với các trường hợp lớn. MTF và MSF có thời gian thực thi trung bình chỉ tính bằng giây, trong khi Gurobi Solver có thể mất hàng trăm đến hàng nghìn giây hoặc không hoàn thành.

Thảo luận kết quả

Nguyên nhân chính khiến Gurobi Solver mất nhiều thời gian là do tính phức tạp của bài toán lập lịch với nhiều ràng buộc và biến quyết định nhị phân. Giải thuật heuristic MTF ưu tiên sắp xếp máy theo thời gian thực thi giảm dần, giúp máy có thời gian xử lý lớn được ưu tiên hoạt động trước, giảm thiểu thời gian rỗi và makespan. MSF ưu tiên theo tổng lượng yêu cầu, phù hợp với các trường hợp khách hàng có nhu cầu tập trung vào một số máy nhất định.

So với các nghiên cứu trước đây về bài toán lập lịch máy chuyên dụng song song với server đơn, kết quả của luận văn cho thấy giải thuật MTF có hiệu quả vượt trội trong việc cân bằng giữa chất lượng lời giải và thời gian thực thi. Các biểu đồ so sánh giá trị nghiệm trung bình và thời gian thực thi minh họa rõ ràng sự ưu việt của MTF trong hầu hết các trường hợp.

Ý nghĩa của kết quả là cung cấp cho nhà quản lý cửa hàng thức ăn nhanh một công cụ hỗ trợ ra quyết định nhanh chóng và hiệu quả, đặc biệt trong điều kiện biến động số lượng khách hàng và yêu cầu phục vụ đa dạng.

Đề xuất và khuyến nghị

1. Áp dụng giải thuật MTF trong hệ thống quản lý cửa hàng:
   Triển khai giải thuật MTF vào phần mềm quản lý vận hành để tự động lập lịch cho các máy chế biến, giúp giảm thiểu thời gian phục vụ và tăng năng suất. Thời gian thực hiện: 3-6 tháng; Chủ thể: Bộ phận công nghệ thông tin và quản lý vận hành.

2. Phát triển giao diện trực quan cho nhà quản lý:
   Xây dựng giao diện hiển thị giản đồ Gantt và báo cáo thời gian phục vụ theo từng máy, giúp nhà quản lý dễ dàng theo dõi và điều chỉnh lịch trình khi cần. Thời gian thực hiện: 2-4 tháng; Chủ thể: Bộ phận phát triển phần mềm.

3. Mở rộng mô hình cho nhiều server và đa loại máy:
   Nghiên cứu và phát triển mô hình lập lịch cho trường hợp nhiều nhân viên phục vụ và các loại máy đa chức năng, nhằm phù hợp với quy mô cửa hàng lớn hơn. Thời gian thực hiện: 6-12 tháng; Chủ thể: Nhóm nghiên cứu và phát triển sản phẩm.

4. Đào tạo nhân viên và nhà quản lý:
   Tổ chức các khóa đào tạo về ứng dụng công nghệ lập lịch và quản lý thời gian phục vụ, nâng cao nhận thức và kỹ năng vận hành hiệu quả. Thời gian thực hiện: liên tục; Chủ thể: Phòng nhân sự và đào tạo.

Đối tượng nên tham khảo luận văn

1. Nhà quản lý cửa hàng thức ăn nhanh:
   Giúp hiểu rõ các phương pháp tối ưu hóa lịch trình vận hành, từ đó nâng cao hiệu quả phục vụ và giảm thiểu thời gian chờ đợi của khách hàng.

2. Chuyên gia phát triển phần mềm quản lý nhà hàng:
   Cung cấp cơ sở lý thuyết và thuật toán để tích hợp vào các hệ thống quản lý, hỗ trợ tự động hóa lập lịch và điều phối nguồn lực.

3. Nhà nghiên cứu trong lĩnh vực khoa học máy tính và quản lý sản xuất:
   Tham khảo mô hình toán học và giải thuật heuristic áp dụng cho bài toán lập lịch phức tạp, mở rộng nghiên cứu trong các lĩnh vực liên quan.

4. Sinh viên và học viên cao học chuyên ngành khoa học máy tính, kỹ thuật công nghiệp:
   Học tập phương pháp xây dựng mô hình, phát triển giải thuật và đánh giá thực nghiệm trong bài toán thực tế, nâng cao kỹ năng nghiên cứu khoa học.

Câu hỏi thường gặp

1. Bài toán lập lịch trong cửa hàng thức ăn nhanh có điểm gì đặc biệt?
   Bài toán kết hợp các máy chuyên dụng song song với một nhân viên phục vụ duy nhất, thời gian xử lý cố định, yêu cầu tối thiểu hóa thời gian hoàn thành tổng thể, khác với các bài toán lập lịch truyền thống do có ràng buộc server đơn.

2. Giải thuật MTF và MSF khác nhau như thế nào?
   MTF ưu tiên sắp xếp máy theo thời gian thực thi giảm dần, còn MSF ưu tiên theo tổng lượng yêu cầu của khách hàng trên từng máy. MTF thường cho kết quả tốt hơn về giá trị mục tiêu và thời gian thực thi.

3. Tại sao không chỉ sử dụng Gurobi Solver để giải bài toán?
   Gurobi Solver hiệu quả với các bài toán nhỏ nhưng khi số lượng máy và khách hàng tăng lên, thời gian giải quyết tăng rất nhanh, không phù hợp cho ứng dụng thực tế cần phản hồi nhanh.

4. Làm thế nào để áp dụng kết quả nghiên cứu vào thực tế?
   Có thể tích hợp giải thuật MTF vào phần mềm quản lý vận hành cửa hàng, kết hợp với giao diện trực quan để nhà quản lý dễ dàng theo dõi và điều chỉnh lịch trình.

5. Nghiên cứu có thể mở rộng như thế nào trong tương lai?
   Mở rộng mô hình cho nhiều nhân viên phục vụ, đa loại máy, hoặc tích hợp các yếu tố ngẫu nhiên như thời gian xử lý biến đổi, yêu cầu khách hàng thay đổi theo thời gian để phù hợp hơn với thực tế.

Kết luận

• Luận văn đã xây dựng thành công mô hình toán học và đề xuất hai giải thuật heuristic MTF và MSF cho bài toán lập lịch cửa hàng thức ăn nhanh với máy chuyên dụng song song và một server duy nhất.
• Giải thuật MTF thể hiện hiệu quả vượt trội về giá trị mục tiêu và thời gian thực thi so với MSF và Gurobi Solver trong hầu hết các trường hợp thử nghiệm.
• Kết quả thực nghiệm trên 240 bộ dữ liệu mô phỏng cho thấy MTF đạt tỷ lệ gần bằng chặn dưới hàm mục tiêu lên đến 51%, đồng thời thời gian thực thi rất nhanh.
• Nghiên cứu cung cấp công cụ hỗ trợ nhà quản lý ra quyết định điều hành hiệu quả, giảm thiểu thời gian phục vụ và nâng cao sự hài lòng khách hàng.
• Các bước tiếp theo bao gồm triển khai giải thuật vào phần mềm quản lý thực tế, mở rộng mô hình cho các trường hợp phức tạp hơn và đào tạo nhân viên vận hành.

Hành động ngay: Các nhà quản lý và chuyên gia công nghệ nên xem xét áp dụng giải thuật MTF để nâng cao hiệu quả vận hành cửa hàng thức ăn nhanh, đồng thời tiếp tục nghiên cứu mở rộng để đáp ứng nhu cầu thực tế ngày càng đa dạng.