Nghiên cứu các bài toán lịch biểu và ứng dụng

- TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH.
- Định nghĩa bài toán lập lịch Jobshop (JSP.
- Tình hình nghiên cứu thuật toán tìm kiếm lịch biểu tối ƣu.
- Các phƣơng pháp tiếp cận giải bài toán lập lịch.
- Cách tiếp cận chính xác, thuật toán nhánh cận.
- THUẬT TOÁN DI TRUYỀN.
- Lƣu đồ thuật toán di truyền đơn giản.
- Các tham số của thuật toán di truyền.
- HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP Error!.
- Bài toán Flowshop hoán vị.
- Mô tả bài toán.
- Cách tính thời gian hoàn thành trong một lịch biểu hoán vị.
- Thuật toán Johnson cho PFSP 2 máy và PFSP 3 máyError! Bookmark not defined..
- Một thuật di truyền mã hóa tự nhiên cho bài toán FSP tổng quát.
- Bài toán lập lịch Flowshop.
- Mô bài toán.
- 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 Error!.
- MỘT THUẬT TOÁN DI TRUYỀN LAI CHO BÀI TOÁN LẬP LỊCH JOB SHOP.
- Thuật toán Giffler - Thompson (GT.
- Áp dụng thuật toán GT cho JSP để sinh ra các lịch biểu tích cực.
- Một thuật toán di truyền lai tuần tự cho bài toán JSP.
- Thuật toán di truyền.
- Tính đúng đắn của thuật toán.
- Lập lịch là một chủ đề quan trọng trong lĩnh vực nghiên cứu hoạt động xuất hiện từ đầu những năm 1950.
- Mục tiêu chính của lập lịch là phân phối một cách hiệu quả tài nguyên dùng chung qua thời gian hoàn thành các tác vụ..
- Có rất nhiều các bài toán quan trọng trong thực tế của lập lịch nhƣ: Lập lịch sản xuất.
- lập lịch xếp lớp cho giảng viên.
- lập lịch thực hiện công việc cho dự án.
- lập lịch trực cho bác sỹ, y tá trong bệnh viện.
- lập lịch hàng không, lập lịch tàu hỏa….
- Với nhiều ứng dụng nhƣ vậy việc nghiên cứu và đƣa ra một thuật toán có thể thống kê một lịch biểu để thực hiện công việc hoàn thành trong thời gian tối ƣu là vô cùng quan trọng..
- Từ năm 1950 đến nay mặc dù có rất nhiều công trình nghiên cứu về lập lịch đƣợc đề xuất.
- Nhƣng có hai vấn đề cần quan tâm xung quanh bài toán lập lịch đó là lịch biểu thực hiện công việc đã tối ƣu chƣa và tốc độ thực hiện của thuật toán là nhanh hay chậm.
- Xuất phát từ hai vấn đề đó, có hai phƣơng pháp tiếp cận chính để giải bài toán lập lịch đó là phƣơng pháp chính xác và phƣơng pháp gần đúng..
- Phƣơng pháp thứ nhất là phƣơng pháp chính xác.
- Với phƣơng pháp này thì ƣu điểm lớn nhất là sẽ tiến hành tìm kiếm trên toàn bộ không gian bài toán và kết quả sẽ luôn tìm đƣợc một lịch biểu thực hiện các công việc tối ƣu.
- Phƣơng pháp chính xác nhìn nhận sâu vào vấn đề bài toán, đƣa ra đƣợc những quyết định với các thông tin quan trọng về cấu trúc của vấn đề hoặc phân tích chính xác các lịch biểu.
- Tuy nhiên do bản chất là vét cạn nên có nhiều hạn chế khả năng áp dụng phƣơng pháp này nhƣ tốn nhiều chi phí thực hiện, mất nhiều thời gian xử lý để tìm ra lời giải.
- Một số thuật toán giải quyết bài toán lập lịch theo phƣơng pháp tiếp cận nàytiêu biểu nhƣ các kỹ thuật nhánh cận (Branch and Bound), Quy hoạch tuyến tính nguyên (Integer Linear Programming)....Trong đó, thuật toán nhánh cận đƣợc đánh giá là thuật toán tốt nhất trong các thuật toán nghiên cứu theo phƣơng pháp tiếp cận chính xác..
- Phƣơng pháp thứ hai là phƣơng pháp gần đúng sử dụng các hàm ƣớc lƣợng heuristic đánh giá để tìm lịch biểu công việc, việc sử dụng các hàm ƣớc lƣợng này có nhƣợc điểm lớn là lời giải của phƣơng pháp tìm ra không đƣợc chắc chắn là lời giải tối ƣu nhất.
- Kết quả của bài toán bị ảnh hƣởng bởi các thông số (kích thƣớc của tập hợp, lời giải ban đầu của thuật toán, các lân cận.
- Và cách thức để giải quyết bài toán đôi khi đƣợc xem nhƣ kỹ xảo để xử lý hơn là khoa học.
- Tuy nhiên phƣơng pháp này lại có lợi thế hơn so với phƣơng pháp chính xác là chi phí thời gian tìm kiếm để đƣa ra lời giải thấp.
- Gần đây một số thuật toán mạnh mẽ đƣợc tiếp cận bằng phƣơng pháp gần đúng điển hình nhƣ là: “Taboo Search”, “Simulated Annearling”, “Genetic Algorithms”,.
- Trong lĩnh vực lập lịch, một mô hình chung nhất cho lập lịch là bài toán lập lịch Jobshop (Jobshop Scheduling Problem)viết tắt JSP.
- Bài toán này 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.
- 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.
- Vì vậy em mạnh dạn chọn đề tài 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”..
- 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..
- 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..
- Đị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:.
- Thời gian xử lý thao tác 𝑂 𝑖𝑗 đƣợ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.1.
- Công việc Máy (thời gian xử lý).
- Bảng 1.1: Bài toán JSP 3 công việc, 3 máy.
- 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.2.1.
- 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.
- 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..
- 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).
- 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.
- 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.1..
- Hình 1.1: Các tiếp cận cho bài toán lập lịch JSP 1.2.2.
- 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.2.3.
- 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.
- Các phƣơng pháp chính xác.
- Tìm kiếm.
- Tìm kiếm Taboo.
- để giải quyết các bài toán rời rạc và tổ hợ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.
- 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.
- 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).
- 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..
- 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).
- 1.Nguyễn Hữu Mùi(2013), Thuật toán và các bài toán lịch biểu, Luận án Tiến sĩ, Trƣờng Đại học Công nghệ, Đại học Quốc Gia Hà Nội..
- 3.Pham Việt Anh, Bùi Thu Lâm(2013), Giải thuật di truyền và ứng dụng trong hỗ trợ lập lịch điều hành công tác bệnh viện, Chuyên san công nghệ thông tin và Truyền thông - Số 02, tr.95-98..
- 4.Vũ Đình Trung (2012), Song song hóa bài toán JSP trên một số môi trường tính toán song song và phân tán, Luận văn Thạc sĩ, Trƣờng Đại học Lạc Hồng.