Bài giảng Quản trị sản xuất chương 7

Chia sẻ: Banh Long | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

306
lượt xem 145
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lập lịch trình sản xuất là toàn bộ các hoạt động xây dựng lịch trình sản xuất, điều phối, phân giao các công việc cho từng người, từng nhóm, từng máy và sắp xếp thứ tự các công việc ở từng nơi làm việc nhằm đảm bảo hoàn thành đúng tiến độ đã xác định trong lịch trình sản xuất trên cơ sở sử dụng có hiệu quả khả năng sản xuất hiện có của doanh nghiệp

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Quản trị sản xuất chương 7

I. KHÁI QUÁT VỀ CÔNG TÁC LẬP LỊCH TRÌNH SẢN XUẤT Chươ Ch ương ng 77 n Lập lịch trình sản xuất là toàn bộ các hoạt động xây LẬP LẬP LỊCH LỊCH TRÌNH TRÌNH SẢN SẢN XUẤT XUẤT dựng lịch trình sản xuất, điều phối, phân giao các công việc cho từng người, nhóm người, từng máy và sắp xếp thứ tự các công việc ở từng nơi làm việc Mọi thứ đều nhằm đảm bảo hoàn thành đúng tiến độ đã xác định ưu tiên số 1 trong lịch trình sản xuất trên cơ sở sử dụng có hiệu quả khả năng sản xuất hiện có của doanh nghiệp. n 2 bài toán cơ bản: Ø Bài toán sắp xếp thứ tự tối ưu trong sản xuất. Ø Bài toán phân công công việc. II. SẮP XẾP THỨ TỰ TỐI ƯU TRONG SẢN XUẤT 2.1. Trường hợp 1 máy - N công việc 2.1.1. Các nguyên tắc ưu tiên đối với những công 2.1. Trường hợp 1 máy - N công việc việc cần làm trước 2.1.1. Các nguyên t ắc ư u tiên đối với nhữ ng công việc cần làm trước Tổng thời gian hoàn thành của tất cả các công việc Có 4 nguyên tắc ưu tiên thường áp dụng gồm: Thời gian hoàn tất trung - Nguyên tắc 1: Đến trước - phục vụ trước bình một công việc (Ttb) Số công việc (First come first served – FCFS) - Nguyên tắc 2: Bố trí theo thời hạn hoàn thành sớm nhất Số công việc TB nằm ∑ (Số c/việc trong hệ thống trong thời gian sản (Earliest due date – EDD) trong hệ thống xuất t x thời gian sản xuất t) - Nguyên tắc 3: Bố trí theo thời gian gia công ngắn nhất (Ntb) (Shortest processing time – SPT) Tổng thời gian sản xuất - Nguyên tắc 4: Bố trí theo thời gian gia công dài nhất Thời gian trễ hẹn Tổng thời gian trễ hẹn (Longest processing time – LPT) trung bình (TRtb) Số công việc 2.1. Trường hợp 1 máy - N công việc 2.1.1.Các nguyên tắc ưu tiên đối với những công việc cần làm trước Theo nguyên tắc 1: FCFS Thời gian hoàn Thời hạn hoàn Thời gian sản Thời gian trễ Ví dụ : Vào đầu tháng 1 Thời hạn Công việc xuất (ngày) thành kể cả chờ thành (ngày hẹn (ngày) năm N, công ty cơ khí Thời gian hoàn đợi (ngày) thứ...) A 6 6 8 0 PX có nhận được 5 hợp Công sản xuất thành B 2 8 6 2 đồng với thứ tự đặt việc (ngày) (ngày C 8 16 18 0 hàng là A, B, C, D, E. thứ...) D 3 19 15 4 Thời gian sản xuất và A 6 8 E 9 28 23 5 thời hạn hoàn thành Tæng 28 77 11 của từng công việc cho B 2 6 trong bảng sau: C 8 18 t tb = 77 = 15,4 ngµy 5 D 3 15 6 × 5 + 2 × 4 + 8 × 3 + 3 × 2 + 9 ×1 77 N tb = = = 2,75 c«ngviÖc 28 28 E 9 23 11 TRtb = = 2,2 ngµy 5 1
Theo nguyªn t¾c 2: EDD Theo nguyên tắc 3: SPT Thời gian Thời gian hoàn Thời hạn Thời gian Thời gian hoàn Thời hạn Thời gian Công Thời gian sản Công việc sản xuất thành kể cả hoàn thành trễ hẹn thành kể cả chờ hoàn thành trễ hẹn việc xuất (ngày) (ngày) chờ đợi (ngày) (ngày thứ...) (ngày) đợi (ngày) (ngày thứ...) (ngày) B 2 2 6 0 B 2 2 6 0 A 6 8 8 0 D 3 5 15 0 D 3 11 15 0 A 6 11 8 3 C 8 19 18 1 28 5 C 8 19 18 1 E 9 23 Tæng 28 68 6 E 9 28 23 5 Tæng 28 65 9 68 t tb = = 13 , 6 ngµy 5 t = 65 = 13 ngµy tb 68 5 N tb = = 2 , 42 c«ng viÖc 28 65 N tb = = 2 , 3 c«ng viÖc 6 28 TR tb = = 1 , 2 ngµy 9 5 TR tb = = 1 , 8 ngµy 5 Theo nguyên tắc 4: LPT Thời gian hoàn Thời hạn Thời gian Công Thời gian sản thành kể cả chờ hoàn thành trễ hẹn Các nguyên tắc ưu ttb Ntb TRtb việc xuất (ngày) đợi (ngày) (ngày thứ...) (ngày) tiên E 9 9 23 0 FCFS 15,4 2,75 2,2 C 8 17 18 0 EDD 13,6 2,42 1,2 A 6 23 8 15 SPT 13 2,32 1,8 D 3 26 15 11 LPT 20,6 3,68 9,6 B 2 28 6 22 Tæng 28 103 48 103 t tb = = 20 , 6 ngµy 5 103 N tb = = 3 , 68 c«ng viÖc 28 48 TR tb = = 9 , 6 ngµy 5 2.1. Trường hợp 1 máy - N công việc 2.1. Trường hợp 1 máy - N công việc 2.1.2. Nguyên tắc dùng tỉ số tới hạn ( CR - 2.1.2. Nguyên tắc dùng tỉ số tới hạn ( CR - Critical Ratio) Critical Ratio) Ti Ví dụ: Vào ngày 25/12/N, tại một công ty có 3 công việc được CR = đặt hàng như sau: Ni Thêi h¹n Sè ngµy cÇn thiÕt C«ng Trong đó: Ti: là thời gian còn lại tính đến thời hạn hoàn thành hoµn cho c«ng viÖc 5 của công việc i viÖc thµnh cßn l¹i CR A = = 1, 25 Ni: là thời gian cần thiết để hoàn thành phần công việc i 4 còn lại, hay là phần công việc i còn lại phải làm mất bao nhiêu thời 3 A 30/12 4 CR B = = 0 ,6 gian tính đến thời hạn hoàn thành. 5 * Ý nghĩa của tỉ số tới hạn: Nếu CR > 1: Công việc sẽ được hoàn thành trước thời hạn. 2 B 28/12 5 CR C = = 1 CR = 1: Công việc sẽ hoàn thành đúng thời hạn. 2 CR < 1: Công việc sẽ không hoàn thành đúng hạn (trễ hạn). C 27/12 2 2
2. 2. Lập lịch trình N công việc trên 2 máy 2. 2. Lập lịch trình N công việc trên 2 máy - nguyên tắc Johnson - nguyên tắc Johnson Bước 1 : Liệt kê tất cả các công việc và thời gian thực hiện chúng trên mỗi máy. Mục tiêu của nguyên tắc Johnson: Bố trí Bước 2 : Chọn công việc có thời gian thực hiện các công việc sao cho tổng thời gian thực hiện nhỏ nhất. các công việc đó là nhỏ nhất hay tổng thời gian + Nếu công việc này nằm trên máy 1 thì ngừng việc trên các máy là nhỏ nhất. được sắp xếp trước. Điều kiện áp dụng nguyên tắc Johnson: + Nếu công việc này nằm trên máy 2 thì - Các máy không có khả năng thay thế được sắp xếp cuối cùng. nhau. Bước 3 : Khi một công việc đã được sắp xếp rồi - Công việc phải đi từ máy này đến máy thì ta loại trừ nó đi, chỉ xét những công việc còn kia. lại. Bước 4 : Trở lại bước 2 và 3 cho đến khi tất cả các công việc đều đã sắp xếp xong. 2. 2. Lập lịch trình N công việc trên 2 máy 2. 2. Lập lịch trình N công việc trên 2 máy - nguyên tắc Johnson - nguyên tắc Johnson Theo nguyên tắc Johnson, ta xếp thứ tự các công việc trên 2 Ví d ụ: Có 5 công việc được sản xuất bằng 2 máy: máy máy như sau: khoan và máy tiện. Thời gian thực hiện mỗi công việc trên B E D C A mỗi máy cho trong bảng sau. Hỏi nên sắp xếp các công Máy 1 3 7 10 8 5 việc như thế nào? (Biết rằng công việc nào cũng phải làm Máy 2 6 12 7 4 2 trên máy 1 trước rồi mới chuyển sang máy 2). Dòng thời gian được biểu diễn như sau: Thời gian thực hiện (giờ) Công việc 0 3 10 20 28 33 Máy khoan (máy 1) Máy tiện (máy 2) B=3 E=7 D = 10 C=8 A=5 A 5 2 B=6 E = 12 D=7 C=4 A=2 B 3 6 9 22 29 33 35 C 8 4 D 10 7 E 7 12 2.3. Lập lịch trình N công việc trên 3 máy 2.3. Lập lịch trình N công việc trên 3 máy Ví dụ: Có 4 công việc được thực hiện lần lượt trên 3 máy như sau. Hãy Sử dụng nguyên tắc Johnson nếu có 1 trong 2 điều kiện sau: chuyển đổi để có thể áp dụng nguyên tắc Johnson. - Thời gian ngắn nhất trên máy 1 phải lớn hơn hoặc bằng thời gian dài nhất trên máy 2. Công Thời gian (Giờ) - Thời gian ngắn nhất trên máy 3 phải lớn hơn hoặc bằng thời gian dài nhất trên máy 2. viÖc Máy 1 (t1) Máy 2 (t2) Máy 3 (t3) Nếu bài toán thoả mãn một trong hai điều kiện trên, ta tiến A 18 9 16 hành giải bài toán theo trình tự sau: B 12 3 11 - Đối với mỗi công việc, ta lấy t1+t2 và lấy t2+t3 để đưa về C 10 2 20 trường hợp lập lịch trình cho N công việc trên 2 máy. D 1 4 15 - Áp dụng nguyên tắc Johnson để sắp xếp thứ tự tối ưu cho các (Ngắn nhất = 1) (Dài nhất = 9) (Ngắn nhất = 11) công việc - Dùng lịch trình đã lập và bảng thời gian gốc (gồm đủ 3 máy) để vẽ dòng thời gian. 3
2.3. Lập lịch trình N công việc trên 3 máy 2.4. Sắp xếp lịch trình N công việc trên M máy Trong trêng hîp nµy, ®iÒu kiÖn 2 ®îc tháa m·n (11 > 9). Bµi to¸n cã thÓ gi¶i ®îc. Ta lËp b¶ng chuyÓn ®æi nh sau: - Bước 1 : Xác định số lượng các phương án sắp xếp. C«ng viÖc t1 + t2 t2 + t3 Nếu có N công việc thì có N ! cách sắp xếp A 27 25 Ví dụ : Xét trường hợp N = 3; M = 4; 3 công việc là A, B, C và 4 B 15 14 máy là máy I, II, III, IV. Khi ta thay đổi M, N thì thuật toán C 12 22 không có gì thay đổi. Với N = 3 ta có số phương án sắp xếp là D 5 19 3! = 6 cách sắp xếp. Dựa theo nguyên tắc Johnson, ta điều độ các công việc theo thứ tự D C A B. 2.4. Sắp xếp lịch trình N công việc trên M máy 2.4. Sắp xếp lịch trình N công việc trên M máy - Bước 2: Tính tổng thời gian hoàn thành của từng phương án T và x1 x1 ’ x1’’ chọn Tmin theo trình tự sau : a1 a2 a3 a4 + Lập bảng tính : x2 x2’ x2’’ - Xét phương án trình tự sản xuất là A- B- C ta sẽ lập được b1 b2 b3 b4 bảng tính sau x3 x3’ x3’’ c1 c2 c3 c4 M¸y I II III IV C«ng viÖc A a1 x1 a2 x'1 a3 x”1 a4 Ÿ ai ( i = 1,4): lµ thêi gian thùc hiÖn c«ng viÖc A trªn m¸y i. B b1 x2 b2 x'2 b3 x”2 b4 Ÿ bi ( i = 1,4): lµ thêi gian thùc hiÖn c«ng viÖc B trªn m¸y i. C c1 c2 c3 x”3 c4 Ÿ ci (i = 1,4): là thời gian thực hiện công việc C trên máy i. x3 x3 xj, x'j, x''j : là thời gian chờ đợi của các công việc khi chuyển từ máy này sang máy kia. (Điều kiện: xj , xj’, xj” ≥ 0) 2.4. Sắp xếp lịch trình N công việc trên M máy 2.4. Sắp xếp lịch trình N công việc trên M máy Ta có thể lập các phương trình như sau: x1 + a2 = b1 + x2 x2 + b2 = c1 + x3 Tổng thời gian nhỏ nhất để hoàn thành các công việc theo trình tự x'1 + a3 = b2 + x'2 ABC là: x'2 + b3 = c2 + x'3 T = a1 + x1 + a2 + x'1 + a3 + x''1 + a4 + b4 + c4 x''1 + a4 = b3 + x''2 x''2 + b4 = c3 + x''3 hoặc T = a1 + b1 + c1 + x3 + c2 + x'3 + c3 + x''3 + c4 + Tính các xj , x’j , x''j để biết thời gian chờ đợi của các công việc khi chuyển từ máy này sang máy kia. + Chọn trong các T của các phương án, phương án nào Vì số ẩn số lớn hơn số phương trình nên có ít nhất một xj, x'j, có Tmin- thì ta chọn phương án đó. x''j bằng 0. Khi tính toán nếu có xj < 0, ví dụ xj = -3, thì ta phải cộng xj với + 3 để biến chúng bằng 0. Kết quả tính ra các xj ≥ 0. 4
2.4. Sắp xếp lịch trình N công việc trên M máy 2.4. Sắp xếp lịch trình N công việc trên M máy x1 + 2 = 2 + x2 Ví dụ: Có 3 công việc được bố trí trên 4 máy. Thời gian tiến hành và thời x2 + 4 = 3 + x3 gian chờ đợi cho ở bảng sau: x'1 + 4 = 4 + x'2 Bước 1: Số lượng các phương án = 3! = 6 x'2 + 2 = 5 + x'3 Cụ thể có các phương án sau: ABC, ACB, BAC, BCA, CAB, CBA. x''1 + 3= 2 + x''2 Bước 2: Tính T. Xét phương án ABC TÝnh T: x''2 + 4= 3 + x''3 - TÝnh theo hµng trªn cïng vµ cét cuèi cïng. M¸y T =2 +0 +3+4+0 +3+4 +2 = 20 I II III IV C«ng viÖc - TÝnh theo cét ®Çu tiªn vµ hµng cuèi cïng. T = 2 + 2 + 3 + 1 + 5 + 0 + 3 + 2 + 2 = 20 A 2 x1 = 0 2 x'1 = 3 4 x”1 = 0 3 KÕt quả T (ABC) = 20 giê B 2 x2 = 0 4 x'2 = 3 2 x”2 = 1 4 B©y giê, ta thay ®æi thø tù vµ tÝnh l¹i sÏ cã c¸c kÕt quả sau ®©y: C 3 x3 = 1 5 x'3 = 0 3 x”3 = 2 2 T(BAC) = 18 giê T(ACB) = 20 giê T(BCA) = 21 giê VËy Tmin = 18 giê T(CAB) = 22 giê T(CBA) = 21 giê III. PH¦¥NG PH¸P PH¢N C¤NG C¤NG VIÖC CHO C¸C M¸Y 3.1. Bµi to¸n cùc tiÓu 3.1. Bµi to¸n cùc tiÓu Bíc 1: Chän trong mçi hµng mét sè min. LÊy c¸c sè trong hµng trõ ®i sè min ®ã Bíc 2: Chän trong mçi cét mét sè min. LÊy c¸c sè trong cét trõ ®i sè min ®ã. Trong trêng hîp cã: Bíc 3: Chän hµng nµo cã mét sè 0, khoanh trßn sè 0 ®ã. KÎ mét ®êng xuyªn - N m¸y, N c«ng viÖc suèt cét. - C¸c m¸y ®Òu cã tÝnh n¨ng thay thÕ nhau. Do ®ã Chän cét nµo cã mét sè 0, khoanh trßn sè 0 ®ã. KÎ mét ®êng xuyªn mçi c«ng viÖc chØ cÇn bè trÝ trªn 1 m¸y. suèt hµng. - Chi phÝ c¸c m¸y lµm c¸c c«ng viÖc kh¸c nhau lµ - NÕu sè c¸c sè 0 khoanh trßn b»ng sè ®¸p ¸n cÇn t×m th× bµi to¸n ®· gi¶i xong. kh¸c nhau. - NÕu sè c¸c sè 0 khoanh trßn cha b»ng sè ®¸p ¸n cÇn t×m th× ta ph¶i Ta cÇn bè trÝ mçi c«ng viÖc trªn mçi m¸y sao cho thùc hiÖn tiÕp bíc 4. tæng chi phÝ hay tæng thêi gian thùc hiÖn tÊt c¶ c¸c c«ng Bíc 4: Ta t¹o thªm sè 0 b»ng c¸ch: viÖc trªn tÊt c¶ c¸c m¸y lµ nhá nhÊt. Chän trong c¸c sè kh«ng n»m trªn ®êng th¼ng mét sè min, lÊy c¸c sè §èi víi bµi to¸n nµy, ta cã thÓ sö dông ph¬ng ph¸p kh«ng n»m trªn ®êng th¼ng trõ ®i sè min ®ã. LÊy sè min ®ã céng vµo c¸c sè n»m trªn giao ®iÓm cña c¸c ®êng th¼ng. Hungary ®Ó gi¶i. Sau ®ã ta l¹i bè trÝ c«ng viÖc nh ®· tr×nh bµy ë bíc 3. Khi sè c¸c sè 0 khoanh trßn b»ng sè ®¸p cÇn t×m th× bµi to¸n gi¶i xong. 3.1. Bµi to¸n cùc tiÓu 3.1. Bµi to¸n cùc tiÓu VÝ dô: Cã 3 c«ng viÖc A, B, C vµ cã 3 m¸y I, II, III. Chi phÝ cho c¸c c«ng viÖc LËp ma trËn vµ tÝnh to¸n c¸c bíc nh sau: thùc hiÖn trªn c¸c m¸y ®îc cho ë b¶ng sau. T×m ph¬ng ¸n bè trÝ c¸c c«ng viÖc Bíc 1: Bíc 2 vµ 3: trªn c¸c m¸y sao cho tæng chi phÝ lµ nhá nhÊt. 5 8 0 5 6 0 0 2 3 0 0 3 2 5 0 2 3 0 Sè ph¬ng ¸n lµ 3 nhng c¸c sè 0 ®îc khoanh trßn chØ cã 2. Ta ph¶i ®i tiÕp bíc 4. M¸y 3 4 0 I II III 0 0 5 C«ng viÖc 0 1 0 A 11 14 6 B 8 10 11 KÕt qu¶ ta bè trÝ nh sau: C«ng viÖc A: bè trÝ trªn m¸y III víi chi phÝ = 6 C 9 12 7 C«ng viÖc B: bè trÝ trªn m¸y II víi chi phÝ = 10 C«ng viÖc C: bè trÝ trªn m¸y I víi chi phÝ = 9 Tæng chi phÝ: 6 + 10 + 9 = 25 5
3.2. Bµi to¸n khèng chÕ 3.2. Bµi to¸n khèng chÕ Cïng bµi to¸n ph©n c«ng c«ng viÖc trªn c¸c m¸y nh trªn nhng ®îc ®Æt ra víi 2 môc tiªu : - Tæng chi phÝ (tæng thêi gian thùc hiÖn) lµ tèi thiÓu. - Chi phÝ thùc hiÖn tõng c«ng viÖc hoÆc thêi gian thùc hiÖn tõng c«ng viÖc Tríc hÕt ta lo¹i bá c¸c sè h¹ng lín h¬n hoÆc b»ng 110 giê, thay kh«ng ®îc vît qu¸ mét giíi h¹n nµo ®ã. vµo ®ã dÊu X. Sau ®ã gi¶i t¬ng tù nh bµi to¸n trªn. VÝ dô: T¹i mét ph©n xëng cã 4 c«ng viÖc A, B, C, D cã thÓ bè trÝ trªn c¸c m¸y I, II, III, IV víi thêi gian thùc hiÖn c¸c c«ng viÖc ®îc cho theo b¶ng sau: KÕt qu¶ cña viÖc bè trÝ nh sau : M¸y - C«ng viÖc B bè trÝ trªn m¸y I thêi gian 40 giê. I II III IV - C«ng viÖc A bè trÝ trªn m¸y II thêi gian 100 giê. C«ng viÖc - C«ng viÖc C bè trÝ trªn m¸y IV thêi gian 45 giê. A 70 100 110 130 - C«ng viÖc D bè trÝ trªn m¸y III thêi gian 50 giê. B 40 110 140 80 C 30 50 90 45 Tæng thêi gian thùc hiÖn lµ 235 giê vµ tÊt c¶ c¸c c«ng D 60 30 50 70 viÖc ®Òu thùc hiÖn víi sè giê díi 110 giê. H·y bè trÝ c¸c c«ng viÖc vµo c¸c m¸y sao cho tæng thêi gian thùc hiÖn chóng lµ tèi thiÓu vµ thêi gian thùc hiÖn c¸c c«ng viÖc ph¶i lµm díi 110 giê. 3.3. Bµi to¸n cùc ®¹i 3.3. Bµi to¸n cùc ®¹i Ví dụ: Trong một phân xưởng sản xuất của một xí nghiệp may có 3 nhóm công nhân đều có thể làm được các công việc là cắt, may và nhuộm. Năng suất của mỗi nhóm đối với từng loại công việc được cho Cïng bµi to¸n ph©n c«ng c«ng viÖc nh trªn nhng ®èi víi ở bảng sau: bµi to¸n cùc ®¹i th× môc ®Ých ph©n c«ng lµ tèi ®a hãa lîi Cắt May Nhuộm nhuËn. §Ó gi¶i bµi to¸n nµy, ta lµm nh sau: Nhóm 1 3 9 6 - §Æt chi phÝ = - tiÒn lêi (năng suất). Nhóm 2 5 10 15 - ChuyÓn bµi to¸n nh lµ ®i tÝnh chi phÝ nhá nhÊt. Nhóm 3 12 8 4 - Gi¶i bµi to¸n b×nh thêng. Hãy phân công công việc cho các nhóm công nhân sao cho tổng năng suất đạt được cao nhất? 3.3. Bµi to¸n cùc ®¹i Đặt chi phí = - năng suất -3 -9 -6 6 0 3 -5 -10 -15 10 5 0 -12 -8 -4 0 4 8 Nhóm 1: May (9) Nhóm 2: Nhuộm (15) Nhóm 3: Cắt (12) Tổng năng suất = 36 cái áo/ giờ 6