Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    TIẾN SĨ Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô

    VipHư Trúc Hư Trúc Đang Ngoại tuyến (2601 tài liệu)
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô

    MỞ ĐẦU
    Dân số thế giới tăng nhanh và đời sống vật chất của con người không ngừng
    nâng cao. Điều đó dẫn tới nhu cầu về tài nguyên thiên nhiên ngày càng lớn. Chúng
    ta đã và đang chứng kiến sự cạn kiệt của tài nguyên thiên nhiên, nhất là những
    nguồn tài nguyên không tái tạo được như khoáng sản. Để phát triển bền vững, việc
    sử dụng tài nguyên một cách hiệu quả luôn là vấn đề thời sự của toàn nhân loại.
    Trong các ngành kinh tế như chế tạo máy, xây dựng, dệt may việc sử dụng hiệu
    quả tài nguyên thể hiện bởi việc sử dụng hiệu quả các loại vật liệu thô phục vụ cho
    mục đích kinh tế.
    Lĩnh vực cắt vật tư và đóng hàng (Cutting & Packing-C&P) bao gồm nhiều bài
    toán tổ hợp, hình học, các mô hình và thuật toán lý thuyết cũng như thực tiễn liên
    kết với nhau. Mục tiêu chính của lĩnh vực này là sắp xếp một cách hiệu quả các đối
    tượng được mô tả bằng ngôn ngữ hình học trong một miền lớn hơn. Các bài toán
    sau đây là các bài toán điển hình cho chủ đề này: Cắt vật tư và bài toán phế thải, xếp
    thùng (bin packing), bài toán sắp ba lô (knapsack), cân bằng luồng (line balancing),
    bài toán phân phối bộ nhớ và lập lịch cho bộ đa xử lý (memory allocation and
    multiprocessor scheduling problem) Các bài toán cắt vật tư và đóng hàng được
    phát biểu và xử lý trong nhiều ngành khoa học khác nhau như khoa học quản lý,
    khoa học kỹ thuật, khoa học máy tính và công nghệ thông tin, toán học và vận trù
    học. Chúng là các bài toán thực tế đặt ra cho các ngành công nghiệp như công
    nghiệp kính, thép, giấy, da, may mặc, vận tải và hậu cần.
    Từ giữa thế kỷ trước đã có nhiều cá ch tiếp cận giải các bài toán cắt vật tư và
    đóng hàng được đề xuất. Công trình khởi nguồn cho chủ đề này do
    L.V.Kantorovich đưa ra năm 1939 khi ông đề xuất áp dụng các mô hình toán học để
    2
    tổ chức và lập kế hoạch sản xuất. Các mô hình này được phát biểu dướ i dạng các
    bài toán Quy hoạch nguyên và được chỉ ra thuộc lớp các bài toán NP-hard. Mô hình
    có một số nhược điểm như có nới lỏng liên tục yếu và tính đối xứng nên việc áp
    dụng nó trong các bài toán thực tiễn tỏ ra không hiệu quả.
    Để khắc phục nhược điểm củ a mô hình trên, một mô hình khác cùng với kỹ thuật
    giải hiệu quả bài toán cắt vật tư một chiều được Gilmore và Gomory đề xuất vào
    những năm 60 thế k ỷ trước. Trong kỹ thuật này, các tác giả sử dụng công cụ quy
    hoạch tuyến tính để giải bài toán nới lỏng liên tục dẫn xuất từ bài toán quy hoạch
    nguyên. Nghiệm của bài toán quy hoạch nguyên ban đầu sẽ nhận được bằng các kỹ
    thuật làm tròn nghiệm của bài toán nới lỏng liên tục khi bài toán đảm bảo tính chất
    làm tròn nguyên (Integer Round-Up Property-IRUP). Đề xuất của Gilmore và
    Gomory đặc biệt hiệu quả khi giải các bài toán cắt vật tư nhờ kỹ thuật tạo sinh cột
    với việc giải Bài toán xếp ba lô như một bài toán con. Sau này kỹ thuật tạo sinh cột
    trở thành kỹ thuật được ưa chuộng nhất khi người ta đề cập tới việc giải các bài toán
    quy hoạch cỡ lớn.
    Do tính khoa học cũng như thực tiễn cao của chủ đề c ắt vật tư và đóng hàng nên
    vào năm 1988 H. Dyckhoff và G. Waescher đã thành lập Special Interest Group on
    Cutting and Packing (SICUP), bước quan trọng để hỗ trợ nghiên cứu quốc tế về chủ
    đề này. Một trong những đóng góp nổi bật của H.Dyckhoff vào năm 1990 cho việc
    phát triển các nghiên cứu lý thuyết cũng như ứng dụng trong lĩnh vực này là việc
    đưa ra phân loại (Typology) các bài toán cắt vật tư và đóng hàng dựa trên điều t ra
    các đặc tính của cấu trúc hình học, cấu trúc logic và ngữ cảnh xuất hiện của chúng
    trong thực tế. Sự phân loại này được G. Waescher và các đồng nghiệp tiếp tục hoàn
    thiện vào năm 2007. Việc phân loại được thực hiện dựa trên bốn tiêu chí:
    3
    1. Số chiều của bài toán: có thể là 1, 2, 3 hoặc lớn hơn
    2. Kiểu gán (Kind of assignment): Có hai kiểu gán là cực đại hóa đầu ra
    (Output Maximization) hoặc cực tiểu hóa đầu vào (Input Minimization)
    3. Phân loại các đối tượng nhỏ (Assortment of small items): đồng nhất, tương
    đối không thuần nhất (weakly heterogeneous assortment), hoàn toàn không
    thuần nhất (Strongly heterogeneous assortment)
    4. Phân loại các đối tượng lớn (Assortment of large objects):
    - Một đối tượng lớn (có thể được xem xét chi tiết hơn phụ thuộc vào các
    chiều của đối tượng được cố định hay có thể biến đổi )
    - Một số đối tượng lớn với các chiều cố định. Trường hợp này có thể được
    chia thành các bài toán với các đối tượng lớn đồng nhất , tương đối đồng
    nhất và hoàn toàn không đồng nhất.
    Trong các kiểu bài toán cắt vật tư thì Bài toán cắt vật tư một chiều (One
    Dimensional Cutting Stock Problem – OneDCSP) giữ một vị trí quan trọng và
    chiếm gần một nửa tổng số công trình đã được công bố về chủ đề này. Có nhiều lý
    do giải thích về mối quan tâm của cộng đồng nghiên cứu dành cho bài toán này
    trong đó có thể dẫn ra nhận xét của Gilmore và Gomory khi nói rằng, nhiều bài toán
    cắt vật tư nhiều chiều có thể được xử lý bằng một quy trình nhiều công đoạn dựa
    trên nền tảng bài toán cắt vật tư một chiều. Từ công trình khởi đầu của Gilmor e và
    Gomory, hàng loạt các biến thể khác nhau của bài toán OneDCSP đã được phát biểu
    và giải quyết bằng các cách tiếp cận khác nhau.

    MỤC LỤC
    MỞ ĐẦU 1
    Chương 1. CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN .9
    1.1. Bài toán cắt vật tư một chiều với một loại vật liệu thô và thuật giải 9
    1.1.1. Mô hình Gilmore-Gomory .10
    1.1.2. Mô hình Arc-flow của Valerio de Carvalho 13
    1.2. Giải thuật di truyền 19
    1.3. Kết luận .25
    Chương 2. BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚC
    VẬT LIỆU THÔ: MÔ HÌNH VÀ GIẢI PHÁP .26
    2.1. Phát biểu bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô theo
    Gilmore và Gomory 26
    2.2. Phát biểu mới của bài toán OneDCSP_M .28
    2.3. Giải thuật di truyền lai ghép giải bài toán OneDCSP_M 32
    2.4. Kết quả tính toán .40
    2.5. Kết luận .50
    Chương 3. HỆ THỐNG ĐA TÁC TỬ GMAS-OneDCSP_M GIẢI BÀI TOÁN
    OneDCSP_M 52
    3.1. Yêu cầu của hệ thống GMAS-OneDCSP_M 54
    3.2. Thiết kế hệ thống GMAS-OneDCSP_M .55
    3.2.1. Kiến trúc hệ thống GMAS-OneDCSP_M .55
    3.2.2. Thiết kế chi tiết hệ thống GMAS-OneDCSP_M .58
    3.3. Đánh giá tính hiệu quả của hệ thống GMAS-OneDCSP_M .65
    3.4. Kết luận .67
    KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO 68
    DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ .70
    TÀI LIỆU THAM KHẢO 71
    PHỤ LỤC .78

    Xem Thêm: Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu
Tài liệu mới

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status