MỘT THUẬT TOÁN DI TRUYỀN HIỆU QUẢ CHO BÀI TOÁN LẬP LỊCH JOB SHOP

Abstract

Bài báo này trình bày một thuật toán di truyền mới cho bài toán lập lịch job shop (Jobshop Scheduling Problem - JSP). Thuật toán mới này có một số đổi mới sau đây: Một lịch biểu được mã hoá bởi các số tự nhiên; các luật ưu tiên của Giffler và Thompson được dùng để tạo ra các lịch biểu tích cực; phép đột biến được thực hiện trên các cá thể tiềm năng và kết hợp với kĩ thuật tìm kiếm lân cận; phép trao đổi chéo mới kết hợp trao đổi chéo đồng nhất với thuật toán GT và được thực hiện trên 3 cá thể cha.   Dựa trên phương pháp đã đề nghị, chúng tôi đã thực hiện một chương trình tìm lịch biểu tối ưu gần đúng cho JSP. Chương trình đã chạy trên các bài toán test chuẩn do Muth và Thompson đề nghị. Phương pháp được đề nghị của chúng tôi ưu điểm hơn hẳn so với các phương pháp khác ở chỗ thời gian tính toán và tỉ lệ các lời giải tối ưu có thể tìm được. Để minh chứng cho điều đó, trong mục 4 chúng tôi trình bày các kết quả thử nghiệm và so sánh các kết quả của chúng tôi với các kết quả của Yamada.