Luận văn này trình bày về bài toán ngược của bài toá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 gian đến như nhau trên mô hình máy đơn. Mời các bạn tham khảo!
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 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 ứng dụng thành công các kỹ thuật này, giúp giảm số lượng đạn pháo phòng không cần thiết từ 20,000 xuống chỉ còn 4,000 vào năm 1941 Sau chiến tranh, vận trù học đã được áp dụng rộng rãi trong kinh doanh, công nghiệp và xã hội, từ ngành hóa dầu đến hàng không, hậu cần và chính phủ Ngày nay, lĩnh vực này 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, trở thành một ngành học quan trọng và được nghiên cứu sâu rộng.
Vận trù học nghiên cứu phân bổ nguồn lực tối ưu, cung cấp cơ sở hợp lý cho quyết định thông qua việc phân tích các tình huống phức tạp và dự đoán hành vi của hệ thống 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à các hoạt động Vai trò của vận trù học đang gia tăng trong cả lĩnh vực công và tư, 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, quản lý tài sản và rủi ro Trong lĩnh vực công, vận trù học tập trung vào các vấn đề như 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 và thiết kế hệ thống khẩn cấp đô thị.
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 toán học bao 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 trên máy tính, cũng như giải quyết chúng bằng phần mềm và đánh giá hiệu quả từ dữ liệu 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 đã phát triển để giải quyết các vấn đề thực tế trong các lĩnh vực kỹ thuật và kinh tế.
Trong vận trù học, các nhà nghiên cứu mô hình hóa các vấn đề thực tế bằng cách sử dụng toán học, thống kê và ứng dụng máy tính để tìm giải pháp tối ưu cho các mô hình bị giới hạn bởi thời gian, nguồn lực lao động, nguồn lực vật liệu và quy tắc kinh doanh Các lý thuyết và mô hình toán học mới được phát triển nhằm phân tích hành vi và đặc điểm của các vấn đề thực tế, từ đó hỗ trợ ra quyết định tốt hơn trong việc phát triển và quản lý quy trình cũng như doanh nghiệp, nhằm tối đa hóa lợi nhuận Mô hình tối ưu thường được biểu diễn dưới dạng max (min) f(x) với các điều kiện ràng buộc.
Các giải pháp khả thi là những phương án đáp ứng các yêu cầu đã đề ra Tối ưu hóa chính là quá trình tìm kiếm các giải pháp tốt nhất trong số những giải pháp khả thi đó.
Vấn đề tối ưu hóa tổ hợp
Tối ưu hoá tổ hợp, một nhánh của tối ưu hóa toán học, liên quan đến các lĩnh vực như 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 chính của nghiên cứu trong lĩnh vực này là xác định giải pháp tốt nhất từ một tập hợp lớn các giải pháp 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 cho 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, một lĩnh vực tương đối trẻ so với các ngành toán học ứng dụng khác, 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 trở nên thống nhất Lịch sử của tối ưu hóa tổ hợp 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 thúc đẩy bởi các ứng dụng trong vận chuyển và chuyển tải Việc xây dựng quy hoạch tuyến tính như một bài toán tổng quát và phát triển phương pháp đơn hình bởi Dantzig vào năm 1947 đã giúp giải quyết nhiều bài toán tối ưu hóa tổ hợp một cách hiệu quả.
Tối ưu hóa tổ hợp là lĩnh vực nghiên cứu liên quan đến 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, xuất phát từ lý thuyết quy hoạch tuyến tính Nó có mối liên hệ 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 Trong lĩnh vực này, một số vấn đề đã đượ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, trong khi nhiều bài toán khác lại thuộc loại 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 là áp dụng thuật toán xấp xỉ với thời gian chạy đa thức, trong khi cách thứ ba sử dụng các kỹ thuật tìm kiếm kinh nghiệm, tuy nhiên không đảm bảo chất lượng giải pháp hay thời gian chạy.
Nhiều quyết định trong cuộc sống thực tế có thể được xem như các bài toá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à thực tiễn Các vấn đề như bài toán người giao hàng, kế hoạch mua sắm, tham quan và phân công công việc đã thu hút sự chú ý của nhiều nhà toán học 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, vì vậy nghiên cứu về độ 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ả trở thành trọng tâm 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}.
S thường được gọi là không gian tìm kiếm, nơi mỗi phần tử của S đại diện cho một giải pháp khả thi Giải quyết Bài toán tối ưu tổ hợp đồng nghĩa với việc tìm kiếm một giải pháp tối ưu s ∗ thuộc S, sao cho giá trị hàm được tối thiểu hóa (hoặc tối đa hóa); cụ thể 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 (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 được xem như một 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 Lời giải tối ưu thường được xác định từ một tập hợp hữu hạn các giải pháp khả thi của vấn đề ban đầu, giúp hàm mục tiêu đạt được 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 quy trình gia công, trình tự khả thi được hiểu là một chuỗi các bước mà từ đó có thể sắp xếp tất cả các nhiệm vụ cần thực hiện trên máy xử lý.
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ủa tập các công việc đều có thể được coi là trình tự khả thi Tuy nhiên, trình tự tối ưu cho vấn đề 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 Đối với một trình tự khả thi, 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 gặp 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ỉ, nó 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 xử lý hoạt động liên tục mà không có thời gian nghỉ Đối với hầu hết các vấn đề về trình tự gia công, trình tự tối ưu thường là không trì hoãn Tuy nhiên, một số trường hợp đặc biệt cho thấy rằng trình tự gia công có thể trì hoãn cũng có thể là tối ưu.
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 :
Công việc T j là công việc thứ j trong một chuỗi công việc được đề xuất, với p j là thời gian cần thiết để hoàn thành công việc T j, và d j là thời gian hoàn thành hạn định cho công việc T j.
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 đó, để giảm thiểu thời gian trễ tối đa khi gia công một tập hợp công việc với thời gian hoàn thành hạn định, cần sắp xếp thứ tự thực hiện các công việc một cách hợp lý.
Bài toán 1kL max có thể được giải quyết một cách đơn giản bằng cách sắp xếp các nhiệm vụ theo quy tắc ưu tiên kỳ hạn sớm nhất (EDD) Với quy tắc này, các công việc sẽ được tổ chức theo thứ tự không giảm của các hạn chót, từ đó tạo ra trình tự tối ưu cho việc thực hiện.
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ả một hệ thống vật lý, cho phép xác định kết quả của các phép đo Quá trình này được gọi là mô hình hóa hay vấn đề thuận Ngược lại, vấn đề ngược liên quan đến việc chuyển đổi các phép đo và quan sát thành thông tin về một vật thể hoặc hệ thống vật lý mà chúng ta quan tâm.
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, với phân bố khối lượng bên trong hành tinh, chúng ta có thể xác định duy nhất các giá trị của lực hấp dẫn xung quanh hành tinh Tuy nhiên, trong các 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 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 phải 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 Trong khi giải quyết bài toán tối ưu, chúng ta thường giả định rằng các thông số như chi phí và năng lực đã được biết rõ, nhưng thực tế có thể chỉ cho phép ước lượng Đôi khi, chúng ta có thể xác định rằng một số giải pháp 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 trở nên tối ưu, đồng thời giảm thiểu sự thay đổi của các tham số so với ướ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 trình tự công việc đã được xác định trước, với mục tiêu là tối ưu hóa các thông số như thời gian xử lý để đạt được hiệu quả tốt nhất cho một hàm mục tiêu đã chọn Trong khi vấn đề sắp xếp thuận hỗ trợ thiết kế hệ thống mới, vấn đề sắp xếp ngược lại đóng vai trò quan trọng trong việc nâng cao hiệu suất 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 sự chú ý đáng kể từ các nhà nghiên cứu Nhiều nghiên cứu đã chỉ ra ứng dụng của lập trình tự ngược trong lĩnh vực vận chuyển, cho thấy tầm quan trọng của vấn đề này trong việc cải thiện hiệu suất và hiệu quả.
Các vấn đề ngược trong lập trình đơn máy nhằm giảm thiểu tổng thời gian hoàn thành công việc đang được nghiên cứu Bài viết trình bày một số kết quả mới liên quan đến các vấn đề phân loại ngược, góp phần nâng cao hiệu quả trong quản lý thời gian và tối ưu hóa quy trình làm việc.
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 kiểm soát được, 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 có thể 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 đề ngược của lập trình máy đơn nhằm giảm thiểu tổng trọng số.
Thời gian hoàn thành trong bài toán 1kP w j C j được tối ưu hóa với các giải pháp tương ứng theo các chuẩn l1, l2 và l∞ Ngoài ra, bài viết cũng đề cập đến các vấn đề đảo ngược liên quan đến tổng thời gian hoàn thành trong bối cảnh máy đơn 1kP.
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 với vấn đề khách quan tối đa, 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 Họ xem xét khả năng điều chỉnh ngày tháng hoặc thời gian xử lý theo các tiêu chuẩn khác nhau như l1, l2 và l∞ Hai vấn đề mà họ đề xuất được cho là NP-khó, và để giải quyết chúng, họ đã phát triển công thức lập trình toán học cùng với 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 chi phí tối đa hoặc tối thiểu 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 theo các ràng buộc tuyến tính Các ràng buộc này là các hàm và phương trình hoặc bất phương trình tuyến tính của các biến trong hàm mục tiêu Quy hoạch tuyến tính có mối liên hệ chặt chẽ với đạ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 tuyến tính.
Quy hoạch tuyến tính là một trong những phương pháp hiệu quả nhất trong tối ưu tổ hợp, cho phép mô tả nhiều vấn đề thực tế như tối đa hóa lợi nhuận hoặc giảm thiểu chi phí Phương pháp này đã được ứng dụng rộng rãi trong kinh tế và quản lý doanh nghiệp, giúp các công ty tối ưu hóa nguồn lực hạn chế Với sự thay đổi trong các vấn đề quản lý hiện đại, quy hoạch tuyến tính vẫn giữ vai trò quan trọng trong các lĩnh vực như sản xuất, vận chuyển và công nghệ.
Quy hoạch tuyến tính đã giới thiệu 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à tầm quan trọng của tính lồi cùng các khái quát hóa của nó Các trường hợp đặc biệt như vấn đề mạng lưới và vấn đề đa giao thức được xem là quan trọng, dẫn đến nhiều nghiên cứu về thuật toán chuyên dụng nhằm ứng dụng giải pháp trong thực tế.
Đị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 để thể hiện 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ể, ký hiệu |x| symb được áp dụng, trong đó chỉ số dưới là một cách ghi nhớ để chỉ ra định nghĩa có liên quan.
Cho p≥1 là một số thực, độ dài của vector x = (x1, x2, , xn) trong không gian Euclide n chiều được định nghĩa thông qua chuẩn p Cụ thể, chuẩn p của vector x thuộc Rn được ký hiệu là kxk p.
Các tính chất của chuẩn Euclidean có thể áp dụng cho tất cả các chuẩn p, bao gồm: độ lớn của vector kxk p luôn không âm và chỉ bằng 0 khi x bằng 0; chuẩn của một vector nhân với hằng số k là kkxk p = |k|kxk; và chuẩn của tổng hai vector kx+yk p không vượt quá tổng của các chuẩn riêng biệt kxk p và ky k 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à max i=1, ,n|x i | Định nghĩa này vẫn có ý nghĩa với 0 < p < 1, tuy nhiên, hàm kết quả không tạo thành một chuẩn vì nó vi phạm bất đẳng thức tam giác.
Vấn đề ngược của 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 gian đến như nhau trên mô hình máy đơn
Trong chương này, chúng tôi nghiên cứu các đối tượng liên quan đến lập trình tự trên mô hình máy đơn, tập trung vào tiêu chí độ trễ tối đa trong bối cảnh tối ưu hóa ngược Trong lập trình tự thuận, mục tiêu là tối ưu hóa dãy công việc để giảm thiểu thời gian trễ tối đa, trong khi lập trình tự ngược yêu cầu xác định các giá trị thời gian gia công hoặc kỳ hạn để tối ưu hóa một dãy công việc đã được xác định trước Chúng tôi phân loại các bài toán ngược dựa trên việc điều chỉnh thời gian gia công hoặc kỳ hạn và áp dụng các tiêu chuẩn khác nhau để đo độ lệch của các tham số điều chỉnh so với các ước tính ban đầu.
2.1 Sơ lược về vấn đề sắp xếp ngược
Trong những năm gần đây, tối ưu hóa ngược đã trở thành một lĩnh vực quan trọng, khác biệt với tối ưu hóa truyền thống khi mà các tham số chưa biết được xác định để đạt được kết quả tối ưu nhất Mặc dù đã thu hút sự quan tâm của nhiều nhà nghiên cứu trong lĩnh vực tối ưu hóa tổ hợp, nhưng các vấn đề lập lịch trình vẫn chưa được khai thác nhiều trong ngữ cảnh tối ưu hóa ngược.
Trong bài viết này, chúng tôi 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 1kL max Chúng tôi sẽ trình bày các phương pháp và kết quả đạt được trong việc giải quyết bài toán này.
Trong bài toán lập trình tự thuận 1kL max , một tập hợp các công việc đã cho
Tập hợp công việc T = {1, 2, , n} có thể được thực hiện trên một máy đơn mà không có ràng buộc ưu tiên Tất cả các công việc bắt đầu tại thời điểm t = 0, với thời gian gia công mỗi công việc tại thời điểm j, j ∈ N là p_j và được hoàn thành bởi một kỳ hạn d_j Kỳ hạn được ký hiệu là d = (d_1, d_2, , d_n) Một trình tự thực hiện công việc được xác định duy nhất bởi một dãy sắp thứ tự các công việc π, cùng với thời gian hoàn thành C_j(π).
Với mỗi trình tự cho bởi dãy sắp thứ tự công việc π, độ trễ của công việc j được xác định bởi công thức
L j (π, d) =C j (π)−d j và toàn bộ quá trình thực hiện của trình tự π được tính theo độ trễ tối đa
Mục tiêu của bài toán thuận 1kL max là tìm ra một hoán vị công việcπ ∗ , sao cho
L max (π, d) đạt giá trị nhỏ nhất,
L max (π∗, d) ≤ L max (π, d),với mọi giá trị π bất kỳ.
Trong bài toán ngược, thời gian gia công p j và kỳ hạn d j được xác định cùng với một dãy công việc π Tuy nhiên, hoán vị π có thể không đạt được tối ưu cho các giá trị p j và d j đã cho Mục tiêu là điều chỉnh các thông số trong những giới hạn cho phép để tối ưu hóa dãy công việc đã được cung cấp.
Giả sử dãy công việc mục tiêu là π = (1, 2, , n) và các công việc có thể được đánh số lại Nếu thời gian gia công được xác định và các kỳ hạn d j có thể điều chỉnh, thì bài toán ngược sẽ được ký hiệu tương ứng.
Trong bài toán này, với mỗi công việcT j ,∀j ∈N, kỳ hạnd j của nó được cho cùng với đoạn biến thiên d j ;d j
Thời gian điều chỉnh db db 1 ,db 2 , ,db n có thể chọn trong đoạn đã cho db j ∈ d j ;d j
, j ∈N, sao cho độ lệch kdb−dk so với kỳ hạn gốc là nhỏ nhất min db−d s.t L max π,db
≤ L max σ,db , d j ≤db j ≤d j ,với mọi hoán vị công việc σ, j ∈N.
Các chuẩn được đề cập trong luận văn được định nghĩa lại như sau l 1 : db−d
∞,α,β = max j=1, ,n h α j max n d b j −d j ,0 o +β j max n d j −d b j ,0 oi trong đó các giá trị α j , β j là không âm.
Trong phần bổ sung cho bài toán ngược 1|adjustabled j , π|L max , chúng ta điều chỉnh kỳ hạn d j để đảm bảo trình tự π là tối ưu Cụ thể, thay vì chỉ điều chỉnh kỳ hạn d j để tối ưu hóa trình tự π, chúng ta giới hạn kỳ hạn d j sao cho độ trễ tối đa không vượt quá giá trị L ∗ đã cho Kết quả là bài toán được định nghĩa như sau: tối thiểu hóa db−d với điều kiện L max π, db.
≤ L ∗ , d j ≤ d j ≤ d j , với mọi hoán vị công việc σ, j ∈N.
Ta ký hiệu bài toán này là 1|adjustabled j , L ∗ |L max
Bài toán ngược đề cập đến thời gian gia công và kỳ hạn điều chỉnh, trong đó các công thức áp dụng cho thời gian hạn định và thời gian gia công điều chỉnh pb j Các giá trị này được lựa chọn sao cho p j ≤ pb j ≤ p j, với j ∈ N, nhằm đảm bảo độ lệch so với thời gian gia công ban đầu kbp− pk là nhỏ nhất Chúng ta chỉ cần thay thế ký hiệu adjustable d j bằng adjustable p j.
Trong bài viết này, tôi trình bày các kịch bản liên quan đến vấn đề ngược, nơi mà lợi ích của khách hàng và người bán thường mâu thuẫn Mô hình ngược có thể được áp dụng như một công cụ đàm phán hiệu quả nhằm giải quyết những xung đột này.
Trong tình huống đầu tiên, khi đối mặt với bài toán ngược về thời gian gia công các công việc điều chỉnh được, nhà sản xuất có thể thiết lập một trình tự công việc ưu tiên π cùng với các ước tính thời gian gia công và hạn hoàn thành Nếu trong quá trình sản xuất, các tham số thực tế khác với ước tính, dẫn đến việc không đảm bảo thời hạn của khách hàng, nhà sản xuất có thể xác định một số công việc có thể gia công nhanh hơn với chi phí bổ sung Điều này tạo cơ hội để hoàn thành tất cả các công việc đúng thời hạn và theo trình tự đã định Thời gian gia công điều chỉnh cần đảm bảo rằng π là trình tự tối ưu nhất cho nhà sản xuất và vẫn đáp ứng được kỳ hạn của khách hàng.
Trong tình huống thứ hai, nhà sản xuất có thể điều chỉnh kỳ hạn của từng công việc để hoàn thành đúng thời hạn hoặc trong giới hạn chấp nhận được L ∗, mà không bị ràng buộc bởi trình tự công việc cố định Nếu tuân thủ theo trình tự đã định, nhà sản xuất sẽ không thể hoàn thành đúng hạn, do đó họ có thể thương lượng với khách hàng để điều chỉnh kỳ hạn công việc nhằm đảm bảo tiến độ Cuộc thương lượng này cần đảm bảo chất lượng đạt mức L ∗ và tối thiểu hóa các chi phí phát sinh.
Điều kiện cần và đủ của vấn đề tối thiểu hóa thời gian trễ tối đa
Điều kiện đủ của vấn đề 1kL max là tối ưu
Một điều kiện cần thiết để đạt được giải pháp tối ưu là trình tự EDD phải thỏa mãn điều kiện d π(i) ≤ d π(2) ≤ ≤ d π(n) Theo Định lý 2.1, quy tắc EDD là phương pháp hiệu quả để tìm trình tự tối ưu cho bài toán 1kL max.
Chúng ta có thể chứng minh rằng bất kỳ trình tự nào không tuân theo quy tắc EDD đều có khả năng được chuyển đổi thành một trình tự phù hợp với quy tắc EDD mà không làm tăng giá trị của hàm mục tiêu.
Giả sử rằng mọi trình tự tối ưu π đều không tuân theo quy tắc EDD, thì trong trình tự này sẽ tồn tại ít nhất hai công việc liền kề Tj và Tk.
Giả sử công việc T J bắt đầu được gia công tại thời điểm t Khi đó,
Trong trình tự π, khi thay đổi vị trí của hai công việc Tj và Tk, ta tạo ra trình tự mới π0 Trong đó, thời gian bắt đầu gia công của công việc Tj là t, và Tj sẽ được gia công ngay sau khi công việc Tk kết thúc.
Vì vậy, L max lớn hơn L 0 max, cho thấy rằng mọi trình tự không tuân thủ quy tắc EDD có thể được chuyển đổi thành trình tự tuân thủ quy tắc EDD mà không làm tăng hàm mục tiêu Điều này cần được chứng minh.
Ví dụ 2.1 Ở 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).
Theo quy tắc EDD ta tìm được trình tự tối ưu là {T 1 , T 4 , T 3 , T 2 , T 5 , T 6 } và trễ tối đa L max = 2
Điều kiện cần và đủ của vấn đề 1kL max
Một công việc T π(r) trong trình tự sắp xếp π được coi là chủ chốt nếu thời gian trễ tối đa của nó là T π(r) = T max(π) Trình tự sắp xếp π được xem là tối ưu cho vấn đề 1kL max nếu tồn tại một công việc chủ chốt T π(r) thỏa mãn điều kiện d π(i) ≤ d π(r) với mọi i < r.
Giả sử π là một giải pháp tối ưu, chúng ta chứng minh điều kiện cần bằng cách đánh số các công việc chủ chốt của π Đầu tiên, nếu chỉ có một công việc chủ chốt, và tồn tại một i < r sao cho d π(i) > d π(r), thì 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 so với T π(r) đối với π, 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 (π), điều này mâu thuẫn với tính tối ưu của π.
Giả sử điều kiện cần giữ nguyên tất cả các trình tự tối ưu nhỏ 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ì đối 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) Do đó, chúng ta có thể thay đổi công việc T π(i) tới vị trí ngay sau T π(r), làm cho T π(r) không còn là công việc chủ chốt nữa 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, điều này 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.
Chúng ta có thể tổ chức lại thứ tự các công việc trước và sau π(r) dựa trên quy tắc EDD, từ đó tạo ra một trình tự sắp xếp mới là π 0.
Theo quy tắc EDD, chuỗi π 0 là tối ưu, và 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 xem là tối ưu Định lý đã đượ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 }.
Trong bài toán tối ưu hóa L max, điều kiện tối đa cho độ trễ là L max = 2 Định lý 2.3 chỉ ra rằng dãy công việc π = (1, 2, , n) sẽ là tối ưu cho bài toán 1kL max nếu và chỉ nếu tồn tại một công việc k thỏa mãn hai điều kiện nhất định.
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 sẽ 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 Tiếp theo, chúng ta sẽ giải thích cách tìm ra kỳ hạn điều chỉnh tối ưu db, 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, sẽ có một phương án tối ưu dbsao cho công việc h đóng vai trò quan trọng đối với 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 khả thi nếu kỳ hạn không thể điều chỉnh trong đoạn của chúng, dẫn đến việc không thể tối ưu hóa dãy sắp thứ tự công việc π.
Giả sử công việc h là chủ chốt cho kỳ hạn gốc d nhưng không phải cho các kỳ hạn điều chỉnh khác Nếu công việc b k là chủ chốt với d, thì cần xem xét mối liên hệ giữa các công việc để xác định vai trò của chúng trong quá trình điều chỉnh.
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 rằng tồn tại một tập hợp các kỳ hạn tối ưu db khác nhau, đảm bảo các tính chất nhất định được thỏa mãn.
(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) sẽ đúng với db và công việc j đứng 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 được duy trì với b db và công việc chủ chốt k.
L 0 =L h L_0\} \) có độ trễ lớn hơn \( L_0 \) Tập hợp \( U \) bao gồm công việc \( k \), với mỗi công việc \( u \in U \), kỳ hạn \( d_{b_u} \) có thể thay đổi đến giá trị \( bb \, d_u = C_u - L_0 \) (2.11) để giảm độ trễ đến giá trị \( L_0 \).
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), khi kỳ hạn các công việc trong tập U được gia hạn, tất cả các công việc, bao gồm cả công việc h, trở thành chủ chốt đối với b d.b Xét tính chất (i) với công việc h: nếu h thuộc U, công việc h sẽ được điều chỉnh đúng như mô tả và trở thành chủ chốt đối với d Ngược lại, nếu h không thuộc U, tức là b h không nằm trong U.
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 sẽ chứng minh tính chất (iv) Dựa vào tính chất (i), 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, để hoán vị π tối ưu thỏa mãn với công việc chủ chốt k và kỳ hạn db, ta có 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 vào 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 được xác định là công việc chủ chốt cho kỳ hạn ban đầu d Nếu các đ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 π và công việc chủ chốt h với thời gian ban đầu d, thì không cần phải điều chỉnh; khi đó, 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, chúng 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ỏ, mỗi đoạn nhỏ sẽ có cùng tập con các công việc cần điều chỉnh Tiến hành phân tích tham số cho từng đoạn con, từ đó biểu diễn toàn bộ đoạn d h.
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}, đảm bảo thỏa mãn điều kiện của Định lý (2.3) và có độ lệch kdb−dkl nhỏ nhất Kết quả bài toán được tìm ra bằng cách xem xét tất cả các đoạn con và chọn kết quả có độ lệch kdb−dk nhỏ nhất Đoạn d h được chia bởi các giá trị khác nhau trong tập {C h −L 1 , C h −L 2 , C h −L n } ∪ {d 1 , d 2 , d n } Dãy sắp thứ tự của các giá trị này là d h =t k 1 < t k 2 < < t k z = d h.
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} thỏa mãn điều kiện (2.16) sẽ vi phạm điều kiện (2.1) của Định lý 2.3 với bất kỳ thuộc t k g, t k g+1 Đồng thời, những công việc không thỏa mãn điều kiện (2.17) cũng không đáp ứng được đ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ủa các công việc có kỳ hạn có thể được sắp xếp theo thứ tự nhằm đáp ứng điều kiện cần và đủ của Định lý 2.3 Điều này liên quan đến việc 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 con 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 con tiếp theo t k g+1 và t k g+2.
. Đặ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 khi sắp xếp các công việc theo thứ tự kỳ hạn sớm nhất (EDD) Do đó, phạm vi tìm kiếm có thể được giới hạn trong các lớp trình tự đáp ứng tiêu chí EDD.
Bắt đầu với trình tự EDD theo kỳ hạn gốc, nếu thỏa mãn điều kiện L max ≤ L ∗ thì không cần điều chỉnh Ngược lại, nếu kỳ hạn của một số công việc có thể tăng, hãy xác định H = {h i} là tập hợp các công việc chủ chốt và L = L max.
Nếu L > L ∗, có thể mở rộng kỳ hạn của công việc từ tập H Kỳ hạn tăng thêm có thể tính bằng tất cả các công việc từ H: db j = d j + x, với x ≥ 0 và j ∈ H Biên độ của kỳ hạn có thể được xác định như sau: x ≤ min j∈H (n db j − d j).
Để giải quyết vấn đề 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 kỳ hạn, ta cần xem xét các yếu tố liên quan Nếu không có công việc nào là chủ chốt trong số đó, thứ tự thực hiện các công việc sẽ không quan trọng Ngược lại, nếu chỉ có công việc cuối cùng trong nhóm có cùng kỳ hạn là chủ chốt, thì việc điều chỉnh mong muốn 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 phù hợ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 cho mỗi chuẩn khi 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 σ đượ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, đặc biệt khi có các công việc chủ chốt mới xuất hiện Trong quá trình duy trì thứ tự chính và theo dõi các công việc chủ chốt H, sự điều chỉnh kỳ hạn có thể được thực hiện lặp lại, với giả định rằng các công việc được đánh số theo thứ tự chính Việc tăng kỳ hạn d h j của công việc h j ∈ H có thể dẫn đến một sự thay đổi cấu trúc, với ba trường hợp khả thi Giả định rằng 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 khi thời gian của tất cả các công việc trong tập H tăng lên một lượng x cho đến khi xảy ra trường hợp sớm nhất A, B, C hoặc D Do đó, x được xác định bằng cách tính toán các giá trị tối thiểu sau: 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).
Nếu trường hợp A xảy ra và kỳ hạn của các công việc σ(k) và σ(k+1) bằng nhau, việc đánh số lại và cập nhật thứ tự có thể cần thiết để các 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 Trong trường hợp B, tập H có thể được cập nhật, và trong cả hai trường hợp, giá trị L của độ trễ tối đa có thể giảm bởi x Việc tăng kỳ hạn của tập H sẽ tiếp tục cho đến khi xảy ra 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, tối ưu hóa quá trình vì hoán vị kỳ hạn sớm nhất được xem xét và công việc với giá trị nhỏ nhất của α j được chọn để điều chỉnh thời hạn 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 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), trong khi lượng điều chỉnh x được tính trong thời gian O(n) trong mỗi lần lặp lại.
Trong bài toán ngược 1|adjustable d j , L ∗ |L max, trường hợp B xảy ra không quá n lần trong khi trường hợp C xảy ra đúng một lần, dẫn đến thời gian hoàn thành giải quyết bài toán là O(n²) Chúng tôi đã chứng minh rằng bài toán này có thể được giải quyết trong thời gian O(n²) cho bất kỳ thời gian chuẩn nào bằng cách 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 bởi (2.22) Nếu không có kết quả, phương pháp tương tự cũng cho phép giải quyết 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 thứ tự tối ưu π, thì thời gian gia công p là 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, cho thấy rằng trong một kết quả tối ưu cho bài toán ngược, công việc mới h có thể trở thành chủ chốt h ∈ J Để xem xét khả năng công việc bất kỳ h /∈ J là chủ chốt, ta phân tích các lớp kế hoạch khác nhau với công việc chủ chốt ấn định h, 1 ≤ h ≤ n Bổ đề 2.1 chỉ ra rằng đối với bài toán ngược 1|adjustablepj, π|Lmax, chỉ một số 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 được điều chỉnh Nếu kỳ hạn không đáp ứng điều kiện (2.2) với hoán vị mục tiêu π và công việc h đã chọn, thì không thể điều chỉnh thời gian gia công để tối ưu hóa sắp thứ tự công việc π.
Nếu mối liên hệ (2.2) được thỏa mãn, 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 Cj, nhằm đảm bảo mối liên hệ (2.1) cũng được đáp ứng.
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
Khi thời gian gia công gốc p được điều chỉnh theo các ràng buộc của (2.23), 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 lên, 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 xuống Đ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) cung cấp một giải pháp tối ưu cho bài toán ngược trong các lớp kế hoạch với công việc chủ chốt h Tuy nhiên, có một số lớp không thể tìm ra kết quả cho bài toán ngược 1|adjustablep j , π|L max thông qua việc liệt kê tất cả các lớp có kết quả và chọn lớp có giá trị nhỏ nhất của F.
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,α,β,
Vì hàm mục tiêu F P (u, v) có khả năng tách rời, bài toán (2.26) có thể được phân tích thành hai bài toán con Cụ thể, chúng ta có thể tối thiểu hóa α j (A j −u j ) với chuẩn l 1 hoặc α j (A j −u j ) 2 với chuẩn l 2, với 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 Resource Allocation Problem with Nested Constraints với các 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 Đối với các lớp kế hoạch có công việc chủ chốt h, bài toán cũng được giải quyết trong thời gian O(nlogn) Thời gian hoàn thành toàn phần khi xét n lớp các kế hoạch 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 Nếu N 1 và N 2 là các tập con của các biến đạt cận dưới, thì x j (θ) sẽ bằng A i và y k (θ) sẽ bằng B k, với i thuộc N 1 và 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ị gần đây của θ tăng lên bởi δ > 0, các ẩn x i (θ) với i ∈ N 1 \N 1 sẽ tăng lên với lượng δ/α i, trong khi các ẩn y k (θ) với k ∈ N 2 \N 2 cũng tăng lên với lượng δ/β k Do đó, vế trái của ràng buộc (2.31) sẽ tăng lên với lượng δP i∈{j, ,h}\N 11/α i, và vế trái của ràng buộc (2.32) sẽ tăng lên với lượng δP i∈{h+1, ,j}\N 21/β i Để đảm bảo tất cả các ràng buộc (2.31) và (2.32) được thỏa mã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 của nó, tức là A i hoặc B k.
Đặt θ := θ+δ và thay đổi 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 bị vi phạm, chúng ta sẽ tìm số gia δ tiếp theo và tiếp tục tăng θ.
Mỗi 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 việc không có nhiều hơn n lần lặp, từ đó làm tăng θ Mỗi giá trị của gia δ có thể được tìm trong thời gian O(n) Vì vậy, trong trường hợp 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 cho 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 để kpb−pk là nhỏ nhất và đạt giá trị L ∗ Giá trị L ∗ sẽ làm thay đổi hạn d j thành d j + L ∗ cho công việc j ∈ N Do đó, bài toán ngược 1|adjustablep j, L ∗ |L max sẽ chuyển 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, sao cho các công việc đáp ứng kỳ hạn d j và mức độ co K là nhỏ nhất Bài toán này thuộc dạng ngược 1|adjustable p j, L∗|L max 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
The equation B j = p j − p j, where K represents either a linear or quadratic function, pertains to Resource Allocation Problems with Nested Constraints 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 trong chuẩn l ∞ được quy về bài toán máy đơn với thời gian gia công có thể đ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(n log n + cn) trong bài báo [3], trong đó c là một hằng số phụ thuộc vào log h max j∈N n α j p j − p j oi.
Luận văn nghiên cứu bài toán ngược nhằm tối thiểu hóa thời gian trễ tối đa cho 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∞ để phân tích và giải quyết các bài toán liên quan.
• 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 có thể mở rộng việc giải quyết 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ụ thể, bài toán này áp dụng cho các loại chuẩn 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) đã thực hiện nghiên cứu về 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 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 này tập trung vào các vấn đề quan trọng liên quan đến tối ưu hóa quy trình gia công, nhằm nâng cao hiệu quả sản xuất và giảm thiểu thời gian chế biến.
Hoàng Thị Mơ (2017) trong luận văn thạc sĩ của mình đã 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 được thực hiện tại Đại học Khoa học – Đại học Thái Nguyên, góp phần vào việc cải thiện hiệu quả quy trình gia công.
[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.
