- 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). - Thực tế, bài toán sắp lịch được nghiên cứ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áy tí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ủa cá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. - 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. - lý 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ạng flowshop.. - các bài toán dạng flowshop đã không ngừng tiến triển và thu hút ngày càng nhiề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òn về 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ác bà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ể áp dụ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án sắ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 quan hệ 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ố định cù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 m máy với ràng buộc độ trễ cố định cùng thời gian chuẩn bị và tháo dỡ. - Ngoài ra, MaxPlus còn cho phép ta biến đổi bài toán dạng flowshop thành bài toá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 đại số MaxPlus. - Thật ra, chúng ta nhận thấy rằng độ trễ giữa các tác vụ (operations) thường được xét đến trong các bài toán dạng flowshop. - Vì vậy, chúng ta hy vọng có thể mô hình hóa một lớp bài toán dạng flowshop với các điều kiện ràng buộc liên quan đến độ trễ.. - Sau phần giới thiệu chung này, chúng ta sẽ nhắc lại định nghĩa và các quy ước của bài toán dạng flowshop, ký hiệu và các loại ràng buộc được nghiên cứu đến trong bài viết. - Cuối cùng, với mỗi bài toán cụ thể, ma trận công việc (job associated matrix) sẽ được thiết lập và từ đó, một bài toán trọng tâm (hàm chứa nhiều bài toán khác) sẽ được chỉ ra.. - Bài toán dạng flowshop. - Một bài toán dạng flowshop m máy là một bài toán sắp xếp thứ tự cho n-công việc (job) khi chúng lần lượt được xử lý trên m máy (machine). - Thứ tự các tác vụ của mỗi công việc là giống nhau. - Ngoài ra, chúng ta xem xét bài toán với thứ tự các công việc được xử lý trên mỗi máy là như nhau. - Hình dưới đây thể hiện một bài toán dạng flowshop có 2 máy và 3 công việc.. - Hình 4.1: Bài toán dạng flowshop 2 máy.. - Ở đây ta sử dụng loại ký hiệu được đề xuất bởi Graham và các đồng tác giả để mô tả một bài toán sắp lịch. - Bài viết này đề cập đến các bài toán dạng flowshop nên trường ˛ chứa ký hiệu F m . - n W Số lượng công việc cần sắp lịch.. - J n g W Tập hợp các công việc cần sắp lịch.. - M m g W Tập hợp các máy để xử lý các công việc (quy ước các máy được sắp theo thứ tự của quy trình sản xuất).. - J i W Công việc i .i D 1. - O ij W Tác vụ j của công việc J i : p ij W Thời gian xử lý của tác vụ O ij : ı j W Thời điểm nhàn rỗi của máy M j. - W Tập hợp có thứ tự các công việc . - W Thời điểm hoàn thành công việc J i trên máy M m. - C .i / W Thời điểm hoàn thành công việc thứ i của tập có thứ tự (trên máy cuối cùng). - C i m g W Véc-tơ các thời điểm hoàn thành của công việc J i trên các máy.. - D .i / W Thời điểm giải phóng máy M m khỏi công việc thứ i của tập có thứ tự. - D i m g W Véc-tơ các thời điểm giải phóng các máy khỏi công việc J i. - perm được sử dụng trong bài toán dạng flowshop và thể hiện thứ tự (một hoán vị) các công việc giống nhau trên tất cả các máy.. - Phép tính ma trận. - Cho A là một ma trận kích thước m p. - cho B là một ma trận kích thước p n;. - Ứng dụng của đại số MaxPlus trong bài toán sắp lịch. - Tuy nhiên, chúng ta cũng có thể tham khảo một vài nghiên cứu có liên quan của Giffler đối với bài toán sắp lịch dự án, của Hanen và Munier đối với các bài toán máy song song có chu kỳ, của Gaubert và Mairesses, và của Cohen cùng các đồng tác giả. - Cohen đối với bài toán dạng flowshop có chu kỳ, của Gaubert và của Houssin đối với các bài toán dạng jobshop có chu kỳ.. - Trong luận án của mình, Lenté đã chứng minh rằng các bài toán dạng flowshop m máy với ràng buộc hoán vị .perm/ có thể được mô hình hóa bằng đại số MaxPlus. - Cụ thể hơn, mỗi công việc J i có thể được đặc trưng hoàn toàn bằng một ma trận T i tương ứng. - Ma trận T i này hoàn toàn đặc trưng được các ràng buộc của bài toán. - Trong Bouquard and Lenté, các tác giả cũng sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop 2 máy với độ trễ tối đa và tối thiểu .F 2 j permI min max /delay j C max. - đại số này lại một lần nữa cho phép ta chứng minh sự tương đương giữa hai bài toán: Bài toán với ràng buộc độ trễ (tối đa và tối thiểu) F m j permI min max /delay j và bài toán với ràng buộc gồm độ trễ (tối đa và tối thiểu) và thời gian chuẩn bị và tháo dỡ. - cũng như làm xuất hiện bài toán trọng tâm. - C i / từ các chặn dưới của mỗi thời điểm hoàn thành của từng công việc. - Những chi tiết về ứng dụng của đại số MaxPlus trong bài toán dạng flowshop cũng như các kết quả trên đây được trình bày cụ thể trong Vo and Lenté 2015:. - Phần này sẽ tập trung trình bày việc sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop, cụ thể là giới thiệu các ma trận MaxPlus tương ứng với mỗi công việc. - tồn tại một ma trận MaxPlus tương ứng T i kích thước m m được định nghĩa hoàn toàn bởi các dữ liệu của công việc J i và các điều kiện ràng buộc của bài toán. - Ma trận này biểu diễn mối quan hệ tuyến tính MaxPlus kết nối các thời điểm nhàn rỗi của các máy trước và sau khi thực thi một công việc. - Cho một công việc J i . - trong đó ı E là véc-tơ các thời điểm nhàn rỗi của các máy trước khi thực thi công việc J i và D E i. - Tất cả hệ số của ma trận T i được tính trực tiếp từ công việc J i và các điều kiện ràng buộc của bài toán, và ngược lại, ma trận này hoàn toàn đặc trưng cho công việc J i cũng như các điều kiện ràng buộc của bài toán flowshop.. - Ngay khi ta thiết lập được các ma trận T i , ta cũng có thể định nghĩa các ma trận tương ứng với các tập có thứ tự các công việc.. - Cho là một tập có thứ tự của -công việc: Ma trận tương ứng của nó T được định nghĩa bởi T D O. - Giống như các ma trận T i . - các ma trận T định nghĩa quan hệ tuyến tính MaxPlus giữa các thời điểm nhàn rỗi của các máy trước và sau khi thực hiện tập có thứ tự các công việc.. - Cho D E là véc-tơ các thời điểm các máy được giải phóng bởi tập có thứ tự các công việc . - Hình 4.2: Bài toán flowshop với ràng buộc độ trễ, thời gian thiết lập, tháo dỡ.. - Ma trận tương ứng với mỗi công việc 4.2.1. - Bài toán cơ bản. - Ta gọi bài toán cơ bản dạng flowshop là một bài toán dạng flowshop hoán vị và không có thêm điều kiện ràng buộc khác. - Bài toán này được ký hiệu F m j perm j trong đó là một tiêu chí bất kỳ. - Với mọi công việc J i . - ma trận T i thể hiện mối liên hệ giữa các thời điểm nhàn rỗi và kết thúc sớm nhất của một công việc được định nghĩa bởi:. - Bài toán với ràng buộc độ trễ tối thiểu. - Với bài toán với ràng buộc độ trễ tối thiểu .F m j perm. - min delay j trong đó là một tiêu chí bất kỳ), cùng một cách thức, ta có thể có ma trận tương ứng với công việc J i Lenté 2001:. - Bài toán với ràng buộc độ trễ tối thiểu và tối đa. - Một bài toán dạng flowshop với ràng buộc độ trễ là một bài toán dạng flowshop với sự có mặt của các độ trễ giữa hai tác vụ liên tiếp nhau của cùng một công việc. - Loại bài toán này được ký hiệu F m j perm. - Mệnh đề dưới đây giới thiệu ma trận tương ứng với mỗi công việc trong dạng bài toán flowshop này. - Ma trận T i tương ứng với công việc J i được định nghĩa bởi:. - trong đó T i là ma trận tương ứng với công việc J i. - Bài toán với ràng buộc độ trễ tối đa và tối thiểu cùng thời gian chuẩn bị và tháo dỡ. - Chúng ta trở lại với bài toán ngay phía trên nhưng lần này có xem xét đến cả ràng buộc về thời gian chuẩn bị và tháo dỡ. - Hình 4.4 dưới đây minh họa cho các ràng buộc về độ trễ và thời gian chuẩn bị, thời gian tháo dỡ liên quan đến tác vụ thứ k của công việc J i . - Cùng một cách thức như ở bài toán phía trên, ta có Mệnh đề sau.. - Ma trận T i tương ứng với công việc J i được xác định như sau:. - Phần chứng minh này được thực hiện tương tự như trường hợp bài toán chỉ có ràng buộc về độ trễ tối đa và tối thiểu.. - Bài toán trọng tâm. - Nói cách khác, ta có thể quy các bài toán dạng flowshop với ràng buộc độ trễ về một bài toán duy nhất với ràng buộc bao gồm cả độ trễ tối thiểu và độ trễ tối đa.. - Sau đây, ta sẽ xem xét bài toán với ràng buộc độ trễ tối thiểu và tối đa cùng với thời gian chuẩn bị và tháo dỡ (F m j perm I mi n max delay I S nsd I R nsd j. - Ma trận tương ứng với mỗi công việc J i đã được xác định như sau:. - ma trận T i trở thành:. - Ma trận này cũng là ma trận tương ứng với mỗi công việc trong bài toán dạng flowshop với ràng buộc độ trễ tối thiểu và tối đa. - Trong trường hợp này, ta vừa làm xuất hiện một bài toán trọng tâm.. - Tóm lại, từ tập hợp các bài toán với các ràng buộc liên quan đến độ trễ, thời gian chuẩn bị và thời gian tháo dỡ, ta có thể quy về một bài toán duy nhất với ràng buộc độ trễ tối thiểu và độ trễ tối đa. - Bài toán trọng tâm này giúp ta tập trung toàn bộ thời gian để giải quyết một bài toán duy nhất, thay vì giải quyết nhiều bài toán riêng lẻ.. - Bài viết này giới thiệu việc sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop. - Ta có thể xây dựng các ma trận hoàn toàn đặc trưng các công việc. - Các kết quả thu được đã xác nhận mối quan hệ tuyến tính MaxPlus giữa các thời điểm nhàn rỗi của các máy trước và sau khi thực hiện công việc. - Các kết quả này cũng giúp ta thực hiện việc nghiên cứu các bài toán ma trận thay vì nghiên cứu trực tiếp trên các bài toán dạng flowshop. - Ngoài ra, chúng ta đã tìm ra được một bài toán trọng tâm với ràng buộc độ trễ tối thiểu và tối đa.. - Bài toán này cho phép ta tránh việc trùng lặp các nghiên cứu trên các bài toán dạng flowshop với các ràng buộc khác nhau. - Bài toán trọng tâm này cho phép thay thế các bài toàn có ràng buộc liên quan độ trễ và thời gian chuẩn bị, tháo dỡ.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt