Tài liệu Nghiên cứu điều kiện cần và đủ của giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công trên mô hình máy đơn (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- HOÀNG THỊ MƠ NGHIÊN CỨU ĐIỀU KIỆN CẦN VÀ ĐỦ CỦA GIẢI PHÁP TỐI ƯU ĐỐI VỚI MỘT SỐ VẤN ĐỀ LẬP KẾ HOẠCH GIA CÔNG TRÊN MÔ HÌNH MÁY ĐƠN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- HOÀNG THỊ MƠ NGHIÊN CỨU ĐIỀU KIỆN CẦN VÀ ĐỦ CỦA GIẢI PHÁP TỐI ƯU ĐỐI VỚI MỘT SỐ VẤN ĐỀ LẬP KẾ HOẠCH GIA CÔNG 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 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. PHẠM HỒNG TRƯỜNG THÁI NGUYÊN - 2017 i Mục lục Bảng ký hiệu iii Lời nói đầu 1 1 Một số kiến thức cơ bản về vấn đề gia công trên máy đơn 3 1.1 Vấn đề trình tự gia công trên máy đơn . . . . . . . . . . . . 3 1.1.1 1.1.2 1.2 Lời dẫn . . . . . . . . . . . . . . . . . . . . . . . . . Các định nghĩa . . . . . . . . . . . . . . . . . . . . . 3 5 1.1.3 Phân loại các vấn đề trình tự gia công . . . . . . . . 10 Tìm lời giải của vấn đề gia công trên máy đơn . . . . . . . . 13 1.2.1 Trình tự có thể thực hiện (trình tự khả thi) và trình tự tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2 Trình tự gia công không trì hoãn và trình tự gia công trì hoãn được . . . . . . . . . . . . . . . . . . . . . . 14 1.2.3 Sơ lược thuật toán và độ phức tạp của vấn đề trình tự gia công . . . . . . . . . . . . . . . . . . . . . . . 15 2 Điều kiện cần và đủ của giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công trên mô hình máy đơn 19 2.1 Vấn đề tối thiểu hóa tổng thời gian hoàn thành gia công các P công việc tương đương nhau trên mô hình máy đơn (1k Cj ) 21 P 2.1.1 Vấn đề 1k Cj . . . . . . . . . . . . . . . . . . . . . 21 P 2.1.2 Điều kiện cần và đủ của vấn đề 1k Cj . . . . . . . 22 ii 2.2 Vấn đề tối thiểu hóa tổng thời gian hoàn thành gia công các công việc có trọng số khác nhau trên mô hình máy đơn P (1k wj Cj ) . . . . . . . . . . . . . . . . . . . . . . . . . . 24 P 2.2.1 Vấn đề 1k wj Cj . . . . . . . . . . . . . . . . . . . 24 P 2.2.2 Điều kiện cần và đủ của vấn đề 1k wj Cj . . . . . 25 2.3 Vấ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 như nhau trên mô hình máy đơn (1kLmax ) . 27 2.3.1 2.3.2 2.4 Vấn đề 1kLmax . . . . . . . . . . . . . . . . . . . . . 27 Điều kiện đủ để vấn đề 1kLmax là tối ưu . . . . . . . 28 2.3.3 Điều kiện cần và đủ của vấn đề 1kLmax . . . . . . . 29 Vấn đề tối thiểu hóa thời gian gia công tối đa của công việc trên mô hình máy đơn với thời gian tham gia vào quá trình gia công bất kì (1 |rj | Cmax ) . . . . . . . . . . . . . . . . . . 31 2.4.1 Vấn đề 1 |rj | Cmax . . . . . . . . . . . . . . . . . . . 31 2.5 2.4.2 Điều kiện cần và đủ của vấn đề 1 |rj | Cmax . . Vấn đề tối thiểu hóa tổng các công việc trễ trên mô P máy đơn (1k Uj ) . . . . . . . . . . . . . . . . . . . P 2.5.1 Vấn đề 1k Uj . . . . . . . . . . . . . . . . P 2.5.2 Điều kiện cần và đủ của vấn đề 1k Uj . . . . . . . 33 hình . . . . 35 . . . . 35 . . . . 37 Kết luận 43 Tài liệu tham khảo 44 iii Bảng ký hiệu Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: Jj công vụ thứ j Pj tập các máy sử lý Tj là công việc thứ j. pj là thời gian gia công (thực hiện) của công việc Tj . rj là thời gian đạt đến hay thời gian chuẩn bị. dj là kỳ hạn biểu thị thời gian hoàn thành hạn định của nhiệm vụ Tj . wj là một trọng số biểu thị mức độ ưu tiên quan trọng của nhiệm vụ Tj Cj là thời gian hoàn thành của công việc Tj . Pn j=1 Cj là tổng thời gian hoàn thành của các công việc từ T1 đến Tn . 1 Lời nói đầu Hàng ngàn dạng vấn đề sắp xếp trong lĩnh vực của tổ hợp tối ưu hóa, trong đó rất nhiều kết quả lý thuyết được phát triển. Cụ thể, chúng được thúc đẩy bởi các ứng dụng thực tế, việc nghiên cứu các vấn đề sắp xếp trong khía cạnh thuật toán, bao gồm các phép tính toán phức tạp, các thuật toán đa thức, các thuật toán sấp xỉ, có nhiều tiến bộ trong những năm gần đây. Tổ hợp tối ưu hóa có ảnh hưởng đến hầu hết các lĩnh vực khoa học - công nghệ, kinh tế - xã hội. Tối ưu hóa là quá trình đi đến cái "tốt nhất". Phương pháp tối ưu hóa là các biện pháp, các thuật toán, các kỹ xảo, các thao tác,... nhằm đi đến điểm tối ưu. 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 chúng tôi nghiên cứu điều kiện cần và đủ của giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công 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 hóa. Đó 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. Trong phạm vi một doanh nghiệp, một nhà máy sản xuất 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. 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 đề ra. Chính vì vậy việc nghiên cứu điều kiện cần và đủ của giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công trên mô hình máy đơn trong 2 sản xuất ở các nhà máy đóng vai trò rất quan trọng. Việc tìm ra giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công trên mô hình máy đơn sẽ giúp 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ễ của các công việc tham gia vào quá trình gia công, tối thiểu hóa thời gian gia công tối đa của các công việc, 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, nghiên cứu điều kiện cần và đủ của giải pháp tối ưu đối với một số vấn đề lập kế hoạch gia công trên mô hình máy đơn. Một số vấn đề đã được tài liệu [1] nói đến, tuy nhiên trong luận văn này các vấn đề đã được nghiên cứu đầy đủ hơn về cả điều kiện cần và điều kiện đủ. 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 đã 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 K9C (khóa 2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập . 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,10 tháng 7 năm 2017 Tác giả Hoàng Thị Mơ 3 Chương 1 Một số kiến thức cơ bản về vấn đề gia công trên máy đơn 1.1 Vấn đề trình tự gia công trên máy đơn (xem [1]) 1.1.1 Lời dẫn Vấn đề trình tự gia công trên máy đơn là một trong những vấn đề trình tự gia công đơn giản nhất, đồng thời cũng là một trong những vấn đề sắp xếp rất quan trọng. Vấn đề trình tự gia công trên máy đơn tương đối dễ tìm ra phương pháp giải quyết, những phương pháp này có những tác dụng cụ thể đối với việc nghiên cứu những vấn đề trình tự sắp xếp phức tạp hơn, có thể giúp cho việc tìm ra những thuật toán xấp xỉ đối với những vấn đề trình tự gia công trên máy đơn được giới thiệu là những vấn đề tồn tại trong cuộc sống hiện thực, có bối cảnh thực tế. Vì vậy, vấn đề trình tự gia công trên máy đơn có phạm vi ứng dụng lớn, nâng cao hiệu suất lao động, có ý nghĩa cực kỳ to lớn. Việc nghiên cứu các thuộc tính cấu trúc đối với các vấn đề sắp xếp gia công cũng là một lĩnh vực phong phú. Vấn đề trình tự gia công 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 4 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ự gia công. Trước khi đưa ra định nghĩa của vấn đề trình tự gia công trên máy đơn, 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 Sắp xếp điều hành chuyến bay 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. Ví dụ 1.1.2 Trình tự xử lý trên máy tính khi thực hiện hệ thống thao tác đa nhiệm, phát sinh thêm một nhiệm vụ. Về tổng quan ta có thể hiểu là đồng thời tiến hành nhiều tiến trình. Tuy nhiên tại một thời điểm bất kỳ CPU chỉ có thể tiến hành một tiến trình. Thời gian đạt đến của tiến trình là không như nhau. Vấn đề đặt ra là sắp đặt như thế nào những tiến trình đó thì mới có thể làm cho hiệu suất sử dụng của CPU là cao nhất hoặc thời gian để thay đổi của tiến trình là ngắn nhất? Đây cũng là một vấn đề sắp xếp. Ngoài ra thời gian đạt đến của mỗi tiến trình và thời gian thay đổi là không biết trước, nhưng kì vọng toán, phương sai, ... của thời 5 gian đạt đến ngẫu nhiên và thời gian thay đổi đã được biết trước. Lúc này mục tiêu là tối thiểu hóa kì vọng của thời gian trung chuyển. Như vậy vấn đề sắp xếp xuất hiện biến lượng ngẫu nhiên và được gọi là vấn đề trình tự sắp xếp ngẫu nhiên. 1.1.2 Các định nghĩa Vấn đề trình tự gia công 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ự gia công, 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ự gia công: Cho tập hợp n nhiệm vụ (task) Tập hợp m máy xử lý (processors) T = {T1 , . . . , Tn } P = {P1 , . . . , Pm } Tập hợp s loại nguồn lực (resources) R = {R1 , . . . , Rs }. Mục đích của vấn đề trình tự gia công đó là sắp xếp những điều kiện nhất định được đưa ra để 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 là vấn đề trình tự gia công 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ự gia công đa máy. Vấn đề trình tự gia công song song là vấn đề trình tự gia công đ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ự gia công song song . 6 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ự. Nếu mỗi công việc đều cần thực hiện gia công trên các máy xử lý, mỗi công việc có quá trình thực hiện 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 thực hiện 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ở. ∗ Công việc: Những điều kiện ràng buộc trong vấn đề trình tự gia công 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 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 7 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ự gia công, 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 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à trọng số ưu tiên của n nhiệm vụ. 8 Ký hiệu  p11   p21 P = ...  pm1 p12 . . . p1n   p22 . . . p2n   ... ... ...  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ó. 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ó. • Đồ thị ràng buộc ưu tiên dạng cây xuất: mỗi nhiệm vụ có nhiều nhất một nhiệm vụ tiếp ngay trước nó. 9 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 hoàn thành gia công 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) Tổng thời gian hoàn thành gia công các công việc có trọng số khác nhau n X C= wj C j j=1 Đặc biệt khi wj = 1, ∀j = 1, 2, . . . , n thì tổng thời gian hoàn thành gia công các công việc có trọng số khác nhau trở thành tổng thời gian hoàn thành gia công các công việc tương đương nhau (total completion time) C= n X Cj j=1 (2) Độ dài thời gian gia công Độ dài thời gian gia công được định nghĩa là: Cmax = max{Cj } 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 10 làm việc cao. (3) Thời gian gia công tối đa với thời gian tham gia vào quá trình gia công bất kì Thời gian gia công tối đa với thời gian tham gia vào quá trình gia công bất kì được định nghĩa là: 1 |rj | Cmax (4) Thời gian trễ tối đa của các công việc Thời gian trễ tối đa (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 (5) Tổng các công việc trễ của các nhiệm vụ có trọng số khác nhau (weighted number of tardy task) U= n X wj Uj j=1  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 . Đặc biệt khi wj = 1, ∀j = 1, 2, . . . , n thì tổng các công việc trễ của các nhiệm vụ có trọng số khác nhau trở thành tổng các công việc trễ tương đương nhau n X U= Uj j=1 1.1.3 Phân loại các vấn đề trình tự gia công Trong phân loại vấn đề trình tự gia công, 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ự gia công xác định. Nếu như có một vài dữ liệu số liệu chưa được 11 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ự gia công 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ự gia công. 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ự gia công 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ự gia công: α|β|γ 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. + Rm : 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. 12 + 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; P 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 nhau; Lmax : thời gian trễ tối đa; P ωj Uj : Tổng các công việc trễ của các nhiệm vụ có trọng số khác nhau; P Uj : Tổng các công việc trễ tương đương nhau. Ví dụ 1.1.3 Một số vấn đề lập kế hoạch gia công trên mô hình máy đơn P • Vấn đề 1k Cj là vấn đề tổng thời gian hoàn thành gia công các công việc tương đương nhau, hàm mục tiêu là tối thiểu hóa tổng thời gian hoàn thành gia công các công việc tương đương nhau. P • Vấn đề 1k wj Cj là vấn đề tổng thời gian hoàn thành gia công các công việc có trọng số khác nhau, hàm mục tiêu là tối thiểu hóa tổng thời gian hoàn thành gia công các công việc có trọng số khác nhau. • Vấn đề 1kLmax là vấn đề thời gian trễ tối đa, hàm mục tiêu là 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 như nhau. P • Vấn đề 1k Uj là vấn đề tổng các công việc trễ, hàm mục tiêu là tối thiểu hóa tổng các công việc trễ. • Vấn đề 1 |rj | Cmax là vấn đề thời gian gia công tối đa, hàm mục tiêu là tối thiểu hóa thời gian gia công tối đa của các công việc với thời gian tham gia vào quá trình gia công bất kì. 13 Ví dụ 1.1.4 Vấn đề 1 | rj , pmtn | P wj Cj là vấn đề trình tự gia công trên máy đơ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.5 Vấn đề P m k Cmax là vấn đề gia công 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). 1.2 Tìm lời giải của vấn đề gia công trên máy đơn (xem [1]) 1.2.1 Trình tự có thể thực hiện (trình tự khả thi) và trình tự tối ưu Vấn đề trình tự gia công 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ự gia công đề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ự gia công, 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ự gia công, 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ự gia công 1k p = (12, 4, 7, 11, 6, 5), ω = (4, 2, 5, 5, 6, 3) P wj Cj trong đó, n = 6, 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 đó [T5 , T3 , T6 , T2 , T4 , T1 ] là trình tự tối ưu. Ví dụ 1.2.2 Cho vấn đề trình tự gia công F2 ||Cmax , trong đó n = 5. 14 Hình 1.3: Trình tự tối ưu của ví dụ 1.2.1 ! 4 4 10 6 2 P = 5 1 4 10 3 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 đó [J5 , J1 , J4 , J3 , J2 ] là trình tự tối ưu. Hình 1.4: Sơ đồ Grant Charts 1.2.2 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 đề trình tự gia công, có một loại trình tự khả thi rất quan trọng được định nghĩa. Định nghĩa 1.2.3 Đố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ự gia công này gọi là trình tự gia công không trì hoãn. Nếu ngược lại, sẽ được gọi là trình tự gia công trì hoãn được. Trình tự gia công 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ự gia công, bao gồm tất cả các trình tự gia công có thể gián đoạn, trình tự tối ưu là trình tự không trì hoãn, tuy nhiên cũng có một vài vấn đề trình tự gia công có thể gián đoạn mà trình tự tối ưu của nó là trình tự trì hoãn được. 15 Ví dụ 1.2.4 Trình tự gia công 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à: Hình 1.5: Trình tự khả thi của ví dụ 1.2.4 1.2.3 Sơ lược thuật toán và độ phức tạp của vấn đề trình tự gia công a) Thuật toán Khái niệm thuật toán đã được biết đến từ lâu. Thuật ngữ thuật toán (Algorithm) là biến tướng của tên nhà toán học Arập: Aba Jafa Mohamedibn Musaal Khowarizmi. Hiện nay cùng với sự phát triển của máy tính, khái niệm thuật toán được định nghĩa một cách hình thức chính xác thông qua máy Turing. Tuy nhiên trong phạm vi luận văn này thuật toán có thể hiểu một cách trực quan qua định nghĩa sau: Định nghĩa 1.2.5 Một thuật toán để giải một bài toán (P) đã cho là một thủ tục được chia ra thành các phép toán cơ bản, biến đổi một dãy các dấu hiệu diễn tả các dữ liệu, không quan trọng ở chỗ thuộc bản chất gì, của bài toán (P) thành một dãy các dấu hiệu đặc trưng cho các kết quả của (P). b) Độ phức tạp của vấn đề trình tự gia công Vấn đề trình tự gia công 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ự gia công, 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