Luận văn Thạc sĩ Toán học: Một số vấn đề sắp xếp lập kế hoạch gia công tối ưu trên mô hình máy đơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

20
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn phân tích, tìm hiểu, thiết lập phương pháp gia công các nguyên liệu đầu vào của một quá trình sản xuất để đạt được quá trình gia công tối ưu của một số vấn đề gia công trên máy sản xuất đơn trong sản xuất kinh tế. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số vấn đề sắp xếp lập kế hoạch gia công tối ưu trên mô hình máy đơn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGUYỄN VIỆT HƯNG MỘT SỐ VẤN ĐỀ SẮP XẾP LẬP KẾ HOẠCH GIA CÔNG TỐI ƯU TRÊN MÔ HÌNH MÁY ĐƠN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGUYỄN VIỆT HƯNG MỘT SỐ VẤN ĐỀ SẮP XẾP LẬP KẾ HOẠCH GIA CÔNG TỐI ƯU TRÊN MÔ HÌNH MÁY ĐƠN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 GIÁO VIÊN HƯỚNG DẪN TS. PHẠM HỒNG TRƯỜNG THÁI NGUYÊN - 2016
i Mục lục Lời nói đầu 1 Chương 1. Một số vấn đề lý luận về vấn đề trình tự sắp xếp 3 1.1 Vấn đề trình tự sắp xếp . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Lời dẫn . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 Phân loại vấn đề trình tự sắp xếp . . . . . . . . . . . 10 1.2 Tìm lời giải (giải quyết) vấn đề trình tự sắp xếp . . . . . . . 12 1.2.1 Trình tự khả thi và trình tự tối ưu . . . . . . . . . . 12 1.2.2 Trình tự sắp xếp không trì hoãn . . . . . . . . . . . . 13 1.2.3 Sơ lược về thuật toán và độ phức tạp của thuật toán 14 1.2.4 Thuật toán và độ phức tạp của vấn đề trình tự sắp xếp 15 Chương 2. Vấn đề trình tự sắp xếp trên máy đơn 18 2.1 Vấn đề tổng thời gian hoàn thành gia công của các nhiệm vụ có trọng số khác nhau . . . . . . . . . . . . . . . . . . . . 18 2.1.1 Vấn đề 1k wj Cj (xem [2]) . . . . . . . . . . . . . . 18 P 2.1.2 Vấn đề 1|chain| wj Cj (xem [2]) . . . . . . . . . . . 20 P 2.1.3 Vấn đề 1 | rj | Cj (xem [3]) . . . . . . . . . . . . . 25 P 2.2 Vấn đề trễ cực đại . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.1 Vấn đề 1kLmax (xem [1]) . . . . . . . . . . . . . . . . 28 2.2.2 Vấn đề 1 | rj , prmp | Lmax (xem [3]) . . . . . . . . . . 29 2.2.3 Vấn đề 1 | rj | Lmax (xem [1]) . . . . . . . . . . . . . 31 2.2.4 Vấn đề 1 | rj , pj = 1 | Lmax (xem [2]) . . . . . . . . . 34
ii 2.2.5 Vấn đề 1 | prec | Lmax (xem [3]) . . . . . . . . . . . . 35 Kết luận 39 Tài liệu tham khảo 40
1 Lời nói đầu Tổ hợp tối ưu hóa là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế – xã hội. Trong thực tế, việc tìm giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò rất quan trọng. Trong luận văn này tôi xin trình bày về vấn đề sắp xếp lập kế hoạch gia công tối ưu của một số vấn đề sắp xếp trên mô hình máy đơn. Lập kế hoạch gia công là một phần ứng dụng của tối ưu hoá. Đó là một trong những hoạt động cơ bản của quá trình quản lý cấp công ty, xét về mặt bản chất thì hoạt động này nhằm mục đích xem xét các mục tiêu, các phương án kinh doanh, bước đi trình tự và cách cải tiến hành các hoạt động sản xuất kinh doanh. Trong phạm vi một doanh nghiệp hay một tổ chức, lập kế hoạch gia công là khâu đầu tiên, là chức năng quan trọng của quá trình quản lý và là cơ sở để thúc đẩy hoạt động kinh doanh có hiệu quả cao, đạt được mục tiêu đề ra. Các nhà quả lý cần phải lập kế hoạch bởi vì lập kế hoạch cho biết phương hướng hoạt động trong tương lai, làm giảm sự tác động của những thay đổi từ môi trường, tránh được sự lãnh phí và dư thừa nguồn lực, thiết lập nhưng tiêu chuẩn thuận tiện cho công tác kiểm tra. Lập kế hoạch gia công sẽ làm giảm sự chồng chéo và những hoạt động làm lãng phí nguồn lực của doanh nghiệp để sử dụng nguồn lực một cách có hiệu quả, cực tiểu hóa chi phí nhằm đạt được mục tiêu đã được lựa chọn. Chính vì vậy việc nghiên cứu lập kế hoạch gia công tối ưu của một số vấn đề gia công tối ưu của một số vấn đề gia công trên máy sản xuất đơn hình kinh tế đóng vai trò rất quan trọng. Việc tìm ra và thiết lập được
2 kế hoạch gia công tối ưu sẽ giúp cho nhà sản xuất đảm bảo các điều kiện: Đáp ứng kì hạn giao hàng, tối thiểu hóa sự chậm trễ (nếu có) của các công việc tham gia vào quá trình gia công, tối thiểu hóa tổng thời gian hoàn thành công việc. Luận văn phân tích, tìm hiểu, thiết lập phương pháp gia công các nguyên liệu đầu vào của một quá trình sản xuất để đạt được quá trình gia công tối ưu của một số vấn đề gia công trên máy sản xuất đơn trong sản xuất kinh tế. Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn tận tình của TS. Phạm Hồng Trường, tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã người dành nhiều thời gian và tâm huyết để hướng dẫn tận tình, giúp đỡ tác giả trong quá trình học tập, nghiên cứu và viết bản luận văn này. Tác giả cũng 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 Toán - Tin cùng toàn thể các thầy cô trong và ngoài trường đã giảng dạy giúp tôi trau dồi thêm rất nhiều kiến thức phục vụ cho việc học tập và nghiên cứu của bản thân. Đồng thời tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học Toán K8A (khóa 2014-2016) đã động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập. Tác giả xin gửi lời cảm ơn chân thành đến các thầy cô. Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi trong quá trình học tập, nghiên cứu và làm luận văn. Xin chân thành cảm ơn! Thái Nguyên, 30 tháng 06 năm 2016 Tác giả Nguyễn Việt Hưng
3 Chương 1 Một số vấn đề lý luận về vấn đề trình tự sắp xếp 1.1 Vấn đề trình tự sắp xếp 1.1.1 Lời dẫn Vấn đề trình tự sắp xếp ra đời chủ yếu là trong lĩnh vực chế tạo máy, về sau được phát triển trong lĩnh vực hệ thống máy tính, lập kế hoạch trong giao thông vận tải, quản lý sản xuất. . . Từ những sắp xếp kế hoạch trong cuộc sống hàng ngày, lập kế hoạch của nhân viên, xây dựng thời khóa biểu của nhà trường, từ những tính toán kế hoạch bay cho những chuyến bay cho một sân bay lớn đều cần dùng đến phương pháp và lý luận của vấn đề trình tự sắp xếp. Trước khi đưa ra định nghĩa của vấn đề trình tự sắp xếp, chúng ta xem xét một vài ví dụ ứng dụng thực tế trong lĩnh vực này. Ví dụ 1.1.1 Gia công trong phân xưởng cơ khí Xưởng cơ khí cần gia công một lô linh kiện, mỗi linh kiện đều có trình tự gia công giống nhau, nghĩa là dựa vào thứ tự gia công như gia công trên các máy khác nhau nhưng thời gian gia công của mỗi linh kiện trên mỗi máy có thể không giống nhau. Mục tiêu đặt ra là sắp xếp thứ tự gia công các linh kiện thế nào để thời gian hoàn thành lô linh kiện là ít nhất. Ví dụ 1.1.2 Sắp xếp chuyến bay tại sân bay
4 Một sân bay, có vài chục cửa ra máy bay, mỗi ngày có vài trăm chuyến bay cất cánh và hạ cánh. Cửa ra sân bay có kiểu và kích cỡ không giống nhau, kích cỡ của các máy bay cũng khác nhau (số lượng hành khách có thể chứa khác nhau) một vài cửa chỉ cho phép sắp xếp máy bay cỡ lớn và một vài cửa chỉ cho phép sắp xếp với máy bay cỡ nhỏ. Các máy bay đều có thời gian biểu để hạ cánh và cất cánh. Do ảnh hưởng của thời tiết và các nhân tố khác của sân bay, thời gian biểu đó có tính ngẫu nhiên rất lớn. Khi máy bay vào đến cửa ra vào để hành khách lên xuống, máy bay cần bơm dầu, kiểm tra kỹ thuật, sửa chữa (nếu có), sắp xếp hành lý. Nếu có máy bay không thể hạ cánh đúng giờ sẽ ảnh hưởng đến các máy bay khác ở sân bay, ảnh hưởng đến việc chiếm hữu cửa ra vào, thời gian lên máy bay bị lùi lại và các máy bay khác không thể được đưa vào sử dụng. Nhân viên phụ trách điều động của sân bay cần đưa ra phương pháp sắp xếp các cửa ra vào cho các máy bay hạ cánh và cất cánh sao cho hiệu suất sử dụng của sân bay là cao nhất, số máy bay bị trễ thời gian cất cánh là ít nhất. Đây cũng là một vấn đề sắp xếp trình tự có ứng dụng rất lớn. 1.1.2 Định nghĩa Vấn đề trình tự sắp xếp là một vấn đề tổ hợp tối ưu hóa quan trọng, đó là sử dụng một số máy xử lý, máy móc, nguồn lực để hoàn thành tối ưu một số lượng nhiệm vụ hoặc công việc đã cho. Khi thực hiện giải quyết những nhiệm vụ hoặc những công việc này, cần thỏa mãn một số điều kiện giới hạn như: thời gian đạt đến, thời gian hạn định phải hoàn thành, thứ tự thực hiện các nhiệm vụ,. . . Mục đích là làm cho hàm mục tiêu đạt giá trị tối ưu, trong đó hàm mục tiêu thông thường là khoảng thời gian gia công, cách thức hiệu suất sử dụng của máy xử lý. Trong vấn đề trình tự sắp xếp, số lượng, chủng loại của máy xử lý, thứ tự của các công việc (nhiệm vụ), thời gian đạt đến, hạn chế hoàn thành công việc,. . . là những nhân tố rắc rối phức tạp, rất khó dùng toán học mô tả chính xác để đưa ra định nghĩa một thứ tự thông thường. Trong luận văn này, ta dùng cách thức sau đây để mô tả vấn đề trình tự sắp xếp:
5 Cho tập hợp n nhiệm vụ T = {T1 , . . . , Tn} Tập hợp m máy xử lý P = {P1 , . . . , Pm } Tập hợp s loại nguồn lực R = {R1, . . . , Rs }. Mục đích của vấn đề trình tự sắp xếp đó là sắp xếp những điều kiện được đưa ra nhất định để hoàn thành các hạng mục nhiệm vụ đưa ra, sắp xếp các máy xử lý và các nguồn lực (nếu có) phân phối sắp xếp đối với các nhiệm vụ để làm cho hàm mục tiêu đạt được tối ưu. ∗ Máy xử lý: Vấn đề máy đơn : Vấn đề trình tự sắp xếp chỉ có một máy xử lý. Nếu số máy xử lý nhiều hơn một, ta gọi là vấn đề trình tự sắp xếp đa máy. Trong vấn đề trình tự sắp xếp đa máy, nếu tất cả các máy xử lý đều có công năng như nhau thì ta gọi đó là vấn đề trình tự sắp xếp song song . Máy song song phân thành 3 loại dựa vào tốc độ xử lý: + Đồng tốc độ: Tất cả các máy xử lý đều có tốc độ như nhau. + Hằng tốc độ: Tốc độ các máy không giống nhau, nhưng tốc độ xử lý của các máy đều là hằng số, không phụ thuộc vào nhiệm vụ gia công. + Biến tốc độ : Tốc độ các máy phụ thuộc vào nhiệm vụ gia công. Một trường hợp khác của đa máy xử lý đó là đa loại hình. Mục đích của loại vấn đề này là sử dụng các máy có các công năng khác nhau. Trong trường hợp xử lý đa máy, các nhiệm vụ cần gia công cần được gia công xử lý trên những máy khác nhau. Trong trường hợp này các nhiệm vụ được gọi cụ thể là công việc. Giả sử có tập các công việc J = {J1 , . . . , Jn }. Mỗi công việc Jj có nj quá trình gia công T1j , T2j , . . . Tnj . Nếu mỗi công việc đều cần xử lý gia công trên các máy xử lý, tức là nj = m, j = 1, 2, . . . , n mà quá trình gia công của mỗi công việc đều như nhau, tức là thứ tự gia công trên mỗi máy giống nhau thì vấn đề này được gọi là đồng thứ tự tuần tự.
6 Nếu mỗi công việc đều cần xử lý gia công trên các máy xử lý, mỗi công việc có quá trình xử lý không giống nhau thì được gọi là thứ tự tuần tự khác nhau. Nếu mỗi công việc đều cần xử lý gia công trên các máy xử lý, mỗi công việc có thể có thứ tự gia công xử lý bất kỳ thì được gọi là thứ tự gia công mở. ∗ Nhiệm vụ và công việc: Những điều kiện ràng buộc trong vấn đề trình tự sắp xếp chủ yếu là những hạn định, yêu cầu trong quá trình gia công và tính chất của nhiệm vụ công việc. (1) Véctơ thời gian gia công Vectơ thời gian gia công của nhiệm vụ là pj (p1j , p2j , . . . , pnj ) trong đó pij là thời gian gia công cần thiết của nhiệm vụ Tj trên máy pi . Đối với máy đồng tốc, ta có pij = pj với i = 1, 2, . . . , m. Đối với máy hằng tốc, ta có pij = pj /bi với i = 1, 2, . . . , m. Trong đó pj là thời gian gia công tiêu chuẩn (thông thường là thời gian gia công trên máy xử lý có tốc độ chậm nhất), bi là tốc độ trên máy xử lý pi . Trong vấn đề trình tự sắp xếp, vectơ thời gian gia công của công việc Ji là pj = (p1j , p2j , . . . , pnj ). Trong đó pij là thời gian gia công tương ứng trên máy xử lý của quá trình gia công Tij . (2) Thời gian đạt đến hay thời gian chuẩn bị rj là thời gian đã chuẩn bị xong để có thể tham gia vào quá trình gia công của nhiệm vụ Tj . Nếu tất cả các nhiệm vụ đều có thời gian chuẩn bị đều như nhau, ta quy ước rj = 0, ∀j = 1, 2, . . . , n. (3) Kỳ hạn và hạn định kết thúc Kỳ hạn dj biểu thị thời gian hoàn thành hạn định của nhiệm vụ Tj , nếu không hoàn thành đúng kỳ hạn sẽ bị “phạt”. Mốc thời gian tuyệt đối không được kéo dài quá được gọi là hạn định kết thúc. (4) Yếu tố ưu tiên Yếu tố ưu tiên wj là một trọng số biểu thị mức độ ưu tiên quan trọng
7 của nhiệm vụ Tj , đối với các nhiệm vụ khác để tiện cho trình bày, ta giả sử các tham số pi , ri , dj và wj là các số trị nguyên. Trên thực tế chúng có thể là những số hữu tỷ bất kỳ. Ta dùng vectơ và ma trận để đưa ra các số liệu này r = (r1 , r2 , . . . , rn ) d = (d1 , d2 , . . . , dn ) w = (w1 , w2 , . . . , wn ) lần lượt là thời gian đạt đến, kỳ hạn và yếu tố ưu tiên của n nhiệm vụ. Ký hiệu   p11 p12 . . . p1n    p21 p22 . . . p2n  P = ... ... ... ...    pm1 pm2 . . . pmn trong đó dòng thứ i, vectơ (pi1 , . . . , pin ) biểu thị thời gian gia công của n nhiệm vụ trên máy thứ i. Một ràng buộc quan trọng khi nhiệm vụ được gia công đó là có thể gián đoạn hoặc không được gián đoạn. Một hạn chế quan trọng khác khi gia công nhiệm vụ đó là ràng buộc ưu tiên giữa các nhiệm vụ trên tập các nhiệm vụ J, thiết lập một quan hệ ưu tiên ≺. Nếu viết Ti ≺ Tj thì được hiểu là cần thiết phải gia công xong Ti rồi mới được bắt đầu gia công Tj . Ta dùng đồ thị ràng buộc ưu tiên để biểu thị mức độ ưu tiên của những nhiệm vụ, ví dụ: Trong ràng buộc ưu tiên có 3 trường hợp ràng buộc đặc biệt quan trọng: - Đồ thị ràng buộc ưu tiên dạng xích: Mỗi nhiệm vụ có nhiều nhất một nhiệm vụ ngay trước nó và một nhiệm vụ tiếp ngay sau nó.
8 T6 b T1 T3 T7 T9 b b b b T4 T10 b b b b T2 T8 b T5 Hình 1.1: Ví dụ của đồ thị ràng buộc ưu tiên - Đồ thị ràng buộc ưu tiên dạng cây nhập: mỗi nhiệm vụ có nhiều nhất một nhiệm vụ tiếp ngay sau nó. b b b - Đồ thị ràng buộc ưu tiên dạng cây xuất: mỗi nhiệm vụ có nhiều b nhất một nhiệm vụ tiếp ngay trước nó. T1 T4 T1 T3 T6 T3 b b b b b b T2 T4 T7 T4 T5 b T5 b T2 b b b b b b T1 T3 b b b b b T6 T6 T2 T5 (a) (b) (c) Hình 1.2: Ví dụ của đồ thị ràng buộc ưu tiên (a) dạng xích; (b) dạng cây nhập; (c) dạng cây xuất . ∗ Hàm mục tiêu: Kí hiệu C = (C1 , C2 , . . . , Cn ) biểu thị thời gian gia công hoàn thành nhiệm vụ mục tiêu là cực tiểu hóa thời gian hoàn thành các nhiệm vụ. Hàm mục tiêu có một số loại chủ yếu sau: (1) Độ dài thời gian gia công Độ dài thời gian gia công được định nghĩa là: Cmax = max{Cj }
9 Nghĩa là thời gian hoàn thành gia công của nhiệm vụ cuối cùng. Nếu độ dài thời gian gia công ngắn thì có nghĩa là máy xử lý có hiệu suất làm việc cao. (2) Tổng thời gian hoàn thành của các nhiệm vụ có trọng số khác nhau n X C= wj Cj j=1 Đặc biệt khi wj = 1, ∀j = 1, 2, . . . , n thì tổng thời gian hoàn thành của các nhiệm vụ có trọng số khác nhau trở thành tổng thời gian hoàn thành của các nhiệm vụ (total completion time) n X C= Cj j=1 (3) Chậm trễ lớn nhất Chậm trễ lớn nhất (maximum lateness) được định nghĩa là: Lmax = max{Lj } trong đó, Lj = Cj − dj , là thời gian chậm trễ của nhiệm vụ Tj (4) Tổng trễ hẹn của các nhiệm vụ có trọng số khác nhau (total weighted tardiness) Xn D= wj Dj j=1 trong đó, Dj = max {Cj − dj , 0} = max {Lj , 0} là thời gian trễ hẹn gia công của nhiệm vụ Tj . (5) Số nhiệm vụ trễ hẹn của các nhiệm vụ có trọng số khác nhau (weighted number of tardy task) n X U= wj Uj j=1
10  1, C > d j j trong đó Uj = là đơn vị phạt của nhiệm vụ trễ 0, C 6 d j j hẹn Tj . 1.1.3 Phân loại vấn đề trình tự sắp xếp Trong phân loại vấn đề trình tự sắp xếp, nếu như tất cả những dữ liệu số liệu đều được biết trước khi tiến hành thực hiện thì được gọi là vấn đề trình tự sắp xếp xác định. Nếu như có một vài dữ liệu số liệu chưa được biết, những số liệu đó là một vài biến lượng ngẫu nhiên, nhưng sự phân bố của chúng là đã biết, khi đó vấn đề này được gọi là vấn đề trình tự sắp xếp ngẫu nhiên. Dù là vấn đề trình tự sắp xếp ngẫu nhiên hay xác định, ta đều có thể giả sử như sau: (1) Số nhiệm vụ (hoặc công việc) và số máy xử lý là hữu hạn. (2) Trong bất kỳ một khoảng thời gian trên bất kỳ 1 máy xử lý nào chỉ được xử lý duy nhất 1 nhiệm vụ hoặc thứ tự nhiệm vụ nào đó. Ba yếu tố : máy xử lý, nhiệm vụ (hoặc công việc) và hàm mục tiêu tạo thành vấn đề trình tự sắp xếp. Số lượng loại hình và điều kiện của các máy xử lý có gần 10 trường hợp khác nhau, điều kiện ràng buộc của các nhiệm vụ (công việc) và dữ liệu hiện có cực kỳ phức tạp và rắc rối, thêm vào đó là yêu cầu cần đặt ra không giống nhau của các hàm mục tiêu đã tạo ra nhiều loại hình trình tự sắp xếp phong phú đa dạng. Ta dùng ba thành phần cơ bản trong dạng thức các loại hình của vấn đề trình tự sắp xếp: α|β|γ trong đó, vị trí α biểu thị số lượng loại hình, điều kiện máy xử lý, vị trí đó có thể là: + 1: máy đơn (1 máy xử lý). + Pm : m máy đồng tốc. + Qm : m máy hằng tốc.
11 + R: m máy biến tốc. Vị trí β biểu thị tính chất, hạn chế, yêu cầu, chủng loại dữ liệu. Số lượng và điều kiện ràng buộc ảnh hưởng của các nhiệm vụ (hoặc công việc). Vị trí này có thể có cùng lúc nhiều điều kiện theo yêu cầu của vấn đề. Vị trí đó có thể là: + ri : các nhiệm vụ có thời gian đạt đến không giống nhau. Nếu vị trí β không có mặt ri , điều đó có nghĩa là ri = 0, ∀j = 1, 2, . . . , m. + pmtn: thời gian gia công có thể gián đoạn. + prec, chains, intree, ontree: biểu thị tính tương quan giữa các nhiệm vụ, lần lượt biểu thị là ràng buộc ưu tiên thông thường, xích, cây nhập, cây xuất. Nếu vị trí β không có xuất hiện những yêu cầu này, điều đó có nghĩa là tập nhiệm vụ là không có quan hệ (các nhiệm vụ không có ràng buộc lẫn nhau). Vị trí γ biểu thị hàm mục tiêu cần tối ưu hóa, vị trí đó có thể là: Cmax : độ dài thời gian biểu tối đa; Cj : tổng thời gian hoàn thành; P wj Cj : tổng thời gian hoàn thành của các công việc có trọng số khác P nhau; Lmax : chậm trễ tối đa. Ví dụ 1.1.3 1 | rj , pmtn | wj Cj là vấn đề trình tự sắp xếp trên máy P đơn, có thể gián đoạn, các nhiệm vụ có thời gian chuẩn bị không giống nhau, hàm mục tiêu cần cực tiểu hóa là tổng thời gian hoàn thành của các nhiệm vụ có trọng số khác nhau. Ví dụ 1.1.4 P m k Cmax là vấn đề sắp xếp trên m máy đồng tốc, các nhiệm vụ không có quan hệ với nhau, không được gián đoạn, hàm mục tiêu là cực tiểu hóa thời gian hoàn thành của nhiệm vụ có thời gian gia công lâu nhất (cực tiểu hóa độ dài thời gian biểu dãy sắp xếp).
12 1.2 Tìm lời giải (giải quyết) vấn đề trình tự sắp xếp 1.2.1 Trình tự khả thi và trình tự tối ưu Vấn đề trình tự sắp xếp là một vấn đề của tổ hợp tối ưu hóa. Do các nhiệm vụ, số lượng các máy cần xử lý trong vấn đề trình tự sắp xếp đều là hữu hạn, nên lời giải tối ưu của đại bộ phận vấn đề trình tự đều được tìm ra từ hữu hạn các lời giải khả thi của vấn đề trật tự ban đầu, làm cho hàm mục tiêu đạt giá trị tối ưu. Trong vấn đề trình tự sắp xếp, ta gọi lời giải khả thi là trình tự khả thi, lời giải tối ưu được gọi là trình tự tối ưu (optimal schedule). Trong vấn đề trình tự sắp xếp, một trình tự khả thi là một dãy thứ tự mà dựa vào đó có thể sắp xếp tất cả các nhiệm vụ gia công trên máy xử lý. Ví dụ 1.2.1 Cho vấn đề trình tự sắp xếp 4 X 1 | rj | Cj , trong đó n = 4, p = (3, 2, 5, 1), r = (0, 1, 0, 0). j=1 Khi đó [p1 , p3 , p4 , p2 ] là một trình tự khả thi, tổng thời gian gia công là 31; [p4, p2 , p1 , p3 ] là một trình tự tối ưu, tổng thời gian gia công tối ưu là 21. Ví dụ 1.2.2 cho vấn đề trình tự sắp xếp F2 ||Cmax , trong đó n = 5. ! 4 4 10 6 2 P = 5 1 4 10 3 Một trình tự sắp xếp bất kỳ của tập các công việc đều là trình tự khả thi, trong đó [J5, J1 , J4 , J3 , J2] là trình tự tối ưu.
13 P1 J5 J1 J4 J3 J2 P2 J5 J1 J4 J3 J2 0 2 5 6 11 12 22 26 27 Hình 1.3: Sơ đồ Grant Charts 1.2.2 Trình tự sắp xếp không trì hoãn Trong quá trình giải quyết các vấn đề trình tự sắp xếp, có một loại trình tự khả thi rất quan trọng được định nghĩa. Định nghĩa: Đối với một trình tự khả thi, nếu có các công việc đều được chuẩn bị trước, máy xử lý không có thời gian nghỉ trong cả quá trình gia công, loại trình tự sắp xếp này gọi là trình tự sắp xếp không trì hoãn. Nếu ngược lại, sẽ được gọi là trình tự sắp xếp trì hoãn được. Trình tự sắp xếp không trì hoãn tương đương với việc không được để máy xử lý có thời gian nghỉ trong quá trình gia công. Đối với đại đa số các vấn đề trình tự sắp xếp, bao gồm tất cả các trình tự sắp xếp có thể gián đoạn, trình tự tối ưu là tình tự không trì hoãn, tuy nhiên cũng có một vài vấn đề trình tự sắp xếp có thể gián đoạn mà trình tự tối ưu của nó là trình tự trì hoãn được. Ví dụ 1.2.3 Trình tự sắp xếp 1|rj | P wj Cj , n = 2, p = (10, 5), r = (0, 1), w = (1, 5). Vấn đề này có hai trình tự khả thi đó là: b b b P b T1 b T2 b b 0 10 15 (a) b b b b b b b b
b b b b b b b 14 b b b P T2 T1 b b b b b 0 1 6 16 (b) Hình 1.4: Trình tự khả thi của ví dụ 1.2.3 1.2.3 Sơ lược về thuật toán và độ phức tạp của thuật toán Lý thuyết độ phức tạp tính toán là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như kiểm tra tính nguyên tố là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là có hoặc không tùy theo số đó có là nguyên tố hay không. Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các mô hình tính toán để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong độ phức tạp truyền thông), số lượng cổng logic trong mạch (dùng trong độ phức tạp mạch) và số lượng bộ xử lý (dùng trong tính toán song song). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì máy tính có thể làm và không thể làm. Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là phân tích thuật toán và lý thuyết khả tính. Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn
15 đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyên. 1.2.4 Thuật toán và độ phức tạp của vấn đề trình tự sắp xếp Vấn đề trình tự sắp xếp là một loại hình của tổ hợp tối ưu hóa, ý tưởng cơ bản để giải quyết vấn đề này đó là: Sử dụng những phương pháp của các vấn đề tổ hợp tối ưu hóa khác, tích cực sử dụng các tính chất đặc trưng của bản thân vấn đề trình tự sắp xếp, từ đó xác định trình tự tối ưu thỏa mãn điều kiện ràng buộc. Có một vài vấn đề trình tự có thể trực tiếp chuyển hóa thành các vấn đề tổ hợp tối ưu hóa khác để giải quyết. Đối với vấn đề trình tự sắp xếp có thuật toán đa thức, cần cố gắng tìm ra thuật toán tốt và độ phức tạp và thời gian tính toán thuật toán đó. Đối với những vấn đề trình tự sắp xếp mà chưa biết thuật toán có phải là thuật toán đa thức hay không, trước tiên cần dùng lý luận về độ phức tạp tiến hành phân tích xem xét vấn đề đó có phải là NP-hard hay không để biết được độ khó của việc giải quyết loại vấn đề đó. Thông thường có một số trường hợp sau, thuật toán của một loại vấn đề trình tự sắp xếp có thể dùng để giải quyết một vấn đề trình tự sắp xếp khác. Ví dụ như vấn đề 1k Cj là một trường hợp đặc biệt của 1k wj Cj , P P do đó thuật toán giải quyết vấn đề 1k wj Cj cũng có thể được dùng để P giải quyết vấn đề 1k Cj . Trong lý luận về độ phức tạp, ta gọi quan hệ P này là tổng quát hóa đa thức thời gian. Ta nói 1k Cj tổng quát hóa đến P 1k wj Cj , ký hiệu 1k Cj ∝ 1k wj Cj . Dựa trên định nghĩa cơ bản P P P này, ta có thể xây dựng được rất nhiều chuỗi tổng quát hóa. Ví dụ 1.2.4 X X 1k Cj ∝ 1k wj Cj ∝ P m k wj Cj ∝ Qm | prec | wj Cj Tổng quát hóa là 1 loại quan hệ thứ tự, có rất nhiều vấn đề không thể
16 tổng quát hóa lẫn nhau, ví dụ như Pm k wj Cj và Jm k Cmax . P Hình 1.5, 1.6, 1.7 chỉ ra quan hệ tổng quát hóa của một số vấn đề trình tự sắp xếp. Trong đó, hình 1.5 sắp xếp dựa vào điều kiện máy xử lý, hình 1.6 sắp xếp dựa vào ràng buộc gia công, hình 1.7 sắp xếp dựa theo hàm mục tiêu. Chú ý rằng quan hệ ∝ được thay thế bằng "−→" để biểu thị ký hiệu 0 trong hình 1.6 biểu thị không có ràng buộc tương ứng. Nghiên cứu ranh giới giữa những vấn đề có thể giải được theo đa thức thời gian b b trong quan hệ tổng quát hóa và NP-hard là một việc rất quan trọng. b b b b Rm Qm FFs Jm Pm Fm Om 1 Hình 1.5: Quan hệ tổng quát hóa của một số vấn đề trình tự sắp xếp dựa theo điều kiện của máy xử lý. b b b b block rj sjk prmp prec Mj nwt recrc brkdwn 0 0 0 0 0 0 0 0 0 Hình 1.6: Quan hệ tổng quát hóa của một số vấn đề trình tự sắp xếp dựa theo điều kiện ràng buộc. Ví dụ trong chuỗi tổng quát hóa trên, vấn đề P m k wj Cj là NP-hard, P điều này nói lên rằng Qm|pree| wj Cj cũng là NP-hard. P Ta có một số quan hệ tổng quát hóa được phân chia theo ranh giới giữa vấn đề “dễ giải quyết” và vấn đề NP-hard như sau: