ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BẾ NHẬT VINH VẤN ĐỀ NGƯỢC CỦA VẤN ĐỀ TỐI THIỂU HĨA THỜI GIAN TRỄ TỐI ĐA TRÊN MƠ HÌNH MÁY ĐƠN THÁI NGUYÊN, THÁNG 5/2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BẾ NHẬT VINH VẤN ĐỀ NGƯỢC CỦA VẤN ĐỀ TỐI THIỂU HÓA THỜI GIAN TRỄ TỐI ĐA TRÊN MƠ HÌNH MÁY ĐƠN Chun ngành: Toán ứng dụng Mã số: 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC GIÁO VIÊN HƯỚNG DẪN TS PHẠM HỒNG TRƯỜNG THÁI NGUYÊN, THÁNG 5/2018 Mục lục Danh mục ký hiệu Lời nói đầu Kiến thức chuẩn bị 1.1 Vận trù học 1.2 Vấn đề tối ưu hóa tổ hợp 1.3 Lời giải vấn đề gia cơng mơ hình máy đơn 10 1.3.1 Trình tự khả thi trình tự tối ưu 10 1.3.2 Trình tự gia cơng khơng trì hỗn trình tự gia cơng trì hỗn 11 1.4 Vấn đề tối thiểu hóa thời gian trễ tối đa cơng việc với thời gian đến mơ hình máy đơn Lmax 12 1.5 Vấn đề xếp ngược 14 1.6 Vấn đề quy hoạch tuyến tính 17 1.7 Định nghĩa ba loại chuẩn l1 , l2 , l∞ 18 Vấn đề ngược vấn đề tối thiểu hóa thời gian trễ tối đa cơng việc với thời gian đến mơ hình máy đơn 20 2.1 Sơ lược vấn đề xếp ngược 21 2.2 Điều kiện cần đủ vấn đề tối thiểu hóa thời gian trễ tối đa 24 2.2.1 Điều kiện đủ vấn đề Lmax tối ưu 24 2.2.2 Điều kiện cần đủ vấn đề Lmax 26 2.3 Điều chỉnh kỳ hạn (Adjustable Due Dates) 28 2.3.1 Bài toán ngược |adjustable dj , π| Lmax 28 2.3.2 Bài toán ngược |adjustable dj , L∗ | Lmax 37 2.4 Điều chỉnh thời gian gia công (Adjustable Processing Times) 40 2.4.1 Bài toán ngược |adjustable pj , π| Lmax 41 2.4.2 Bài toán ngược |adjustable pj , L∗ | Lmax 47 Kết luận Tài liệu tham khảo 49 51 Danh mục ký hiệu Tj Công việc thứ j dãy công việc đưa pj Thời gian gia công công việc Tj dj Kỳ hạn công việc Tj Cj Thời gian hồn thành cơng việc Tj Cj Tổng thời gian hồn thành cơng việc có trọng số w j Cj Tổng thời gian hoàn thành cơng việc có trọng số khác Lmax Thời gian trễ tối đa EDD Quy tắc ưu tiên xếp kỳ hạn sớm Lmax Vấn đề tối thiểu hóa thời gian trễ tối đa của cơng việc mơ hình máy đơn 1|adjustable dj , π|Lmax Bài tốn điều chỉnh kỳ hạn dj để dãy cơng việc π tối ưu 1|adjustable dj , L∗ |Lmax Bài toán điều chỉnh kỳ hạn dj để trễ tối đa Lmax ≤ L∗ 1|adjustable pj , π|Lmax Bài tốn điều chỉnh thời gian gia cơng pj để dãy công việc π tối ưu 1|adjustable pj , L∗ |Lmax Bài tốn điều chỉnh thời gian gia cơng pj để trễ tối đa Lmax ≤ L∗ Lời nói đầu Từ kỷ XX tối ưu hóa có ứng dụng nhiều hiệu lĩnh vực quản trị kinh doanh, chế tạo sản xuất, quy hoạch tài nguyên, công nghệ thông tin, hỗ trợ cho vấn đề định quản lý, mục tiêu nghiên cứu tối ưu hóa tìm giải pháp tốt từ số lượng lớn giải pháp khả thi Trong mơ hình tối ưu hóa truyền thống tất thơng số đưa mục tiêu tìm giải pháp tối ưu đáp ứng ràng buộc cụ thể, tối ưu hóa ngược xác định trước giải pháp với giá trị số thông số không cho xác mục tiêu tìm giá trị xác thơng số để giải pháp đưa ban đầu tối ưu, tối ưu hóa ngược giúp cải thiện hệ thống có sẵn Trong năm gần đây, vấn đề tối ưu hóa ngược trở thành chủ đề nghiên cứu nhiều hơn, tầm quan trọng ứng dụng tối ưu hóa ngược ngày gia tăng Luận văn trình bày tốn ngược tốn tối thiểu hóa thời gian trễ tối đa công việc với thời gian đến mơ hình máy đơn Vấn đề trình tự gia cơng cơng việc vấn đề tốn tối ưu hóa tổ hợp Với vấn đề tối ưu hóa trình tự gia cơng thuận dãy cơng việc đưa với thơng số cho trước (ví dụ thời gian gia công hay kỳ hạn công việc) ta cần xếp lại trình tự cơng việc để cho độ trễ tối đa nhỏ Tuy nhiên trình tự cơng việc ấn định mục tiêu tối ưu hóa ngược ta cần điều chỉnh thông số cho trước để cho trình tự cho tối ưu để đạt độ trễ tối đa thỏa mãn thời hạn cho trước Chính việc nghiên cứu toán ngược toán tối thiểu hóa thời gian trễ tối đa cơng việc với thời gian đến mơ hình máy đơn cần thiết Giải toán nhằm để đáp ứng kỳ hạn giao hàng cho khách hàng, khách hàng có dãy cơng việc ấn định trước cho độ trễ tối đa sản xuất nhỏ Luận văn hoàn thành Trường Đại học Khoa học - Đại học Thái Nguyên hướng dẫn TS Phạm Hồng Trường Tơi xin tỏ lịng kính trọng biết ơn sâu sắc thầy, người trực tiếp hướng dẫn tơi tận tình việc học tập, nghiên cứu để hoàn thành luận văn Xin chân thành cảm ơn Lãnh đạo Trường Đại học Khoa học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Tốn - Tin tồn thể thầy ngồi trường giảng dạy giúp tơi trau dồi thêm nhiều kiến thức phục vụ cho việc học tập nghiên cứu thân Cuối tơi xin gửi lời cảm ơn tới gia đình, bạn bè động viên, giúp đỡ tạo điều kiện tốt cho tơi q trình học tập, nghiên cứu hoàn thành luận văn Xin chân thành cảm ơn! Thái Nguyên, ngày 10 tháng năm 2018 Tác giả luận văn Bế Nhật Vinh Chương Kiến thức chuẩn bị 1.1 Vận trù học Vận trù học (Operations Research-OR) hình thành từ việc lập kế hoạch nhà quân chiến tranh giới thứ II Mục tiêu Vận trù học lúc sử dụng cho hiệu nguồn lực quân cách sử dụng kỹ thuật định lượng Kết ứng dụng thực Patrick Blackett Trong chiến thứ nhất, ơng thành lập nhóm gọi Circus giúp giảm số lượng pháo phịng khơng với tầm xa cần thiết để bắn hạ máy bay đối phương từ mức trung bình 20000 đầu đạn trận đầu chiến xuống 4000 đầu đạn vào năm 1941 Trong thập kỷ sau chiến tranh, kỹ thuật bắt đầu áp dụng rộng rãi cho vấn đề kinh doanh, cơng nghiệp xã hội Từ Vận trù học mở rộng sử dụng rộng rãi ngành cơng nghiệp từ hóa dầu đến hãng hàng khơng, hậu cần phủ, tập trung vào việc phát triển mơ hình tốn học sử dụng để phân tích tối ưu hóa hệ thống phức tạp trở thành lĩnh vực học tập nghiên cứu Vận trù học với mục đích nghiên cứu phân bổ nguồn lực tối ưu, vận trù học cung cấp sở hợp lý cho việc định cách tìm hiểu cấu trúc tình phức tạp, dự đoán hành vi hệ thống cải thiện hiệu suất hệ thống Phần lớn công việc thực tế thực cách sử dụng kỹ thuật phân tích số để phát triển vận dụng mơ hình tốn học hệ thống tổ chức bao gồm người, máy móc hoạt động Vai trị vận trù học hai lĩnh vực công lĩnh vực tư nhân gia tăng nhanh chóng Vận trù học giải nhiều vấn đề khác giao thông vận tải, lập kế hoạch kiểm kê, kế hoạch sản xuất, hoạt động truyền thơng, hoạt động máy tính, quản lý tài sản, quản lý rủi ro, quản lý doanh thu nhiều lĩnh vực khác Trong lĩnh vực công, nghiên cứu vận trù học tập trung vào sách lượng, quốc phịng, chăm sóc sức khoẻ, quy hoạch tài nguyên nước, thiết kế vận hành hệ thống khẩn cấp đô thị thực thi pháp luật Nghiên cứu vận trù học, khoa học quản lý phân loại thành ba lĩnh vực sau: Một nghiên cứu sở tảng ba lĩnh vực toán học (Xác suất, tối ưu hóa, lý thuyết hệ động lực) Hai nghiên cứu mơ hình việc thiết lập mơ hình, phân tích chúng mặt tốn học, mã hóa chúng lên máy tính, giải chúng cơng cụ phần mềm, đánh giá hiệu thu từ liệu máy tính Mức chủ yếu nhờ máy tính định hướng xác suất kinh tế lượng thứ ba nghiên cứu ứng dụng vận trù học, giống ngành kĩ thuật kinh tế, sử dụng mơ hình thu để áp dụng cho vấn đề thực tế Trong vận trù học, nhà nghiên cứu yêu cầu phải mơ hình hóa vấn đề thực tế cách áp dụng kỹ thuật toán học, thống kê, ứng dụng máy tính sau tìm giải pháp tối ưu cho mơ hình bị hạn chế thời gian, nguồn lực lao động, nguồn lực vật liệu quy tắc kinh doanh với mục tiêu cụ thể Các lý thuyết mới, mô hình tốn học phát minh vận trù học để mơ tả phân tích hành vi, đặc điểm, thay đổi vấn đề thực tế, để giúp người định tốt để phát triển quản lý quy trình doanh nghiệp với lợi nhuận tối đa Mơ hình tối ưu mơ tả sau max ( min) f (x) s.t Điều kiện ràng buộc Các giải pháp đáp ứng yêu cầu nêu thường gọi giải pháp khả thi Tối ưu hóa tìm giải pháp tối ưu số giải pháp khả thi 1.2 Vấn đề tối ưu hóa tổ hợp Tối ưu hố tổ hợp nhánh tối ưu hóa tốn học xuất toán học rời rạc, vận trù học, lý thuyết thuật tốn lý thuyết tính toán phức tạp Mục tiêu nghiên cứu tối ưu hóa tổ hợp tìm giải pháp tốt từ số lượng lớn giải pháp khả thi Trong nhiều vấn đề, chẳng hạn phân công tối ưu, khung ngắn nhất, vận chuyển toán người giao hàng, giải pháp rời rạc việc tìm kiếm tồn diện khơng khả thi So với ngành toán học ứng dụng khác, tối ưu hóa tổ hợp tương đối trẻ Xem xét lịch sử loạt nghiên cứu độc lập diễn riêng biệt Chỉ năm 1950, cơng cụ đại số tuyến tính số ngun trở nên thống có sẵn lĩnh vực tối ưu tổ hợp bắt đầu thu hút ý mối quan hệ chúng đặt Thật vậy, tối ưu hóa tuyến tính tạo thành lề lịch sử tối ưu hóa tổ hợp Quan niệm ban đầu Kantorovich Koopmans thúc đẩy ứng dụng tổ hợp, đặc biệt vận chuyển chuyển tải Sau xây dựng quy hoạch tuyến tính tốn tổng quát, phát triển vào năm 1947 Dantzig phương pháp đơn cơng cụ, Dantzig cố gắng giải tất toán tối ưu hóa tổ hợp với phương pháp quy hoạch tuyến tính thường thành cơng Tối ưu hóa tổ hợp liên quan đến mơ hình phương pháp để tối ưu hóa 38 Ta bắt đầu với trình tự EDD với kỳ hạn gốc Nếu trình tự thỏa mãn Lmax ≤ L∗ khơng không cần điều chỉnh Mặt khác, kỳ hạn số cơng việc tăng đặt H = {hi } tập công việc chủ chốt, L = Lmax Nếu L > L∗ , tăng kỳ hạn cơng việc từ tập H Rõ ràng kỳ hạn tăng thêm tất công việc từ H: dj = dj + x, x ≥ 0, j ∈ H, biên độ kỳ hạn nhận sau: x ≤ dj − dj j∈H Trước tiên ta đưa vấn đề làm mà nút thắt tháo gỡ kỳ hạn sớm số cơng việc có thời hạn Nếu số khơng có cơng việc chủ chốt, thứ tự chúng khơng quan trọng Mặt khác, có cơng việc cuối số có kỳ hạn chủ chốt có điều chỉnh mong muốn, phụ thuộc loại chuẩn, độ lệch d − d tính công thức sau: d−d =    αh x    h∈H   f or l1,α,β norm, α h x2 f or l2,α,β norm,   h∈H     max {αh } × x f or l∞,α,β norm h∈H Trong lớp kế hoạch kỳ hạn sớm nhất, giá trị d − d nhỏ với chuẩn dãy cơng việc có kỳ hạn nằm dãy thứ tự không tăng αj Ta giới thiệu ký hiệu thứ tự Sắp thứ tự σ gọi thứ tự công việc xếp theo thứ tự không tăng của αj Sự điều chỉnh kỳ hạn cơng việc chủ chốt vi phạm thứ tự kỳ hạn sớm công việc chủ chốt xuất Trong trình tự trì 39 thứ tự giữ vết công việc chủ chốt H, điều chỉnh kỳ hạn tiến hành lặp lại, lần lặp, ta giả sử công việc đánh số phù hợp với thứ tự Sự tăng kỳ hạn dhj cơng việc hj ∈ H tạo thay đổi cấu trúc đến trường hợp Ta giả sử hj cơng việc thứ k thứ tự σ, chẳng hạn hj = σ(k) Trường hợp A: Kỳ hạn công việc σ(k) đạt tới kỳ hạn công việc σ(k + 1) thứ tự chính; Trường hợp B: Một cơng việc j ∈ N\H trở thành chủ chốt; Trường hợp C: Giá trị mục tiêu L∗ độ trễ tối đa đạt được; Trường hợp D: Kỳ hạn công việc σ(k) đạt tới cận dσ(k) Xác định gia tăng dσ(k) xA σ(k) = dσ(k+1) − dσ(k) , xB σ(k) = L − max {Cj − dj } , j∈N\H ∗ xC σ(k) = L − L , xD σ(k) = dσ(k) − dσ(k) theo thứ tự dẫn tới trường hợp A, B, C D Giá trị Lmax giảm kỳ hạn tất công việc từ tập H tăng lượng x trường hợp sớm A, B, C D xảy Do x xác định sau: x = min σ(k)∈H dσ(k+1) − dσ(k) , L − max {Cj − dj } , L − L∗ , σ(k)∈H dσ(k) − dσ(k) (2.22) Nếu trường hợp A xảy kỳ hạn công việc σ(k) σ(k + 1) nhau, việc đánh số lại cập nhật thứ tự gần yêu cầu cho 40 công việc với kỳ hạn nối tiếp số thứ tự không tăng αj Nếu trường hợp B xảy ra, tập H cập nhật Trong hai trường hợp giá trị L độ trễ tối đa giảm x Việc tăng kỳ hạn tập H tiếp tục lặp lại trường hợp C D xảy Trong trường hợp trường hợp C xảy ra, giá trị mục tiêu L∗ đạt được; kết tối ưu lân lặp lại, hoán vị kỳ hạn sớm xem xét công việc thời hạn, công việc với giá trị bé αj chọn điều chỉnh thời hạn Trong trường hợp trường hợp D, kỳ hạn công việc chủ chốt tăng giá trị mục tiêu L∗ khơng thể đạt Dãy cơng việc ban đầu xây dựng thời gian O(n log n) Trong lần lặp lại lượng điều chỉnh x tính thời gian O(n) Mỗi trường hợp A B xảy không n lần trường hợp C xảy lần Do thời gian hồn thành việc giải tốn ngược O(n2 ) Do ta chứng minh kết Định lý 2.4 Bài toán ngược |adjustable dj , L∗ | Lmax giải thời gian O(n2 ), thời gian chuẩn việc giảm sức ép tất công việc chủ chốt lặp lại lượng x xác định (2.22) Nếu không tồn kết quả, thực thời gian O(n2 ) sử dụng cách tiếp cận tương tự 2.4 Điều chỉnh thời gian gia công (Adjustable Processing Times) Trong phần này, giả sử tất kỳ hạn dj , ∀ j ∈ N cố định, thời gian gia công pj phải điều chỉnh, cho dãy trình tự công việc π = (1, 2, , n) tối ưu giá trị L∗ trễ tối đa Lmax thỏa mãn Lmax ≤ L∗ 41 2.4.1 Bài toán ngược |adjustable pj , π| Lmax Mục tiêu toán ngược |adjustable pj , π| Lmax tìm thời gian gia cơng điều chỉnh p, pj ∈ pj ; pj , j ∈ N, độ lệch so với thời gian gia công gốc p − p nhỏ thứ tự công việc π = (1, 2, , n) tối ưu Xét thứ tự công việc π với thời gian gia công ban đầu p Đặt J tập hợp công việc chủ chốt, |J| ≥ Nếu tồn công việc chủ chốt thỏa mãn điều kiện cần đủ thứ tự tối ưu π, thời gian gia cơng p tối ưu khơng có phải bàn luận thêm Mặt khác điều kiện (2.1) Định lý 2.3 thỏa mãn điều kiện (2.2) bị vi phạm công việc chủ chốt từ tập J không thỏa mãn sử điều chỉnh thời gian gia công điều có nghĩa kết tối ưu cho tốn ngược, cơng việc h chủ chốt h ∈ J Vì khả công việc h ∈ / J chủ chốt, ta xét lớp kế hoạch khác với công việc chủ chốt ấn định h, ≤ h ≤ n Nhận thấy toán ngược |adjustable pj , π| Lmax Bổ đề 2.1 chứng tỏ số tốn xem xét Gọi h, ≤ h ≤ n, cơng việc chọn trở thành chủ chốt với thời gian gia công điều chỉnh p Nếu kỳ hạn khơng thỏa mãn (2.2) với hốn vị mục tiêu π công việc chọn h, khơng có điều chỉnh thời gian gia cơng làm cho thứ tự cơng việc π tối ưu Nếu mối liên hệ (2.2) thỏa mãn điều chỉnh thời gian gia cơng làm thay đổi thời gian hồn thành cơng việc Cj cho mối liên hệ (2.1) thỏa mãn, j pi , Cj = i=1 42 Bất đẳng thức (2.1) đơn giản thành dạng sau đây: h pi ≥ dh − dj với ≤ j ≤ h − 1, i=j+1 j pi ≤ dj − dh với h + ≤ j ≤ n i=h+1 Do toán đưa dạng đây: p − p h pi ≥ dh − dj−1 , với ≤ j ≤ h, s.t i=j j (2.23) pi ≤ dj − dh , h + ≤ j ≤ n, i=h+1 pj ≤ pj ≤ pj , ≤ j ≤ n Rõ ràng thời gian gia công gốc p ràng buộc (2.23) thời gian gia công số công việc từ tập N1 = {2, 3, , h} tăng thời gian gia công số công việc từ tập N2 = {h + 1, h + 2, , n} giảm Điều kéo theo điều chỉnh mong muốn biểu diễn dạng sau: p j = p j + x j , j ∈ N1 , p j = p j − y j , j ∈ N2 Và độ lệch khoảng sau: ≤ x j ≤ p j − p j , j ∈ N1 , ≤ y j ≤ p j − p j , j ∈ N2 Ta gọi số Pj , Qj , Aj , Bj xác định sau: h pj , Pj = (dh − dj−1 ) − j ∈ N1 , i=j j Qj = pj − (dj − dh ) , j ∈ N2 , i=h+1 Aj = p j − p j , j ∈ N, B j = pj − pj , j ∈ N 43 Và ta viết lại công thức (2.23) sau: F (x, y) h x i ≥ Pj , s.t j ∈ N1 , i=j j y i ≥ Q j , j ∈ N2 , (2.24) i=h+1 ≤ xj ≤ Aj , j ∈ N1 , ≤ yj ≤ B j , j ∈ N2 Trong hàm mục tiêu F có dạng :     βj yj , f or l1,α,β norm, α j xj +    j∈N j∈N   F (x, y) = f or l2,α,β norm, βj yi2 , αj x2j +  j∈N j∈N       max max {αj xj } , max {βj yj } , f or l∞,α,β norm j∈N1 j∈N2 Kết toán (2.24) xác định kết tối ưu cho toán ngược số lớp kế hoạch với công việc chủ chốt h Nhận thấy, tồn số lớp khơng có kết toán ngược |adjustable pj , π| Lmax tìm việc liệt kê tất lớp có kết chọn lớp có giá trị nhỏ F Sau ta nghiên cứu toán (2.24) với loại chuẩn khác Bài toán ngược |adjustable pj , π| Lmax với chuẩn l1 l2 Trước tiên ta xét chuẩn l1,α,β l2,α,β Để thuận tiện, ta viết lại công thức (2.24) đặt biến uj vj sau: uj = pj − pj = Aj − xj , j ∈ N1 , v j = p j − p j = B j − y j , j ∈ N2 (2.25) 44 Khi đó: ≤ uj ≤ Aj , j ∈ N1 , (2.26) ≤ v j ≤ B j , j ∈ N2 Do công thức (2.24) viết lại thành F h (u, v) h s.t ui ≤ i=j j Ai − Pj , j ∈ N1 , i=j j ui ≤ i=h+1 (2.27) B i − Q j , j ∈ N2 , i=h+1 ≤ u j ≤ Aj , j ∈ N1 , ≤ vj ≤ B j , j ∈ N2 , FK (u, v) = Vì hàm mục tiêu F          βj (Bj − vj ) , αj (Aj − uj ) + f or l1,α,β , j∈N2 j∈N1 2 βj (Bj − vj ) , f or l2,α,β αj (Aj − uj ) + j∈N2 j∈N1 (u, v) tách nên tốn (2.26) phân tích thành toán với ràng buộc biến N1 : αj (Aj − uj ) với chuẩn l1 αj (Aj − uj ) Ai − Pj , j ∈ N1 , ui ≤ i=j với chuẩn l2 h h s.t i=j ≤ uj ≤ Aj , j ∈ N1 , biến N2 : βj (Bj − vj ) với chuẩn l1 45 βj (Bj − vj ) h với chuẩn l2 h s.t vi ≤ i=j B i − Q j , j ∈ N2 , i=j ≤ vj ≤ B j , j ∈ N2 Các toán phân loại toán Resource Allocation Problem with Nested Constraints với biến liên tục, giải thời gian O(n log n) hàm mục tiêu tuyến tính bậc hai thuật tốn Vì lớp kế hoạch với cơng việc chủ chốt h, tốn giải thời gian O(n log n) thời gian hoàn thành toàn phần để xét n lớp kế hoạch O(n2 log n) Bài toán ngược |adjustable pj , π| Lmax với chuẩn l∞ Xét chuẩn l∞ công thức (2.24) Hàm mục tiêu đạt cực tiểu max max {αj xj } , max {βj yj } j∈N1 j∈N2 Ta thêm biến phụ θ cho giá trị hàm mục tiêu viết lại toán (2.24) sau: (2.28) θ s.t αj xj ≤ θ, j ∈ N1 , (2.29) βj yj ≤ θ, j ∈ N2 , (2.30) h x j ≥ P j , j ∈ N1 , (2.31) i=j j y j ≥ Q j , j ∈ N2 , (2.32) i=h+1 ≤ xj ≤ Aj , j ∈ N1 , (2.33) ≤ y j ≤ B j , j ∈ N2 (2.34) 46 Có thể thấy biết giá trị tối ưu θ∗ = max max {αj xj } , max {βj yj } j∈N1 j∈N2 hàm mục tiêu tất biến xj yj đặt giá trị lớn chúng: x∗j = {Ai , θ∗ /αj } , i ∈ N1 , yk∗ = {Bk , θ∗ /βk } , k ∈ N2 Rõ ràng, giá trị tối ưu θ∗ nhỏ cho tất ràng buộc (2.31) − (2.34) thỏa mãn Ta bắt đầu với θ = tăng cách cách lặp lại Với giá trị θ, giá trị x y cho bởi: xj (θ) = {Ai , θ/αj } , i ∈ N1 , yk (θ) = {Bk , θ/βk } , k ∈ N2 Đặt N ⊆ N1 N ⊆ N2 tập biến đạt tới cận chúng: xj (θ) = Ai , i ∈ N , yk (θ) = Bk , k ∈ N Ta tính độ hụt Dj ràng buộc (2.31) − (2.32): h Dj = max Pj − xi (θ) , i=j j Dj = max Qj − yi (θ) , j ∈ N1 , j ∈ N2 i=h+1 Nếu Dj > bất đẳng thức tương ứng bị vi phạm biến kéo theo tăng tổng lượng Dj Việc tăng xảy θ tăng Giả sử giá trị gần θ tăng δ > 0, ẩn xi (θ) , i ∈ N1 \N tăng lượng δ/αi ẩn yk (θ) , k ∈ N2 \N tăng lượng δ/βk Khi vế trái 47 ràng buộc (2.31), j tăng lượng δ (2.32), j tăng lượng δ i∈{h+1, ,j}\N i∈{j, ,h}\N 1/αi vế trái ràng buộc 1/βi Chọn σ giá trị nhỏ tất ràng buộc (2.31) − (2.32) thỏa mãn ẩn xi , i ∈ N1 \N yk , k ∈ N2 \N đạt tới cận Ai Bk δ = min j∈N1 Dj i∈{j, ,h}\N 1/αj j∈N2 , max{Aj − xj (θ), 0} Dj i∈{h+1, ,j}\N 1/βj , , max {Bj − yj (θ), 0} Đặt θ := θ + δ thay đổi tập công việc N , N Nếu ràng buộc (2.31) − (2.32) bị vi phạm ta tìm số gia δ tiếp tục việc tăng θ Vì với thời gian có ẩn đạt tới cận Ai Bk , khơng có nhiều n lần lặp kéo theo việc tăng θ Mỗi giá trị số gia δ tìm thời gian O(n) Do trường hợp kế hoạch với công việc chủ chốt h, toán giải thời gian O(n2 ) thời gian hoàn toàn phần O(n3 ) 2.4.2 Bài toán ngược |adjustable pj , L∗ | Lmax Cho trước thời gian trễ L∗ , điều điều chỉnh thời gian gia cơng pj để cho độ trễ tối đa Lmax ≤ L∗ Giả sử giá trị mục tiêu Lmax giá trị cho pj dj L, mục tiêu để tìm thời gian gia cơng điều chỉnh pj , pj ∈ pj , pj cho: p − p nhỏ giá trị L∗ đạt Giá trị L∗ đem lại kỳ hạn dj = dj + L∗ với công việc j ∈ N Do tốn ngược |adjustable pj , L∗ | Lmax quy toán máy đơn với thời gian gia cơng điều khiển xác định sau: pj contr, dj ≤ dj K 48 Trong tốn này, thời gian gia cơng cơng việc co lại đoạn pj , pj Sự co lại thời gian gia công công việc j từ giá trị lớn pj lượng yj , ≤ yj ≤ pj − pj K (y1 , , yn ) =  n   βj yj ,    j=1   f or l1 − norm, n βj yj2 , f or l2 − norm,   j=1     max {β y } , f or l − norm j j ∞ (2.35) Mục tiêu tìm thời gian gia cơng co pj = pj − yj với công việc j ∈ N cho công việc gặp kỳ hạn chúng dj đánh giá co K nhỏ Bài toán ngược |adjustable pj , L∗| Lmax với chuẩn l1 l2 Đầu tiên ta xét chuẩn l1,α,β l2,α,β Bài toán với thời gian gia cơng điều khiển pj contr, dj ≤ dj K biểu diễn dạng: K j (pi − yi ) ≤ dj , j ∈ N, s.t (2.36) i=1 ≤ yi ≤ B j , j ∈ N Trong đó: Bj = pj − pj K tuyến tính bậc hai Bài toán sau với: Bài toán Resoure Allocation Problems with Nested constraints giải thời gian O(n log n) thuật toán hàm mục tiêu tuyến tính bậc hai K Bài tốn ngược |adjustable pj , L∗| Lmax với chuẩn l∞ Xét chuẩn l∞ Bài toán ngược |adjustable pj , L∗| Lmax quy toán máy đơn với thời gian gia cơng điều khiển pj contr, dj ≤ dj max {βj yj } với hàm co tối thiểu Với toán này, Choi đồng tác giả báo [3] có đưa thuật toán độ phức tạp thời gian (n log n + cn) , c số phụ thuộc vào log maxj∈N αj pj − pj 49 Kết luận Luận văn nghiên cứu tốn ngược tốn tối thiểu hóa thời gian trễ tối đa công việc với thời gian đến mơ hình máy đơn loại chuẩn l1 , l2 , l∞ Cụ thể nghiên cứu tốn: • Bài toán ngược |adjustable dj , π| Lmax : Mục tiêu tốn ngược tìm kỳ hạn điều chỉnh d, dj ∈ dj , dj , j ∈ N, cho độ lệch d − d nhỏ nhất, thứ tự công việc π = (1, 2, , n) cho tối ưu • Bài toán ngược |adjustable dj , L∗ | Lmax : Giả sử cho trước giá trị thời gian trễ L∗ , mục tiêu tìm kỳ hạn điều chỉnh d, dj ∈ dj , dj , j ∈ N, cho độ lệch d − d nhỏ Lmax ≤ L∗ • Bài tốn ngược |adjustable pj , π| Lmax : Mục tiêu tốn ngược tìm thời gian gia cơng điều chỉnh p, pj ∈ pj ; pj , j ∈ N , cho độ lệch p − p nhỏ thứ tự công việc π = (1, 2, , n) cho tối ưu • Bài toán ngược |adjustable pj , L∗ | Lmax : Giả sử cho trước giá trị thời gian trễ L∗ , mục tiêu tốn ngược tìm thời gian gia công điều chỉnh p, pj ∈ pj ; pj , j ∈ N, cho độ lệch p − p nhỏ Lmax ≤ L∗ Nội dung đề tài phát triển nghiên cứu thêm toán ngược toán tối thiểu hóa thời gian trễ tối đa cơng việc với thời gian đến Σ max mơ hình máy đơn loại chuẩn lH , lH , với chuẩn định nghĩa 50 sau: n Σ lH = : d−d H,α,β max : d−d lH max H,α,β αj sgn max dj − dj , + βj sgn max dj − dj , j=1 = max αj sgn max dj − dj , j=1, ,n với αj , βj không âm + βj sgn max dj − dj , , 51 Tài liệu tham khảo Tiếng Việt [1] Nguyễn Việt Hưng (2016), Một số vấn đề xếp lập kế hoạch gia cơng tối ưu mơ hình máy đơn, Luận văn thạc sĩ, Đại học Khoa học - Đại học Thái Nguyên [2] Hoàng Thị Mơ (2017), Nghiên cứu điều kiện cần đủ giải pháp tối ưu số vấn đề lập kế hoạch gia cơng mơ hình máy đơn, Luận văn thạc sĩ, Đại học Khoa học – Đại học Thái Nguyên Tiếng Anh [3] Choi K., Jung G., Kim T., Jung S (1998) "Real – time scheduling algorithm for minimizing maximum weight error with O(n log n + cn) complexity" Information Processing Letters, 67:311-315 [4] C.W Duin, A Volgenant (2006), “Some inverse optimization problem under the Hamming distance”, European Journal of Operation Research, 170:887-899 [5] L.C Liu, J.Z Zhang (2006), “Inverse maximum flow problems under the eighted Hamming distance”, Journal of Combinatorial Optimization, 12:395408 52 [6] P Brucker (2001), Scheduling algorithms, Springger, Berlin [7] P Brucker, Natalia V Shakhlevich (2009), “Inverse scheduling with maximum lateness objective”, Journal of Scheduling, 12:475-488 ... 18 Vấn đề ngược vấn đề tối thiểu hóa thời gian trễ tối đa công việc với thời gian đến mơ hình máy đơn 20 2.1 Sơ lược vấn đề xếp ngược 21 2.2 Điều kiện cần đủ vấn đề tối thiểu. .. Chương Vấn đề ngược vấn đề tối thiểu hóa thời gian trễ tối đa công việc với thời gian đến mơ hình máy đơn Trong chương đưa vấn đề việc nghiên cứu số đối tượng vấn đề lập trình tự mơ hình máy đơn. .. 11 1.4 Vấn đề tối thiểu hóa thời gian trễ tối đa công việc với thời gian đến mơ hình máy đơn Lmax 12 1.5 Vấn đề xếp ngược 14 1.6 Vấn đề quy hoạch tuyến