Mô hình hóa bài toán sắp lịch dạng flowshop bằng đại số maxplus

Trong bài toán miêu tả phía trên, ta có bốn công việc cần hoàn thành (sản xuất bốn loại dầu gội) trên một dây chuyền gồm ba máy (ba bước sản xuất). Nhiệm vụ của xưởng sản xuất là sắp xếp thứ tự các sản phẩm để thời gian hoàn thành cuối cùng là nhanh nhất, hoăc để tổng thời gian hoàn thành tất cả sản phẩm là ngắn nhấn. Khi các nhóm người đẹp có vai trò khác nhau thì các sản phẩm yêu thích của các nhóm sẽ có trọng số khác nhau.
Nội dung trích xuất từ tài liệu:
Mô hình hóa bài toán sắp lịch dạng flowshop bằng đại số maxplus MÔ HÌNH HÓA BÀI TOÁN SẮP LỊCH DẠNG FLOWSHOP BẰNG ĐẠI SỐ MAXPLUS Võ Nhật Vinh (Đại học Fran¸cois-Rabelais, Tours, Pháp)Chuyện kể rằng ở một vương quốc nọ, nhà vua có rất nhiều cung tần mỹ nữ và họ đều để tócdài. Để chăm sóc cho mái tóc dài của các người đẹp, nhà vua ra lệnh cho một xưởng sản xuấtdầu gội tin cậy sản xuất các loại sản phẩm khác nhau để đáp ứng nhu cầu của các mỹ nữ này.Hiện tại, nhu cầu của các người đẹp là bốn loại dầu gội mang hương bưởi, hương sen, hươnglài và hương chanh. Trong xưởng sản xuất, ba giai đoạn cần được lưu ý theo thứ tự là tách mùihương, pha trộn mùi và đóng chai. Mỗi loại dầu gội có thời gian đặc trưng để tách mùi hương,để pha trộn mùi và để đóng chai khác nhau. Có thời điểm, xưởng sản xuất quan tâm đến thứtự các loại dầu gội cần được sản xuất để có thể hoàn thành tất cả các đơn hàng của các ngườiđẹp trong thời gian sớm nhất. Có thời điểm, xưởng sản xuất cân nhắc thứ tự các loại dầu gội đểtổng thời gian chờ đợi của các quý bà là ít nhất. Cũng có lúc, xưởng sản xuất phải lưu ý đến vaitrò khác nhau của các nhóm người đẹp. Vì vậy, xưởng sản xuất phải suy nghĩ tìm lời giải tối ưucho từng trường hợp.Trong bài toán miêu tả phía trên, ta có bốn công việc cần hoàn thành (sản xuất bốn loại dầugội) trên một dây chuyền gồm ba máy (ba bước sản xuất). Nhiệm vụ của xưởng sản xuất là sắpxếp thứ tự các sản phẩm để thời gian hoàn thành cuối cùng là nhanh nhất, hoăc để tổng thờigian hoàn thành tất cả sản phẩm là ngắn nhấn. Khi các nhóm người đẹp có vai trò khác nhauthì các sản phẩm yêu thích của các nhóm sẽ có trọng số khác nhau.1. Giới thiệu chungCâu hỏi về mối liên hệ giữa các ngành Toán Học, Tin Học và Kinh Doanh đã thúc đẩy tôi nghiêncứu sâu hơn về lý thuyết sắp lịch (scheduling theory). Thực tế, bài toán sắp lịch được nghiêncứu trong các khoa Tin Học bởi vì nó cần các kỹ thuật Tin Học cũng như các tài nguyên máytính để tìm ra các kết quả số. Tuy vậy, các bài toán sắp lịch lại là những trường hợp cụ thể củacác bài toán tối ưu hóa tổ hợp (Combinatorial Optimisation) mang đầy bản chất Toán Học. Vìthế mà lý thuyết sắp lịch cũng được nghiên cứu trong các đơn vị nghiên cứu Toán Học. Ngoàira, sắp lịch nói riêng và vận trù học (Operations Research) nói chung được giảng dạy và nghiêncứu trong các trường về kinh doanh tại Anh và Bắc Mỹ. Thực vậy, trong bài viết của mình Shah,tác giả đã kết luận rằng sắp lịch quan trọng bởi hai lý do chính. Lý do thứ nhất liên quan đến cácrủi ro kinh tế quan trọng (ví dụ sự bồi thường do chậm trễ tiến độ) nếu như một lịch trình tồi tệđược thực hiện. Lý do thứ hai liên quan đến sự nắm bắt các cơ hội (trong kinh doanh) nếu nhưchúng ta có một kỹ thuật sắp lịch hiệu quả. Vì lẽ đó, ta có thể nói rằng sắp lịch có mối quan hệmật thiết với lĩnh vực kinh doanh, thương mại. Nói một cách khác, sắp lịch không chỉ đơn thuầnlà một ngành khoa học lý thuyết (Toán Học) mà còn là một ngành khoa học ứng dụng (KinhDoanh). Trong khuôn khổ bài viết này, chúng ta sẽ quan tâm đến một dạng bài toán cụ thể trong 47 Tạp chí Epsilon, Số 04, 08/2015lý thuyết sắp lịch và có liên quan mật thiết với sản xuất theo dây chuyền: Bài toán sắp lịch dạngflowshop.Từ những năm 1950; các bài toán dạng flowshop đã không ngừng tiến triển và thu hút ngày càngnhiều sự quan tâm của các nhà nghiên cứu bởi cả những lợi ích cũng như độ khó của chúng.Thực tế, các bài toán dạng flowshop không chỉ đa dạng về các loại điều kiện ràng buộc mà cònvề các mục tiêu tối ưu. Chính sự đa dạng này khiến các bài toán dạng flowshop rất gần với cácbài toán thực tế. Dù vậy, ta quan tâm trong bài viết này một phương pháp tiếp cận có thể ápdụng được cho một lớp bài toán thay vì từng bài toán riêng lẻ.Trong luận án của mình, Lenté đã giới thiệu đại số MaxPlus để mô hình hóa một số bài toánsắp lịch dạng flowshop. Phương pháp tiếp cận này đã được sử dụng để làm xuất hiện các quanhệ tuyến tính trong các bài toán 2 máy (bài toán cơ bản, bài toán với ràng buộc độ trễ cố địnhcùng thời gian chuẩn bị và tháo dỡ, bài toán không có độ trễ) cũng như trong các bài toán mmáy với ràng buộc độ trễ cố định cùng thời gian chuẩn bị và tháo dỡ. Lợi ích của MaxPlus làđơn giản hóa các ký hiệu để dễ dàng làm nổi bật tính chất của các phép tính. Ngoài ra, MaxPluscòn cho phép ta biến đổi bài toán dạng flowshop thành bài toán ma trận. Nói một cách khác,chúng ta có thể thực hiện các phép tính và biến đổi trên ma trận.Trong bài viết này, chúng ta sẽ mô hình hóa một lớp bài toán sắp lịch bằng cách sử dụng đạisố MaxPlus. Thật ra, chúng ta nhận thấy rằng độ trễ giữa các tác vụ (operations) thường đượcxét đến trong các bài toán dạng flowshop. Các độ trễ này có thể được gây nên bởi thời gian sấykhô, thời gian làm nguội hoặc thờ ...