Bài giảng Chương 4: Lập lịch trình sản xuất

CHƢƠNG 4. LAÄP LÒCH TRÌNH SAÛN XUAÁT • NOÄI DUNG CHÍNH • I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT • II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT I. CÔNG TÁC LẬP LỊCH TRÌNH SẢN XUẤT Nhiệm vụ và mục tiêu của công tác lập lịch trình sx Nhiệm vụ Phân phối đơn hàng, MMTB, nhân lực cho các xưởng sản xuất, nghĩa là hoạch định công suất sản xuất trong ngắn hạn. Thiết lập thứ tự ưu tiên cho các công việc. Tổ chức thực hiện công việc theo lịch trình. Kiểm soát tình hình và tiến độ thực hiện Thực hiện nhanh các đơn hàng bị trễ hạn. I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Nhiệm vụ và mục tiêu của công tác lập lịch trình sx Mục tiêu Thiết lập thời hạn thực hiện công việc. Tối thiểu hoá TG thực hiện đơn hàng. Tối thiểu hoá khối lượng sản xuất sản phẩm dở dang. Nâng cao hệ số sử dụng các nguồn lực I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Lập lịch trình sản xuất Thông tin đầu vào: + Dự trữ đầu kỳ + Số liệu dự báo + Đơn đặt hàng của khách. Kết quả của quá trình lập lịch trình sản xuất: + Dự trữ kế hoạch + Khối lượng và thời điểm sản xuất + Dự trữ sẵn sàng bán. I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Lập lịch trình sản xuất  Dự trữ kế hoạch = Dđk - max(Đh, Db) Trong đó: Dđk - dự trữ đầu kỳ Đh - khối lượng theo đơn đặt hàng Db - khối lượng theo dự báo  Khối lượng và thời điểm sản xuất xác định dựa vào lượng dự trữ kế hoạch. Khi lượng dự trữ kế hoạch không đáp ứng được nhu cầu dự báo hoặc theo đơn đặt hàng thì đưa vào sản xuất để có lượng dự trữ thay thế thoả mãn nhu cầu trong bất kỳ tuần nào. I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Lập lịch trình sản xuất  Lượng dự trữ sẵn sàng bán chỉ tính cho tuần đầu tiên khi lập lịch trình và tại các tuần đưa vào sản xuất (theo nguyên tắc “nhìn về phía trước”). Đối với tuần đầu tiên, lượng dự trữ sẵn sàng bán được tính bằng hiệu số giữa dự trữ đầu kỳ và tổng khối lượng theo các đơn đặt hàng từ tuần đó đến tuần bắt đầu sản xuất. Đối với các tuần đưa vào sản xuất, lượng dự trữ sẵn sàng bán được tính bằng hiệu số giữa số lượng đưa vào sản xuất trong tuần và tổng khối lượng theo các đơn đặt hàng từ tuần đó đến tuần sản xuất tiếp theo. I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Lập lịch trình sản xuất Ví dụ: Một doanh nghiệp sản xuất sản phẩm A có khối lượng dự báo nhu cầu tháng 1 là 120 sản phẩm, tháng 2 là 160 sản phẩm. Số lượng sản phẩm dự báo này được phân đều cho các tuần trong tháng. Doanh nghiệp nhận được các đơn đặt hàng ở các tuần như sau: tuần 1: 33 sản phẩm, tuần 2: 20 sản phẩm, tuần 3: 10 sản phẩm, tuần 4: 4 sản phẩm, tuần 5: 2 sản phẩm. Doanh nghiệp có dự trữ đầu kỳ là 64 sản phẩm, mỗi loạt sản xuất của doanh nghiệp là 70. Hãy lập lịch trình sản xuất trong 2 tháng. I. COÂNG TAÙC LAÄP LÒCH TRÌNH SAÛN XUAÁT Lập lịch trình sản xuất  Dự trữ kế hoạch tuần 1=64 - max(33, 30)=31  Dự trữ kế hoạch tuần 2=31 - max(30, 20)=1  Dự trữ kế hoạch tuần 3=1 +70 - max(30, 10)=41  Dự trữ kế hoạch tuần 4=41 - max(30, 4)=11  Dự trữ kế hoạch tuần 5=11 +70 - max(40, 2)=41  Dự trữ kế hoạch tuần 6=41 - max(40, 0)=1  Dự trữ kế hoạch tuần 7=1 +70 - max(40, 0)=31  Dự trữ kế hoạch tuần 8=31 +70 - max(40, 0)=61  Dự trữ sẵn sàng bán tuần 1 =64 - (33+20)=11  Dự trữ sẵn sàng bán tuần 3 =70 - (10+4)=56... I. COÂNG TAÙC LAÄP LÒCH TRÌNH SX Lập lịch trình sản xuất Thời gian  Tháng 1 Tháng 2 Chỉ tiêu  Tuần 1 Tuần 2 Tuần 3 Tuần 4 Tuần 5 Tuần 6 Tuần 7 Tuần 8 Dự trữ đầu kỳ Dự báo Đơn hàng Dự trữ kế hoạch Khối lượng và thời điểm sản xuất - - - - Dự trữ sẵn sàng bán - - - 64 30 30 30 30 40 40 40 40 33 20 10 4 2 31 1 41 11 41 1 31 61 70 70 70 70 11 56 68 70 70 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) 1. FCFS (First come first served) – Nguyên tắc công việc được đặt hàng trước làm trước. 2. SPT (Shortest Processing time) – Nguyên tắc công việc có TG thực hiện ngắn nhất làm trước. 3. EDD (Earliest due date) – Nguyên tắc công việc phải hoàn thành trước làm trước. 4. LPT (Longest Processing time) – Nguyên tắc công việc có TG thực hiện dài nhất làm trước. II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) 5. LCFS (Last come first served) – Nguyên tắc công việc đặt hàng sau đƣợc làm trƣớc. 6. STR (Slack Time Remaining) – Nguyên tắc công việc có dự trữ thời gian còn lại ngắn nhất làm trƣớc. Thời gian dự trữ còn lại đƣợc tính bằng hiệu số giữa thời gian còn lại đến ngày giao hàng và thời gian sản xuất còn lại. 7. CR (Critical Ratio) – Tỷ số tới hạn, đƣợc tính bằng thời gian còn lại tính đến thời điểm giao hàng chia cho thời gian sản xuất còn lại. II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) Thời hạn hoàn thành (ngày) A 3 5 B 4 6 C 2 7 D 6 9 E 1 2 Ví dụ: Có 5 công việc A, B, C, D, E. Thời gian sx và thời điểm giao hàng cho như bảng: II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) TH phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) A 3 5 3 0 B 4 6 7 1 C 2 7 9 2 D 6 9 15 6 E 1 2 16 14 (+) 16 50 23 1. Nguyên tắc công việc được đặt hàng trước làm trước (First come first served – FCFS) II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 23 = = 4,6 ngày 5 Tổng dòng thời gian = Số công việc • 50 = = 10 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 50 = = 3,13 công việc 16 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) TH phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) E 1 2 1 0 C 2 7 3 0 A 3 5 6 1 B 4 6 10 4 D 6 9 16 7 (+) 16 36 12 2. Nguyên tắc SPT II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 12 = = 2,4 ngày 5 Tổng dòng thời gian = Số công việc • 36 = = 7,2 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 36 = = 2,25 công việc 16 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) Thời hạn phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) E 1 2 1 0 A 3 5 4 0 B 4 6 8 2 C 2 7 10 3 D 6 9 16 7 (+) 16 39 12 3. Nguyên tắc EDD II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 12 = = 2,4 ngày 5 Tổng dòng thời gian = Số công việc • 39 = = 7,8 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 39 = = 2,44 công việc 16 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) Thời hạn phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) D 6 9 6 0 B 4 6 10 4 A 3 5 13 8 C 2 7 15 8 E 1 2 16 14 (+) 16 60 34 4. Nguyên tắc LPT II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 34 = = 6,8 ngày 5 Tổng dòng thời gian = Số công việc • 60 = = 12 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 60 = = 3,75 công việc 16 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) Thời hạn phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) E 1 2 1 0 D 6 9 7 0 C 2 7 9 2 B 4 6 13 7 A 3 5 16 11 (+) 16 46 20 5. Nguyên tắc LCFS II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 20 = = 4 ngày 5 Tổng dòng thời gian = Số công việc • 46 = = 9,2 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 46 = = 2,88 công việc 16 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Công việc Thời gian sản xuất (ngày) Thời hạn phải hoàn thành (ngày thứ..) Dòng thời gian (ngày) Thời gian chậm trễ, (ngày) E 1 2 1 0 A 3 5 4 0 B 4 6 8 2 C 6 9 14 5 D 2 7 16 9 (+) 16 43 16 6. Nguyên tắc STR II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SX 2.1. Tổ chức sx n sp trên 1 trung tâm sx (n/1) Tính các chỉ tiêu hiệu quả: + Thời gian hoàn thành trung bình của mỗi công việc + Số công việc trung bình nằm trong hệ thống + Thời gian chậm trễ trung bình của mỗi công việc Tổng số ngày trễ hạn = Số công việc • 16 = = 3,2 ngày 5 Tổng dòng thời gian = Số công việc • 43 = = 8,6 ngày 5 Tổng dòng thời gian = Tổng thời gian gia công • 43 = = 2,69 công việc 16 So sánh kết quả giữa các nguyên tắc Nguyên tắc Thời gian hoàn thành TB, ngày Số CVTB nằm trong hệ thống Thời gian chậm trễ TB, ngày FCCS (First come first served) – Nguyên tắc công việc đƣợc đặt hàng trƣớc làm trƣớc 10 3.13 4.6 SPT (Shortest Processing time) – Nguyên tắc công việc có thời gian thực hiện ngắn nhất làm trƣớc 7.2 2.25 2.4 EDD (Earliest due date) – Nguyên tắc công việc phải hoàn thành trƣớc làm trƣớc 7.8 2.44 2.4 LPT (Longest Processing time) – Nguyên tắc công việc có thời gian thực hiện dài nhất làm trƣớc 12 3.75 6.8 LCFS (Last come first served) – Nguyên tắc công việc đặt hàng sau đƣợc làm trƣớc 9.2 2.88 4 STR (Slack Time Remaining) – Nguyên tắc công việc có dự trữ thời gian còn lại ngắn nhất làm trƣớc. 8.6 2.69 3.2 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT Đánh giá mức độ hợp lý của việc bố trí các công việc: Để đánh giá mức độ hợp lý của việc bố trí các công việc ta dùng tỷ số tới hạn (Critical Ratio - CR). Thời gian còn lại CR = Thời gian sản xuất còn lại II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT Công việc Thời điểm giao hàng Công việc còn lại tính theo ngày Tỷ số tới hạn, CR Thứ tự ưu tiên A 30/12 4 (30-25)/4=1,25 3 B 28/12 5 (28-25)/5=0,6 1 C 27/12 2 (27-25)/2=1,0 2 Ví dụ: Công ty NATFISHCO có 3 công việc được đặt hàng như bảng sau. Giả sử thời điểm chúng ta xét là ngày 25/12. II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT 2.2 Tổ chức sx n sản phẩm trên 2 trung tâm sx (n/2)  Bước 1: Liệt kê tất cả các sản phẩm và thời gian thực hiện chúng trên mỗi máy.  Bước 2: Tìm sản phẩm có thời gian sản xuất nhỏ nhất.  - Nếu sản phẩm này nằm trên máy I thì được sắp xếp trước.  - Nếu sản phẩm này nằm trên máy II thì được sắp xếp cuối cùng.  Bước 3: Khi một sản phẩm đã được sắp xếp rồi thì ta loại trừ nó đi, chỉ xét những sản phẩm còn lại.  Bước 4: Trở lại bước 2 và bước 3 cho đến khi tất cả các sản phẩm đều đã sắp xếp hết. II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT Sản phẩm Thời gian sản xuất, giờ Máy I Máy II A 3 2 B 6 8 C 5 6 D 7 4 Ví dụ: Có 4 sản phẩm cần thực hiện trên 2 máy I và II. Sản phẩm nào cũng phải được làm trên máy I trước rồi mới chuyển sang máy II. Thời gian gia công cho trong bảng sau: Thời gian, giờ 21 18 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT D 25 23 19 11 5 0 0 B C A C B A Máy I Máy II Thời gian, giờ D Lịch trình sản xuất tối ưu theo nguyên tắc Johnson, trường hợp n/2. 2.3. Tổ chức sản xuất n sản phẩm trên 3 trung tâm sản xuất (n/3) Trong một số trường hợp đặc biệt bài toán tổ chức sản xuất trên 3 trung tâm sản xuất có thể quy về tổ chức sản xuất trên 2 máy (sử dụng nguyên tắc Johnson) nếu có đủ 2 điều kiện sau đây: • Thời gian ngắn nhất trên máy I phải  thời gian dài nhất trên máy II. • Thời gian ngắn nhất trên máy III phải  thời gian dài nhất trên máy II. II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT Sản phẩm Thời gian sản xuất, giờ Máy I (t1) Máy II (t2) Máy III (t3) A 13 5 9 B 5 3 7 C 6 4 5 D 7 2 6 Ví dụ: Bài toán tổ chức sản xuất trên 3 máy có các số liệu cho ở bảng: II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT Sản phẩm Thời gian sản xuất, giờ Máy A (t1+ t2) Máy B (t2+ t3) A 13+5=18 5+9=14 B 5+3=8 3+7=10 C 6+4=10 4+5=9 D 7+2=9 2+6=8 II. SAÉP XEÁP THÖÙ TÖÏ TOÁI ÖU TRONG SAÛN XUAÁT 43 37 33 28 24 5 32 23 15 18 8 31 0 0 B A D Máy I Máy II Thời gian, giờ C B A C D B A Máy III Thời gian, giờ C D Bài toán phân công công việc - Sự cần thiết phải phân công công việc rõ ràng  Mỗi nhân viên có thể thực hiện bất kỳ công việc nào, mặc dù với mức độ thành thạo khác nhau.  Nếu nhƣ phân cho nhân viên một công việc nào đó đúng chuyên môn, thì chi phí thực hiện công việc sẽ thấp hơn so với không đúng chuyên môn. - Mục tiêu: Tìm sự phân công công việc tối ƣu c11 c12 c1n c21 c22 c2n cn1 cn2 cnn 1 2 n Công việc 1 2 n Nhân viên Bài toán phân công công việc Thành lập bài toán 2 3 4 3 2 1 5 1 6 1 2 3 Công việc 1 2 3 Nhân viên Bài toán phân công công việc Thành lập bài toán Phương pháp Hungary Bƣớc 1. Mục đích của bƣớc này là làm xuất hiện các phần tử có giá trị 0 càng nhiều càng tốt trong ma trận Để làm đƣợc điều này, ta lấy tất cả các phần tử của từng hàng trừ cho phần tử nhỏ nhất tƣơng ứng trong hàng đó. Sau đó, ta lấy tất cả các phần tử của từng cột trừ cho phần tử nhỏ nhất tƣơng ứng trong cột đó Phương pháp Hungary Bƣớc 2. Nếu nhƣ sau khi thực hiện bƣớc 1, trong mỗi dòng và mỗi cột của ma trận có thể chọn 1 phần tử 0, thì bài toán đã đƣợc giải xong. Phương pháp Hungary Bƣớc 3. Nếu nhƣ đáp số bao gồm các phần tử bằng 0 chƣa đƣợc tìm thấy, thì ta kẻ số đƣờng thẳng tối thiểu đi qua các hàng và cột sao cho tất cả các phần tử 0 đều bị gạch. Chọn phần tử bé nhất chƣa bị gạch. Lấy mỗi số chƣa bị gạch trừ cho số này; Lấy mỗi số bị gạch bởi 2 đƣờng thẳng cộng cho số này; Chép lại các số bị gạch bởi một đƣờng thẳng. Nếu vẫn chƣa tìm đƣợc nghiệm tối ƣu, thì lặp lại bƣớc 2. $1 $4 $6 $3 $9 $7 $10 $9 $4 $5 $11 $7 $8 $7 $8 $5 1 2 3 4 Công việc 1 2 3 4 Nhân viên Bài toán phân công công việc Phương pháp Hungary $1 $4 $6 $3 $9 $7 $10 $9 $4 $5 $11 $7 $8 $7 $8 $5 1 2 3 4 Công việc 1 2 3 4 Nhân viên Tìm trong mỗi hàng phần tử bé nhất. Bài toán phân công công việc Phương pháp Hungary $0 $3 $5 $2 $2 $0 $3 $2 $0 $1 $7 $3 $3 $2 $3 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Lấy tất cả các phần tử của từng hàng trừ cho phần tử nhỏ nhất tƣơng ứng trong hàng đó. Bài toán phân công công việc Phương pháp Hungary $0 $3 $5 $2 $2 $0 $3 $2 $0 $1 $7 $3 $3 $2 $3 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Tìm trong mỗi cột phần tử bé nhất. Bài toán phân công công việc Phương pháp Hungary $0 $3 $2 $2 $2 $0 $0 $2 $0 $1 $4 $3 $3 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Lấy tất cả các phần tử của từng cột trừ cho phần tử nhỏ nhất tƣơng ứng trong cột đó (thực tế chỉ có cột thứ 3). Nghiệm vẫn chƣa tìm đƣợc Bài toán phân công công việc Phương pháp Hungary $0 $3 $2 $2 $2 $0 $0 $2 $0 $1 $4 $3 $3 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Gạch bỏ tất cả phần tử zê-rô Bài toán phân công công việc Phương pháp Hungary $0 $3 $2 $2 $2 $0 $0 $2 $0 $1 $4 $3 $3 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Tìm phần tử nhỏ nhất chƣa bị gạnh. Bài toán phân công công việc Phương pháp Hungary $0 $2 $1 $1 $2 $0 $0 $2 $0 $0 $3 $2 $3 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Trừ các phần tử chƣa bị gạnh cho phần tử bé nhất. Bài toán phân công công việc Phương pháp Hungary $0 $2 $1 $1 $3 $0 $0 $2 $0 $0 $3 $2 $4 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Cộng thêm phần tử bé nhất ($1) cho các phần tử bị gạch 2 lần. Bài toán phân công công việc Phương pháp Hungary $0 $2 $1 $1 $3 $0 $0 $2 $0 $0 $3 $2 $4 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Kết quả nhận đƣợc: Đầu tiên phân việc cho các phƣơng án duy nhất. Bài toán phân công công việc Phương pháp Hungary $0 $2 $1 $1 $3 $0 $0 $2 $0 $0 $3 $2 $4 $2 $0 $0 1 2 3 4 Công việc 1 2 3 4 Nhân viên Kết quả nhận đƣợc. Bài toán phân công công việc Phương pháp Hungary $13 $10 $12 $11 $15 $50 $13 $20 $5 $7 $10 $6 1 2 3 4 Công việc 1 2 3 Nhân viên Bài toán phân công công việc Phương pháp Hungary VD 2: Bài toán phân công công việc • Mô hình tổng quát • Mô hình bài toán • Phương pháp giải bài toán phân công (phương pháp Hungary). Mô hình tổng quát Xét trường hợp, khi cần phân bổ m công việc cho n máy. Công việc i (i=1, , m) được thực hiện trên máy j (j=1, , n) với chi phí là cij. Vấn đề đặt ra là hãy phân bổ sao cho mỗi công việc được thực hiện trên mỗi máy với tổng chi phí là bé nhất. Mô hình bài toán • Đây là một trường hợp đặc biệt của bài toán vận tải. Ở đây công việc là điểm nguồn, còn máy móc – điểm đích. Cung trong mỗi điểm nguồn bằng 1, nghĩa là ai=1 với mọi i. Tương tự, cầu trong mỗi điểm đích bằng 1, nghĩa là bj=1 với mọi j. Chi phí của công việc i trên máy j là cij. Nếu như có một công việc nào đó không thể thực hiện được trên một máy nào đó, thì cij tương ứng sẽ lấy bằng một số rất lớn. • Trước khi giải bài toán này ta phải đưa thêm công việc giả hoặc máy giả (phụ thuộc vào điều kiện ban đầu của bài toán) để đảm bảo cân bằng cho bài toán. Cho nên ta có thể đặt m=n mà không làm mất đi tính tổng quát của bài toán. Mô hình bài toán • xij = 0 - nếu công việc i không thực hiện được trên máy j, • xij = 1 - nếu công việc i thực hiện được trên máy j. • Như vậy, nghiệm của bài toán có thể ghi dưới dạng ma trận X=(xij). Với n giá trị bài toán có n! nghiệm. • Bài toán phân công có thể viết như sau: • Với các ràng buộc: , i=1, , n; , j=1, , n;. min 1 1    n i n j ijij xcZ    n j ijx 1 1   n i ijx 1 1 Mô hình bài toán Ví dụ 1: Một công ty mua 3 máy mới A, B, C và có 4 vị trí có thể đặt máy. Chi phí đặt mỗi máy vào mỗi vị trí được cho ở bảng sau, trong đó máy B không thể đặt ở vị trí thứ 2. Vị_trí Máy 1 2 3 4 A 13 10 12 11 B 15 - 13 20 C 5 7 10 6 Yêu cầu: Đặt các máy A, B, C vào các vị trí nào để tổng chi phí là nhỏ nhất. Mô hình bài toán Để đảm bảo tính cân bằng cho bài toán, ta thêm 1 máy giả D với chi phí lắp đặt tại mọi vị trí