Bài giảng Quản trị sản xuất - Lập lịch trình sản xuất

CHƯƠNG 6 : LẬP LỊCH TRÌNH SẢN XUẤT I. SẮP XẾP THỨ TỰ CÁC CÔNG VIỆC 1. Sắp xếp các công việc trên 1 máy (1 bộ phận, 1 cá nhân). Các công việc được thực hiện tuần tự qua 1 máy (1 bộ phận, 1 cá nhân) cho nên với n công việc ta có n ! cách sắp xếp thứ tự . Trong thực tế người ta thường áp dụng các ưu tiên sau đây để sắp xếp thứ tự các công việc. * Nguyên tắc FCFS (first come first served). Công việc nào đến trước thì làm trước. * Nguyên tắc EDD (Earliest due date). Công việc nào đến hạn trước thì làm trước. * Nguyên tắc SPT (Shortest processing time). Công việc có thời gian thực hiện ngắn thì làm trước. * Nguyên tắc LPT (longest processing time) Công việc nào có thời gian thực hiện dài thì làm trước Ví dụ : FCFS. T T Thời gian gia công (ngày) Thời hạn hoàn thành (ngày thứ .....) Thời điểm hoàn thành (ngày thứ..) Thời gian trễ hạn (ngày) A 8 12 8 - B 5 8 13 5 C 9 28 22 D 7 15 29 14 E 6 14 35 21  35 40 Thời gian trễ hạn trung bình một công việc = 40/5 = 8 ngày EDD T T Thời gian gia công (ngày) Thời hạn hoàn thành (ngày thứ .....) Thời điểm hoàn thành (ngày thứ......) Thời gian trễ hạn (ngày) B 5 8 5 - A 8 12 13 1 E 6 14 19 5 D 7 15 26 11 C 9 28 35 7  35 24 Thời gian trễ hạn trung bình một công việc = 24/5 = 4,8 ngày SPT T T Thời gian gia công (ngày) Thời hạn hoàn thành (ngày thứ .....) Thời điểm hoàn thành (ngày thứ....) Thời gian trễ hạn (ngày) B 5 8 5 - E 6 14 11 - D 7 15 18 3 A 8 12 26 14 C 9 28 35 7  35 24 Thời gian trễ hạn trung bình một công việc là 24/5 = 4,8 ngày LPT T T Thời gian gia công (ngày) Thời hạn hoàn thành (ngày thứ .....) Thời điểm hoàn thành (ngày thứ ...) Thời gian trễ hạn (ngày) C 9 28 9 - A 8 12 17 5 D 7 15 24 9 E 6 14 30 16 B 5 28 35 27  35 57 Thời gian trễ hạn trung bình một công việc là 57/5 = 11,4 NGÀY 2.. Sắp xếp các công việc trên 2 máy Bài toán: Công việc được thực hiện tuần tự từ Máy1 -> Máy 2 (do quy trình sản xuất yêu cầu). Hãy sắp xếp thứ tự các công việc sao cho tổng thời gian hoàn thành các công việc nhỏ nhất. + Nguyên tắc Johnson “Công việc nào có thời gian nhỏ thuộc máy 1 thì xếp trước , thuộc máy 2 thì xếp cuối ” CV Thời gian thực hiện (giờ) Thứ tự sắp xếp M1 M2 1 2 3 4 5 A 10 12 A B 14 13 C 16 15 D 17 16 E 19 30 CV Thời gian thực hiện (giờ) Thứ tự sắp xếp M1 M2 1 2 3 4 5 A 10 12 A B B 14 13 C 16 15 D 17 16 E 19 30 CV Thời gian thực hiện (giờ) Thứ tự sắp xếp M1 M2 1 2 3 4 5 A 10 12 A C B B 14 13 C 16 15 D 17 16 E 19 30 CV Thời gian thực hiện (giờ) Thứ tự sắp xếp M1 M2 1 2 3 4 5 A 10 12 A D C B B 14 13 C 16 15 D 17 16 E 19 30 CV Thời gian thực hiện (giờ) Thứ tự sắp xếp M1 M2 1 2 3 4 5 A 10 12 A E D C B B 14 13 C 16 15 D 17 16 E 19 20 M1 A= 10 E=19 D=17 C=16 B=14 M2 A =12 E = 20 D = 16 C = 15 B = 13 10 22 29 49 65 80 93 10 29 46 62 76 3. Sắp xếp thứ tự công việc trên 3 máy Có n công việc với mỗi công việc được thực hiện tuần tự Máy 1 -> Máy 2 – Máy 3 Yêu cầu: Sắp xếp công việc theo tuần tự sao cho tổng thời gian hình thành công việc là nhỏ nhất. Từ ba máy ta thực hiện việc chuyển đổi về hai máy rồi áp dụng nguyên tắc Johnson CV Thời gian thực hiện CV M1 + M2 M2 + M3 M1 M2 M3 A 12 10 14 A 22 24 B 13 8 16 B 21 24 C 14 12 15 C 26 27 D 16 10 18 D 26 28 E 19 9 14 E 28 23 Thứ tự sắp xếp 1 2 3 4 5 PA1 B A D C E PA2 B A C D E 13 25 39 55 74 B = 13 A = 12 C = 14 D = 16 E = 19 B = 8 A = 10 C = 12 D = 10 E = 9 B = 16 A = 14 C = 15 D = 18 E = 14 21 37 51 66 84 98 Ghi chú: Phương pháp trên chỉ thực hiện tốt khi thời gian nhỏ nhất trên máy 1 lớn hơn hay bằng thời gian lớn nhất trên máy2, thời gian nhỏ nhất trên M3  thời gian lớn nhất trên M2. tmin1  tmax2 tmin3  tmax2 Vùng Nhà .máy 1 2 3 Công suất A 20 21 22 120 B 22 25 27 80 C 24 28 30 100 Nhu cầu 90 70 140 90 70 140 bj ai 20 21 22 120 22 25 27 80 24 28 30 100 Ui Vj Vùng Nhà .máy 1 2 3 Công suất A 20 21 22 100 B 22 25 27 100 C 24 28 30 100 Nhu cầu 100 100 100 100 100 100 bj ai 20 21 22 100 22 25 27 100 24 28 30 100 Ui Vj Cviệc C.nhân 1 2 3 Công suất A 20 21 22 1 B 22 25 27 1 C 24 28 30 1 Nhu cầu 1 1 1 II.PHÂN CÔNG CÔNG VIỆC Các bước giải bài toán chọn( bài toán min) : Bước 1: Lập ma trận vuông n x n với các phân tử Cij. Bước 2: Trên các hàng của ma trận xác định phân tử nhỏ nhất rồi lấy các phân tử trên hàng trừ đi phân tử này. Bước 3: Tương tự bước 2 thực hiện trên cột. Bước 4: Trên các hàng của ma trận chọn hàng có 1 số 0, đánh dấu số 0 đó rồi gạch bỏ cột rồi tiếp tục thực hiện. = n x i j = 0 x i j = 1  i j Bước 5: Trên các cột chọn cột có 1 số 0. Đánh dấu số 0 này rồi gạch hàng. Bước 6: Kiểm tra xem số 0 được đánh dấu có bằng n chưa ? Nếu bằng bài toán đã giải xong. Nếu chưa bằng thực hiện bước thứ 7. Bước 7: Trên các phân tử chưa bị gạch, xác định phân tử nhỏ nhất. - Đối với các phân tử bị gạch 2 đường thì cộng với phân tử này. - Chưa bị gạch thì trừ đi phân tử này. - Bị gạch 1 đường thì giữ nguyên. Sau đó trở lại bước 4. Ghi chú: 1. Khi thực hiện B5 nếu thấy xuất hiện các số 0 tạo vòng thì chọn 1 số 0 bất kỳ trên vòng rồi gạch cả cột lẫn hàng sau đó trở lại B4. III. ỨNG DỤNG SƠ ĐỒ PERT ( Program Evaluation and Review Technique ) 1/ Phương pháp lập sơ đồ PERT Một sơ đồ PERT bao gồm các sự kiện và các công việc . - Các sự kiện được biểu diễn bằng vòng tròn ( còn gọi là điểm nút ) - Các công việc được biểu diễn bằng các cung có mũi tên định hướng. A(dij) i j Một số chú ý khi xây dựng sơ đồ PERT + Một dự án chỉ có một sự kiện bắt đầu và một sự kiện kết thúc. + Hai công việc được tiến hành đồng thời A B B C A 1(3) A 2(3) D +Hai công việc hội tụ +Đưa thêm công việc giả ( có thời gian bằng 0 ) +Đưa thêm công việc giả ( có thời gian khác 0 ) X (2) 2/ Phương pháp xác định đường găng Đường găng là đường có thời gian dài nhất nối giữa sự kiện bắt đầu và sự kiện kết thúc dự án . Tổng thời gian của dự án chính là độ dài của đường găng , tức là đường nối các công việc găng . Để xác định đường găng , với mỗi sự kiện , ta cần xác định thời gian sớm nhất và muộn nhất. Thời gian sớm nhất của sự kiện i ( ký hiệu là ti ) là thời gian sớm nhất kể từ khi bắt đầu dự án cho đến khi đạt tới sự kiện i ti = Max ( tj + dji ) với j là đỉnh bất kỳ trước i và dji là độ dài cung j, i Thời gian muộn nhất của sự kiện i ( ký hiệu là t’i ) là thời gian chậm nhất phải đạt tới sự kiện i nếu như không muốn kéo dài thời gian của dự án . t’i = min ( t’j – dij ) với j là đỉnh bất kỳ ngay sau i Đường găng là đường bao gồm các đỉnh có ti = t’i Một dự án gồm 9 công việc có mối liên hệ và thời gian như sau : Công việc Công việc trước Thời gian ( tháng ) A B C D E F G H I Không A Không Không B, C B,C A D, E, G F, H 4 6 4 12 10 24 7 10 3 13 2 4 65 Ta có thể xây dựng sơ đồ PERT như sau : Đường găng bao gồm các công việc A, B, F, I . Thời gian thực hiện dự án là 37 tháng Noäi dung coâng vieäc Thôøi gian CV 1/ Xin giaáy pheùp khai thaùc 32 A 2/ Laøm ñöôøng 24 B 3/ Laép 2 maùy doø 1 C 4/ Döïng laùn traïi taïm 3 D 5/ Raûi nhöïa ñöôøng vaøo moû 8 E 6/ Daãn nöôùc vaøo moû 28 F 7/ Thaêm doø 16 G 8/ Taïo gieáng khoan 20 H 9/ Laép thieát bò khai thaùc 6 I 10/ Xaây nhaø cho coâng nhaân 20 J 11/ Ñöôøng xaù vaø boá trí döôùi moû 44 K 12/ Xaây döïng khu vöïc röûa quaëng 28 L Bài tập : Đưa vào khai thác một mỏ than mới cần thiết phải thực hiện các công việc sau : Mối liên hệ giữa các công việc như sau : + Công việc A thực hiện trước B , B trước C,D,E,F. + Công việc C và D trước G. + Công việc E,F,G trước H và J. + Công việc H,J trước I,K và L. Yêu cầu : - Xác định các tiến trình thực hiện dự án. - Xác định thời gian hoàn thành dự án Một dự án gồm 7 công việc có mối liên hệ và thời gian như sau : Công việc Công việc trước Thời gian ( tháng ) Tổng chi phí (tr.đồng) Chi phí cho mỗi tháng A B C D E F G Không Không A B B C,D E 2 3 1 3 2 2 1 10 30 3 6 20 10 8 5 10 3 2 10 5 8 Công việc Bắt đầu sớm (ES) Bắt đầu muộn (LS) Kết thúc sớm (EF) Kết thúc muộn (LF) Thời gian di động (tháng) A 0 3 2 5 3 B 0 0 3 3 0 C 2 5 3 6 3 D 3 3 6 6 0 E 3 5 5 7 2 F 6 6 8 8 0 G 5 7 6 8 2 Thời điểm sớm nhất để công việc bắt đầu (Earliest start_ES) – Thời điểm sớm nhất để một công việc có thể bắt đầu khi mọi công việc trước đó đã hoàn thành nhanh nhất có thể. Thời điểm trễ nhất để công việc bắt đầu (Latest start_LS) – Thời điểm trễ nhất để một công việc bắt đầu mà không kéo dài thời gian hạn định của dự án. Thời điểm kết thúc công việc sớm nhất (Earliest finish_EF) – Thời điểm sớm nhất để công việc bắt đầu (ES) cộng với thời gian thực hiện công việc (D). Thời điểm kết thúc công việc trễ nhất (Latest finish_LF) – Thời điểm trễ nhất để công việc bắt đầu (LS) cộng với thời gian thực hiện công việc (D). Thời gian dự trù của công việc (Total Float_TF) – Thời gian dư hay thời gian trừ hao cho phép khi hoạch định công việc để tránh đụng chạm với bất kỳ công việc nào trên đường tới hạn; thời kỳ trì trệ giữa thời điểm sớm nhất và trễ nhất (LS - ES = TF). Ngân sách theo thời hạn sớm nhất Công việc Tháng 1 2 3 4 5 6 7 8 A 5 5 x x x B 10 10 10 x x x x x C 3 x x D 2 2 2 E 10 10 x F 5 5 G 8 Chi phí mỗi tháng 15 15 13 12 12 10 5 5 Tổng chi phí dự án 15 30 43 55 67 77 82 87 Ngân sách theo thời hạn muộn nhất Công việc Tháng 1 2 3 4 5 6 7 8 A 5 5 B 10 10 10 C 3 D 2 2 2 E 10 10 F 5 5 G 8 Chi phí mỗitháng 10 10 10 7 7 15 15 13 Tổng chi phí dự án 10 20 30 37 44 59 74 87 Danh sách công việc Côngviệc trước Thời gian Thiết kế Đặt hàng các bộ phận Phác thảo Giao các bộ phận Chuẩn bị các hướng dẫn Tạo các bộ phận Lắp ráp Kiểm tra Vận chuyển A B C D E F G H I KHÔNG A A B C C D, F G E, H 3 5 4 6 3 9 11 4 8 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 0 4 8 12 16 20 24 28 32 Thời gian Sơ đồ GANTT ST T Danh saùch coâng vieäc Coâng vieäc tröôùc Thôøi gian 1 2 3 4 5 6 7 8 9 Thieát keá Ñaët haøng caùc boä phaän Phaùc thaûo Giao caùc boä phaän Chuaån bò caùc höôùng daãn Taïo caùc boä phaän Laép raùp Kieåm tra Vaän chuyeån A B C D E F G H I None A A B C C D, F G E, H 3 5 4 6 3 9 11 4 8 STT Danh saùch coâng vieäc Thôøi gian bình thöôøng Chi phí bình thöôøng Thôøi gian ruùt ngaén Chi phí ruùt ngaén 1 2 3 4 5 6 7 8 9 Thieát keá Ñaët haøng caùc boä phaän Phaùc thaûo Giao caùc boä phaän Chuaån bò höôùng daãn Taïo caùc boä phaän Laép raùp Kieåm tra Vaän chuyeån A B C D E F G H I 3 5 4 6 3 9 11 4 8 100 400 200 100 350 520 180 200 260 2 4 2 5 3 7 9 3 7 150 500 600 200 620 300 400 360 Coäng ? 2310 ? 3130 Tính Toán Sơ Đồ Pert 1.Ước định thời gian thực hiện công việc được cho trong khoảng. Thời gian gần đúng nhất (m) là thời gian hoàn thành một công việc nếu nó được lặp lại với điều kiện giống nhau. Thời gian lạc quan (a) và bi quan (b) là thời gian thực hiện công việc trong điều kiện tốt nhất và xấu nhất, đây là hai giới hạn biên của thời gian thực hiện công việc. Thời gian kỳ vọng (te ) được tính toán theo trung bình có trọng số của ba ước định thời gian theo công thức sau 6 4 bma te   Quan hệ của a, b và m với te Thời gian ước lượng của các họat động của dự án Caùc hoïat ñoäng Coâng vieäc tröôùc m a b Thieát keá Ñaët haøng chi tieát Sô cheá Chuyeån chi tieát Chuaån bò Laøm caùc chi tieát Laép raùp Kieåm tra Vaän chuyeån A B C D E F G H I – A A B C C D, F G E, H 3 5 4 6 3 9 11 4 8 3 4 3 5 2 6 9 3 6 4 7 6 8 4 10 14 6 9 Ứng Dụng PERT/ CPM trong Hoạch Định Sản Xuất Môi trường sản xuất cần đến hoạch định bằng sơ đồ mạng có những đặc tính sau: 1.Các sản phẩm phức tạp và cơ bản là cùng một loại; nhưng nhiều sản phẩm được sản xuất cùng một lúc trong một phương tiện. 2.Thời điểm bắt đầu và hạn giao hàng khó xác định trước (ví dụ khách hàng thương lượng kỳ hạn theo nhu cầu của họ và họ có xu hướng muốn giao ngày hôm qua). 3.Công việc thiết kế và sản xuất thực hiện theo nhóm cho mỗi sản phẩm hay dự án. 4.Nguyên vật liệu cho mỗi sản phẩm được đặt hàng riêng biệt bởi vì không đoán trước được yêu cầu khách hàng cho những khoản mục cụ thể. 5.Phương thức và công cụ chế tạo thay đổi từ sản phẩm này đến sản phẩm kế tiếp, đôi khi cần những hiệu chỉnh hay những cải tiến đáng kể. 6.Chi phí cho thay đổi nhân lực, huấn luyện/giảng dạy, và khởi động lại có xu hướng cao do sản phẩm không lặp lại. Câu 1: Một dự án di chuyển nơi làm việc gồm 8 công việc được thiết kế như sau: Coâ ng vieä c Söï kieän baét ñaàu Thôøi gian thöïc hieän (ngaøy) Chi phí cho 1 ngaøy taêng theâm khi laøm nhanhBình thöôøng Khi laøm nhanh A Baét ñaàu ngay 14 10 200 B Baét ñaàu ngay 12 9 120 C Sau A, B 4 3 310 D Sau A, B 18 14 240 E Sau C 3 3 F Sau C 2 2 G Sau D 1 1 H Sau E, F, G 2 1 400 a.Dùng sơ đồ PERT, GANTT biểu diễn tiến trình thực hiện dự án. Tính thời gian hoàn thành dự án. b.Tìm phương án tối ưu để giảm thời gian thực hiện dự án còn 30 ngày, còn 26 ngày. Câu 2: Một dự án gồm 8 công việc: Coâ ng vieä c Söï kieän baét ñaàu Thôøi gian thöïc hieän (ngaøy) Chi phí thöïc hieän (USD) Bình thöôøng Khi laøm nhanh Bình thöôøng Khi laøm nhanh A Laøm ngay 30 25 1500 2100 B Sau A 50 40 900 2100 C Sau A 40 25 2400 3000 D Sau A 50 40 1700 2700 E Sau B 30 10 1200 4400 F Sau C 35 15 3100 5200 G Sau D 60 40 4300 5700 H Sau E, F 45 20 800 3300 Tìm phương án để giảm thời gian hoàn thành dự án còn 130 ngày; 120 ngày; 110 ngày. Câu 1: Có 5 công việc được gia công tuần tự trên 3 máy với thời gian: Coâng vieäc Thôøi gian gia coâng (giôø/maùy) Maùy 1 Maùy 2 Maùy 3 A 8 8 10 B 14 6 18 C 12 7 14 D 9 7 9 E 15 8 17 Hãy tìm các phương án, sắp xếp thứ tự tối ưu các công việc. Tính tổng thời gian hoàn thành tất cả các công việc. Câu 2: Một HTX vận chuyển có 5 hợp đồng. Tiền lời các xe khi thực hiện các hợp đồng như sau: Xe HÑ1 HÑ2 HÑ3 HÑ4 HÑ5 A 7 6 8 9 8 B 10 8 9 6 7 C 8 10 9 8 10 D 9 9 10 8 9 E 8 7 6 7 6 a.Haõy phaân coâng nhieäm vuï cho caùc xe. b.Haõy phaân coâng nhieäm vuï vôùi ñieàu kieän tieàn lôøi cho caùc xe phaûi >700.000ñ c.Giaû söû coù theâm HÑ thöù 6 vôùi möùc tieàn lôøi töông öùng laø 10, 9, 8, 11, 10 (ñvt 100.000ñ) thì coâng ty neân töø choái HÑ naøo neáu coù theå. Câu 3: a/Hãy phân công các công nhân thực hiện các công việc sao cho tổng thời gian thực hiện các công việc nhỏ nhất. b/ Hãy phân công các công nhân thực hiện các công việc với điều kiện thời gian từng công nhân thực hiện công việc nhỏ hơn 65 giờ. Coâng vieäc coâng nhaân Thôøi gian thöïc hieän (giôø) I II III IV V A 35 50 55 70 40 B 40 55 65 80 70 C 30 50 90 70 45 D 60 45 50 70 90 E 50 30 65 45 80 Câu 4: Có 5 nhân viên có thể bán hàng tại 5 cửa hàng với doanh thu bán hàng của mỗi nhân viên tại mỗi cửa hàng như sau: (Đvt : triệu đồng/tháng) I II III IV V Huøng 30 20 10 30 40 Thaûo 70 40 60 50 70 Laân 40 50 20 30 40 Caûnh 60 70 30 40 90 Hoøa 50 60 40 60 50 a.Haõy phaân coâng nhieäm vuï cho caùc nhaân vieân baùn haøng. b.Haõy phaân coâng nhieäm vuï cho caùc nhaân vieân baùn haøng sao cho moãi nhaân vieân ñaït doanh thu töø 40 trieäu ñoàng/thaùng trôû leân .