Thuật toán và các bài toán lịch biểu

- Thuật toán và các bài toán lịch biểu.
- Nghiên cứu về tổng quan của bài toán: Phân tích, đánh giá, so sánh các tiếp cận đã áp dụng cho các bài toán lập lịch job shop, trên cơ sở đó đề xuất một số hƣớng nghiên cứu cho bài toán này.
- Nghiên cứu và đề xuất một thuật toán lai mới 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 lập lịch job shop..
- Phƣơng pháp đề xuất này đã đƣợc thử nghiệm trên các bài toán test chuẩn và so sánh kết quả với các giải pháp trƣớc đó để chứng tỏ tính vƣợt trội của nó.
- Song song hóa thuật toán đã đề xuất cho bài toán lập lịch job shop, thuật toán đã đƣợc cài đặt và chạy thử nghiệm cho kết quả tốt và rút ngắn đƣợc nhiều lần thời gian thực thi với cùng bộ tham số và dữ liệu vào trong thuật toán tuần tự.
- Chứng minh tính hội tụ của thuật toán di truyền lai mới với mã hóa tự nhiên cho bài toán lập lịch job shop đã đề xuất..
- Thuật toán di truyền.
- Bài toán lịch biểu.
- Các bài toán lập lịch rất đa dạng, chúng xuất hiện trong các lĩnh vực khác nhau nhƣ:.
- Các ví dụ khác về lập lịch bao gồm các bài toán vận chuyển (chẳng hạn nhƣ bài toán ngƣời du lịch, lập lịch hàng không, lập lịch tầu hỏa.
- các bài toán lập lịch tính toán (chẳng hạn nhƣ lập lịch CPU, lập lịch phân công,...)..
- Chẳng hạn nhƣ thuật toán di truyền phỏng theo học thuyết tiến hóa của Darwin đƣợc áp dụng khá rộng rãi cho các bài toán lập lịch..
- Trong lĩnh vực lập lịch, một mô hình tổng quát nhất về lập lịch đó là bài toán lập lịch job shop (Job shop Scheduling Problem - JSP), bài toán này thuộc lớp NP-hard (NP là lớp các bài toán giải đƣợc bởi một thuật toán không đơn định trong thời gian đa thức) và 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 tới nay.
- JSP cũng là một trong những bài toán đƣợc nghiên cứu nhiều nhất và là một mô hình phát triển tốt về lý thuyết lập lịch.
- Các tiếp cận này đƣa ra các lời giải tối ƣu thực sự cho bài toán.
- Về mặt lý thuyết, các tiếp cận chính xác đóng vai trò quan trọng và đã đƣợc áp dụng thành công cho một số bài toán lập lịch có kích cỡ nhỏ.
- Tuy nhiên, các tiếp cận này đòi hỏi khá nhiều thời gian thực thi ngay cả với các bài toán cỡ trung bình.
- Thậm chí, để tìm ra một lời giải thỏa mãn hoàn toàn các ràng buộc của bài toán có thể yêu cầu thời gian tính toán tăng theo hàm mũ trong khi cỡ bài toán chỉ tăng theo tuyến tính..
- Trong thực tế, chúng ta thƣờng phải giải quyết các bài toán lập lịch có kích cỡ lớn trong một khoảng thời gian khả thi với các kết quả chấp nhận đƣợc (các kết quả này không nhất thiết là phải tối ƣu thực sự).
- Tuy nhiên, cho tới nay chƣa có một tiếp cận nào đã đƣợc đề xuất có thể giải quyết triệt để bài toán lập lịch job shop tổng quát, nhất là đối với JSP có nhiều máy và nhiều công việc.
- Một số vấn đề chính liên quan tới việc giải quyết bài toán này còn tồn tại nhƣ sau:.
- Tính hội tụ của các thuật toán mới đƣợc đề xuất chƣa đƣợc chứng minh dựa trên cơ sở toán học..
- Ở nƣớc ta, việc nghiên cứu về bài toán lập lịch job shop vẫn chƣa phát triển..
- Trong các trƣờng đại học, đại đa số các sinh viên, học viên cao học về công nghệ thông tin vẫn chƣa biết tới bài toán này.
- Trong những năm gần đây đã xuất hiện một số báo cáo khoa học đề cập tới bài toán này.
- Tuy nhiên, kết quả đạt đƣợc còn rất khiêm tốn, chƣa tƣơng xứng với tầm quan trọng của bài toán..
- Vì những lý do trên, luận án chọn đề tài "Thuật toán và các bài toán lịch biểu".
- Phạm vi nghiên cứu của đề tài chủ yếu tập trung vào thuật toán di truyền và bài toán lập lịch job shop..
- Trên cơ sở đó đề xuất một giải pháp mới cho bài toán này..
- Đề xuất một thuật toán di truyền lai mới cho JSP và song song hóa thuật toán nhằm khắc phục độ phức tạp tính toán vốn có của các JSP cỡ lớn..
- Chứng minh tính hội tụ của thuật toán di truyền lai với mã hóa tự nhiên áp dụng cho JSP mà luận án đề xuất..
- Đối tƣợng nghiên cứu: Thuật toán và các bài toán lịch biểu..
- Phạm vi nghiên cứu: Ứng dụng thuật toán di truyền giải quyết bài toán lập lịch job shop..
- Phƣơng pháp nghiên cứu dựa trên thực nghiệm: Thông qua việc thử nghiệm trên các bài toán test chuẩn và đối sánh với các kết quả đã công bố..
- Nghiên cứu về tổng quan của bài toán: Phân tích, đánh giá, so sánh các tiếp cận đã áp dụng cho các bài toán lập lịch job shop.
- Trên cơ sở đó đề xuất một số hƣớng nghiên cứu cho bài toán này..
- Nghiên cứu và đề xuất một thuật toán lai mới 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 lập lịch job shop.
- Phƣơng pháp đề xuất này đã đƣợc thử nghiệm trên các bài toán test chuẩn và so sánh kết quả với các giải pháp trƣớc đó để chứng tỏ tính vƣợt trội của nó..
- Song song hóa thuật toán đã đề xuất cho bài toán lập lịch job shop, thuật toán đã đƣợc cài đặt và chạy thử nghiệm cho kết quả tốt và rút ngắn đƣợc nhiều lần thời gian thực thi với cùng bộ tham số và dữ liệu vào trong thuật toán tuần tự..
- Chứng minh tính hội tụ của thuật toán di truyền lai mới với mã hóa tự nhiên cho bài toán lập lịch job shop mà luận án đề xuất..
- Luận án có thể đƣợc sử dụng làm tài liệu tham khảo cho các sinh viên đại học và các học viên cao học ngành công nghệ thông tin làm đề tài về thuật toán di truyền và ứng dụng giải các bài toán tối ƣu..
- Nếu đƣợc đầu tƣ về tài chính và nhân lực, luận án có thể đƣợc hoàn thiện và áp dụng để giải quyết các bài toán trong thực tiễn về qui hoạch và tối ƣu hóa..
- TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP.
- Chƣơng này trình bày vắn tắt về thuật toán di truyền cổ điển (mã hóa nhị phân), phân tích, đánh giá các giải pháp quan trọng nhất cho JSP đã đƣợc công bố trong những năm qua.
- Nhận diện những khó khăn khi giải quyết bài toán lập lịch job shop mà chúng ta cần phải vƣợt qua trong hiện tại và tƣơng lai.
- Sau khi phân tích, đánh giá, luận án đề xuất một số hƣớng nghiên cứu cho bài toán này..
- CHƢƠNG 2: HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP Bài toán flow shop và flow shop hoán vị là hai trƣờng hợp riêng của bài toán job shop rất thƣờng gặp trong thực tiễn.
- 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 và thuật toán Johnson cho bài toán flow shop 2 máy và 3 máy có hạn chế điều kiện.
- Cuối cùng, một thuật toán di truyền mã hóa số tự nhiên đƣợc đề xuất cho hai bài toán này..
- CHƢƠNG 3: MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP.
- Bài toán lập lịch job shop là bài toán lập lịch tổng quát nhất và cũng khó giải quyết nhất.
- Trong chƣơng này, luận án đề xuất một thuật toán di truyền lai mới cho JSP.
- Thuật toán đƣợc cài đặt và chạy thử nghiệm trên các bài toán test chuẩn, các kết quả tính toán đã khẳng định tính.
- Để khắc phục độ phức tạp tính toán của JSP, thuật toán đã đƣợc song song hóa, cài đặt và chạy thử nghiệm trên các bài toán test chuẩn.
- CHƢƠNG 4: PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP.
- Trong chƣơng này, luận án phân tích thuộc tính hội tụ của thuật toán đã đề xuất bằng cách áp dụng các tính chất của xích Markov.
- A Computational Study of Local Search Algorithms for Job-Shop Scheduling", ORSA Journal on Computing Vol.
- 6 (2), pp.118-125..
- The shifting bottleneck procedure for job shop scheduling", Management Science Vol.
- Andrea Rossi và Elena Boschi A hybrid heuristic to solve the parallel machines job shop sheduling problem", Advances in Engineering.
- A Computational Study of the Job- Shop Scheduling Problem", ORSA Journal on Computing, Spring Vol.
- Nasser Mebarki Discovering dispatching rules for job shop scheduling problem through data mining", www.enim.fr/mosim2010/articles/206.pdf.
- (1994), A polynomial time algorithm for the two machines Job Shop scheduling problem with a fixed number of jobs, OR Spektrum 16, pp.
- An algorithm for solving the job-shop problem", Management Science Vol.
- A Tutorial Survey of Job-Shop Scheduling Problems using Genetic Algorithms-I", Representation, Computers &.
- Dominique Feillet A branch and bound method for the job-shop problem with sequence-dependent setup times",.
- Ant- System for Job-Shop Scheduling", Belgian Journal of Operations Research, Statistics and Computer Science Vol.
- Deming Lei, "Fuzzy job shop scheduling problem with availability constraints", Computers &.
- Surrogate Duality Relaxation for Job-Shop Scheduling", Discrete Applied Mathematics Vol.
- The complexity of flow shop and job shop scheduling", Mathematics of Operations Research Vol..
- Heuristic Methods for Solving Job-Shop Scheduling Problems", www.en.scientificcommons.org Hoa Kỳ..
- Hybrid Rollout Approaches for the Job Shop Scheduling Problem", Jounal Optimization Theory and Applications Vol..
- Two-Machines Unit-Time Job-Shop Schedule-Length Problem", Mathematics of Operations Research Vol.
- Ching-Yu Wang A Tabu Genetic algorithm with Search Area Adaptation for the Job-Shop Scheduling Problem", Proceedings of the 6 th WSEAS Int.
- Yun Qian Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problems", Journal of Bionic Engineering Vol.
- GA with Priority Rules for Solving Job- Shop Scheduling Problems", Evolutionary Computation, CEC 2008 (IEEE World Congress on Computational Intelligence), pp.
- A Heuristic Approach for Large Scale Job Shop Scheduling Problems", Journal of Applied Sciences Vol.
- Kewei Yang Knowledge-based ant colony optimization for the flexible job shop scheduling problems", Dynamics of Continuous, Discrete and Impulsive Systems, Series B:.
- Hsu A Parallel Distributed Processing Technique for Job- Shop Scheduling Problems", IJCNN International Joint Conference on Neural Networks, Nagoya, Japan, 25-29 Oct, Vol.
- On the Job-Shop Scheduling Problem", Operations Research Vol.
- Miloš Šeda (2007), Mathematical Models of Flow Shop and Job Shop Scheduling Problems, World Academy of Science, Engineering and Technology 31..
- Job-Shop Scheduling Problem With Sequence Dependent Setup Times", Proceedings of the International.
- (2005), “Genetic Local Search for Job Shop Scheduling Problem”, www.essex.ac.uk/technical- reports/2005/ csm435.pdf.
- Conventional genetic algorithm for job shop problems", In Proceedings of International Conference on Genetic Algorithms (ICGA ’91), pp.
- Jaime Giraldo Job shop methodology based on an ant colony", Dyna, Año 76 (159), pp.
- Ramezanali Mahdavinejad A New Approach to Job Shop Scheduling Problem", Journal of Achievements in Materials and Manufacturing Engineering Vol.
- Machine aggregation heuristics in shop scheduling", Methods of Operations Research Vol.
- Cheng Wu Bottleneck machine identification based on optimization for the job shop scheduling problem", ICIC Express Letters Vol.
- ChengWu Bottleneck identification procedures for the job shop scheduling problem with applications to genetic algorithms", International Journal Advanced Manufacturing Technology Vol.
- Cheng Wu A hybrid approach to large-scale job shop scheduling", Application Intelligence Vol.
- Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem", Artificial Intelligence Vol.
- Solving Fuzzy based Job Shop Scheduling Problems using Ga and Aco", Journal of Emerging Trends in Computing and Information Sciences Vol.
- Job shop scheduling by simulated annealing", Operations Research Vol.
- Dynamic job-shop scheduling with sequence-dependent setup times: simulation modeling and analysis", International Journal Advanced Manufacturing Technology Vol.
- Job-Shop Scheduling by Simulated Annealing Combined with Deterministic Local Search", MIC’95 Meta- heuristics International Conference, Hilton, Breckenridge, Colorado, USA, July 22-26, pp.
- Yan Chen A Genetic Algorithm for Job-Shop Scheduling", Journal of Software Vol.
- Yan Chen Hybrid Algorithm Approach To Job Shop Scheduling Problem", Global Journal of Computer Science and Technology Vol.
- An Approach to the Autonomous Job-Shop Scheduling Problem by Vibrating potential Method", IEEE ICNN'94 International Conference on Neural Network, Orlando, Florida, 26-29 June Vol.
- A very fast TS/SA algorithm for the job shop scheduling problem", Computers and Operations Research Vol.
- Zhi Huang, "A Modified Shifting Bottleneck Procedure for Job Shop Scheduling", www.paper.edu.cn/index.php/default/releasepaper/...