Một thuật toán di truyền hiệu quả cho bài toán lập lịch Job shop.

Tóm tắt

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.