Luận văn thạc sĩ: Nghiên cứu các bài toán lịch biểu và ứng dụng

Luận văn thạc sĩ nghiên cứu các bài toán lịch biểu và ứng dụng, cung cấp cái nhìn sâu sắc về phương pháp và ứng dụng thực tiễn trong quản lý thời gian.

• Tác giả: Nguyễn Xuân Minh
• Người hướng dẫn: GS.TS Vũ Đức Thi
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nghiên cứu các bài toán lịch biểu và ứng dụng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH
• 1.1. Định nghĩa bài toán lập lịch Jobshop (JSP)
• 1.2. Tình hình nghiên cứu thuật toán tìm kiếm lịch biểu tối ưu
• 1.2.1. Tình hình nghiên cứu trên thế giới
• 1.2.2. Tình hình nghiên cứu trong nước
• 1.3. Các phương pháp tiếp cận giải bài toán lập lịch
• 1.3.1. Cách tiếp cận chính xác, thuật toán nhánh cận
• 1.3.2. Cách tiếp cận gần đúng
• 2. CHƯƠNG 2: THUẬT TOÁN DI TRUYỀN
• 2.1. Lịch sử ra đời
• 2.2. Một số khái niệm cơ bản
• 2.2.1. Cá thể, nhiễm sắc thể. Lưu đồ thuật toán di truyền đơn giản
• 2.3. Các tham số của thuật toán di truyền
• 2.3.1. Kích thước quần thể
• 2.3.2. Xác suất lai ghép
• 2.3.3. Xác suất đột biến
• 2.3.4. Khởi tạo quần thể ban đầu
• 2.3.5. Hàm tính độ thích nghi
• 2.4. Toán tử chọn lọc. Các toán tử lai ghép
• 2.5. Toán tử đột biến
• 3. CHƯƠNG 3: HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP
• 3.1. Bài toán Flowshop hoán vị
• 3.1.1. Mô tả bài toán
• 3.1.2. Cách tính thời gian hoàn thành trong một lịch biểu hoán vị
• 3.1.3. Thuật toán Johnson cho PFSP 2 máy và PFSP 3 máy
• 3.1.4. Một thuật di truyền mã hóa tự nhiên cho bài toán FSP tổng quát
• 3.1.5. Kết quả thực nghiệm
• 3.2. Bài toán lập lịch Flowshop
• 3.2.1. Mô bài toán
• 3.2.2. Một thuật toán di truyền mã hóa tự nhiên cho bài toán FPS tổng quát
• 4. CHƯƠNG 4: MỘT THUẬT TOÁN DI TRUYỀN LAI CHO BÀI TOÁN LẬP LỊCH JOB SHOP
• 4.1. Các luật ưu tiên của Giffler và Thompson
• 4.2. Thuật toán Giffler - Thompson (GT)
• 4.3. Áp dụng thuật toán GT cho JSP để sinh ra các lịch biểu tích cực
• 4.4. Một thuật toán di truyền lai tuần tự cho bài toán JSP
• 4.4.1. Khởi tạo tập lời giải cho thế hệ ban đầu. Xây dựng hàm thích nghi
• 4.4.2. Các toán tử di truyền
• 4.4.3. Thuật toán di truyền
• 4.4.4. Tính đúng đắn của thuật toán. Kết quả thực nghiệm

Tóm tắt

I. Tổng quan về bài toán lập lịch

Bài toán lập lịch là một lĩnh vực nghiên cứu quan trọng trong quản lý thời gian và tài nguyên. Lịch biểu được định nghĩa là một kế hoạch chi tiết cho việc thực hiện các công việc trong một khoảng thời gian nhất định. Mục tiêu chính của bài toán này là tối ưu hóa thời gian hoàn thành các tác vụ, từ đó nâng cao hiệu quả sử dụng tài nguyên. Các ứng dụng của bài toán lịch biểu rất đa dạng, từ lập lịch sản xuất, lập thời khóa biểu cho giảng viên, đến lập lịch cho các bác sĩ trong bệnh viện. Việc nghiên cứu và phát triển các thuật toán để giải quyết bài toán này là rất cần thiết, đặc biệt trong bối cảnh ngày càng gia tăng nhu cầu tối ưu hóa trong các lĩnh vực khác nhau. Theo nghiên cứu, có hai phương pháp chính để giải bài toán lập lịch: phương pháp chính xác và phương pháp gần đúng. Phương pháp chính xác, như thuật toán nhánh cận, đảm bảo tìm ra giải pháp tối ưu nhưng thường tốn nhiều thời gian. Ngược lại, phương pháp gần đúng, mặc dù không đảm bảo giải pháp tối ưu, lại có ưu điểm về tốc độ và khả năng áp dụng trong thực tế.

