Mở đầu Chương 4 – Mô hình bài toán: Thu thập dữ liệu tại doanh nghiệp để xây dựng mô hình bài toán điều độ, bao gồm các khía cạnh từ thành phần đến cấu trúc dữ liệu đầu vào cho mô hình, đến dữ liệu đầu ra sau khi giải quyết vấn đề, với sự hỗ trợ của phần mềm hỗ trợ. Chương 5 – Áp dụng mô hình giải thuật di truyền: Mô hình lập kế hoạch đã được xây dựng từ chương 4 sẽ được áp dụng vào thực tế hiện tại của công ty, sử dụng dữ liệu đầu vào thực tế từ tình trạng làm việc hàng ngày của nhà máy. Chương 6 – Kết quả thực hiện và kiến nghị: Đánh giá kết quả của dự án, chương này thảo luận về những hạn chế hiện tại. Ngoài ra, nó còn đưa ra định hướng phát triển trong tương lai của dự án.
3 Chương 2: Cơ sở lý thuyết và phương pháp luận CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN 2. Điều độ trong sản xuất và dịch vụ 2. Lý thuyết điều độ cơ bản Điều độ là một quá trình ra quyết định được sử dụng một cách thường xuyên trong nhiều ngành công nghiệp sản xuất và dịch vụ. Nó liên quan đến việc phân bổ nguồn lực cho các nhiệm vụ trong khoảng thời gian nhất định và mục tiêu của nó là tối ưu hóa một hoặc nhiều mục tiêu.
Các nguồn lực và nhiệm vụ trong một tổ chức có thể ở nhiều dạng khác nhau. Tài nguyên có thể là máy móc trong xưởng, đường băng tại sân bay, đội ngũ tại công trường xây dựng, các đơn vị xử lý trong môi trường máy tính, v. Các nhiệm vụ có thể là hoạt động trong quy trình sản xuất, cất cánh và hạ cánh tại sân bay, các giai đoạn trong một dự án xây dựng, thực hiện các chương trình máy tính, v. Mỗi nhiệm vụ có thể có một mức độ ưu tiên nhất định, thời gian bắt đầu sớm nhất có thể và ngày đến hạn.
Các mục tiêu cũng có thể có nhiều hình thức khác nhau. Một mục tiêu có thể là giảm thiểu thời gian hoàn thành của nhiệm vụ cuối cùng và một mục tiêu khác có thể là giảm thiểu số lượng nhiệm vụ được hoàn thành sau ngày đến hạn tương ứng của chúng. Điều độ, với tư cách là một quá trình ra quyết định, đóng một vai trò quan trọng trong hầu hết các hệ thống sản xuất và chế tạo cũng như trong hầu hết các môi trường xử lý thông tin. Nó cũng quan trọng trong môi trường vận tải và phân phối cũng như trong các loại hình công nghiệp dịch vụ khác.
Chức năng điều độ trong sản xuất Chức năng lập kế hoạch trong hệ thống sản xuất hoặc tổ chức dịch vụ phải tương tác với nhiều chức năng khác. Những tương tác này phụ thuộc vào hệ thống và có thể khác nhau đáng 4 Chương 2: Cơ sở lý thuyết và phương pháp luận kể từ tình huống này sang tình huống khác. Chúng thường diễn ra trong một hệ thống thông tin toàn doanh nghiệp. Các đơn đặt hàng được phát hành trong môi trường sản xuất phải được chuyển thành các công việc có ngày đến hạn liên quan.
Những công việc này thường phải được xử lý trên máy trong một trung tâm làm việc theo một thứ tự hoặc trình tự nhất định. Quá trình xử lý công việc đôi khi có thể bị trì hoãn nếu một số máy đang bận và quyền ưu tiên có thể xảy ra khi các công việc có mức độ ưu tiên cao đến với các máy đang bận. Cũng phải tính đến các sự kiện không lường trước được trong khu vực sản xuất, chẳng hạn như sự cố máy móc hoặc thời gian xử lý lâu hơn dự kiến, vì chúng có thể ảnh hưởng lớn đến lịch sản xuất. Trong một môi trường như vậy, việc phát triển một điều đọi nhiệm vụ chi tiết giúp duy trì hiệu quả và kiểm soát các hoạt động.
Khu vực sản xuất không phải là bộ phận duy nhất của tổ chức tác động đến quá trình điều độ. Nó cũng bị ảnh hưởng bởi quá trình lập kế hoạch sản xuất. Điều độ trong môi trường flowshop linh hoạt Bài toán điều độ flowshop tổng quát là một bài toán sản xuất trong đó một tập hợp n công việc phải được xử lý với thứ tự công việc giống hệt nhau trên m máy và điều độ flowshop linh hoạt là sự tổng quát hóa của điều độ flowshop đơn giản và cổ điển với môi trường máy song song. Điều độ trong môi trường flowshop linh hoạt (FFSP) là một bài toán phức tạp liên quan đến việc điều độ một tập hợp công việc trên một tập hợp máy có nhiều giai đoạn xử lý, trong đó mỗi công việc có thể được xử lý trên nhiều máy trong một giai đoạn nhất định.
Mục tiêu của FFSP là giảm thiểu thước đo hiệu suất nhất định, chẳng hạn như tổng thời gian hoàn thành hoặc thời gian thực hiện. Trong bài toán FFSP tất định, có một số công việc cần được xử lý. Mỗi công việc đều có số lượng thao tác và trình tự xử lý cụ thể. Thời gian sẵn sàng của một công việc là thời điểm thao tác đầu tiên của nó sẵn sàng được xử lý, trong khi thời gian đến hạn của công việc là thời điểm thao tác cuối cùng phải được hoàn thành.
Cả hai dữ liệu này đều được xác định trước và khác với những dữ liệu khác. Mỗi thao tác chỉ có thể được xử lý bởi một máy trong một tập hợp các máy được xác định. Ngoài ra, còn một số hạn chế nữa góp phần làm phức 5 Chương 2: Cơ sở lý thuyết và phương pháp luận tạp bài toán như thời gian có sẵn của máy, mức độ ưu tiên của công việc, thời gian setup máy, thời gian vận chuyển, sản xuất hàng loạt… Hình 2.1 Sơ đồ dòng thông tin trong hệ thống sản xuất 2. Giải thuật di truyền Giải thuật di truyền (Genetic Algorithm - GA) lần đầu tiên được phát triển bởi John Holland và các cộng sự vào những năm 1960 và 1970 trong cuốn sách "Adaptation in Natural 6 Chương 2: Cơ sở lý thuyết và phương pháp luận and Artificial Systems".
Giải thuật này ban đầu là một mô hình của quá trình tiến hóa sinh học dựa trên lý thuyết chọn lọc tự nhiên của Darwin, sử dụng các nguyên tắc của phép lai chéo và tái tổ hợp, đột biến, và chọn lọc. Ứng dụng của Holland đối với GA đã được mở rộng thành nhiều loại bài toán tối ưu hóa khác nhau, và liên tục được phát triển và áp dụng trong nhiều lĩnh vực, từ thị trường tài chính đến tối ưu hóa kỹ thuật đa mục tiêu. Giải thuật di truyền, nổi tiếng nhờ hiệu quả trong việc giải các bài toán tối ưu hóa, đặc biệt có liên quan trong bối cảnh của các nhiệm vụ điều độ và tối ưu hóa. Mặc dù đã được mở rộng vào lĩnh vực kỹ thuật, thuật ngữ sử dụng cho GA vẫn bao gồm một số thuật ngữ sinh học.
Bao gồm "quần thể," ám chỉ nhóm các cá thể; "nhiễm sắc thể," chỉ các cá thể trong một quần thể; và "gen," là thành phần của một nhiễm sắc thể. Do đó, mỗi nhiễm sắc thể đại diện cho một giải pháp tiềm năng cho bài toán tối ưu hóa hiện tại. Giải thuật di truyền gồm có bốn quy luật cơ bản là: - Lai chéo. - Chọn lọc tự nhiên.
Quy trình lai chéo (phép lai): Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: - Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. - Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1.
Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12. - Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa. 7 Chương 2: Cơ sở lý thuyết và phương pháp luận Quá trình đột biến (phép đột biến).
Quá trình tiến hóa được gọi là quá trình đột biến khi một hoặc một số tính trạng của con không được thừa hưởng từ hai chuỗi nhiễm sắc thể cha-mẹ. Phép đột biến xảy ra với xác suất thấp hơn rất nhiều lần so với xác suất xảy ra phép lai. Phép đột biến có thể mô tả như sau: - Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m. - Thay đổi giá trị của gen thứ k.
- Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn). Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ thích nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của nó.
Phép tái sinh có thể mô phỏng như sau: - Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft. Tổng độ thích nghi là Fm.
- Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm. - Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới. - Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép chọn được mô tả như sau: Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất.2 là biểu đồ dựa trên khái niệm Giải thuật Di truyền (GA) do Elisaveta G. Shopova và Natasha G. Vaklieva-Bancheva đề xuất, minh họa ứng dụng của GA trong việc giải quyết các bài toán tối ưu hóa. Ban đầu, thuật toán tạo ra một quần thể các nhiễm sắc thể đáp ứng các ràng buộc của vấn đề, sau đó giá trị độ phù hợp của từng nhiễm sắc thể được tính toán để đánh giá hiệu suất của nó.
Tiếp theo, các nhiễm sắc thể có giá trị độ phù hợp cao hơn sẽ được chọn cho quá trình tiến hóa.