//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10

Chuyên đề 5. BÀI TOÁN LẬP LỊCH

Số tiết: 5


1. Giới thiệu bài toán lập lịch


1.1. Các thành phần của bài toán lập lịch

Kiến thức:
Hiểu các khái niệm về:

  • Công việc: Trình tự thực hiện, Ngắt quãng, Thời điểm sẵn sàng, Thời gian xử lý, Thời điểm hoàn thành, Thời gian trôi, Thời gian chờ đợi, Thời hạn hoàn thành, Thời gian lệch, Khoảng trễ, Độ trễ, Đúng hạn.
  • Môi trường máy: Máy, Máy đơn, Máy song song, Xưởng công việc (Job Shop), Xưởng dây chuyền (Flow Shop), Xưởng mở (Open Shop).
  • Hàm mục tiêu: Thời điểm hoàn thành lịch (Makespan), Tổng (có trọng số) thời gian xử lý (Total (Weighted) Completion Time), Thời gian trôi trung bình (có trọng số) ((Weighted) Mean Flow Time), Thời gian chờ đợi trung bình (Mean Waiting Time), Khoảng trễ (Lateness), Độ trễ, Đúng hạn, Tiêu chuẩn tổng quát, Qui dẫn giữa các bài toán lập lịch.

1.2. Ký pháp Graham

Kiến thức:
Hiểu biết các khái niệm:
– Trường mô tả môi trường máy
– Trường mô tả các ràng buộc và thuộc tính của công việc
– Trường mô tả tiêu chuẩn tối ưu


2 Một số phương pháp giải cơ bản


2.1. Giải thuật tham lam

Kiến thức:
Hiểu biết các thuật toán:
– Thời gian xử lý lớn nhất (Longest Processing Time, viết tắt là LPT)
– Thời gian xử lý nhỏ nhất (Shortest Processing Time, viết tắt là SPT)
– Thời gian xử lý có trọng số nhỏ nhất (Weighted Shortest Processing Time – WSPT)
– Thời hạn hoàn thành sớm nhất (Earliest Due Date- EDD)
– Thời gian lệch nhỏ nhất (Minimum Slack Time – MST)
– Lập luận hoán đổi
– Các ví dụ ứng dụng:

  • Bài toán 1| | Cj . Bài toán 1||Lmax. Bài toán 1|rj, pmtn|Lmax. Bài toán 1|rj, pmtn|Cj. Bài toán 1|prec|hmax
  • – Thuật toán Lawler.
  • Thuật toán Johnson giải bài toán F2||Cmax

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên

2.2. Qui hoạch động

Kiến thức:
Hiểu biết các thuật toán:

  •  Bài toán lập lịch cực đại lợi nhuận 1| | wi(1-Ui)
  •  Thuật toán Moore

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên

2.3. Qui về bài toán tối ưu trên đồ thị

Kiến thức:
Hiểu biết các nội dung:

  •  Bài toán lập lịch thi công (PERT).
  • Qui dẫn bài toán R||Cj về bài toán ghép cặp trên đồ thị hai phía

Kĩ năng:
Cài đặt chương trình cho các thuật toán trên

2.4. Thuật toán nhánh cận

Kiến thức:

Hiểu biết các nội dung:

  • Sơ đồ chung của thuật toán nhánh cận
  • Ví dụ áp dụng: Bài toán 1|ri|Lmax.

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên


Tham khảo


  1. Ký pháp Graham
  2. Tham khảo Open Shop
  3. Tham khảo Flow shop
  4. Tham khảo Job shop
  5. Hill climbing heuristic algorithms.
  6. Particle swarm optimization
  7. Simulated annealing
  8. Tabu search
  9. Ant colony optimization algorithms

 

 

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Livin' on an Island

A better future...

The Last Hurrah

More Photos

Thống kê

  • 95,498 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: