1
TÓM TẮT LUẬN VĂN THẠC SĨ
Đề tài: Lập lịch tối ưu Flowshop bằng giải thuật di truyền
Tác giả luận văn: Nhữ Văn Giang Khóa: 2015B-CNTT
Người hướng dẫn: TS. Phạm Quang Dũng
Từ khóa: Giải thuật di truyền; Lập lịch JobShop; Lập lịch FlowShop; Tối ưu hóa tổ hợp.
Nội dung tóm tắt:
a) Lý do chọn đề tài:
Trên thưc tế, trong sản xuất việc làm thế nào để xây dựng được phướng án lập lịch sản
xuất tối ưu nhất để được hiệu quả về năng suất cũng như thời gian sản xuất, lợi nhuận cao
nhất vẫn là bài toán khiến các nhà đầu tư, chủ doanh nghiệp đau đầu. Xuất phát từ thực tế này,
tác giả đã lựa chọn hướng nghiên cứu tìm giải pháp: Lập lịch tối ưu FlowShop bằng giải
thuật di truyền. Thực hiện đề tài này, tác giả mong muốn đóng góp thêm một giải thuật hỗ trợ
cho các doanh nghiệp sản xuất trong việc lập lịch sản xuất , đặc biệt là trong sản xuất liên tục.
b) Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu:
Mục đích nghiên cứu:
- Nghiên cứu, m hiểu nội dung bài báo, thuật toán hai tác giả đưa ra như một
công cụ, công nghệ để đáng giá và giải quyết bài toán lập lịch tối ưu flowshop.
- Ứng dụng thuật toán vào phần mềm demo thực hiện việc lập một lịch biểu tối ưu cho n
công việc ở trên M máy
Đối tượng nghiên cứu:
- Nghiên cứu, tìm hiểu nội dung bài báo, thuật toán mà hai tác giả đã đưa ra.
- Nghiên cứu một ngôn ngữ lập trình để cài đặt thuật toán, viết phần mềm demo để thực
hiện việc lập một lịch biểu tối ưu cho n công việc trên m máy sản xuất.
Phạm vi nghiên cứu: Đề tài tập trung nghiên cứu lý thuyết nội dung bài báo của hai tác
giả: Vũ Đình Hòa và Nguyễn Hữu Mùi đăng bài Solving flow shop scheduling problem
using genetic algorithms trên tp chí JOURNAL OF SCIENCE OF HNUE T54, s 6
(2009) 35 41, và áp dụng các kiến thức của giải thuật di truyền, áp dụng giải thuật di
truyền cải tiến để giải quyết bài toán lập lịch tối ưu flowshop.
c) Tóm tắt cô đọng các nội dung chính và đóng góp mới của tác giả:
Đề tài sẽ trình bày các nội dung như sau:
CHƯƠNG 1. TỔNG QUAN VỀ BAI TOAN LẬP LỊCH
- Trình bày những khái niệm cơ bản về giải thuật di truyền: mã hóa nghiệm của bài
toán, các toán tử di truyền các đồ thuật toán di truyền. Tính hội tụ của giải thuật di
truyền chính tắc và biến thể của nó được dựa trên kết quả nghiêm cứu của Ruldoph.
- Phần tiếp theo của chương dành cho việc trình bày một số bài toán lập lịch căn bản,
hình toán học các giải thuật phổ biến được dùng đgiải quyết bài toán lập lịch căn
bản, phát biểu bài toán lập lịch Flowshop.
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT VỀ TỐI ƯU HOA TỔ HỢP
- Nội dung chương 2 bao gồm : Giới thiệu về bài toán tối ưu hóa tổ hợp và các hướng
2
tiếp cận để giải bài toán tối ưu hóa tổ hợp, đề xuất giải sử dụng giải thuật tìm kiếm cục
bộ để giải bài toán tối ưu hóa tổ hợp ứng dụng trong bài toán lập lịch sản suất.
CHƯƠNG 3. THIẾT KẾ I ĐẶT THUẬT TOÁN DI TRUYỀN GIẢI BÀI
TOÁN LẬP LỊCH FLOWSHOP
- Trong chương này chủ yếu nói về việc mô tả bài toán lập lịch Flowshop tổng quát và
đưa ra hình toán học của bài toán, một số nghiên cứu liên quan từ giải thuật di
truyền.
- Dưa ra cách thức mã hóa lời giải và cài đặt thuật toán di truyền để xây dựng lời giải
đối với bài toán lập lịch Flowshop, đánh giá ưu điểm hạn chế của thuật toán khi áp
dụng để xây dựng lời giải.
CHƯƠNG 4 : KẾT QUẢ THỰC NGHIỆM VÀ KẾT LUẬN
- Từ thuật toán được trình bày ở trên, tôi đã cài đặt một chương trình bằng ngôn ngữ
Java chạy thử nghiệm trên y PC với bộ dữ liệu đầu o được sử dụng cho chương
trình 2 bộ test chuẩn từ bài toán benmark của Muth G. L. Thompsonm 1 test
chuẩn từ bài toán benmark của Taillard. Sau đây là các kết quả thử nghiệm:
d) Phương pháp nghiên cứu:
Kết hp nghiên cu lý thuyết tài liệu, các đ tài nghiên cu liên quan bài báo ca 2
tác gi t đó kho sát thc nghim li kết qu bài báo ca hai tác gi Đình Hòa
Nguyn Hữu Mùi đã đề xuất để gii quyết bài toán lp lch FlowShop. để tiến hành xây
dng ng dụng để th nghiệm, đánh giá kết qu thc nghip. C th như sau:
- Các nghiên cứu lý thuyết sẽ được thực hiện trên cơ sở tổng hợp, phân tích thông tin từ các
nghiên cứu liên quan.
- Mô hình hóa, ứng dụng giải thuật di truyền vào việc giải quyết bài toán.
- Cài đặt thử nghiệm thuật toán dựa trên bộ dữ liệu Test chuẩn để thực nghiệm lại kết
quả.
e) Kết luận
Qua quá trình nghiên cứu đề tài “Lập lịch tối ưu Flowshop bằng giải thuật di truyền”,
luận văn đã đạt được một số kết quả sau:
1. Tìm hiểu được các phương pháp giải bài toán Flowshop, đặc biệt các phương pháp
dùng giải thuật di truyền để giải quyết bài toán trên.
2. Cài đặt demo bài toán FSP bằng giải thuật di truyền.
3. Từ các kết quả thực nghiệm số liệu các test chuẩn độ khó cao đánh giá hiệu quả của
giải thuật di truyền đối với bài toán Flowshop hoán vị.
Hướng nghiên cứu tiếp theo của luận văn:
4. Tiếp tục nghiên cứu cách cải tiến giải thuật di truyền để nâng cao nh hiệu quả khi sử
dụng giải thuật di truyền để giải quyết các bài toán lập lịch.
5. Xây dựng một ứng dụng cụ thể dùng giải thuật di truyền để giải quyết các bài toán thực
tế.
3
Các kết quả chính đạt được trong đề tài:
1. Đề tài đã y dựng thành công hình thuật toán cải tiến ứng dựng giải thuật di
truyền trong giải quyết bài toán lập lịch tối ưu Flowshop.
2. Kết quả nghiên cứu của đề tài cũng cho thấy tính khả thi khi áp dụng giải thuật di
truyền để tìm ra phương án lập lịch sản xuất trong thực tế. Từ đó cung cấp cho các nhà
máy các phương án lập lịch sản xuất phù hợp, sao cho đạt được lợi ích tối đa nhất cho con
người.
Những khó khăn gặp phải trong quá trình thực hiện đề tài:
Luận văn y một số hạn chế cần được xem xét khi nghiên cứu. Đó việc tổng kết
hóa các kết quả nghiên cứu bị giới hạn do chưa đưa ra được tính nổi bật khi áp dụng thuật
toán di truyền so với việc áp dụng các thuật toán khác trong việc giải quyết bài toán lập lịch
tối ưu Flowshop
Chưa thống được những rủi ro khó khăn thể nảy sinh hoặc các khoản chi phí
phát sinh khi đưa vào thực tế. Do đó, hình đề xuất thử nghiệm trong nghiên cứu này
đòi hỏi phải tiếp tục thử nghiệm để phát hiện, khám phá xây dựng một hình giải quyết
bài toán tổng quát và chính xác hơn.
Hướng giải quyết:
Tìm hiểu, nghiên cứu các bài toán lập lịch khác sử dụng các thuật toán khác để đưa ra
cái nhìn tổng quan hơn, hiệu quả hơn trong việc nghiên cứu. Từ đó đưa ra hướng giải quyết
đối với vòng lặp điều kiện, hàm thích nghi cho giải thuật di truyền để đạt tới kết quả tối ưu
nhất cho việc lập lịch.
Tìm hiểu sâu những thay đổi trong thực tế thxảy ra trong quá trình thực nghiệm
nhằm giảm thiểu những rủi ro khi thực hiện thuật toán. Tiếp tục nghiên cứu thực nghiệm với
các mô hình khác để hoàn thiện bài toán.
Mặc còn các hạn chế, nhưng từ các kết quả nghiên cứu luận thực tiễn cho
thấy việc ứng dụng giải thuật di truyền vào bài toán lập lịch tối ưu Flowshop đã đưa ra các
chiến lược các gợi ý có giá trị giúp nhà sản xuất lập kế hoạch sản xuất phù hợp đạt hiệu
quả cao nhất tốn ít chi phí nhân công thời gian nhất từ đó giúp đạt lợi nhuận cao nhất cho
doanh nghiệp.