Luận văn Thạc sĩ Toán họ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

- 1.1 Vấn đề trình tự gia công trên máy đơn.
- 1.1.3 Phân loại các vấn đề trình tự gia công.
- 1.2 Tìm lời giải của vấn đề gia công trên máy đơn.
- 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.
- 2.1.2 Điều kiện cần và đủ của vấn đề 1k P C j.
- 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 (1k P.
- 24 2.2.1 Vấn đề 1k P.
- 24 2.2.2 Điều kiện cần và đủ của vấn đề 1k P.
- 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.
- 27 2.3.1 Vấn đề 1kL max.
- 28 2.3.3 Điều kiện cần và đủ của vấn đề 1kL max.
- 29 2.4 Vấn đề tối thiểu hóa thời gian gia công tối đa của công việc.
- 31 2.4.1 Vấn đề 1 |r j | C max.
- 31 2.4.2 Điều kiện cần và đủ của vấn đề 1 |r j | C max.
- 33 2.5 Vấn đề tối thiểu hóa tổng các công việc trễ trên mô hình.
- 35 2.5.1 Vấn đề 1k P.
- 35 2.5.2 Điều kiện cần và đủ của vấn đề 1k P.
- p j là thời gian gia công (thực hiện) của công việc T j .
- j=1 C j là tổng thời gian hoàn thành của các công việc từ T 1 đến T n.
- 1.1 Vấn đề trình tự gia công trên máy đơn (xem [1]).
- 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.
- 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..
- Giả sử có tập các công việc J = {J 1.
- Công việc:.
- (1) Véctơ thời gian gia công.
- Trong vấn đề trình tự gia công, vectơ thời gian gia công của công việc J i là p j = (p 1j , p 2j.
- C n ) biểu thị thời gian hoàn thành gia công nhiệm vụ.
- (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.
- (2) Độ dài thời gian gia công.
- (4) Thời gian trễ tối đa của các công việc.
- 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.
- pmtn: thời gian gia công có thể gián đoạn..
- P C j : tổng thời gian hoàn thành;.
- P w j C j : tổng thời gian hoàn thành của các công việc có trọng số khác 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.
- Vấn đề 1k P.
- Ví dụ 1.1.4 Vấn đề 1 | r j , pmtn | P.
- 1.2 Tìm lời giải của vấn đề gia công trên máy đơn (xem [1]).
- Vấn đề trình tự gia công là một vấn đề của tổ hợp tối ưu hóa.
- Ví dụ 1.2.1 Cho vấn đề trình tự gia công 1k P.
- Ví dụ 1.2.2 Cho vấn đề trình tự gia công F 2 ||C max , trong đó n = 5..
- Ví dụ 1.2.4 Trình tự gia công 1|r j | P.
- Vấn đề này có hai trình tự khả thi đó là:.
- b) Độ phức tạp của vấn đề trình tự gia công.
- Có một vài vấn đề trình tự có thể trực.
- Ví dụ như vấn đề 1k P.
- Hình 1.6: Quan hệ tổng quát hóa của một số vấn đề trình tự gia công dựa theo điều kiện của máy xử lý..
- Hình 1.7: Quan hệ tổng quát hóa của một số vấn đề trình tự gia công dựa theo điều kiện ràng buộc.
- Hình 1.8: Quan hệ tổng quát hóa của một số vấn đề trình tự gia công dựa theo điều kiện hàm mục tiê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.
- 2.1 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 tương đương nhau trên mô hình máy đơn (1k P.
- 2.1.1 Vấn đề 1k P C j.
- s=1 p s là thời gian hoàn thành của công việc T j .
- j=1 C j là tổng thời gian hoàn thành của các công việc từ T 1.
- Công việc (T j ) T 1 T 2 T 3 T 4 T 5.
- Khi đó, tổng thời gian hoàn thành của 5 công việc là:.
- Công việc (T j ) T 1 T 2.
- Thời gian thực hiện (p j ) p 1 p 2.
- p n tức là các công việc trong dãy π = (T 1 , T 2.
- p 00 n Khi đó tổng thời gian hoàn thành của dãy công việc là:.
- Như vậy dãy n công việc T 1 , T 2.
- Công việc (T j ) T 2 T 5 T 3 T 4 T 1.
- Tổng thời gian hoàn thành của 5 công việc là:.
- 2.2.1 Vấn đề 1k P w j C j.
- j=1 w j C j là tổng thời gian hoàn thành các công việc có trọng số khác nhau từ T 1 đến T n.
- Đó là vấn đề 1k P.
- 2.2.2 Điều kiện cần và đủ của vấn đề 1k P w j C j.
- Đối với vấn đề.
- Định lý 2.2.1 Quy tắc WSPT tạo thành trình tự tối ưu đối với vấn đề 2.2.
- Ví dụ 2.2.2 Xét vấn đề trình tự sắp xếp 1k P.
- 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 (1kL max ) 2.3.1 Vấn đề 1kL max.
- d j thời gian hoàn thành hạn định đối với công việc T j .
- Thời gian trễ tối đa (maximum lateness):.
- Công việc T j T 1 T 2 T 3 T 4 T 5 T 6.
- Khi đó, thời gian chậm trễ của các công việc T j là:.
- Vấn đề trình tự trễ tối đa của các nhiệm vụ có thời gian đến như nhau:.
- 2.3.2 Điều kiện đủ để vấn đề 1kL max là tối ưu.
- Định lý 2.3.1 Quy tắc EDD giải quyết vấn đề tìm trình tự tối ưu đối với.
- vấn đề 1kL max.
- 2.3.3 Điều kiện cần và đủ của vấn đề 1kL max (xem [5]).
- 2.4.1 Vấn đề 1 |r j | C max.
- Đối với một trình tự sắp xếp π, thời gian hoàn thành của công việc T π(i) là.
- Ví dụ 2.4.1 Xét vấn đề trình tự sắp xếp 1 |r j | C max với n = 4, p r .
- 2.4.2 Điều kiện cần và đủ của vấn đề 1 |r j | C max (xem [5]).
- Ví dụ 2.4.2 Xét vấn đề trình tự sắp xếp 1 |r j | C max với n = 4, p r .
- Ví dụ 2.4.3 Xét vấn đề trình tự sắp xếp 1 |r j | C max với n = 4, p r .
- 2.5 Vấn đề tối thiểu hóa tổng các công việc trễ trên mô hình máy đơn (1k P.
- 2.5.1 Vấn đề 1k P U j.
- Đối với một trình tự π, thời gian hoàn thành của công việc T π(i) là C π(i.
- Vấn đề đặt.
- Ví dụ 2.5.1 Xét vấn đề 1k P.
- Vậy vấn đề là phải tối thiểu hóa tổng các công việc trễ..
- 2.5.2 Điều kiện cần và đủ của vấn đề 1k P U j.
- (1) Sắp xếp các công việc theo trình tự EDD..
- Điều thú vị là mặc dù vấn đề trình tự 1k P.
- Và vấn đề trình tự 1k P.
- Định lý 2.5.5 Một tập hợp độc lập I là tối ưu đối với vấn đề 1k P.
- 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 trên mô hình máy đơ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.

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt