›
›

Bài giảng Toán rời rạc - Chương: Các ứng dụng của bài toán luồng cực đại - Nguyễn Đức Nghĩa

pdf 53 trang ngocly 4520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương: Các ứng dụng của bài toán luồng cực đại - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_cac_ung_dung_cua_bai_toan_luon.pdf

Nội dung text: Bài giảng Toán rời rạc - Chương: Các ứng dụng của bài toán luồng cực đại - Nguyễn Đức Nghĩa

  1. Các ứng dụng của Bài toán luồng cực đại BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • NGUYỄN ĐỨC NGHĨA
  2. Max Flow Applications s Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA t Bộ môn KHMT 2
  3. NỘI DUNG  Một số bài toán luồng tổng quát –Bài toán với nhiều điểm phát và điểm thu –Bài toán với hạn chế thông qua ở nút  Một số ứng dụng trong tổ hợp –Bài toán cặp ghép cực đại trong đồ thị hai phía –Độ tin cậy của mạng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 3
  4. Một số bài toán luồng tổng quát Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 4
  5. M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu  XÐt m¹ng G víi p ®iÓm ph¸t s1, s2, , sp với lượng ph¸t là a1, a2, , ap vµ q ®iÓm thu t1, t2, , tq với lượng thu là b1, b2, , bq  Gi¶ sö r»ng luång cã thÓ ®i tõ mét ®iÓm ph¸t bÊt kú ®Õn tÊt c¶ c¸c ®iÓm thu.  T×m luång cùc ®¹i tõ c¸c ®iÓm ph¸t ®Õn c¸c ®iÓm thu s1 t1 s2 t2 sp tq Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 5
  6. M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu  Đa vµo mét ®iÓm ph¸t gi¶ s vµ mét ®iÓm thu gi¶ t vµ c¸c c¹nh nèi s víi tÊt c¶ c¸c ®iÓm ph¸t vµ c¸c c¹nh nèi c¸c ®iÓm thu víi t.  Kntq cña cung (s,si) sÏ b»ng ai là lîng ph¸t cña si.  Kntq cña (ti, t) sÏ bằng bi là lîng thu cña ®iÓm thu ti.  Bài to¸n dẫn về bài to¸n với 1 điểm ph¸t và một điểm thu. s1 t1 b a1 1 s t 2 2 b t s a2 2 ap bq sp tq Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 6
  7. Bài toán với hạn chế thông qua ở nút  Gi¶ sö trong m¹ng G, ngoµi kh¶ n¨ng th«ng qua cña c¸c cung c(u, v), ë mçi ®Ønh vV cßn cã kh¶ n¨ng th«ng qua cña ®Ønh lµ d(v), vµ ®ßi hái tæng luång ®i vµo ®Ønh v kh«ng ®îc vît qu¸ d(v), tøc lµ d f(w,v) d(v). u  u 4 w V 5 dt ds s 1 t 2 v 3 d • T×m luång cùc ®¹i từ s đến t trong m¹ng G. v Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 7
  8. Bài toán với hạn chế thông qua ở nút  X©y dùng mét m¹ng G' sao cho: mçi ®Ønh v cña G t¬ng øng víi 2 ®Ønh v+, v- trong G', mçi cung (u, v) trong G øng víi cung (u-, v+) trong G', mçi cung (v,w) trong G øng víi cung (v-, w+) trong G'. Ngoµi ra, mçi cung (v+, v-) trong G' cã kh¶ n¨ng th«ng qua lµ d(v), tøc lµ b»ng kh¶ n¨ng th«ng qua cña ®Ønh v trong G. du d u u+ u- 4 u 4 5 5 dt ds d d s 1 t + - t+ t- s 1 t s s 3 2 dv v 2 v+ v- 3 dv Qui về bài toán tìm luồng cực đại trong G’ Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 8
  9. Các ứng dụng của bài toán luồng cực đại ỨNG DỤNG TRONG TỔ HỢP Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 9
  10. Bài toán ghép cặp (Matching Problems) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 10
  11. Cặp ghép (Matching) Cho G = (V, E) là đồ thị vô hướng. Cặp ghép trong đồ thị G là tập các cạnh của đồ thị đôi một không có đỉnh chung Bài toán cặp ghép cực đại : Tìm cặp ghép với lực lượng lớn nhất Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 11
  12. Bài toán cặp ghép cực đại trên đồ thị hai phía Đồ thị vô hướng G=(V,E) là hai phía nếu V có thể 1 6 phân hoạch thành 2 tập X và Y sao cho mỗi cạnh e E đều có thể biểu diễn 2 7 e=(x, y) với x X và y Y. Cặp ghép là tập các 3 8 cạnh đôi một không có đỉnh chung. 4 9 Bài toán cặp ghép cực đại : Tìm cặp ghép có lực lượng lớn nhất 5 10 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 12
  13. Qui dẫn về bài toán luồng cực đại Xây dựng mạng G’ 1 6 Mỗi cung (j, t) có kntq là 1. 1 2 7 s 3 8 t 1 4 9 Mỗi cung (s, i) có kntq là 1. 5 ∞ 10 Mỗi cạnh (x,y) thay bởi cung Toán rời rạc – Fall 2005 (x,y) với kntq + ∞ . NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 13
  14. Tìm luồng cực đại 1 6 2 7 s 3 8 t 4 9 5 10 Giá trị luồng cực đại từ s đến t là 4. Cặp ghép cực đại có lực lượng là 4. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 14
  15. Bipartite Matching: Tính đúng đắn Đinh lý. Lực lượng của cặp ghép cực đại trong G = giá trị của luồng cực đại trong G'. CM. Chỉ cần chứng minh G có cặp ghép lực lượng k khi và chỉ khi G’ có luồng với giá trị k. ) Cho cặp ghép M có lực lượng k.  Xét luồng f đẩy luồng 1 đơn vị dọc theo mỗi một trong k đường đi.  f là luồng có giá trị k. ■ 1 1' 1 1' 1 1 2 2' 2 2' 3 3' s 3 3' t 4 4' 4 4' G G' 5 5' 5 5' Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 15
  16. Bipartite Matching: Tính đúng đắn ) Cho f là luồng giá trị k trong G'.  Từ định lý về tính nguyên tìm được luồng nguyên: f(e) chỉ là 0 hoặc 1.  Gọi M = tập các cạnh e từ X sang Y với f(e) = 1. – mỗi đỉnh trong X và Y là đầu mút của một cạnh trong M – |M| = k, do luồng có giá trị k nên có đúng k cạnh từ X sang Y với giá trị luồng trên cung là 1 ■ 1 1' 1 1' 1 1 2 2' 2 2' s 3 3' t 3 3' 4 4' 4 4' G' G 5 5' 5 5' Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 16
  17. Cặp ghép hoàn hảo (Perfect Matching) ĐN. Cặp ghép M  E được gọi là hoàn hảo (perfect) nếu mỗi đỉnh của đồ thị là đầu mút của đúng 1 cạnh trong M. Câu hỏi. Khi nào đồ thị hai phía có cặp ghép hoàn hảo? Cấu trúc của đồ thị hai phía có cặp ghép hoàn hảo.  Rõ ràng ta phải có |X| = |Y|.  Điều kiện nào là cần nữa?  Các điều kiện đủ là gì? Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 17
  18. Cặp ghép hoàn hảo Ký hiệu. Gỉa sử S là tập con các đỉnh, ký hiệu (S) là tập các đỉnh kề với các đỉnh trong S. Nhận xét. Nếu đồ thị hai phía G = (X  Y, E) có cặp ghép hoàn hảo, thì | (S)| |S| với mọi tập con S  X. CM. Hai đỉnh bất kỳ trong S gắn với hai đỉnh khác nhau trong (S). 1 1' 2 2' Không có cặp ghép hoàn hảo: 3 3' S = { 2, 4, 5 } (S) = { 2', 5' }. 4 4' X 5 5' Y Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 18
  19. Định lý về các đám cưới (Marriage Theorem) Marriage Theorem. [Frobenius 1917, Hall 1935] Giả sử G = (X  Y, E) là đồ thị hai phía với |X| = |Y|. Khi đó, G có cặp ghép hoàn hảo khi và chỉ khi | (S)| |S| với mọi tập con S  X. CM. ) Vừa chứng minh ở trên. 1 1' 2 2' Không có cặp ghép hoàn hảo: 3 3' S = { 2, 4, 5 }  4 4' (S) = { 2', 5' }. X 5 5' Y Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 19
  20. Chứng minh định lý về các đám cưới CM. ) Giả sử G không có cặp ghép hoàn hảo.  Xét bài toán luồng cực đại tương ứng và (A, B) là lát cắt nhỏ nhất trong G'.  Theo định lý luồng cực đại và lát cắt nhỏ nhất, cap(A, B) < | X |.  Gọi XA = X  A, XB = X  B , YA = Y  A.  cap(A, B) = | XB | + | YA |.  Do lát cắt nhỏ nhất không sử dụng cạnh : (XA)  YA. Suy ra:  |(XA )| | YA | = (| XB | + | YA |) - | XB | = cap(A, B) - | XB | < | X | - | XB | = | XA |.  Chọn S = XA ta có |(S)| < |S| ?! ■ 1 1 G' 1' A 2' XA = {2, 4, 5} 2 1 s XB = {1, 3} 1 3' YA = {2', 5'} 4 3 (XA) = {2', 5'} 4' t 5 1 5' Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 20
  21. Ví dụ Boys Girls 1 5 2 6 3 7 4 8 Có cách tổ chức các đám cưới? Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 21
  22. Qui về bài toán luồng cực đại Boys Girls 1 5 1 1 2 1 6 1 s 1 1 t 1 3 7 1 4 8 Tồn tại luồng cực đại với giá trị 4? Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 22
  23. Bipartite Matching: Thời gian tính Sử dụng thuật toán luồng cực đại nào để tìm cặp ghép?  Đường tăng luồng tuỳ ý: O(m val(f*) ) = O(mn). 2 2  Thang độ hoá kntq: O(m log C ) = O(m ). 1/2  Đường tăng ngắn nhất: O(m n ). Cặp ghép trên đồ thị tổng quát. 4  Thuật toán trổ hoa (Blossom algorithm): O(n ). [Edmonds 1965] 1/2  Thuật toán tốt nhất hiện biết: O(m n ). [Micali-Vazirani 1980] Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 23
  24. Đối ngẫu: Bài toán phủ đỉnh tối tiểu 1 6 Phủ đỉnh là Bài toán phủ tập đỉnh CV đỉnh tối tiểu: sao cho mỗi 2 7 Tìm phủ đỉnh cạnh của đồ với lực lượng thị có ít nhất một đầu mút 3 8 nhỏ nhất trong C 4 9 5 10 Ví dụ: C = {2, 5, 6, 8} là một phủ đỉnh Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 24
  25. Tìm luồng cực đại 1 6 2 7 s 3 8 t 4 9 5 10 Giá trị luồng cực đại từ s đến t là 4. Cặp ghép cực đại có lực lượng là 4. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 25
  26. Xác định lát cắt nhỏ nhất 1 6 2 7 s 3 8 t 4 9 5 10 S = {s, 1, 3, 4, 6, 8}. Không có cung từ {1, 3, 4} đến {7, 9, 10} hoặc T = {2, 5, 7, 9, 10, t}. từ {6, 8} đến {2, 5}. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 26
  27. Ý nghĩa của lát cắt nhỏ nhất 1 6 2 7 s 3 8 t 4 9 5 10 Xét tập đỉnh C = (X \ S)  (T\t). Mỗi cạnh của đồ thị xuất phát G kề với một đỉnh như vậy. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 27
  28. Đối ngẫu 1 6 Phủ đỉnh là tập đỉnh CV sao cho mỗi 2 7 cạnh của đồ Tập đỉnh C = thị có ít nhất 3 8 (X \ S)  (T\ t) một đầu mút = { 2, 5, 6, 8 } trong C là một phủ 4 9 đỉnh 5 10 Lực lượng của cặp ghép cực đại là bằng lực lượng của phủ đỉnh nhỏ nhất. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 28
  29. Độ tin cậy của mạng Network Reliability Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 29
  30. Độ tin cậy của mạng  Xét mạng truyền thông (Communication Network)  Hỏi có bao nhiêu đường đi không giao nhau cạnh từ s đến t?  Xác định số này bằng cách nào? Định lý. Giả sử G = (V,E) là đồ thị có hướng. Khi đó số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số ít nhất các cạnh cần loại bỏ khỏi G để không còn đường đi từ s đến t. s t Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 30
  31. Có 3 đường đi không giao nhau cạnh từ s đến t 1 5 9 2 6 10 s t 3 7 11 4 8 12 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 31
  32. Xoá 3 cạnh để tách s và t Đặt S = {s, 3, 4, 8}. 3 cạnh cần xoá là tất cả các cạnh từ S sang T = N\S. 1 5 9 2 6 10 s t 3 7 11 4 8 12 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 32
  33. Đường đi không giao nhau đỉnh  Hai đường đi từ s đến t được gọi là không giao nhau đỉnh nếu chúng có duy nhất hai đỉnh chung là s và t.  Bằng cách nào có thể xác định số lượng đường đi từ s đến t không giao nhau đỉnh? Trả lời: Tách nút Định lý. Giả sử G = (V,E) là mạng không có cung trực tiếp từ s đến t. Số lớn nhất các đường đi không giao nhau đỉnh là bằng số nhỏ nhất các đỉnh mà việc loại bỏ chúng làm gián đoạn mọi đường đi từ s đến t. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 33
  34. Có 2 đường đi không giao nhau đỉnh từ s đến t 1 5 9 2 6 10 s t 3 7 11 4 8 12 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 34
  35. Xoá đỉnh 5 và 6 tách t khỏi s? Gọi S = {s, 1, 2, 3, 4, 8} Gọi T = {7, 9, 10, 11, 12, t} 1 5 9 2 6 10 s t 3 7 11 4 8 12 Không có cung từ S sang T. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 35
  36. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 36
  37. Bài toán đường đi không giao nhau cạnh (Edge Disjoint Paths) Định nghĩa. Hai đường đi được gọi là không giao nhau cạnh nếu chúng không có cạnh chung. Bài toán đường đi không giao nhau cạnh. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh. Ví dụ: mạng truyền thông 2 5 s 3 6 t 4 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 37
  38. Bài toán đường đi không giao nhau cạnh (Edge Disjoint Paths) Định nghĩa. Hai đường đi được gọi là không giao nhau cạnh nếu chúng không có cạnh chung. Bài toán đường đi không giao nhau cạnh. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh. Ví dụ: mạng truyền thông 2 5 s 3 6 t 4 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 38
  39. Bài toán đường đi không giao nhau cạnh Quy về bài toán luồng cực đại: gán cho mỗi cạnh kntq là 1. 1 1 1 1 1 1 s 1 1 t 1 1 1 1 1 1 Định lý. Số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh là bằng giá trị của luồng cực đại. CM. Điều kiện cần  Giả sử có k đường đi không giao nhau cạnh P1, . . . , Pk.  Đặt f(e) = 1 nếu e thuộc vào ít nhất một trong số các đường đi; và f(e) = 0, nếu trái lại.  Do các đđ không có cạnh chung nên f là luồng có giá trị k. ■ Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 39
  40. Bài toán đường đi không giao nhau cạnh Quy về bài toán luồng cực đại: gán cho mỗi cạnh kntq là 1. 1 1 1 1 1 1 s 1 1 t 1 1 1 1 1 1 Định lý. Số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh là bằng giá trị của luồng cực đại. CM. Điều kiện đủ  Giả sử luồng cực đại có giá trị k.  Theo định lý về tính nguyên tồn tại f là luồng 0-1 với giá trị k.  Xét cạnh (s, u) với f(s, u) = 1. – theo đk cân bằng luồng, tồn tại cạnh (u, v) với f(u, v) = 1 – tiếp tục cho đến khi đạt tới t, luôn sử dụng cạnh mới  Tạo được k đường đi (không nhất thiết là đơn) không giao nhau cạnh. ■ Toán rời rạc – Fall 2005 nếu cần, có thể cắt chu trình để thu được đường đi đơn NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 40
  41. Bài toán về độ liên kết của mạng (Network Connectivity) ĐN. Tập cạnh F  E được gọi là tách t với s nếu mọi đường đi từ s đến t đều đi qua ít nhất một cạnh trong F. Liên kết mạng. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng cạnh ít nhất cần loại bỏ để tách t với s. 2 5 s 3 6 t 4 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 41
  42. Đường đi không giao nhau cạnh và Độ liên kết mạng Định lý. [Menger 1927] Số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số nhỏ nhất các cạnh cần loại bỏ để tách t với s. CM. Điều kiện đủ  Giả sử loại bỏ F  E ngăn cách t từ s, và |F| = k.  Do mọi đường đi từ s đến t đều có ít nhất một cạnh trong F, suy ra số lượng đường đi không giao nhau cạnh không vượt quá k. ■ 2 5 2 5 s 3 6 t s 3 6 t 4 7 4 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 42
  43. Đường đi không giao nhau cạnh và Độ liên kết mạng Định lý. [Menger 1927] Số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số nhỏ nhất các cạnh cần loại bỏ để tách t với s. CM. Điều kiện cần  Giả sử k là số lượng lớn nhất các đường đi không giao nhau cạnh.  Khi đó giá trị luồng cực đại là k.  Từ định lý Max-flow min-cut lát cắt nhỏ nhất (A, B) có kntq k.  Gọi F là tập các cạnh từ A sang B.  |F| = k và F tách t với s. ■ A 2 5 2 5 s 3 6 t s 3 6 t 4 7 4 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 43
  44. Bài toán giao hàng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 44
  45. Bài toán giao hàng kho hàng đại lý bán lẻ 6 1 5 6 6 2 7 7 4 3 8 6 5 4 9 5 4 5 Có cách chuyển hàng từ các kho đáp ứng yêu cầu của các đại lý bán lẻ? Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 45
  46. Quy về bài toán luồng cực đại kho hàng đại lý bán lẻ 6 1 6 tổng yêu cầu của 5 6 6 2 6 các đại lý 5 là 24 7 7 4 4 s 3 t 5 8 6 5 4 6 4 9 5 4 5 Tồn tại tương ứng 1-1 giữa luồng từ s đến t với giá trị 24 với một cách chuyển hàng đáp ứng yêu cầu của các đại lý bán lẻ. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 46
  47. Bài toán lập lịch Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 47
  48. Bài toán  Có n chi tiết (job) cần được gia công.  Có M máy (giống hệt nhau) để thực hiện việc gia công.  Đối với chi tiết j biết:  tj - thời gian hoàn thành  rj - thời điểm sẵn sàng  dj - thời hạn hoàn thành  Tìm cách bố trí việc thực hiện gia công n chi tiết trên M máy:  Mỗi chi tiết j được bắt đầu gia công ở thời điểm không sớm hơn rj  Thời điểm hoàn thành việc gia công chi tiết j không muộn hơn dj  Tại mỗi thời điểm có không quá 1 máy thực hiện việc gia công chi tiết j và tổng thời gian thực hiện gia công chi tiết j trên M máy là bằng tj  Cách bố trí thoả mãn các điều kiện vừa nêu gọi là lịch Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 48
  49. Lập lịch trên các máy song song Job ( j ) 1 2 3 4 Thời gian hoàn thành ( tj ) 1.5 3 4.5 5 Thời điểm sẵn sàng ( rj ) 2 0 2 4 Thời hạn ( dj ) 5 4 7 9 Giả sử có M = 2 máy song song 2 1 4 3 Không có lịch ngoại trừ khi cho phép ngắt quãng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 49
  50. Lập lịch trên các máy song song Job ( j ) 1 2 3 4 Thời gian hoàn thành ( tj ) 1.5 3 4.5 5 Thời điểm sẵn sàng ( rj ) 2 0 2 4 Thời hạn ( dj ) 5 4 7 9 Giả sử có M = 2 máy song song 2 1 4 3 4 3 Có lịch nếu cho phép ngắt quãng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 50
  51. Qui về bài toán luồng cực đại cung đỏ: thời lượng cung xanh lá gia công job j trong cây: thời jobs khoảng thời gian t lượng của 0-2 nhiều nhất là t. 2 khoảng thời 1 4 gian t nhiều 1.5 nhất là M t. 2-4 2 4 (M là số máy 3 có thể dùng) 2 s 4.5 1 3 4-5 t 5 4 4 4 5-7 cung xanh da trời: tổng thời lượng dành 2 cho gia công job j 7-9 trong mọi khoảng là pj. khoảng thời gian Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 51
  52. Luồng cực đại – Lịch Lịch tồn tại Cần phân rã tìm được luồng luồng để đưa bão hoà mọi 1 1 0-2 ra lịch cung ra khỏi s .5 4,2 1.5 2 2-4 2 1 4,4 3 2 s 4.5 .5 2,2 3 4-5 t 5 2 4,4 1 4 2 4,2 2 5-7 7-9 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 52
  53. Questions? Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 53