1.1. Định nghĩa bài toán lập lịch Jobshop JSP

Bài toán lập lịch Jobshop (JSP) là một trong những bài toán tối ưu tổ hợp khó nhất hiện nay. Được định nghĩa như sau: cho một tập hợp các công việc, mỗi công việc bao gồm nhiều thao tác cần được thực hiện trên các máy khác nhau theo một trình tự nhất định. Mỗi máy chỉ có thể xử lý một công việc tại một thời điểm. Mục tiêu là tìm ra một lịch biểu sao cho thời gian hoàn thành tất cả các công việc, được gọi là makespan, là nhỏ nhất. Bài toán này không chỉ có độ phức tạp cao mà còn có nhiều ứng dụng thực tiễn trong sản xuất và quản lý. Việc giải quyết bài toán JSP đã thu hút sự quan tâm của nhiều nhà nghiên cứu và đã có nhiều phương pháp được đề xuất, từ các thuật toán chính xác đến các phương pháp gần đúng. Đặc biệt, thuật toán di truyền và các kỹ thuật tìm kiếm địa phương đã cho thấy hiệu quả trong việc tìm kiếm các giải pháp gần tối ưu cho bài toán này.

II. Tình hình nghiên cứu thuật toán tìm kiếm lịch biểu tối ưu

Nghiên cứu về bài toán lịch biểu đã diễn ra từ những năm 1950 và đã có nhiều công trình quan trọng được công bố. Tình hình nghiên cứu trên thế giới cho thấy, bài toán JSP lần đầu tiên được giới thiệu bởi Akers và Friedman, và sau đó trở nên nổi tiếng nhờ vào bài toán 10 công việc 10 máy của Fisher và Thompson. Nhiều phương pháp đã được phát triển để giải quyết bài toán này, bao gồm các thuật toán chính xác như quy hoạch nguyên và thuật toán nhánh cận. Tuy nhiên, do độ phức tạp của bài toán, các phương pháp gần đúng như thuật toán di truyền và tìm kiếm Tabu cũng đã được áp dụng rộng rãi. Tại Việt Nam, nghiên cứu về JSP cũng đang được quan tâm, với nhiều công trình tìm kiếm các phương pháp cải tiến thuật toán đã được đề xuất. Các ứng dụng thực tiễn của bài toán này chủ yếu tập trung vào lĩnh vực giáo dục và sản xuất, như lập thời khóa biểu và kế hoạch sản xuất. Việc phát triển các thuật toán hiệu quả để giải quyết bài toán JSP không chỉ có ý nghĩa lý thuyết mà còn mang lại giá trị thực tiễn cao.

2.1. Tình hình nghiên cứu trên thế giới

Nghiên cứu về bài toán lập lịch đã có một lịch sử dài và phong phú. Các công trình nghiên cứu đầu tiên đã chỉ ra rằng bài toán JSP là NP-hard, điều này có nghĩa là không có giải pháp chính xác nào có thể tìm ra trong thời gian hợp lý cho tất cả các trường hợp. Nhiều nhà nghiên cứu đã phát triển các phương pháp khác nhau để giải quyết bài toán này, từ các thuật toán chính xác đến các phương pháp gần đúng. Các thuật toán như nhánh cận và quy hoạch tuyến tính nguyên đã được chứng minh là hiệu quả trong việc tìm kiếm giải pháp tối ưu. Tuy nhiên, do tính chất phức tạp của bài toán, các phương pháp gần đúng như thuật toán di truyền và tìm kiếm Tabu đã trở thành lựa chọn phổ biến trong thực tế. Những nghiên cứu này không chỉ giúp cải thiện hiệu suất của các thuật toán mà còn mở ra hướng đi mới cho việc ứng dụng trong các lĩnh vực khác nhau.

