Parallel machine scheduling: Min total lateness | Báo cáo bài tập lớn học phần Thuật toán ứng dụng | Trường Đại học Phenikaa

Trường Đại Học Phenikaa
Khoa Công Nghệ Thông Tin ***** BÀI TẬP LỚN
Đề tài : Parallel Machine Scheduling: Min Total Lateness
Giảng viên hướng dẫn: TS. Hà Minh Hoàng
ThS. Nguyễn Minh Anh
Sinh viên thực hiện : Đinh Tiến Đạt – 21013111
Đỗ Thanh Hải - 21011122
Học phần: Thuật Toán Ứng Dụng Hà Nội, 25/05 Lời mở đầu
Thuật toán là một tập hợp các quy trình logic được sắp xếp một cách cụ thể
để giải quyết một vấn đề cụ thể hoặc thực hiện một nhiệm vụ cụ thể. Nó là một
bước quyết định theo trình tự để giải quyết một vấn đề bằng cách thực hiện một
loạt các phép tính hoặc hoạt động trên đầu vào được cung cấp để đạt được đầu ra mong muốn.
Thực tế, thuật toán đã và đang được áp dụng trong hầu hết các lĩnh vực của
cuộc sống và công nghiệp, đóng góp đáng kể vào sự phát triển và tiến bộ của chúng
ta. Giúp cho máy móc có thể thay thế con người lao động và làm việc , cuộc sống
ngày càng tiến bộ và tiện ích
Trong đó Parallel Machine Scheduling: Min Total Lateness là một loại thuật
toán thuộc lĩnh vực lập lịch (scheduling) trong khoa học máy tính. Nhiệm vụ của
thuật toán này là lập lịch cho một tập hợp các công việc (jobs) được thực hiện trên
một tập hợp các máy (machines) song song. Mục tiêu của thuật toán là tối thiểu hóa
tổng thời gian trễ (total lateness). Trong bài báo cáo này chúng em xin tìm hiểu,
làm rõ và triển khai , giải quyết vấn đề của thuật toán. Mục Lục Lời Mở Đầu 1. Tổng quan
1.1. Mô tả bài toán ...............................................................................
1.2.Định nghĩa độ trễ............................................................................
2.Phương pháp giải thuật( thuật toán heuristic) ...................................
2.1.Tìm hiểu chung về giải thuật di truyền...........................................
2.2. Các toán tử của giải thuật di truyền...............................................
2.3. Các tham số của giải thuật di truyền..............................................
2.4. Các thành phần của giải thuật di truyền.........................................
2.5. Ưu điểm của thuật toán di truyền ..................................................
2.6. Nhược điểm của thuật toán di truyền ............................................. 3
Ứng dụng của thuật toán di truyền ....................................................
3.1. Ứng dụng trong lập lịch công việc ................................................
3.2. Lập thời khóa biểu cho trường học ................................................
3.3. Tìm kiếm đường đi.........................................................................
3.4. Vạch đường cho robot di chuyển ...................................................
4.Cài đặt và triển khai thuật toán ........................................................... 5.Tổng
kết...............................................................................................
6. Bảng phân công công việc.................................... .............................
7. Tài liệu tham khảo.................................... ......................................... 1.Tổng quan 1.1 Mô tả bài toán :
Bài toán Parallel Machine Scheduling: Min Total Lateness yêu cầu xếp n công việc
(job) vào m máy (machine) giống nhau. Mỗi công việc i có thời gian xử lý t_i và
thời hạn hoàn thành d_i. Mục tiêu của bài toán là tạo ra một lịch trình sao cho tổng
độ trễ của tất cả các công việc là ít nhất có thể.
1.2 Định nghĩa độ trễ
Độ trễ của một công việc i, ký hiệu là delta_i, được định nghĩa là chênh lệch giữa
thời gian hoàn thành t_i và thời hạn hoàn thành d_i. Độ trễ delta_i = max(0, t_i -
d_i). Một công việc được xem là đúng hạn nếu thời gian hoàn thành của nó trước
hoặc bằng thời hạn d_i, và được xem là muộn nếu thời gian hoàn thành sau thời hạn d_i.
Ví dụ : Học Sinh A được giao bài tập về nhà vào thứ 2, hạn hoàn thành bài
tập là thứ 4 cùng tuần. Sinh viên A hoàn thành và nộp bài tập vào thứ 5. Vậy độ trễ
của sinh viên A là 1 ngày. Bài tập được coi là đúng hạn nếu Sinh viên A hoàn thành
và nộp bài tập trước hoặc vào đúng ngày thứ 4 tuần đó.
2.Phương pháp giải thuật (thuật toán heuristic) 2.1
Tìm hiểu chung về thuật giải di truyền
Genetic algorithms (thuật giải di truyền) là một giải thuật mô phỏng theo quá trình
chọn lọc tự nhiên, là kỹ thuật chung giúp giải quyết vấn đề bài toán bằng cách mô
phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa trên thuyết tiến
hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường. Lấy ý
tưởng từ quá trình tiến hoá tự nhiên, xuất phát từ một lớp các lời giải tiềm năng ban
đầu, thuật giải di truyền tiến hành tìm kiếm trên không gian lời giải bằng cách xây
dựng lớp lời giải mới tốt hơn (tối ưu hơn) lời giải cũ. Quá trình xây dựng lớp lời
giải mới được tiến hành dựa trên việc chọn lọc, lai ghép, đột biến từ lớp lời giải ban
đầu. Quần thể lời giải trải qua quá trình tiến hoá: ở mỗi thế hệ lại tái sinh các lời
giải tương đối tốt, trong khi các lời giải “xấu” thì chết đi.
Vậy thuật giải di truyền làm gì?
Trong thuật giải di truyền, một tập các biến của bài toán đưa ra được mã hóa sang
một chuỗi (hay một cấu trúc mã hóa khác) tương tự như một nhiễm sắc thể trong tự
nhiên. Mỗi chuỗi bao gồm một giải pháp có thể của bài toán. Giải thuật di truyền sử
dụng các toán tử được sinh ra bởi sự chọc lọc tự nhiên một quần thể các chuỗi nhị
phân (hoặc các cấu trúc khác), mã hóa khoảng tham số trên mỗi thế hệ, khảo sát
các phạm vi khác nhau của không gian tham số, và định hướng tìm kiếm đối với
khoảng mà là xác suất cao để tìm kiếm sự thực hiện tốt hơn. Thuật toán di 7 truyền
gồm có bốn quy luật cơ bản là lai ghép, đột biến, sinh sản và chọn lọc tự nhiên.
Quá trình lai ghép (phép lai) quá trình này diễn ra bằng cách ghép một hay nhiều
đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc
tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: Chọn ngẫu nhiên hai hay
nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều
dài là m. Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1. Như vậy,
điểm lai này sẽ chia hai chuỗi nhiễm sắc thể chamẹ thành hai nhóm nhiễm sắc thể
con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và
m21+m12. Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá
trình tiến hóa quá trình đột biến (phép đột biến) quá trình tiến hóa được gọi là quá
trình đột biến khi một hoặc một số tính trạng của con không được thừa hưởng từ
hai chuỗi nhiễm sắc thể cha-mẹ. Phép đột biến xảy ra với xác suất thấp hơn rất
nhiều lần so với xác suất xảy ra phép lai.
Phép đột biến có thể mô tả như sau:
- Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m - Thay đổi giá trị của gen thứ k
- Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo
Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) Phép tái sinh: là
quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ thích
nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của
nó. Phép tái sinh có thể mô phỏng như sau:
- Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá
trị thích nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi
Giả sử quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn
thứ i là Ft. Tổng độ thích nghi là Fm Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm
- Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới.
Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt.
Phép chọn được mô tả như sau:
- Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần - Loại bỏ các cá thể cuối
dãy, chỉ để lại n cá thể tốt nhất. .
Sau đây là những nguyên tắc cơ bản thực hiện giải thuật di truyền:
B1 Khởi tạo quần thể ban đầu: Tạo ra một tập hợp ngẫu nhiên các cá thể biểu diễn
các lời giải ứng viên.
B2: Đánh giá (evaluation): Đánh giá chất lượng của mỗi cá thể bằng cách áp dụng
hàm mục tiêu (objective function) lên genotypes của chúng. Hàm mục tiêu đo lường
mức độ tối ưu của lời giải.
B3: Lựa chọn (selection): Chọn lọc các cá thể tốt nhất trong quần thể dựa trên chất
lượng của chúng. Các cá thể tốt hơn có khả năng cao được chọn để tiếp tục vào các
thế hệ tiếp theo. theo độ thích nghi. Đó sẽ là cha mẹ của những thế hệ tiếp theo.
B4: Lai ghép (crossover): Tạo ra các cá thể mới bằng cách kết hợp thông tin gen từ
hai cá thể cha mẹ. Quá trình lai ghép tạo ra sự đa dạng genotypes và tạo ra các cá thể
mới có tiềm năng tốt hơn.
B5: Đột biến (mutation): Đột biến ngẫu nhiên một số gen trong cá thể mới nhằm tạo
ra đột phá và khám phá không gian tìm kiếm. Quá trình đột biến giúp duy trì đa dạng genotypes trong quần thể.
B6: Tiến hóa thế hệ tiếp theo: Tạo ra thế hệ mới bằng cách lặp lại các bước từ 2 đến
5. Quá trình tiến hóa diễn ra qua nhiều thế hệ cho đến khi đạt được lời giải tối ưu
hoặc đáp ứng tiêu chí dừng khác nhau.
B7: Trả về lời giải tốt nhất: Sau khi quá trình tiến hóa kết thúc, thuật giải di truyền
trả về lời giải tốt nhất tìm được trong quần thể cuối cùng. Lời giải này đại diện cho
một giải pháp tối ưu hoặc gần tối ưu cho bài toán cần giải quyết.
2.2. Các toán tử của giải thuật di truyền + Toán tử chọn lọc
- Chọn lọc dựa trên độ thích nghi.
- Chọn lọc dựa trên sự xếp hạng
- Chọn lọc dựa trên sự cạnh tranh
- Chọn lọc hướng không gian + Toán tử di cư + Toán tử nghịch đảo + Toán tử đột biến + Toán tử lai ghép
- Lai ghép một điểm (one-point crossover)
- Lai ghép hai điểm (two-point crossover)
- Lai ghép N điểm (N-point crossover) - Lai ghép đồng nhất (Uniform crossover)
2.3 Các tham số của giải thuật di truyền.
Xác suất lai ghép: là tham số cho biết tần suất thực hiện toán tử lai ghép.
Nếu không có lai ghép, cá thể con sẽ chính là bản sao của cá thể “cha mẹ”. Nếu xác
suất lai ghép bằng 100%, khi đó mọi cá thể con đều được tạo ra qua quá trình lai ghép.
Xác suất đột biến: là tham số cho biết tần suất đột biến của nhiễm sắc thể.
Nếu không có đột biến, thế hệ con được tạo ra nthuật giải di truyềny sau giai đoạn
lai ghép mà không bị thay đổi. Ngược lại, một hoặc một số phần của nhiễm sắc thể
sẽ bị thay đổi. Nếu xác suất đột biến là 100%, toàn bộ nhiễm sắc thể sẽ bị thay đổi.
Nếu tham số này bằng 0%, không có gì bị thay đổi hết .
Kích thước quần thể: là tham số cho biết có bao nhiêu cá thể (NST) trong 1 thế hệ
của quần thể. Nếu có quá ít cá thể, khả năng thực hiện lai ghép rất nhỏ và khi đó chỉ
có một vùng tìm kiếm nhỏ 10 mới được khảo sát. Ngược lại, việc kích thước quần
thể quá lớn cũng không tốt, do nó sẽ làm chậm quá trình giải bài toán.
2.4. Các thành phần của thuật giải di truyền
Khởi động quần thể ban đầu
Tạo quần thể đầu tiên trong thuật giải, là nơi xuất phát quá trình tiến hóa, bao gồm
tất cả các giá trị thô ban đầu. Tùy theo vấn đề của bài toán mà có cách khởi động
khác nhau. Trước một bài toán áp dụng thuật giải di truyền, ta cần phải xác định rõ
nhiễm sắc thể và cá thể cho vấn đề, và thông thường đó sẽ kết quả cuối cùng. Việc
phân tích sẽ dựa trên kết quả là cơ bản nhất. Đánh giá cá thể Chắc chắn rằng việc
chọn cá thể sẽ thông qua kết quả, hay mục đích của vấn đề. Dựa trên mức độ thích
nghi của cá thể, bao gồm những vướng mắc mà cá thể gặp phải. Thông thường, đặt
mỗi vấn đề nhỏ tương ứng với một giá trị điểm thích nghi, kết quả đánh giá gồm tổng
các số điểm đó. Cá thể tốt nhất sẽ có số điểm thấp nhất hoặc lớn nhất.
Theo thuyết tiến hóa của Darwin, nhiễm sắc thể tốt nhất sẽ tồn tại và tạo ra các cá
thể con mới. Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất.
1) Chọn lọc Roulette (Roulette Wheel Selection)
2) Chọn lọc xếp hạng (Rank Selection)
3) Chọn lọc cạnh tranh (Tournament Selection) Toán tử lai ghép
Lai ghép nhằm nâng cao kết quả cá thể, do đó, toán tử lai ghép sẽ tạo điều kiện cho
tiến trình hội tụ nhanh hay chậm. Còn tùy thuộc vào cách tổ chức và phân bố các
nhiễm sắc thể mà chúng ta có xác suất lai ghép nhanh hay chậm. Sau đây là vài
phương pháp lai ghép thông dụng trong kỹ thuật di truyền:
1) Lai ghép ánh xạ từng phần (PMX Partial Mapped Crossover)
2) Lai ghép có trật tự (OX Order Crossover)
3) Lai ghép dựa trên vị trí (Position Based Crossover)
4) Lai ghép dựa trên thứ tự (Order Base Crossover)
5) Lai ghép có chu trình (CX Cycle Crossover)
6) Lai ghép thứ tự tuyến tính (LOX Linear Order Crossover) Toán tử đột biến
Cũng giống như lai ghép, toán tử đột biến làm tăng nhanh quá trình hội tụ, nhưng
tăng một cách đột ngột, cũng có khi sẽ không gây tác dụng gì một khi không thành
công. Không ai có thể đánh giá được phương pháp đột biến nào tốt hơn, do đó có
một vài phương pháp đơn giản, cũng có vài trường hợp khá phức tạp. Người ta
thường chọn một trong những phương pháp sau :
1) Đột biến đảo ngược (Inversion Mutation)
2) Đột biến chèn (Insertion Mutation)
3) Đột biến thay thế (Displacement Mutation)
4) Đột biến tương hỗ (Reciprocal Exchange Mutation)
5) Đột biến chuyển dịch (Shift Mutation) Điều kiện kết thúc
Thoát ra quá trình tiến hóa quần thể, dựa vào bài toán mà có các cách kết thúc vấn
đề khác nhau, một khi đã đạt đến mức yêu cầu. Một vài trường hợp thông thường như sau: -
Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì chấm dứt thuật
giảidi truyềny quá trình thực hiện. -
Kết thúc dựa vào số thế hệ: chọn số thế hệ, quá trình sẽ dừng đúng hệ đã quy
địnhtrước, không cần biết kết quả như thế nào. -
Tính theo thời gian: không cần biết đã bao nhiêu thế hệ hay kết quả nào, chỉ
dựavào số giờ qui định mà kết thúc.
-Tổ hợp: dùng nhiều phương án khác nhau cho vấn đề, chẳng hạn như: chạy theo số
thế hệ xong sau đó đánh giá cho chạy theo kết quả, hoặc ngược lại.
2.5 Ưu điểm của thuật toán di truyền
- Tính linh hoạt: Thuật giải di truyền có thể áp dụng cho nhiều loại bài toán tối ưu
hóa và có khả năng tìm kiếm trên không gian tìm kiếm lớn.
- Khả năng tìm kiếm không gian tìm kiếm phức tạp: Thuật giải di truyền có thể
khám phá và tìm kiếm trong không gian tìm kiếm có nhiều biến số và ràng buộc phức tạp.
- Dễ dàng triển khai: Thuật giải di truyền có cấu trúc đơn giản và dễ triển khai. Nó
không yêu cầu thông tin chi tiết về bài toán và có thể áp dụng một cách tương đối dễ dàng.
2.6 Nhược điểm của thuật toán di truyền
- Tốn thời gian: Quá trình tiến hóa trong thuật giải di truyền có thể tốn nhiều thời
gian tính toán, đặc biệt đối với các bài toán có không gian tìm kiếm lớn và quần thể lớn.
- Khả năng rơi vào cực tiểu cục bộ: Thuật giải di truyền không đảm bảo tìm ra lời
giải tối ưu toàn cục và có thể rơi vào cực tiểu cục bộ.
- Tham số đầu vào: Thuật giải di truyền yêu cầu lựa chọn và điều chỉnh các tham
số như kích thước quần thể, tỉ lệ lai ghép, tỉ lệ đột biến, v.v. để đạt hiệu suất tốt.
3.Ứng dụng của thuật toán heuristic (di truyền)
Đối với bài toán Parallel Machine Scheduling: Min Total Lateness
Bài toán Parallel Machine Scheduling: Min Total Lateness nói riêng và thuật toán
di truyền nói chung có rất nhiều ứng dụng trong cuộc sống. Đặc biệt là việc xếp lịch và sắp xếp công việc.
3.1 Ứng dụng trong lập lịch công việc
Lập lịch là bài toán tổ chức sản xuất. Một công ty cần sản xuất nhiều loại hàng
hóa; những hàng hóa này có thể được sản xuất theo những kế hoạch khác nhau. Mỗi
kế hoạch xử lý gồm một chuỗi thao tác; những thao tác này sử dụng một số tài
nguyên và cần thời gian chạy máy. Một lịch sản xuất là một kế hoạch thực hiện các
đơn đặt hàng. Trong đó, một số đơn đặt hàng có thể được thực hiện với cùng những
thao tác tương đương. Nhiệm vụ là lên kế hoạch, lập lịch sản xuất, để thực hiện các
đơn đặt hàng này nhanh nhất có thể. Bài toán lập lịch là chọn một chuỗi các thao tác
đồng thời chỉ định về thời gian bắt đầu/ kết thúc và các tài nguyên cần thiết cho mỗi
thao tác. Điều cần quan tâm chính yếu là chi phí thời gian máy rỗi, năng lực lao
động và các đơn đặt hàng cần hoàn thành đúng hạn.Ý tưởng chính trong phương
pháp là mã hóa biểu diễn của lịch phân công là các toán tử di truyền phải thực hiện
theo cách có ý nghĩa, và một bộ giải mã phải luôn tạo ra một lời giải hợp lệ cho bài
toán. Thủ tục giải mã mô phỏng các thao tác của công việc theo cách mà khi một
máy tính sẵn sàng chọn lựa, thì thao tác cho phép đầu tiên từ danh sách ưu tiên được
lấy ra. Ví dụ nếu danh sách ưu tiên của máy m1 là: m1(40 03 01 02 ‘chờ’ ‘nhàn rỗi’),
thì thủ tục giải mã vào thời điểm 40 có thể thực hiện đơn đặt hàng o3 trên máy m1.
Nếu không được, thủ tục giải mã sẽ thực hiện đơn đặt hàng 01 và 02 (nghĩa là, tìm
ở 01 trước; nếu không được mới tìm ở 02). Biểu diễn này bảo đảm tạo một lịch phân công hợp lệ.
3.2 Lập thời khóa biểu cho trường học
Bài toán thời khóa biểu là một bài toán kết hợp nhiều ràng buộc không tầm thường
thuộc nhiều loại. Có nhiều phiên bản của bài toán thời khóa biểu, một trong những
bài toán này có thể được mô tả như sau: Có một danh sách các giáo viên, một danh
sách các khoảng thời gian, một danh sách các lớp. Bài toán cần tìm thời khóa biểu
tối ưu (giáo viên – thời gian – lớp); hàm mục tiêu phải thỏa những mục tiêu này (các
ràng buộc mềm) gồm: Có một số giờ được xác định trước cho mỗi giáo viên và mỗi
lớp; Chỉ một giáo viên trong một lớp vào một giờ nhất định; Một giáo viên không
thể dạy hai lớp cùng lúc; Đối với mỗi lớp được xếp thời khóa biểu vào một khoảng
thời gian, phải có một giáo viên…Ngoài ra còn có các mục tiêu sư phạm như trải
một số lớp ra nguyên tuần, những mục tiêu thuộc cá nhân như những giáo viên hợp
đồng không phải dạy buổi chiều, và các mục tiêu về tổ chức như mỗi giờ có một giáo
viên bổ sung sẵn sàng chỗ dạy tạm thời. Biểu diễn nhiễm sắc thể tự nhiên nhất cho
bài toán này là biểu diễn ma trận: một ma trận , ở đây mỗi hàng tương ứng với một
giáo viên, mỗi cột tương ứng với một giờ, các phần tử của ma trận R là các lớp ).
Các ràng buộc chủ yếu được xử lý bởi các toán tử di truyền và thuật giải sửa chữa
được sử dụng để loại bỏ những trường hợp mà có nhiều hơn một giáo viên xuất hiện
trong cùng một lớp vào cùng một giờ.  Phân hoạch đối tượng và đồ thị Bài toán
phân hoạch là cần chia n đối tượng thành k loại. Lớp bài toán này gồm nhiều bài toán
nổi tiếng như bài toán đóng thùng (gán các mặt hàng vào các thùng), bài toán tô màu
đồ thị (gán các nút của đồ thị vào các màu cụ thể…). Bài toán đóng thùng (Bin
Packing – BP) được phát biểu như sau: Cho danh sách gồm n đồ vật L=a1,a2,a3,…,an
và các thùng giống nhau với cùng sức chứa B. Kích thước của đồ vật ai là si thỏa
mãn . Vấn đề đặt ra là tìm cách xếp các đồ vật vào các thùng sao cho số lượng thùng
cần phải sử dụng là ít nhất.
3.3 Ứng dụng trong việc tìm kiếm đường đi
Trong việc tìm kiếm đường đi, thuật toán heuristic được sử dụng để đưa ra các ước
lượng hoặc thông tin gợi ý về hướng đi tiềm năng tốt nhất từ điểm xuất phát đến
điểm đích. Thay vì kiểm tra tất cả các lựa chọn có thể, thuật toán heuristic giúp hạn
chế không gian tìm kiếm và tập trung vào các lựa chọn tiềm năng tốt nhất dựa trên thông tin đã biết.
Thông qua việc sử dụng heuristic, thuật toán có thể đưa ra các quyết định thông minh
để xác định đường đi ưu tiên và tối ưu trong một môi trường đa dạng và phức tạp.
Các quy tắc heuristic có thể dựa trên thông tin như khoảng cách đến mục tiêu, đánh
giá về khả năng di chuyển hay thông tin về môi trường xung quanh.
Ứng dụng của thuật toán heuristic trong tìm kiếm đường đi rất rộng và đa dạng.
Chẳng hạn, trong lĩnh vực định tuyến, thuật toán heuristic được sử dụng để xác định
đường đi tối ưu trong mạng lưới hoặc hệ thống giao thông. Trong lĩnh vực trò chơi,
thuật toán heuristic được sử dụng để điều khiển hành vi của nhân vật hoặc đối thủ
máy tính để tạo ra trải nghiệm chơi game tương tác. Trong lĩnh vực hệ thống định vị
toàn cầu (GPS), thuật toán heuristic được sử dụng để tính toán đường đi ngắn nhất
từ điểm A đến điểm B.
Tóm lại, thuật toán heuristic là một công cụ hữu ích trong việc tìm kiếm đường đi,
giúp tối ưu hóa quá trình tìm kiếm và đưa ra các quyết định thông minh dựa trên
thông tin gợi ý và ước lượng.
3.4 Vạch đường cho robot di chuyển
Tìm đường là hướng dẫn robot di chuyển đến đích mà không bị lạc hay va vào những
đối tượng khác. Trong bài toán này, một lộ trình được lập trước để robot đi theo, lộ
trình này có thể dẫn dắt robot đi tới đích một cách hoàn hảo. Tuy nhiên, các nhà khoa
học muốn cải tiến hơn bằng cách vạch lộ trình nội tại, phụ thuộc vào tri thức thu
được từ việc cảm nhận môi trường cục bộ để xử lý các chướng ngại chưa biết. Bộ
tìm đường tiến hóa (EN) được đề xuất. Phần đầu của thuật giải là tìm lộ trình toàn
cục tối ưu từ điểm khởi đầu đến đến đích, phần thứ hai có trách nhiệm xử lý những
va chạm có thể xảy ra hay những vật cản chưa được biết trước bằng cách thay một
phần của lộ trình toàn cục gốc bằng một lộ trình con tối ưu.
4. Cài đặt và triển khai thuật toán
Đối với bài toán Parallel Machine Scheduling: Min Total Lateness
- Tạo các file input đầu vào với 2 cột m và n lần lượt là số lượng máy và số lượng công việc
- Đọc thời gian xử lí và deadline cho từng công việc
- Khởi tạo 1 hàm tính độ trễ cho công việc (calculateLateness) dựa vào thời gian
xử lí công việc và deadline của công việc
- Khởi tạo 1 hàm hoán đổi vị trí giữa 2 công việc và 2 máy (swapJobs) . Tiến
hành so sánh , nếu khi thay đổi khiến kết quả tối ưu hơn ( độ trễ nhỏ hơn) thì
ta giữ nguyên. Nếu không thì ra đổi lại.
- Tổng hợp vào hàm applyLocalSearch. Thực hiện vòng lặp 2 điều kiện trên cho
tới khi tìm được phương án tối ưu nhất ( độ trễ nhỏ nhất). Thì ta dừng thuật toán. 5. Tổng Kết
Bài toán Parallel Machine Scheduling: Min Total Lateness là một bài toán quan
trọng trong lĩnh vực quy hoạch lịch trình. Nó được áp dụng rộng rãi trong các ngành
công nghiệp và sản xuất, nơi việc xếp lịch trình các công việc trên các máy đa nhiệm
đóng vai trò quan trọng trong việc tối ưu hoá hiệu suất và đáp ứng yêu cầu thời gian.
Thuật toán được sử dụng trong bài toán là một phương pháp tìm kiếm cục bộ, cho
phép tìm ra một giải pháp xấp xỉ tối ưu cho bài toán. Bằng cách lặp lại việc hoán
đổi vị trí công việc trên các máy và tính toán độ trễ tương ứng, thuật toán tìm kiếm
cục bộ cố gắng cải thiện lời giải bằng cách di chuyển công việc để giảm tổng độ trễ.
Mặc dù thuật toán tìm kiếm cục bộ không đảm bảo tìm được lời giải tối ưu toàn cục,
nó thường cho kết quả tốt và được sử dụng rộng rãi trong thực tế. Điều quan trọng
là lựa chọn các phép biến đổi công việc phù hợp để tăng khả năng tìm kiếm và tránh rơi vào vết cạn kiệt.
Trên cơ sở đó, việc áp dụng thuật toán tìm kiếm cục bộ trong bài toán Parallel
Machine Scheduling: Min Total Lateness giúp cải thiện hiệu suất và hiệu quả của
lịch trình, từ đó tối thiểu hóa tổng lateness và đáp ứng yêu cầu về thời gian hoàn thành công việc.
6. Bảng phân công công việc
Đinh Tiến Đạt - 21013111 Đỗ Thanh Hải -
Tìm hiểu thuật toán heuristic Tìm tài liệu
ứng dụng của thuật toán Chỉnh sửa word
cài đặt và triển khai thuật toán
7. Tài liệu tham khảo
https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_di_truy %E1%BB%81n
http://mit.dthu.edu.vn/uploads/TKHuong.pdf