Vận trù học
Vận trù học (Operations Research - OR) ra đời từ nhu cầu lập kế hoạch quân sự trong Thế chiến II, nhằm tối ưu hóa việc sử dụng nguồn lực quân sự thông qua các kỹ thuật định lượng Patrick Blackett là người đầu tiên áp dụng các kỹ thuật này, giúp giảm đáng kể số lượng đạn cần thiết để bắn hạ máy bay đối phương từ 20,000 đầu đạn xuống còn 4,000 vào năm 1941 Sau chiến tranh, Vận trù học đã được mở rộng ra các lĩnh vực kinh doanh, công nghiệp và xã hội, trở thành công cụ quan trọng trong nhiều ngành như hóa dầu, hàng không, logistics và chính phủ Ngày nay, Vận trù học tập trung vào phát triển các mô hình toán học để phân tích và tối ưu hóa các hệ thống phức tạp, khẳng định vị thế của mình trong nghiên cứu và ứng dụng.
Vận trù học nghiên cứu phân bổ nguồn lực tối ưu và cung cấp cơ sở hợp lý cho quyết định bằng cách phân tích các tình huống phức tạp, dự đoán hành vi hệ thống và cải thiện hiệu suất Công việc thực tế chủ yếu sử dụng kỹ thuật phân tích và số để phát triển mô hình toán học cho các hệ thống tổ chức, bao gồm con người, máy móc và hoạt động Vai trò của vận trù học ngày càng tăng trong cả lĩnh vực công và tư nhân, giải quyết nhiều vấn đề như giao thông vận tải, lập kế hoạch kiểm kê, sản xuất, truyền thông, quản lý tài sản và quản lý rủi ro Trong lĩnh vực công, nghiên cứu vận trù học tập trung vào các chính sách năng 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ế hệ thống khẩn cấp đô thị và thực thi pháp luật.
Nghiên cứu trong vận trù học và khoa học quản lý được phân loại thành ba lĩnh vực chính: Thứ nhất, nghiên cứu cơ sở trong ba lĩnh vực toán học gồm xác suất, tối ưu hóa và lý thuyết hệ động lực Thứ hai, nghiên cứu mô hình tập trung vào việc thiết lập, phân tích và mã hóa các mô hình, giải quyết chúng bằng phần mềm và đánh giá hiệu quả từ dữ liệu máy tính, chủ yếu dựa vào xác suất và kinh tế lượng Cuối cùng, nghiên cứu ứng dụng trong vận trù học áp dụng các mô hình vào các vấn đề thực tế trong kỹ thuật và kinh tế.
Trong vận trù học, các nhà nghiên cứu sử dụng kỹ thuật toán học, thống kê và ứng dụng máy tính để mô hình hóa các vấn đề thực tế và tìm ra giải pháp tối ưu trong bối cảnh hạn chế về thời gian, nguồn lực lao động, nguồn lực vật liệu và quy tắc kinh doanh Những lý thuyết và mô hình toán học mới được phát triển nhằm phân tích các hành vi và đặc điểm của các vấn đề thực tế, hỗ trợ quyết định cho việc phát triển và quản lý quy trình cũng như doanh nghiệp, với mục tiêu tối đa hóa lợi nhuận Mô hình tối ưu thường được diễn đạt dưới dạng max (min) f(x) với các điều kiện ràng buộc cụ thể.
Các giải pháp khả thi đáp ứng các yêu cầu đề ra, trong khi tối ưu hóa là quá trình xác định các giải pháp tối ưu từ những lựa chọn khả thi đó.
Vấn đề tối ưu hóa tổ hợp
Tối ưu hóa tổ hợp là một lĩnh vực trong tối ưu hóa toán học, liên quan đến toán học rời rạc, vận trù học, lý thuyết thuật toán và lý thuyết tính toán phức tạp Mục tiêu của nó là tìm ra giải pháp tối ưu từ một tập hợp lớn các phương án khả thi Trong nhiều bài toán như phân công tối ưu, cây khung ngắn nhất, vận chuyển và bài toán người giao hàng, các giải pháp thường là rời rạc, khiến việc tìm kiếm toàn diện trở nên không khả thi.
Tối ưu hóa tổ hợp là một lĩnh vực tương đối mới trong toán học ứng dụng, bắt đầu thu hút sự chú ý từ những năm 1950 khi các công cụ đại số tuyến tính và số nguyên được phát triển Lịch sử của lĩnh vực này gắn liền với tối ưu hóa tuyến tính, với những quan niệm ban đầu từ Kantorovich và Koopmans, đặc biệt trong các ứng dụng vận chuyển và chuyển tải Năm 1947, Dantzig đã phát triển phương pháp đơn hình và xây dựng quy hoạch tuyến tính như một công cụ tổng quát, nhằm giải quyết hiệu quả các bài toán tối ưu hóa tổ hợp.
Tối ưu hóa tổ hợp là lĩnh vực nghiên cứu các mô hình và phương pháp nhằm tối ưu hóa các lựa chọn rời rạc, bắt nguồn từ lý thuyết quy hoạch tuyến tính và liên kết chặt chẽ với toán học rời rạc, lý thuyết xác suất, khoa học máy tính, và lý thuyết tính độ phức tạp tính toán Mặc dù một số vấn đề trong lĩnh vực này đã được nghiên cứu kỹ lưỡng và có giải pháp tối ưu hóa trong thời gian đa thức, nhiều bài toán khác vẫn được coi là NP-hard Để giải quyết hiệu quả các bài toán tối ưu hóa tổ hợp, có ba phương pháp chính được áp dụng.
Cách thứ nhất là sử dụng một phương pháp liệt kê được đảm bảo để tạo ra một giải pháp tối ưu.
Cách thứ hai để giải quyết vấn đề là áp dụng một thuật toán xấp xỉ với thời gian chạy đa thức Cách thứ ba là áp dụng các kỹ thuật tìm kiếm kinh nghiệm, tuy nhiên không đảm bảo về chất lượng giải pháp hay thời gian thực hiện.
Nhiều quyết định trong cuộc sống thực tế có thể được xem như các vấn đề tối ưu hoá tổ hợp, dẫn đến sự quan tâm ngày càng tăng về lý thuyết và ứng dụng Các vấn đề như bài toán người giao hàng, lập kế hoạch mua sắm, và phân công công việc đều thuộc loại này Những bài toán tối ưu tổ hợp thường có quy mô lớn và khó giải quyết, do đó, nghiên cứu sự phức tạp tính toán và thiết kế thuật toán để phát triển các phương pháp giải quyết hiệu quả là mục tiêu chính của các nhà nghiên cứu trong lĩnh vực này.
Một vấn đề tối ưu tổ hợp P = (S, f) có thể được chỉ ra như sau
• Các ràng buộc giữa các biến,
• Một hàm mục tiêu f tối thiểu hóa (hoặc tối đa hóa), trong đó f :D 1 ×D 2 × ×D n −→R +
Tập hợp tất cả các giải pháp khả thi
S ={s∈D 1 ×D 2 × ×D n | s thỏa mãn các ràng buộc}.
Không gian tìm kiếm, thường được ký hiệu là S, bao gồm các giải pháp khả thi cho bài toán tối ưu tổ hợp Mục tiêu là tìm ra một giải pháp tối ưu s ∗ ∈ S, sao cho giá trị hàm f(s ∗ ) được tối thiểu hóa hoặc tối đa hóa, tức là f(s ∗ ) ≤ f(s) với mọi s ∈ S (hoặc f(s ∗ ) ≥ f(s) với mọi s ∈ S) Giải pháp tối ưu này được gọi là Giải pháp tối ưu của tập hợp (S, f).
S ∗ ⊆S là tập hợp các giải pháp tối ưu.
Lời giải của vấn đề gia công trên mô hình máy đơn
Trình tự khả thi và trình tự tối ưu
Vấn đề trình tự gia công là bài toán tối ưu hóa tổ hợp, trong đó các nhiệm vụ và số lượng máy cần xử lý là hữu hạn Do đó, giải pháp tối ưu thường được tìm ra từ một tập hợp giới hạn các giải pháp khả thi ban đầu, giúp hàm mục tiêu đạt giá trị tối ưu.
Trong vấn đề trình tự gia công, ta gọi giải pháp khả thi là trình tự khả thi, giải pháp tốt ưu được gọi là trình tự tối ưu.
Trong quá trình gia công, trình tự gia công là một yếu tố quan trọng, giúp xác định thứ tự thực hiện các nhiệm vụ trên máy xử lý Một trình tự khả thi cho phép sắp xếp tất cả các nhiệm vụ gia công một cách hợp lý và hiệu quả.
Trong ví dụ 1.1, chúng ta xem xét vấn đề trình tự gia công với n = 6, p = (12, 4, 7, 11, 6, 5) và ω = (4, 2, 5, 5, 6, 3) Mỗi trình tự gia công được chọn từ tập hợp các công việc đều có thể thực hiện, và trình tự tối ưu trong trường hợp này là [T5, T3, T6, T2, T4, T1].
Ví dụ 1.2 Cho vấn đề trình tự gia công F 2 ||C max trong đó n = 5.
Hình 1.1: Trình tự tối ưu của ví dụ 1.2.
Một trình tự gia công bất kỳ của tập các công việc đều là trình tự khả thi, trong đó [J 5 , J 1 , J 4 , J 3 , J 2 ] là trình tự tối ưu.
Hình 1.2: Sơ đồ Grant Charts.
Trình tự gia công không trì hoãn và trình tự gia công trì hoãn được
Trong quá trình giải quyết các vấn đề về trình tự gia công, có một loại trình tự khả thi quan trọng được định nghĩa Cụ thể, nếu tất cả các công việc đều được chuẩn bị trước và máy xử lý không có thời gian nghỉ trong suốt quá trình gia công, thì loại trình tự này được gọi là trình tự gia công không trì hoãn Ngược lại, nếu có thời gian nghỉ, loại trình tự này sẽ được gọi là trình tự gia công trì hoãn.
Trình tự gia công không trì hoãn đảm bảo máy móc luôn hoạt động liên tục mà không bị gián đoạn Đối với nhiều vấn đề liên quan đến trình tự gia công, trình tự tối ưu thường là không trì hoãn Tuy nhiên, cũng tồn tại một số trường hợp mà trình tự gia công có thể trì hoãn và vẫn đảm bảo tối ưu hóa hiệu suất.
Ví dụ 1.3 Trình tự gia công 1|r j |P w j C j , n = 2, p = (10,5), r = (0,1), w (1,5).
Vấn đề này có hai trình tự khả thi đó là:
Hình 1.3: Trình tự khả thi của ví dụ 1.3
Vấn đề tối thiểu hóa thời gian trễ tối đa của các công việc với thời
việc với thời gian đến như nhau trên mô hình máy đơn 1kL max
Một số ký hiệu trong bài toán 1kL max :
Trong một dãy công việc, Tj đại diện cho công việc thứ j, trong khi pj là thời gian cần thiết để gia công công việc Tj Ngoài ra, dj là thời gian hoàn thành hạn định cho công việc Tj.
P s=1 p s là thời gian hoàn thành thành công công việc T j , Thời gian trễ tối đa (maximum latenes)
L max = max{L j } trong đó, L j =C j −d j là thời gian trễ của công việc T j
Bài toán 1.1 Tìm thời gian trễ tối đa của các công việc được sắp thứ tự lần lượt từ công việc
T 1 −→ T 2 −→ T 3 −→ T 4 −→ T 5 −→ T 6 với các dữ kiện được cho theo bảng 1.1.
Thời gian gia công tương ứng (p j ) 3 1 4 1 3 2
Kỳ hạn hoàn thành tương ứng (d j ) 2 10 6 4 11 12
Hình 1.4: Trình tự thực hiện các công việc của bài toán 1.1
Khi đó thời gian trễ của các công việc T j là:
Vậy trễ tối đa L max = 5.
Mặt khác, nếu thay đổi thứ tự các công việc hoàn thành
Hình 1.5: Trình tự thực hiện các công việc của bài toán 1.1 theo thứ tự mới.
Khi đó, thời gian trễ của các công việc T j là
Vậy trễ tối đa L max = 4.
Khi thay đổi thứ tự thực hiện các công việc, thời gian trễ tối đa có thể khác nhau Do đó, vấn đề quan trọng là xác định cách sắp xếp thứ tự thực hiện cho một tập hợp công việc đã được định sẵn, nhằm giảm thiểu thời gian trễ tối đa khi thời gian hoàn thành có hạn.
Bài toán 1kL max có thể được giải quyết hiệu quả bằng cách áp dụng quy tắc ưu tiên kỳ hạn sớm nhất (Earliest Due Date first - EDD) Theo quy tắc này, các nhiệm vụ được sắp xếp theo thứ tự không giảm của các thời hạn dj, giúp tạo ra trình tự tối ưu cho việc thực hiện công việc.
Vấn đề sắp xếp ngược
Lý thuyết vật lý giúp chúng ta dự đoán và mô tả hệ thống vật lý, cho phép đưa ra kết quả đo lường thông qua quá trình mô hình hóa Ngược lại, vấn đề ngược lại liên quan đến việc chuyển đổi các phép đo và quan sát thành thông tin về vật thể hoặc hệ thống vật lý mà chúng ta muốn tìm hiểu.
Trong khi vấn đề thuận có một giải pháp duy nhất, vấn đề ngược lại lại không như vậy Chẳng hạn, khi xem xét các phép đo trọng lượng trên một hành tinh, từ phân bố khối lượng bên trong, chúng ta có thể xác định chính xác các giá trị của lực hấp dẫn xung quanh hành tinh Tuy nhiên, trong không gian tương đồng bên ngoài hành tinh, có thể tồn tại nhiều phân bố khối lượng khác nhau trong cùng một môi trường trọng lực.
Trong việc phân tích sự phân bố khối lượng từ quan sát các môi trường trọng lực, có nhiều giải pháp khả thi Do đó, để đạt được kết quả chính xác, cần xem xét và kiểm tra cẩn thận các thông số của mô hình.
Tối ưu hóa ngược là quá trình xác định sự thay đổi tối thiểu của các thông số để đạt được giải pháp tối ưu cho một vấn đề Trong khi giải quyết bài toán tối ưu, chúng ta thường giả định rằng các tham số như chi phí và năng lực đã được biết, nhưng thực tế thường chỉ có các ước lượng cho những tham số này Bên cạnh đó, có thể có những giải pháp được biết là tối ưu thông qua quan sát hoặc thí nghiệm Mục tiêu của tối ưu hóa ngược là tìm ra giá trị của các tham số khiến cho các giải pháp hiện tại trở thành tối ưu, đồng thời giảm thiểu sự thay đổi của các tham số so với các ước lượng ban đầu.
Các vấn đề sắp xếp thuận liên quan đến việc tổ chức một chuỗi công việc nhằm tối thiểu hóa các thông số như thời gian hoàn thành Ngược lại, các vấn đề sắp xếp ngược lại giả định rằng thứ tự công việc đã được xác định và mục tiêu là điều chỉnh tối thiểu các thông số để tối ưu hóa chuỗi công việc theo một hàm mục tiêu nhất định Vấn đề sắp xếp thuận rất quan trọng trong việc thiết kế hệ thống mới, trong khi vấn đề sắp xếp ngược lại đóng vai trò quan trọng trong việc nâng cao hiệu quả của hệ thống hiện có.
Trong những năm gần đây, tối ưu hóa ngược đã thu hút nhiều sự chú ý nghiên cứu Các nghiên cứu liên quan đến vấn đề này có thể được minh chứng qua các ứng dụng lập trình tự ngược trong lĩnh vực vận chuyển.
Các vấn đề ngược trong lập trình đơn máy đóng vai trò quan trọng trong việc giảm thiểu tổng thời gian hoàn thành công việc Nghiên cứu mới đã đưa ra những kết quả đáng chú ý liên quan đến các vấn đề phân loại ngược, mở ra hướng đi mới cho việc tối ưu hóa quy trình lập trình.
Vào năm 2005, C Koulamas đã nghiên cứu về lập trình tự ngược với các thông số công việc có thể kiểm soát, tập trung vào tổng thời gian hoàn thành có trọng số trên máy đơn Tuy nhiên, ông không xem xét khả năng giá trị của tiêu chí lập trình tự có thể cao hơn giá trị của tiêu chí lập trình tự ban đầu, điều này dẫn đến những kết quả không mong muốn Để khắc phục điểm yếu này, Chen đã chỉ ra và sử dụng công cụ lập trình toán học để nghiên cứu các vấn đề lập trình ngược trên máy đơn nhằm giảm thiểu tổng trọng số.
Thời gian hoàn thành và các giải pháp tối ưu cho bài toán 1kP w j C j đã được xác định theo các chuẩn l1, l2 và l∞ Ngoài ra, các vấn đề đảo ngược liên quan đến tổng thời gian hoàn thành trên máy đơn 1kP cũng đã được nghiên cứu.
C j và các giải pháp tối ưu liên quan của nó cũng đã được nghiên cứu.
Brucker và Shakhlevich đã nghiên cứu lập kế hoạch ngược trong bối cảnh tối đa hóa vấn đề khách quan Họ tập trung vào các đối số ngược của bài toán lập trình trên mô hình máy đơn 1kL max, đặc biệt khi có thể điều chỉnh ngày tháng hoặc thời gian xử lý theo các tiêu chuẩn l1, l2, và l∞ Hai vấn đề mà họ đề cập dường như thuộc loại NP-khó; để giải quyết chúng, họ đã xây dựng công thức lập trình toán học và phát triển các thuật toán giải pháp hiệu quả.
Các kết quả được tóm tắt trong bảng 1.2. Điều chỉnh kì hạn d j
Chuẩn Điều chỉnh thời gian gia công p j
Bài toán ngược với trình tự cho trước π
Bài toán ngược với giá trị L ∗ cho trước
Bảng 1.2: Độ phức tạp của bài toán ngược của bài toán 1kL max đối với các loại chuẩn l 1 , l 2 , l ∞
Vấn đề quy hoạch tuyến tính
Quy hoạch tuyến tính là một nhánh của lý thuyết tối ưu hóa, chuyên giải quyết các bài toán tối ưu hóa như tối đa hóa hoặc tối thiểu hóa chi phí Nó bao gồm một hàm mục tiêu tuyến tính với một số biến nhất định, được tối ưu hóa dựa trên các ràng buộc tuyến tính Các ràng buộc này có thể là các phương trình hoặc bất phương trình tuyến tính, liên quan chặt chẽ đến đại số tuyến tính, với điểm khác biệt chính là các điều kiện ràng buộc thường là bất phương trình.
Quy hoạch tuyến tính là phương pháp hiệu quả trong tối ưu tổ hợp, ứng dụng rộng rãi trong kinh tế và quản lý công ty Nhiều vấn đề thực tế có thể được mô tả dưới dạng quy hoạch tuyến tính, giúp các doanh nghiệp tối đa hóa lợi nhuận hoặc giảm thiểu chi phí với nguồn lực hạn chế Các lĩnh vực như quy hoạch, sản xuất, vận chuyển và công nghệ đều có thể áp dụng quy hoạch tuyến tính để đạt được hiệu quả cao nhất.
Các ý tưởng từ quy hoạch tuyến tính đã phát triển nhiều khái niệm quan trọng trong lý thuyết tối ưu hóa, bao gồm tính hai mặt, sự phân hoạch và vai trò của tính lồi cùng các khái niệm mở rộng của nó Một số trường hợp đặc biệt, như vấn đề mạng lưới và vấn đề đa giao thức, đã thu hút sự chú ý đáng kể và dẫn đến nhiều nghiên cứu về thuật toán chuyên dụng, phục vụ cho các ứng dụng thực tiễn.
Định nghĩa ba loại chuẩn l 1 , l 2 , l ∞
Một hàm f : R n −→ R với domf =R n được gọi là một chuẩn nếu:
• f thỏa mãn bất đẳng thức tham giác: f(x+y) ≤ f(x) +f(y), ∀ x, y ∈R n
Ký hiệu f(x) = |x| được sử dụng để chỉ ra rằng một chuẩn là sự mở rộng của giá trị tuyệt đối trên R Khi xác định một chuẩn cụ thể, chúng ta sử dụng ký hiệu |x| symb, trong đó chỉ số dưới là một ghi chú để chỉ ra định nghĩa nào đang được áp dụng.
Cho p≥1 là một số thực, trên không gian Euclide n chiều, độ dài của vector x = (x1, x2, , xn) được hiểu một cách trực quan Đối với p≥1, chuẩn p của x ∈ Rn được định nghĩa là kxk p.
Các tính chất của chuẩn Euclidean cũng áp dụng cho tất cả các chuẩn p, bao gồm: kxk p ≥ 0 và kxk p = 0 khi và chỉ khi x = 0; kkxk p = |k|kxk với mọi số thực k; và kx+yk p ≤ kxk p + kyky p.
Trong phần này, ta chỉ đề cập đến ba chuẩn p được sử dụng cho tất cả i 1,2, , n, và chúng là:
• Cho p= 1, ta nhận được chuẩn taxicab l 1 kxk 1 n
(Chuẩn taxicab hoặc được gọi là khoảng cách Manhattan).
• Cho p= 2, ta có được chuẩn Euclidean l 2 kxk 2 n
• Và như phương pháp tiếp cận chuẩn p− đạt được chỉ chuẩn hoặc chuẩn tối đa kxk ∞ = lim p→∞kxk ∞ = lim p→∞ n
Chuẩn vô cực được định nghĩa là giá trị lớn nhất tuyệt đối của các phần tử trong một tập hợp, ký hiệu là max i=1, ,n|x i | Định nghĩa này vẫn có thể áp dụng cho các giá trị 0< p d π(r), ta có thể thay đổi thứ tự công việc thành π 0 ( , π(r), π(i), ) Thời gian trễ tối đa của T π(r) đối với π 0 sẽ nhỏ hơn T π(r) của π, trong khi thời gian trễ của các công việc khác không tăng Do đó, L max (π 0 ) < L max (π) dẫn đến mâu thuẫn với tính tối ưu của π.
Giả sử giữ nguyên tất cả các trình tự tối ưu với ít hơn k công việc chủ chốt và xét trường hợp dãy π có k ≥ 2 công việc chủ chốt Nếu khẳng định không giữ nguyên đối với π, thì với công việc chủ chốt đầu tiên T π(r), tồn tại i < r sao cho d π(i) > d π(r) Điều này cho phép chúng ta di chuyển công việc T π(i) đến vị trí ngay sau T π(r), làm cho T π(r) không còn là công việc chủ chốt Kết quả này dẫn đến một trình tự tối ưu π có ít hơn k công việc chủ chốt, tạo ra mâu thuẫn với giả thiết quy nạp.
Ngược lại, giả sử có một công việc chủ chốt T π(r) sao cho d π(r) ≤ d π(i) ,∀ i > r. Chúng ta có thể giả sử rằng d π(r) ≤d π(j) ,∀ i > r Nếu điều này không đúng đối với một vài j, thì
L π(r) = C π(r) −d π(r) < C π(i) −d π(i) = L π(r) , mâu thuẫn với L π(r) =L max (π) do vậy d π(i) ≤d π(r) ≤ d π(j) ,∀ i < r < j.
Kết quả thu được là một trình tự sắp xếp mới π 0, được tạo ra bằng cách sắp xếp lại thứ tự các công việc trước và sau π(r) tương ứng theo quy tắc EDD.
Đoạn văn được viết lại: Theo quy tắc EDD, chuỗi π 0 là tối ưu Việc sắp xếp không làm thay đổi L π(r), dẫn đến L max (π) nhỏ hơn L max (π 0), do đó chuỗi π cũng được coi là tối ưu Định lý này đã được chứng minh.
Ví dụ 2.2 Ở bài toán 1.1, xét vấn đề 1kL max , trong đó n = 6, p= (3,1,4,1,3,2), d = (2,10,6,4,11,12).
Biết thời gian trễ tối đa (maximum latenes):
L max = max{L j } trong đó L j =C j −d j là thời gian trễ của nhiệm vụ T j Ta có: d 1 < d 4 < d 3 < d 2 < d 5 < d 6
Theo quy tắc EDD ta tìm được trình tự tối ưu là {d 1 , d 4 , d 3 , d 2 , d 5 , d 6 }.
Dãy công việc π = (1,2, , n) được coi là tối ưu cho bài toán 1kL max khi và chỉ khi tồn tại một công việc k thỏa mãn hai điều kiện cụ thể Trong đó, trễ tối đa được xác định là L max = 2.
C k −d k ≥ C j −d j với 1≤ j ≤ n, (2.1) d j ≤d k với 1≤ j ≤ k−1 (2.2) Nhận thấy rằng có thể tồn tại một số công việc thỏa mãn (2.1) cùng với giá trị
C k −d k Dưới đây ta gọi các công việc thỏa mãn (2.1) là chủ chốt đối với d và π.
Điều chỉnh kỳ hạn (Adjustable Due Dates)
Bài toán ngược 1 |adjustable d j , π| L max
Mục tiêu của bài toán là tìm kỳ hạn điều chỉnh db= (db 1 ,db 2 , ,db n ) với bd j ∈ d j , d j
, j ∈ N, sao cho độ lệch kdb− dk là nhỏ nhất, và trình tự công việc π (1,2, , n) là tối ưu.
Đầu tiên, chúng ta cần chứng minh rằng một công việc chủ chốt cho kỳ hạn ban đầu d cũng sẽ là chủ chốt cho kỳ hạn điều chỉnh d Sau đó, chúng ta sẽ giải thích cách tìm ra kỳ hạn điều chỉnh tối ưu db từ db1, , dbn.
Bổ đề 2.1 Cho h là một công việc chủ chốt đối với thời gian ban đầu d và một dãy trình tự công việc π= (1,2, , n).
Nếu bài toán ngược 1|adjustabled j , π|L max khả thi, thì sẽ có một phương án tối ưu db đảm bảo rằng công việc h giữ vai trò quan trọng trong kỳ hạn điều chỉnh db và dãy công việc π.
Bài toán 1|adjustabled j , π|L max không thể giải quyết được nếu kỳ hạn không thể điều chỉnh trong khoảng thời gian của chúng, điều này ảnh hưởng đến việc tối ưu hóa thứ tự công việc π.
Giả sử công việc h là yếu tố quyết định cho kỳ hạn gốc d, nhưng không ảnh hưởng đến các chủ chốt điều chỉnh d Nếu công việc b k khác lại là chủ chốt với db, thì điều này chứng minh rằng sự quan trọng của công việc có thể thay đổi tùy thuộc vào bối cảnh và các yếu tố liên quan.
L h =C h −d h ≥ C k −d k = L k (h là tham số với chủ chốt d),
Lb h =C h −db h < C k −db k =Lb k (k là tham số với chủ chốt d).b (2.3) Hơn nữa, ta sẽ sử dụng 2 điều kiện sau đây (đúng với công việc u bất kỳ thuộcN):
L u =C u −d u ≥ C k −d k =L k (h là tham số với chủ chốt d), (2.4)
Để chứng minh bổ đề, cần chỉ ra sự tồn tại của một tập hợp các kỳ hạn tối ưu db khác nhau, thỏa mãn các tính chất cần thiết.
(i) Cả hai công việc k và h là chủ chốt với kỳ hạn b d;b
(ii) Đoạn kỳ hạn thấy được bdb∈ d j , d j với mọi j ∈ N;
(iii) Độ lệch kỳ hạn của bdbso với kỳ hạn ban đầu không vượt quá độ lệch kỳ hạn của d:b bb d−d
(iv) Điều kiện cần và đủ của Định lý 2.3 của dãy sắp thứ tự công việc π tối ưu thỏa mãn với kỳ hạn bdbvà công việc k.
Tính chất cuối nghĩa là π là một dãy sắp thứ tự công việc tối ưu với kỳ hạn bdb cùng với tính chất (i) sẽ chứng minh được bổ đề.
Ta định nghĩa giá trị mới bd, sao cho độ trễ tối đab L o = max j∈N
, được tính đối với dãy sắp thứ tự công việc π và kỳ hạn b dbđược thỏa mãn:
Trong trường hợp này, điều kiện (2.3) nghĩa là:
Lb h ≤ Lb k = L o sao cho công việc u bất kỳ thuộc N\ {k} có độ trễ về kỳ hạn dbkhông lớn hơn
L 0 và tính chất (i) được thỏa mãn với công việc k.
Trong trình tự đạt tới tính chất (i) với công việc h, kỳ hạn của nó có thể thay đổi về giá trị bb d h =C h −L 0 (2.9) sao cho bb
L h = C h −bdb h =L 0 Nhận thấy kỳ hạn bdbnhỏ hơn db k : bdb−db h = C h −L 0
Do đó kỳ hạn b dbcó được từ dbbằng cách giảm một thành phần từ db k để thành bb d k
Ta chứng minh rằng tính chất (ii) – (iii) đúng với công việc h: bdb h (2.9) = C h −L o
Do đó điều kiện (2.6) được thoả mãn.
Xét tính chất (iv), công việc k là chủ chốt với kỳ hạn db và b dbsao cho điều kiện (2.1) được thỏa mãn Điều kiện (2.2) cũng đúng với bất kỳ công việc j nào đứng trước k Theo giả thiết, kỳ hạn db là tối ưu, vì vậy điều kiện (2.2) được thỏa mãn với db và công việc j trước công việc tối ưu k Sau khi giảm một thành phần của db xuống b db, điều kiện (2.2) vẫn giữ nguyên với b db và công việc chủ chốt k.
L 0 =L h L0}, có độ trễ lớn hơn L0 Tập U bao gồm cả công việc k, và với mỗi công việc u ∈ U, kỳ hạn db u của nó có thể điều chỉnh đến giá trị bb d u = C u − L0, nhằm giảm độ trễ xuống còn L0.
Nhận thấy mỗi kỳ hạn b db u lớn hơn kỳ hạn tương ứng db u : bdb u −db u = C u −L 0
Do điều kiện (2.12), sau khi kỳ hạn của các công việc của tập U tăng lên, tất cả chúng trở thành chủ chốt đối với b Khi áp dụng tính chất (i) với công việc h, nếu h thuộc tập U, công việc h sẽ trở thành chủ chốt đối với d.
Và kỳ hạn db k của nó có thể thay đổi đến giá trị: bdb=C k −L 0 (2.14) sao cho bb
Nhận thấy kỳ hạn b db k nhỏ hơn db k bb d h −d u = C u −L 0
Bây giờ ta chứng minh rằng tính chất (ii) – (iii) đúng với các công việc từ tập
U và công việc h Kỳ hạn của công việc bất kỳ u∈ U tăng từ db u ≥d u đến bb d (2.11) = C u −L 0 (2.10) = C u −L h
Kéo theo d u ≤db u ≤bdb u ≤d u , sao cho độ lệch kỳ hạn của công việc bất kỳ u∈U không tăng: bdbu−du
Bây giờ ta xét sự điều chỉnh của kỳ hạn của công việc h.
Nếu h ∈U thì lập luận ở trên đúng với công việc h, còn nếu không thì kỳ hạn của công việc h giảm từ db k ≤d k đến bb d h (2.14) = C h −L 0 (2.10) = C h −L h = d h ≥d h sao cho d u ≤b db h ≤ db h ≤d h
Do đó điều kiện (2.6) được thỏa mãn.
Cuối cùng, chúng ta chứng minh tính chất (iv) bằng cách sử dụng tính chất (i), trong đó công việc k là chủ chốt với kỳ hạn db và b dbsao cho điều kiện (2.1) được thỏa mãn Cần chỉ ra rằng điều kiện (2.2) cũng được thỏa mãn với b db và công việc j bất kỳ đứng trước k Điều này cho thấy rằng để hoán vị π là tối ưu, nó phải thỏa mãn với công việc chủ chốt k và kỳ hạn db, tức là db j ≤ db k.
Nếu j /∈ U thì kỳ hạn của nó không tăng, sao cho: bdb j ≤b db k
Nếu j = u∈U thì điều kiện (2.2) chỉ bị vi phạm nếuC u < C k và b db j >b db k Nghĩa là
Vậy Bổ đề 2.1 được chứng minh
Theo Bổ đề 2.1, để xác định kỳ hạn điều chỉnh tối ưu d,b, chúng ta có thể giới hạn phạm vi xem xét thành một lớp các trình tự với một công việc chủ chốt cố định h, trong đó h là công việc chủ chốt đối với kỳ hạn ban đầu d Nếu điều kiện (2.1)−(2.2) của Định lý 2.3 được thỏa mãn với dãy sắp thứ tự công việc π, thì khi có công việc chủ chốt h và thời gian ban đầu d, sẽ không cần điều chỉnh, đồng nghĩa với việc trình tự công việc hiện tại là tối ưu và độ lệch kdb−dk bằng 0 Ngược lại, khi xem xét các giá trị khác nhau bd h ∈ d h, d h, ta định nghĩa kỳ hạn điều chỉnh db j cho tất cả các công việc còn lại j ∈ N\{h} phụ thuộc vào db h.
Để đạt được công thức điều chỉnh thời hạn, chúng ta chia đoạn d h thành các đoạn nhỏ với cùng tập con các công việc cần điều chỉnh Mỗi đoạn con sẽ được phân tích tham số của toàn bộ đoạn d h, nhằm tối ưu hóa quá trình điều chỉnh.
Trong mỗi đoạn con, chúng ta xác định một kỳ hạn tối ưu db k và kỳ hạn tương ứng db j với j ∈ N\{h}, sao cho điều kiện cần và đủ của Định lý (2.3) được thỏa mãn và độ lệch kdb−dkl là nhỏ nhất Kết quả của bài toán được xác định bằng cách xem xét kết quả của tất cả các đoạn con và chọn ra kết quả có độ lệch kdb−dk nhỏ nhất Đoạn dh được chia bởi các giá trị khác nhau trong tập {Ch−L1, Ch−L2, , Ch−Ln} ∪ {d1, d2, , dn} thuộc đoạn đó, với dãy sắp thứ tự của các giá trị là dh = tk1 < tk2 < < tkz = dh.
Nhận thấy, với công việc h, hai giá trị C h − L h và d h là trùng nhau, sao cho z ≤n+h−1.
Giả sử kỳ hạn điều chỉnh db h thuộc vào đoạn con t k g , t k g+1
,1≤ g ≤z−1. Xét điều kiện (2.1) của Định lý 2.3 với công việc j bất kỳ thuộc N\ {h} giá trị
C h −L j thỏa mãn một trong các điều kiện sau:
Các công việc h∈ N\{h} đáp ứng điều kiện (2.16) sẽ vi phạm điều kiện (2.1) của Định lý 2.3 đối với bất kỳ thuộc t k g và t k g+1 Đồng thời, những công việc không đáp ứng điều kiện (2.17) cũng không thỏa mãn điều kiện (2.1).
Bây giờ ta xét điều kiện (2.2) của Định lý 2.3 với công việc j bất kỳ thuộc {1,2, , h−1}, giá trị d j thỏa mãn một trong các điều kiện sau: d j ≤t k g ≤ db h (2.18) hoặc d j ≤t k g+1 ≤ db h (2.19)
Các công việc thỏa mãn (2.18) không vi phạm điều kiện (2.2) của Định lý 2.3 và các công việc thỏa mãn (2.19) vi phạm điều kiện (2.2) với db h ∈ t k g , t k g+1
Chúng ta có thể xác định hai tập con các công việc có kỳ hạn có thể được điều chỉnh theo thứ tự để đáp ứng các điều kiện cần và đủ của Định lý 2.3 liên quan đến sắp xếp mục tiêu π với công việc chủ chốt h và db h ∈ t k g , t k g+1.
U g u | u∈N\ {h} và C h −L u ≤ t k g - các công việc vi phạm (2.1),
V g v | v ∈ {1, , h−1} và d v ≥t k g+1 - các công việc vi phạm (2.2).
Rõ ràng kỳ hạn của các công việc trong U g có thể tăng, trong khi kỳ hạn của các công việc trong V g lại giảm.
Nhận thấy U g ∩V g = ∅, với bất kỳ v ∈V g thì C v < C h và d v ≥ t k g+1 ≥ t k g Do đó
Điều kiện (2.16) không đảm bảo các tính chất đặc trưng của U g Các tập con U g và V g được xác định trên các đoạn t k g và t k g+1 có thể khác biệt hoàn toàn so với các tập U g+1 và V g+1, được định nghĩa trên các đoạn t k g+1 và t k g+2 tiếp theo.
. Đặc biệt, với hai đoạn liên tiếp U g ⊆U g+1 và V g ⊇V g+1
Ta bắt đầu với kỳ hạn điều chỉnh db h thuộc vào đoạn đầu tiên [t k 1 , t k 2 ] và tiếp tục với các đoạn tiếp theo, tk g , tk g+1
, g = 2,3, , z, xét từng đoạn một Với mỗi đoạn t k g , t k g+1 ta ký hiệu kỳ hạn điều chỉnh của công việc từ U g và V g bởi db u =d u +x u , u∈U g , db v =d v −y v , v ∈ V g
Và xác định các hàm minF db h , x, y
(2.20) trong đó hàm mục tiêu F có dạng :
, f or l ∞,α,β norm. Đánh giá của những điều chỉnh này là nhỏ nhất nếu điều kiện (2.1) và (2.2) được coi như là các đẳng thức đối với kỳ hạn điều chỉnh
Bài toán ngược 1 |adjustable d j , L ∗ | L max
Giả sử cho trước giá trị thời gian trễ L ∗ , và mục tiêu là tìm ra kỳ hạn điều chỉnh db j ,db j ∈ d j , d j sao cho db−d là nhỏ nhất và L max ≤L ∗
Giá trị nhỏ nhất của L max có thể được đảm bảo bằng cách sắp xếp các công việc theo thứ tự kỳ hạn sớm nhất (EDD), do đó, chúng ta có thể giới hạn phạm vi tìm kiếm trong các lớp trình tự phù hợp với EDD.
Bắt đầu với trình tự EDD và kỳ hạn gốc, nếu điều kiện L max ≤ L ∗ được thỏa mãn thì không cần điều chỉnh Ngược lại, nếu có thể tăng kỳ hạn của một số công việc, hãy xác định H ={h i } là tập hợp các công việc chủ chốt, với L = L max.
Nếu L > L ∗, có khả năng mở rộng kỳ hạn cho các công việc trong tập H Các kỳ hạn bổ sung có thể được xác định cho tất cả các công việc từ H, với công thức: db j = d j + x, trong đó x ≥ 0 và j thuộc H Biên độ của kỳ hạn có thể được tính toán như sau: x ≤ min j∈H (n db j − d j).
Để tháo gỡ nút thắt trong thời hạn sớm nhất khi có nhiều công việc cùng thời hạn, cần xem xét tính chất của các công việc này Nếu không có công việc nào là chủ chốt, thứ tự thực hiện không quan trọng Ngược lại, nếu chỉ có một công việc cuối cùng là chủ chốt, việc điều chỉnh sẽ phụ thuộc vào loại chuẩn và độ lệch db−d, được tính theo một trong các công thức đã đề cập.
P h∈H α h x 2 f or l 2,α,β norm, maxh∈H {α h } ×x f or l ∞,α,β norm.
Trong các kế hoạch kỳ hạn sớm nhất, giá trị của db−d đạt mức tối thiểu với mỗi chuẩn nếu dãy công việc có cùng kỳ hạn được sắp xếp theo thứ tự không tăng của αj.
Sắp thứ tự chính, ký hiệu là σ, được định nghĩa là sắp xếp các công việc theo thứ tự không tăng của α j.
Sự điều chỉnh kỳ hạn của các công việc chủ chốt có thể làm thay đổi thứ tự kỳ hạn sớm nhất, đặc biệt khi xuất hiện các công việc chủ chốt mới Trong quá trình duy trì thứ tự chính và giữ vết của công việc chủ chốt H, việc điều chỉnh kỳ hạn có thể lặp lại Tại mỗi lần lặp, các công việc được đánh số theo thứ tự chính Sự tăng kỳ hạn d h j của công việc h j ∈ H có thể dẫn đến sự thay đổi cấu trúc, tạo ra một trong ba trường hợp khác nhau Giả sử h j là công việc thứ k trong thứ tự chính σ, tức là h j = σ(k).
Trường hợp A: Kỳ hạn của công việc σ(k) đạt tới kỳ hạn của công việc tiếp theo σ(k+ 1) của sắp 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 ∗ của độ trễ tối đa đạt được;
Trường hợp D: Kỳ hạn của công việc σ(k) đạt tới cận dưới của nó d σ(k) Xác định sự gia tăng d σ(k) bởi x A σ(k) = d σ(k+1) −d σ(k) , x B σ(k) = L− max j∈ N \H{C j −d j }, x C σ(k) = L−L ∗ , hoặc x D σ(k) =d σ(k) −d σ(k) theo thứ tự dẫn tới trường hợp A, B, C hoặc D.
Giá trị của L max sẽ giảm nếu thời gian hoàn thành của tất cả các công việc trong tập H tăng lên cùng một lượng x, cho đến khi xảy ra các trường hợp sớm nhất A, B, C hoặc D Do đó, giá trị x được xác định bằng công thức: x = min σ(k)∈H min d σ(k+1) − d σ(k), L − max{C j − d j}, L − L ∗, min σ(k)∈H d σ(k) − d σ(k).
Trong trường hợp A, nếu kỳ hạn của các công việc σ(k) và σ(k+1) bằng nhau, cần phải đánh số lại và cập nhật sắp thứ tự để các công việc cùng kỳ hạn được sắp xếp theo thứ tự không tăng của αj Nếu xảy ra trường hợp B, tập H có thể được cập nhật và giá trị L của độ trễ tối đa có thể giảm bởi x trong cả hai trường hợp Việc tăng kỳ hạn của tập H sẽ tiếp tục cho đến khi xảy ra một trong các trường hợp C hoặc D Nếu trường hợp C xảy ra, giá trị mục tiêu L* đạt được và được coi là tối ưu, vì trong mỗi lần lặp, hoán vị kỳ hạn sớm nhất được xem xét, chọn công việc với giá trị αj nhỏ nhất để điều chỉnh Trong trường hợp D, kỳ hạn của ít nhất một công việc chủ chốt không thể tăng thêm, dẫn đến việc giá trị mục tiêu L* không thể đạt được Dãy công việc ban đầu có thể được xây dựng trong thời gian O(nlogn), và mỗi lần lặp lại, lượng điều chỉnh x được tính trong thời gian O(n).
Bài toán ngược 1|adjustable d j , L ∗ |L max có thể được giải quyết trong thời gian O(n²), với điều kiện B xảy ra không quá n lần và C xảy ra đúng một lần Thời gian hoàn thành của việc giải quyết bài toán này được chứng minh thông qua việc giảm sức ép của tất cả các công việc chủ chốt lặp lại với cùng lượng x xác định Nếu không tồn tại kết quả, phương pháp tương tự cũng cho phép giải quyết bài toán trong thời gian O(n²).
Điều chỉnh thời gian gia công (Adjustable Processing Times)
Bài toán ngược 1 |adjustable p j , π| L max
Mục tiêu của bài toán ngược 1|adjustablep j , π|L max là tìm thời gian gia công điều chỉnh p,b pb j ∈ h pj;p j i
, j ∈ N, độ lệch so với thời gian gia công gốc kpb−pk là nhỏ nhất và sắp thứ tự công việc π = (1,2, , n) là tối ưu.
Xét một sắp thứ tự công việc π với thời gian gia công ban đầu p. Đặt J là tập hợp các công việc chủ chốt, |J| ≥1.
Nếu có ít nhất một công việc chủ chốt đáp ứng đầy đủ các điều kiện của sắp thứ tự tối ưu π, thì thời gian gia công plà đã đạt tối ưu và không cần thảo luận thêm.
Điều kiện (2.1) của Định lý 2.3 được thỏa mãn trong khi điều kiện (2.2) bị vi phạm đối với công việc chủ chốt từ tập J Điều này cho thấy rằng trong một kết quả tối ưu cho bài toán ngược, một công việc mới h có thể trở thành chủ chốt h ∈ J Do khả năng công việc bất kỳ h /∈ J cũng có thể là chủ chốt, chúng ta cần xem xét các lớp kế hoạch khác nhau với công việc chủ chốt được ấn định h, với 1 ≤ h ≤ n Đối với bài toán ngược 1|adjustablepj, π|Lmax, Bổ đề 2.1 chứng minh rằng chỉ một số ít bài toán có thể được xem xét.
Công việc h, với 1≤ h≤ n, có thể trở thành chủ chốt nếu thời gian gia công điều chỉnh p Nếu kỳ hạn không đáp ứng yêu cầu (2.2) với hoán vị mục tiêu π và công việc h được chọn, thì không có cách nào điều chỉnh thời gian gia công để đạt được sắp xếp công việc π tối ưu.
Nếu mối liên hệ (2.2) được đáp ứng, việc điều chỉnh thời gian gia công sẽ ảnh hưởng đến thời gian hoàn thành công việc C j, nhằm đảm bảo mối liên hệ (2.1) được thỏa mãn.
Bất đẳng thức (2.1) đơn giản thành dạng sau đây: h
Do đó bài toán được đưa về dạng dưới đây: minkpb−pk s.t. h
Nếu thời gian gia công gốc p các ràng buộc của (2.23) thay đổi, thời gian gia công của một số công việc trong tập N1 ={2,3, , h} sẽ tăng, trong khi thời gian gia công của một số công việc trong tập N2 ={h+ 1, h+ 2, , n} sẽ giảm Điều này dẫn đến sự điều chỉnh mong muốn được thể hiện như sau: pbj = pj + xj với j ∈ N1 và pbj = pj − yj với j ∈ N2.
Và các độ lệch trong khoảng sau:
Ta gọi các hằng số P j , Q j , A j , B j xác định như sau:
Và ta viết lại công thức (2.23) như sau: minF (x, y) s.t. h
Trong đó các hàm mục tiêu F có dạng :
Kết quả của bài toán (2.24) xác định một giải pháp tối ưu cho bài toán ngược trong một số lớp kế hoạch với công việc chủ chốt h Tuy nhiên, có những lớp không có giải pháp cho bài toán ngược 1|adjustablep j , π|L max, và để tìm ra giải pháp, cần liệt kê tất cả các lớp có một kết quả và chọn lớp có giá trị F nhỏ nhất.
Sau đây ta nghiên cứu bài toán (2.24) với các loại chuẩn khác nhau.
Bài toán ngược 1|adjustablep j , π|L max với chuẩn và l 1 và l 2
Trước tiên ta xét các chuẩnl 1,α,β vàl 2,α,β Để thuận tiện, ta viết lại công thức (2.24) đặt các biến u j và v j như sau: uj =p j −pbj =Aj −xj, j ∈N1, vj =pbj−p j =Bj−yj, j ∈N2.
Do đó công thức (2.24) được viết lại thành minF P (u, v) s.t. h
P j∈N 1 αj(Aj−uj) + P j∈N 2 βj(Bj −vj), f or l1,α,β,
Hàm mục tiêu F P (u, v) có khả năng tách biệt, cho phép bài toán (2.26) được phân tích thành hai bài toán con Các bài toán này bao gồm việc tối thiểu hóa α j (A j −u j ) với chuẩn l 1 hoặc tối thiểu hóa α j (A j −u j ) 2 với chuẩn l 2, kèm theo các ràng buộc của biến N 1.
0≤ u j ≤ A j , j ∈N 1 , và của biến N2: minX β j (B j −v j ) với chuẩn l 1 hoặc minX β j (B j −v j ) 2 với chuẩn l 2 s.t. h
Các bài toán phân bổ tài nguyên với các ràng buộc lồng nhau và biến liên tục được giải quyết trong thời gian O(nlogn) cho hàm mục tiêu tuyến tính và bậc hai Đặc biệt, trong các lớp kế hoạch có công việc chủ chốt h, thời gian giải quyết bài toán cũng là O(nlogn) Đối với n lớp kế hoạch, thời gian hoàn thành toàn phần là O(n^2 logn).
Bài toán ngược 1|adjustablep j , π|L max với chuẩn l ∞
Xét chuẩn l ∞ và công thức (2.24) Hàm mục tiêu đạt cực tiểu max maxj∈N 1
Ta thêm một biến phụ θ cho giá trị của hàm mục tiêu và viết lại bài toán (2.24) như sau: minθ (2.28) s.t α j x j ≤θ, j ∈N 1 , (2.29) β j y j ≤θ, j ∈N 2 , (2.30) h
Có thể thấy rằng nếu biết giá trị tối ưu của θ ∗ = max maxj∈N 1
{β j y j } của hàm mục tiêu thì tất cả các biến x j và y j được đặt bằng giá trị lớn nhất có thể của chúng: x ∗ j = min{A i , θ ∗ /α j }, i ∈N 1 , y ∗ k = min{B k , θ ∗ /β k }, k ∈N 2
Rõ ràng, giá trị tối ưu θ ∗ có thể nhỏ nhất có thể sao cho tất cả các ràng buộc (2.31)−(2.34) đều được thỏa mãn.
Bắt đầu với θ = 0, giá trị của θ được tăng lên lặp lại Đối với mỗi giá trị θ, x và y được xác định bởi công thức: x j (θ) = min{A i , θ/α j } với i thuộc N 1, và y k (θ) = min{B k , θ/β k } với k thuộc N 2 Khi N 1 và N 2 là các tập con của các biến đạt cận dưới, ta có x j (θ) = A i với i thuộc N 1, và y k (θ) = B k với k thuộc N 2.
Ta tính độ hụt D j đối với các ràng buộc (2.31)−(2.32):
Nếu Dj > 0 thì bất đẳng thức tương ứng bị vi phạm và các biến kéo theo tăng bởi tổng lượng Dj Việc tăng này chỉ xảy ra nếu θ tăng.
Khi giá trị θ tăng lên bởi δ > 0, các ẩn x i (θ) với i thuộc N 1 \N 1 sẽ tăng lên một lượng δ/α i, trong khi các ẩn y k (θ) với k thuộc N 2 \N 2 cũng tăng lên δ/β k Do đó, vế trái của ràng buộc (2.31) sẽ tăng thêm δP i∈{j, ,h}\N 11/α i, và vế trái của ràng buộc (2.32) sẽ tăng thêm δP i∈{h+1, ,j}\N 21/β i Để đảm bảo tất cả các ràng buộc (2.31)−(2.32) được thỏa mãn, cần chọn σ là giá trị nhỏ nhất sao cho ít nhất một trong các ẩn x i hoặc y k đạt đến cận dưới A i hoặc B k Tham số δ được xác định là min.
Đặt θ := θ+δ và điều chỉnh các tập con của các công việc N1, N2 Nếu các ràng buộc trong (2.31)−(2.32) vẫn không được thỏa mãn, chúng ta sẽ xác định giá trị gia δ tiếp theo và tiếp tục tăng θ.
Mỗi khoảng thời gian có ít nhất một ẩn đạt tới cận dưới A i hoặc B k, dẫn đến không quá n lần lặp làm tăng θ Giá trị của số gia δ có thể tìm thấy trong thời gian O(n) Do đó, đối với các kế hoạch với công việc chủ chốt, bài toán được giải quyết trong thời gian O(n²) và thời gian hoàn thành toàn phần là O(n³).
Bài toán ngược 1 |adjustable p j , L ∗ | L max
Cho trước thời gian trễ L ∗ , khi đó điều khi đó điều chỉnh thời gian gia công p j để sao cho độ trễ tối đa L max ≤ L ∗
Giả sử giá trị mục tiêu L max đối với p j và d j là L, mục tiêu là tìm thời gian gia công điều chỉnh bp j, pb j ∈ h pj, p j i sao cho kpb−pk là nhỏ nhất và đạt được giá trị L ∗ Giá trị L ∗ dẫn đến kỳ hạn d j = d j + L ∗ cho công việc j ∈ N Do đó, bài toán ngược 1|adjustable p j, L ∗ |L max trở thành bài toán máy đơn với thời gian gia công có thể điều khiển xác định: 1 p j contr, d j ≤ d j.
Trong bài toán này, thời gian gia công công việc có thể được co lại trong đoạn hp j, p j i
Sự co lại của thời gian gia công của công việc j từ giá trị lớn nhất p j bởi lượng y j , 0≤y j ≤ p j −p j.
P j=1 β j y j 2 , f or l 2 −norm, max{β j y j }, f or l ∞ −norm.
Mục tiêu của bài toán là tìm thời gian gia công co pb j = p j − y j cho mọi công việc j ∈ N, nhằm đảm bảo rằng các công việc gặp kỳ hạn d j và đánh giá sự co K là nhỏ nhất Bài toán ngược 1|adjustable p j, L∗|L max được nghiên cứu với các chuẩn l 1 và l 2 Đầu tiên, chúng ta xem xét các chuẩn l 1, α, β và l 2, α, β Bài toán này liên quan đến thời gian gia công có thể điều khiển 1 p j contr, với điều kiện d j ≤ d j.
K được biểu diễn dưới dạng: minK s.t. j
In the context of resource allocation problems with nested constraints, the equation B_j = p_j - p_j is relevant, where K can be either linear or quadratic This problem can be efficiently solved in O(n log n) time using an algorithm designed for linear and quadratic objective functions K.
Bài toán ngược 1|adjustablep j , L∗|L max với chuẩn l ∞
Bài toán ngược 1|adjustablep j , L∗|L max được nghiên cứu trong bối cảnh chuẩn l ∞ và có thể quy về bài toán máy đơn với thời gian gia công điều khiển 1 p j contr, d j ≤ d j max{β j y j } nhằm tối thiểu hóa hàm co Choi và các đồng tác giả đã đề xuất một thuật toán với độ phức tạp thời gian 0 (nlogn+cn) trong bài báo [3], trong đó c là hằng số phụ thuộc vào logh max j∈N n α j p j −p j oi.
Luận văn nghiên cứu bài toán ngược liên quan đến việc tối thiểu hóa thời gian trễ tối đa của các công việc có thời gian đến giống nhau trên mô hình máy đơn Nghiên cứu tập trung vào các loại chuẩn l1, l2 và l∞, nhằm phân tích và giải quyết các bài toán cụ thể trong lĩnh vực này.
• Bài toán ngược 1|adjustabled j , π|L max : Mục tiêu của bài toán ngược là tìm kỳ hạn điều chỉnh d,b db j ∈ d j , d j
, j ∈ N, sao cho độ lệch db−d là nhỏ nhất, và thứ tự công việc π = (1,2, , n) đã cho là tối ưu.
• Bài toán ngược 1|adjustable d j , L ∗ |L max : Giả sử cho trước giá trị thời gian trễ
L ∗ , và mục tiêu là tìm ra kỳ hạn điều chỉnh d,b db j ∈ d j , d j
, j ∈ N, sao cho độ lệch db−d là nhỏ nhất và L max ≤ L ∗
• Bài toán ngược 1|adjustablep j , π|L max : Mục tiêu của bài toán ngược là tìm thời gian gia công điều chỉnh p,b pb j ∈ h pj;p j i
, j ∈ N , sao cho độ lệch kpb−pk là nhỏ nhất và thứ tự công việc π= (1,2, , n) đã cho là tối ưu.
• Bài toán ngược 1|adjustablep j , L ∗ |L max : Giả sử cho trước giá trị thời gian trễ
L ∗ , và mục tiêu của bài toán ngược là tìm thời gian gia công điều chỉnh p,b pb j ∈ h pj;p j i
, j ∈ N, sao cho độ lệch kpb−pk là nhỏ nhất và L max ≤ L ∗
Đề tài nghiên cứu mở rộng bài toán ngược liên quan đến tối thiểu hóa thời gian trễ tối đa của các công việc có thời gian đến giống nhau trên mô hình máy đơn Các loại chuẩn được xem xét bao gồm l H Σ và l max H, với chuẩn l H Σ được định nghĩa là db−d.
= max j=1, ,n h αjsgn maxn dbj −dj,0o
+βjsgn maxn dj −dbj,0oi với α j , β j là không âm.
Nguyễn Việt Hưng (2016) đã trình bày trong luận văn thạc sĩ của mình tại Đại học Khoa học - Đại học Thái Nguyên về các vấn đề liên quan đến việc sắp xếp và lập kế hoạch gia công tối ưu trên mô hình máy đơn.
Hoàng Thị Mơ (2017) trong luận văn thạc sĩ của mình tại Đại học Khoa học – Đại học Thái Nguyên đã nghiên cứu các điều kiện cần và đủ để tìm ra giải pháp tối ưu cho một số vấn đề lập kế hoạch gia công trên mô hình máy đơn Nghiên cứu này đóng góp vào việc cải thiện hiệu quả trong quy trình gia công, giúp nâng cao chất lượng sản phẩm và tiết kiệm thời gian.
[3] Choi K., Jung G., Kim T., Jung S (1998) "Real – time scheduling algorithm for minimizing maximum weight error with O(nlogn +cn) complexity" In- formation 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:395-408.
