Thạc Sĩ Ứng dụng mô hình Job-shop linh động để hỗ trợ lập lịch sản xuất cho một công ty

LUẬN VĂN THẠC SĨ CÔNG NGHỆ TT
NĂM 2012

MỤC LỤC
Trang
Trang phụbìa
LỜI CẢM ƠN
LỜI CAM ĐOAN
DANH MỤC CÁC TỪVIẾT TẮT
DANH MỤC BẢNG
DANH MỤC HÌNH
CHƯƠNG 1: GIỚI THIỆU TỒNG QUAN 1
1.1. Tổng quan vềbài toán lập lịch: 1
1.1.1. Bài toán lập lịch Job shop: . 1
1.1.2. Phân loại các vấn đềlập kếhoạch: 3
1.2. Giới thiệu vềluận văn: . 5
1.2.1. Mục tiêu của luận văn: . 6
1.2.2. Nội dung trình bày luận văn: . 6
1.2.3. Các công việc cần thực hiện: 6
i. Giai đoạn đầu tiên: 7
ii. Giai đoạn thứ2: . 7
iii. Giai đoạn thứ3: . 8
CHƯƠNG 2:MỘT SỐVẤN ĐỀHỖTRỢLẬP LỊCH TRONG SẢN XUẤT . 10
2.1. Ý nghĩa lập kếhoạch sản xuất: 10
2.2. Mô hình dữliệu: . 13
2.3. Mô hình sản xuất: . 15
2.3.1. Phân loại theo hình thức tổchức sản xuất: . 16
a. Sản xuất liên tục (Flow shop): . 16
b. Sản xuất gián đoạn (Job shop): . 16
c. Sản xuất theo dựán: (Open shop) . 17
2.3.2. Phương pháp quản lý sản xuất: . 18
2.4. Cấu trúc hệthống: 19
2.5. Mô hình toán học và các giải thuật: . 19
2.5.1. Các phương pháp Metaheuristics: . 20
2.5.1.1. Phương pháp lai metaheuristics (Hybrid metaheuristics): . 20
2.5.1.2. Phương pháp tìm kiếm địa phương (Local search): 21
2.5.1.3. Lặp lại tìm kiếm địa phương (Iterated local search): 23
2.5.2. Các luật phân phối Heuristics: . 24
2.5.3. Thuật toán di truyền (Genetic algorithms): 25
2.5.4. Thuật toán tìm kiếm Tabu (Tabu search): 28
2.5.5. Thuật toán mô phỏng luyện kim (Simulated Annealing): 29
2.5.6. Thuật toán tối ưu hóa thuộc địa đàn kiến (Ant Colony
Optimization) : . 30
2.5.6.1. Nguồn gốc thuật toán: . 30
2.5.6.2. Miêu tảthuật toán ACO: 33
2.5.7. Thuật toán hệthống đẩy (push system): . 37

CHƯƠNG 3:HỆTHỐNG LẬP LỊCH TRONG SẢN XUẤT 39
3.1. Mô hình sản xuất: . 39
3.1.1. Mô hình sản xuất của ngành công nghiệp dược phẩm: 39
3.1.2. Mô hình phương pháp quản lý sản xuất tại công ty BV Pharma:
3.1.3. Quy trình sản xuất: 42
3.1.3.1. Giai đoạn chuẩn bị: . 42
3.1.3.2. Giai đoạn pha chế: 42
3.1.3.3. Giai đoạn dập viên: . 43
3.1.3.4. Giai đoạn bao phim: . 43
3.1.3.5. Giai đoạn ép vĩhay vô chai: . 43
3.1.3.6. Giai đoạn đóng gói: . 43
3.1.4. Các yêu cầu đặt cho hệthống lập lịch : . 43
3.2. Mô hình dữliệu : 47
3.3. Thuật toán lập lịch: 47
3.3.1. Thuật toán Jopshop: . 48
3.3.2. Thuật toán lập kếhoạch đẩy: . 52
3.3.3. Thuật toán tối ưu hóa thuộc địa đàn kiến (Ant Colony
Optimization): 55
3.4. Cấu trúc phần mềm: 58
3.4.1. Cập nhật cơsởdữliệu và tạo ra một lịch trình mặc định: . 58
3.4.2. Tối ưu hóa kết quảlập kếhoạch thông qua ACO: . 59
3.4.3. Sửa đổi kết quảlựa chọn tối ưu hóa: . 60

CHƯƠNG 4:CHƯƠNG TRÌNH THỬNGHIỆM 62
4.1. Cấu trúc hệthống: 62
4.2. Cơsởdữliệu: 62
4.3. Giao diện: 63
4.3.1. Màn hình đăng nhập: . 63
4.3.2. Màn hình cập nhật thông tin đơn đặt hàng: . 64
4.3.3. Màn hình cập nhật thông tin sản phẩm: . 65
4.3.4. Màn hình cập nhật thông tin máy: 65
4.3.5. Màn hình cập nhật thông tin khách hàng: 66
4.3.6. Màn hình thông tin ngày nghỉ: 66
4.3.7. Màn hình thông tin tăng ca: . 67
4.4. Thửnghiệm: . 67
4.4.1. Hệthống tính toán thời gian sản xuất thực tế: 68
4.4.1.1. Thời gian tiêu chuẩn của mỗi sản phẩm trên mỗi máy trạm:. 69
4.4.1.2. Thời gian chờ đợi trên mỗi máy trạm: . 70
4.4.1.3. Thời gian cài đặt máy: 70
4.4.1.4. Xét thời gian thực hiện trên các máy trạm: . 71
4.4.2. Kết quảhoán vịcủa thuật toán ACO: . 78
4.4.3. So sánh kết quảlập kếhoạch mặc định với kết quảcủa thuật
toán ACO: 81




CHƯƠNG 1:
GIỚI THIỆU TỒNG QUAN
1.1. Tổng quan vềbài toán lập lịch:
Lập kế hoạch một hệ thống sản xuất có thể là một trong những nhiệm vụ
phức tạp nhất trong việc quản lý hoạt động sản xuất. Vì vậy, việc trợgiúp của hệ
thống phần mềm máy vi tính đã trởnên hữu ích hơn để đáp ứng nhu cầu của ngành
công nghiệp. Tầm quan trọng của thiết kếmột hệthống có hệthống, đặc biệt là sử
dụng các hệthống máy tính đã làm tăng năng suất của các nhà sản xuất sản phẩm
đáp ứng nhu cầu của khách hàng. Trong môi trường làm việc thực tế, các vấn đề
thích hợp nhất mà thách thức các nhà sản xuất cung cấp sản phẩm đúng thời gian
cho khách hàng và quản lý các nguồn tài nguyên hữu hạn của doanh nghiệp đểtối
đa hóa năng suất của doanh nghiệp.
Với sự đa dạng của bài toán lập lịch chẳng hạn như: lập lịch quản lý một dự
án, lập lịch xếp lớp cho giáo viên, lập lịch sản xuất và lập lịch trong các loại ngành
nghềkhác nhau. Trong chương này nghiên cứu vềbài toán lập lịch sản xuất. Do có
một tính chất chung trong bài toán lập lịch sản xuất thường được mô tảdựa trên ba
tính đặc tính như: công việc, môi trường máy và tiêu chuẩn tối ưu. Sựphân loại này
đang dùng rộng rãi được giới thiệu qua nhiều tài liệu nghiên cứu [19]
1.1.1. Bài toán lập lịch Job shop:
Trong cuối những năm 1950, B.Gi er và GLThompson trong bài báo có tiêu
đề "Các thuật toán để giải quyết các vấn đề kế hoạch sản xuất" [6] cho rằng nó
không phải là cần thiết đểtìm kiếm cho một lịch trình tối ưu trên tất cảcác lịch trình
có thể, nhưng chỉhơn một tập hợp tiến độkhảthi, được gọi là lịch trình hoạt động
sản xuất.
Vấn đềlập lịch sản xuất jobshop cổ điển có thể được xây dựng nhưsau:
Một M tập hợp các máy m có M1,