Nội dung chính

Tổng quan nghiên cứu

Lập lịch là một chủ đề nghiên cứu quan trọng trong lĩnh vực hệ thống thông tin và quản lý sản xuất, xuất hiện từ những năm 1950. Mục tiêu chính của lập lịch là phân phối hiệu quả tài nguyên dùng chung để hoàn thành các tác vụ trong thời gian tối ưu. Theo ước tính, bài toán lập lịch Jobshop (JSP) là một trong những bài toán tối ưu tổ hợp khó tính toán nhất, với ứng dụng rộng rãi trong sản xuất, giáo dục, y tế, vận tải và nhiều lĩnh vực khác. Nghiên cứu này tập trung vào việc phát triển và ứng dụng các thuật toán giải quyết các bài toán lập lịch, đặc biệt là JSP và các bài toán con như Flowshop hoán vị (PFSP) và Flowshop (FSP).

Mục tiêu cụ thể của luận văn là nghiên cứu các thuật toán chính xác và gần đúng để giải quyết bài toán lập lịch, trong đó tập trung vào thuật toán di truyền và các biến thể lai nhằm cải thiện hiệu quả và chất lượng lời giải. Phạm vi nghiên cứu bao gồm các bài toán lập lịch với số lượng công việc và máy đa dạng, áp dụng trong môi trường sản xuất và quản lý thời gian thực hiện công việc tại Việt Nam trong giai đoạn đến năm 2015. Ý nghĩa nghiên cứu được thể hiện qua việc nâng cao hiệu quả lập lịch, giảm thời gian hoàn thành công việc (makespan), từ đó góp phần tăng năng suất và giảm chi phí trong các hệ thống sản xuất và dịch vụ.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai khung lý thuyết chính: lý thuyết bài toán lập lịch tổ hợp và thuật toán di truyền (Genetic Algorithm - GA). Bài toán lập lịch Jobshop (JSP) được định nghĩa là việc sắp xếp thứ tự xử lý các công việc trên nhiều máy sao cho thời gian hoàn thành tổng thể (makespan) là nhỏ nhất. Đây là bài toán NP-hard, đòi hỏi các phương pháp giải quyết hiệu quả.

Thuật toán di truyền là một kỹ thuật tìm kiếm ngẫu nhiên dựa trên mô phỏng quá trình tiến hóa sinh học, bao gồm các khái niệm chính như cá thể (giải pháp), quần thể (tập các giải pháp), hàm thích nghi (fitness), các toán tử lai ghép (crossover) và đột biến (mutation). Các khái niệm chuyên ngành quan trọng bao gồm:

• Makespan: Thời gian hoàn thành công việc cuối cùng trong lịch biểu.
• Thuật toán nhánh cận (Branch and Bound): Phương pháp chính xác tìm kiếm lời giải tối ưu bằng cách loại bỏ các nhánh không khả thi.
• Thuật toán di truyền lai (Hybrid GA): Kết hợp GA với các kỹ thuật tìm kiếm khác để nâng cao hiệu quả.
• Lịch biểu tích cực (Active Schedule): Lịch biểu không thể rút ngắn thời gian hoàn thành bằng cách thay đổi thứ tự công việc.
• Thuật toán Johnson: Thuật toán tối ưu cho bài toán Flowshop 2 và 3 máy với điều kiện nhất định.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm các bài toán lập lịch tiêu chuẩn và dữ liệu thực tế từ các hệ thống sản xuất, đào tạo và dịch vụ. Cỡ mẫu nghiên cứu gồm các bài toán với số lượng công việc từ 3 đến 10 và số máy từ 2 đến 5, phù hợp với các trường hợp thực tế.

Phương pháp phân tích sử dụng kết hợp các thuật toán chính xác như nhánh cận và các thuật toán gần đúng như mô phỏng luyện kim (Simulated Annealing), tìm kiếm Tabu (Taboo Search) và thuật toán di truyền. Đặc biệt, nghiên cứu phát triển thuật toán di truyền lai, kết hợp các toán tử lai ghép đa dạng (PMX, OX, POS, CX) và các toán tử đột biến (đảo ngược, chèn, thay thế, hoán vị) nhằm tối ưu hóa lời giải.

Timeline nghiên cứu kéo dài trong năm 2015, bao gồm giai đoạn khảo sát lý thuyết, phát triển thuật toán, thực nghiệm và đánh giá kết quả trên các bộ dữ liệu chuẩn và thực tế.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả thuật toán nhánh cận: Thuật toán nhánh cận cho phép tìm lời giải tối ưu cho bài toán JSP nhỏ với thời gian xử lý giảm đáng kể nhờ chiến lược phân nhánh và đánh giá cận. Ví dụ, với bài toán JSP 3 công việc, 3 máy, thuật toán nhánh cận có thể loại bỏ nhiều nhánh không khả thi, rút ngắn thời gian tính toán.

2. Thuật toán mô phỏng luyện kim: Áp dụng cho bài toán lập lịch một máy, thuật toán mô phỏng luyện kim đạt được độ trễ trọng số tối thiểu ∑ = 9 sau 5 vòng lặp, giảm đáng kể so với giá trị khởi tạo ∑ = 30. Thuật toán có khả năng thoát khỏi cực tiểu địa phương nhưng có nhược điểm là có thể lặp lại lời giải cũ, gây mất thời gian.

3. Thuật toán tìm kiếm Tabu: Với danh sách Tabu độ dài 2, thuật toán tìm kiếm Tabu đã cải thiện lời giải từ ∑ = 30 xuống ∑ = 9 cho bài toán lập lịch một máy, tránh lặp lại các lời giải cũ hiệu quả hơn mô phỏng luyện kim. Tuy nhiên, việc kiểm tra danh sách Tabu tốn kém về thời gian và bộ nhớ.

4. Thuật toán di truyền và các toán tử lai ghép, đột biến: Thuật toán di truyền với các toán tử lai ghép như PMX, OX, POS, CX và các toán tử đột biến đa dạng giúp duy trì sự đa dạng quần thể và tăng khả năng tìm kiếm lời giải tối ưu. Ví dụ, lai ghép một điểm và hai điểm giúp tạo ra cá thể con có đặc tính tốt hơn cha mẹ, đột biến đảo ngược và hoán vị giúp tránh rơi vào cực tiểu địa phương.

Thảo luận kết quả

Các kết quả thực nghiệm cho thấy thuật toán nhánh cận phù hợp với bài toán quy mô nhỏ do chi phí tính toán cao khi mở rộng. Thuật toán mô phỏng luyện kim và tìm kiếm Tabu là các phương pháp gần đúng hiệu quả, trong đó tìm kiếm Tabu có ưu thế hơn về khả năng tránh lặp lại lời giải cũ. Thuật toán di truyền với các toán tử lai ghép và đột biến đa dạng thể hiện tính linh hoạt và khả năng khai thác không gian tìm kiếm rộng lớn, phù hợp với bài toán lập lịch quy mô lớn.

So sánh với các nghiên cứu quốc tế, kết quả phù hợp với xu hướng ứng dụng thuật toán tiến hóa và tìm kiếm địa phương trong giải bài toán lập lịch. Việc sử dụng biểu đồ Grant và đồ thị không liên thông giúp trực quan hóa lịch biểu và phân tích đường tới hạn, hỗ trợ đánh giá hiệu quả thuật toán.

Đề xuất và khuyến nghị

1. Phát triển thuật toán di truyền lai: Kết hợp thuật toán di truyền với các kỹ thuật tìm kiếm địa phương như tìm kiếm Tabu để nâng cao chất lượng lời giải và giảm thời gian tính toán. Chủ thể thực hiện: nhóm nghiên cứu và phát triển phần mềm, thời gian 6-12 tháng.

2. Tối ưu tham số thuật toán: Nghiên cứu và điều chỉnh các tham số như kích thước quần thể, xác suất lai ghép và đột biến để cân bằng giữa đa dạng quần thể và tốc độ hội tụ. Chủ thể: nhà nghiên cứu, thời gian 3-6 tháng.

3. Ứng dụng trong thực tế sản xuất và dịch vụ: Áp dụng các thuật toán đã phát triển vào các hệ thống lập lịch sản xuất, lịch làm việc, lịch trực bệnh viện nhằm nâng cao hiệu quả vận hành. Chủ thể: doanh nghiệp, bệnh viện, thời gian 12-18 tháng.

4. Xây dựng công cụ hỗ trợ lập lịch trực quan: Phát triển phần mềm có giao diện đồ họa sử dụng biểu đồ Grant và đồ thị không liên thông để người dùng dễ dàng theo dõi và điều chỉnh lịch biểu. Chủ thể: nhóm phát triển phần mềm, thời gian 6-9 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành hệ thống thông tin, công nghệ thông tin: Nắm bắt kiến thức về bài toán lập lịch, thuật toán di truyền và các phương pháp giải quyết bài toán tối ưu tổ hợp.

2. Chuyên gia và kỹ sư lập trình phát triển phần mềm quản lý sản xuất: Áp dụng các thuật toán lập lịch tiên tiến để thiết kế hệ thống quản lý sản xuất hiệu quả.

3. Quản lý doanh nghiệp và nhà hoạch định kế hoạch sản xuất: Hiểu rõ các phương pháp lập lịch để tối ưu hóa quy trình sản xuất, giảm chi phí và nâng cao năng suất.

4. Người làm công tác đào tạo và nghiên cứu ứng dụng: Sử dụng luận văn làm tài liệu tham khảo cho các khóa học về tối ưu hóa, lập lịch và thuật toán tiến hóa.

Câu hỏi thường gặp

1. Bài toán lập lịch Jobshop là gì?
   Bài toán lập lịch Jobshop (JSP) là bài toán sắp xếp thứ tự xử lý các công việc trên nhiều máy sao cho thời gian hoàn thành tổng thể (makespan) là nhỏ nhất. Đây là bài toán NP-hard, rất khó giải chính xác khi quy mô lớn.

2. Thuật toán di truyền hoạt động như thế nào trong lập lịch?
   Thuật toán di truyền mô phỏng quá trình tiến hóa tự nhiên, sử dụng quần thể các giải pháp, áp dụng các toán tử lai ghép và đột biến để tạo ra thế hệ mới với chất lượng lời giải ngày càng cải thiện.

3. Ưu điểm của thuật toán tìm kiếm Tabu so với mô phỏng luyện kim?
   Thuật toán tìm kiếm Tabu tránh lặp lại lời giải cũ bằng cách lưu trữ các di chuyển trong danh sách Tabu, giúp thoát khỏi cực tiểu địa phương hiệu quả hơn mô phỏng luyện kim, vốn dựa trên xác suất chấp nhận lời giải kém hơn.

4. Làm thế nào để đánh giá hiệu quả của một lịch biểu?
   Hiệu quả lịch biểu thường được đánh giá qua thời gian hoàn thành tổng thể (makespan), thời gian chậm trễ, và các chỉ số như độ trễ trọng số. Biểu đồ Grant và đồ thị không liên thông giúp trực quan hóa và phân tích lịch biểu.

5. Thuật toán Johnson áp dụng trong trường hợp nào?
   Thuật toán Johnson được sử dụng để giải bài toán lập lịch Flowshop với 2 hoặc 3 máy thỏa mãn điều kiện nhất định, giúp tìm lời giải tối ưu nhanh chóng cho các trường hợp này.

Kết luận

• Luận văn đã nghiên cứu sâu về bài toán lập lịch Jobshop và các bài toán con Flowshop hoán vị, Flowshop, tập trung phát triển các thuật toán chính xác và gần đúng.
• Thuật toán di truyền và các biến thể lai kết hợp với tìm kiếm địa phương thể hiện hiệu quả cao trong việc tìm lời giải tối ưu hoặc gần tối ưu.
• Các phương pháp mô phỏng luyện kim và tìm kiếm Tabu cũng được đánh giá là công cụ mạnh mẽ trong giải bài toán lập lịch.
• Nghiên cứu cung cấp cơ sở lý thuyết và thực nghiệm để ứng dụng trong các hệ thống sản xuất và dịch vụ thực tế.
• Đề xuất phát triển thuật toán lai và công cụ hỗ trợ trực quan nhằm nâng cao hiệu quả và khả năng ứng dụng trong tương lai.

Để tiếp tục, các nhà nghiên cứu và chuyên gia nên triển khai thử nghiệm thuật toán trên quy mô lớn hơn, đồng thời phát triển phần mềm ứng dụng nhằm hỗ trợ công tác lập lịch trong thực tế. Hành động ngay hôm nay để áp dụng các giải pháp tối ưu hóa lập lịch sẽ giúp nâng cao năng suất và hiệu quả quản lý trong nhiều lĩnh vực.

Trích đoạn nội dung tài liệu

Chương 1. Tổng quan về bài toán lập lịch Chương này trình bày tổng quan về bài toán JSP, tình hình nghiên cứu, các hướng tiếp cận giải quyết bài toán JSP. Thuật toán di truyền Chương này trình bày một số khái niệm cơ bản trong thuật toán di truyền, các tham số đầu vào của thuật di truyền, các toán tử của thuật toán di truyền và thuật toán di truyền. Hai bài toán con của bài toán lập lịch JSP Chương này trình bày các khái niệm cơ bản liên quan đến hai bài toán con của JSP đó là bài toán lập lịch Flowshop hoán vị (PFSP) và Flow shop (FSP) và thuật toán Johnson cho bài toán Flowshop hoán vị 2 máy và 3 máy có hạn chế điều kiện.

Cuối cùng, trình bày thuật toán di truyền mã hóa số tự nhiên cho hai bài toán này. Một thuật toán di truyền lai cho bài toán lập lịch job shop Chương này trình bày một thuật toán di truyền lai là kết hợp thuật toán di truyền với các kỹ thuật tìm kiếm khác cho bài toán JSP và xây dựng chương trình minh họa cho thuật toán di truyền lai. TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH 1. Định nghĩa bài toán lập lịch Jobshop (JSP) Bài toán lập lịch job shop tổng quát được phát biểu như sau: Cho tập công việc { } , mỗi công việc bao gồm công đoạn (hay còn gọi là thao tác) được xử lý trên một tập máy và thỏa mãn các ràng buộc sau: a) Mỗi công việc phải được xử lý ở trên mỗi máy theo một trình tự cho trước của các thao tác.

Trình tự thực hiện thao tác của mỗi công việc lần lượt trên các máy được gọi là tuần tự công nghệ; b) Tại mỗi thời điểm, mỗi máy chỉ có thể xử lý nhiều nhất là một công việc; c) Mỗi máy tùy ý đều có khả năng xử lý một công việc nào đó, phần công việc được xử lý trên máy được gọi là thao tác. d) Mỗi thao tác phải được xử lý một cách liên tục trên máy (từ khi bắt đầu xử lý cho tới khi kết thúc xử lý không bị ngắt); e) Thời gian bắt đầu và thời gian hoàn thành xử lý thao tác được ký hiệu lần lượt là và. Thời gian xử lý thao tác được ký hiệu là ; f) Thời gian hoàn thành việc xử lý tất cả các công việc được gọi mà makespan và được ký hiệu là. Việc giải bài toán lập lịch job shop là xác định một lịch biểu (thứ tự xử lý các công việc ở trên m máy) sao cho makespan là nhỏ nhất.

Để minh họa cho bài toán, một ví dụ về bài toán JSP 3x3 được cho trong Bảng 1. Dữ liệu vào bao gồm một tuần tự công nghệ của các máy cho mỗi công việc và thời gian xử lý của mỗi công việc ở trên mỗi máy (trong dấu ngặc đơn). Công việc Máy (thời gian xử lý) 1 1(3) 2(3) 3(3) 2 1(2) 3(3) 2(4) 3 2(3) 1(2) 3(1) Bảng 1.1: Bài toán JSP 3 công việc, 3 máy Theo Bảng 1.1, các thao tác của được xử lý trên các máy theo trình tự: → → ; tức là, công việc 1 ban đầu được xử lý trên máy 1 với thời gian xử lý là 3, và tiếp theo, được xử lý trên máy 2 với thời gian xử lý là 3, và tiếp theo được xử lý trên máy 3 với thời gian xử lý là 3; các thao tác được xử lý trên các máy theo trình tự: → → các thao tác được xử lý trên các máy theo trình tự: → →. z 2 Bài toán này không chỉ là NP - khó (NP-hard) mà còn nổi tiếng là một trong những bài toán tối ưu tổ hợp khó tính toán nhất cho đến nay.

Độ phức tạp của bài toán này là một trong những lý do tại sao bài toán này được nghiên cứu một cách rộng rãi. Cho đến ngày nay vẫn chưa có một phương pháp nào giải quyết bài toán JSP một cách chính xác và thời gian nhanh. Tình hình nghiên cứu thuật toán tìm kiếm lịch biểu tối ưu 1. Tình hình nghiên cứu trên thế giới Bài toán JSP lần đầu tiên được công bố bởi Akers và Friedman (1955), bài toán này thường được biết với cái tên AkersFriedman.

Tuy nhiên, nó trở nên phổ biến nhờ vào bài toán nổi tiếng 10 công việc 10 máy được đưa ra bởi Fisher và Thompson (1963). Những nỗ lực đầu tiên để giải quyết bài toán JSP được thực hiện bởi Brooks và White (1965), Greenberg (1968) với phương pháp quy hoạch nguyên.Sau đó là phương pháp nhân tử Lagrange của Balas (1969), Charlton và Death (1970) Florian (1971), Ashour(1974), Ashour và Hiremath (1973), Fisher (1973)[5]. Một thuật toán của McMahon và Florian (1975) tìm được dẫn đầu là thuật toán chính xác tốt nhất. Thuật toán kết hợp các giới hạn của bài toán lập lịch trên một máy bằng cách sử dụng hàm mục tiêu để giảm thiểu thời gian trễ và liệt kê các lịch biểu tích cực.

Cùng thời gian đó một phương pháp heutistic dựa trên các luật ưu tiên được nghiên cứu bởi Gere (1966), Panwalkar và Iskander (1977) và Haupt (1989). Xa hơn nữa một số thuật toán mãnh mẽ được nghiên cứu với các phương pháp tiếp cận tối ưu. Barker và McMahon (1985) đã công bố công trình giải quyết bài toán lập lịch bằng cách sử dụng cấu trúc lân cận dựa trên các thuật toán tìm kiếm địa phương(local search)[5]. Lịch biểu tối ưu của bài toán JSP 10x10 lần đầu tiên được đưa ra bởi Leageweg (1984) nhưng việc chứng minh về tính tối ưu của lịch biểu này không được đưa ra.

Arlier và Pinson (1989) đã chứng minh rằng lịch biểu này là tối ưu và họ được ghi với việc giải quyết bài toán nổi tiếng Fisher và Thompson từ năm 1963[5]. Ngày nay, thuật toán hiệu quả nhất trong số các phương pháp chính xác là thuật toán nhánh cận của Caseau và Laburthe (1995), Baptiste (1995), Carlier và Pinson (1994), Brucker (1994), Brucker (1992) và các kỹ thuật khác nhau sau nhánh cận bởi Applegate và Cook (1991), Martin và Shmoys (1995) và Perregaard và Clausen (1995). Những hướng mới nghiên cứu giải quyết bài toán JSP tại thời điểm hiện tại là phương pháp gần đúng. Phương pháp đầu tiên trong danh sách là phương pháp dịch chuyển nút cổ chai (Shifting Bottleneck) của Adam 1998,Balas (1995), Dauzere-Peres và Lasserre (1993).

Tuy nhiên phần lớn của cách tiếp cận gần đúng là kỹ thuật tìm kiếm địa phương và tiến hóa. Trong kỹ thuật tìm kiếm địa phương và tiến hóa thì các thuật toán mạnh mẽ nhất là thuật toán mô phỏng luyện kim (simulated annealing) của Van Laarhoven (1992), Matsuo (1988) và Yamada (1994), Tìm kiếm Tabu (Taboo z 3 Search)bởi Dell’Amico và Trubian (1993), Taillard (1994), Barnes và Chambers (1995), Nowicki và Smutnicki (1996) và Thomsen (1997), Thuật toán di truyền (Genetic Algorithms)bởi Storer (1992), Yamada và Nakano (1992), Pesch (1993) và Dorndorf và Pesch (1995), vàkỹ thuật Tìm kiếm địa phương có chỉ dẫn (Guided Local Search)đề xuất bởiBalas và Vazacopoulos (1998)[5]. Các tiếp cận đã được đề xuất để giải bài toán JSP được trình bày trong Hình 1. Các phương Các phương pháp gần đúng pháp chính xác Các luật ưu Dịch chuyển tiên nhanh Các kỹ thuật Công thức nút cổ chai nhánh cận toán học Trí tuệ nhân tạo Tìm kiếm Mô phỏng Quy hoạch tuyến địa phương luyện kim tính nguyên Các mạng Tìm kiếm Nơron Taboo Giải thuật di truyền Hình 1.1: Các tiếp cận cho bài toán lập lịch JSP 1.

Tình hình nghiên cứu trong nước Hiện nay, bài toán JSP vẫn đang được quan tâm và nghiên cứu và ngày càng phát triển. Các công trình nghiên cứu về vấn đề này chủ yếu theo hướng các thuật toán đã được đề xuất và ứng dụng ở trên thế giới, từ đó tìm ra các phương pháp để cải tiến làm cho thuật toán tốt hơn. Ứng dụng thực tiễn của bài toán lập lịch chủ yếu trong lĩnh vực đào tạo: xây dựng thời khóa biểu, kế hoạch thi, lịch làm việc, lịch trực bệnh viện,lập kế hoạch sản xuất kinh doanh trong doanh nghiệp. Các phương pháp tiếp cận giải bài toán lập lịch 1.

Cách tiếp cận chính xác, thuật toán nhánh cận Thuật toán nhánh cận là phương pháp hiệu quả nhất trong số các phương pháp chính xác để giải bài toán JSP. Thuật toán nhánh cận là kỹ thuật được phát triển z 4 để giải quyết các bài toán rời rạc và tổ hợp. Mô hình được sử dụng để tìm kiếm là mô hình cây phân cấp. Tư tưởng cơ bản của phương pháp là trong quá trình tìm kiếm lời giải, sẽ phân hoạch tập các phương án của bài toán thành hai hay nhiều tập con biểu diễn như một nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận), tìm cách loại bỏ các nhánh cây (những tập con các phương án của bài toán) mà ta biết chắc chắn không phải là phương án tối ưu.

Mặc dù trong trường hợp xấu nhấtthuật toán sẽ duyệt toàn bộ, nhưng những trường hợp cụ thể nó rút ngắn đáng kể thời gian tìm kiếm. Hiệu quả của thuật toán nhánh cận phụ thuộc cách thức phân nhánh và đánh giá cận. Việc phân nhánh sai sẽ không làm giảm việc bỏ bớt các phương án không tốt hoặc thậm chí cũng không thể thu gọn các miền khả thi xuống. Đánh giá cận sai sẽ tạo ra các nhánh không chính xác làm ảnh hưởng đến số lượng các phương án hoặc các tập con có thể lược bỏ được.

Như vậy thì một chiến lược nhánh cận không tốt sẽ làm giảm việc xác định các phương án khả thi và lúc này thuật toán sẽ liệt kê toàn bộ các cấu hình có thể cho dù bài toán không thực sự lớn. Chính vì thế những quy tắc khác nhau được áp dụng với mục đích làm sao để phân nhánh và đánh giá cận đúng là vấn đề quan trọng trong việc xây dựng thuật toán. Với bài toán lập lịch, thì lịch biểu các công việc được mô tả bằng một đồ thịnối rời (disjunctive graph). Tất cả các công đoạn cùng một công việc được nốithành một chuỗi các cung nối liền và các cung nối rời giữ các công đoạn thực hiệntrên cùng một máy.

Việc lập lịch sẽ trở thành việc sắp thứ tự các công việc trên từngmáy, nghĩa là làm cố định mối liên hệ trước sau giữa các công đoạn trên cùng mộtmáy bằng cách thay đổi hướng các cung nối rời theo một hướng cố định ta sẽ cómột lời giải khả thi, mỗi lời giải khả thi này ta tính được hàm mục tiêu chiềudài lớn nhất đi từ nút nguồn đến nút đích. Một vấn đề gặp phải của phương pháp nhánh cận là thời gian tính toán lớn. Cách tiếp cận gần đúng 1. Giới thiệu Một lớp quan trọng của loại cải tiến thuật toán là thủ tục tìm kiếm địa phương (local search).

Một thủ tục tìm kiếm địa phương không đảm bảo là một lời giải tối ưu.