Bài giảng Quản trị sản xuất - Chương 6: 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 điểm hoàn thành (ngày thứ..)

Thời gian gia công (ngày) Thời hạn hoàn thành (ngày thứ .....) Thời gian trễ hạn (ngày)

12 8 - A 8

8 13 5 B 5

28 22 C 9

15 29 14 D 7

14 35 21 E 6

40  35

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)

5 B 8 5 -

6 E 14 11 -

7 D 15 18 3

8 A 12 26 14

9 C 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ứ ...)

C 9 28 9 Thời gian trễ hạn (ngày) -

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 1 2 3 4 5

M1

M2

A

10

12 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 1 2 3 4 5

M1

M2

A B

A

10

12 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 1 2 3 4 5

M1

M2

A C B

A

10

12 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 1 2 3 4 5

M1

M2

A D C B

A

10

12 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 1 2 3 4 5

M1

M2

A E D C B

A

10

12 B

14

13 C

16

15 D

17

16 E

19

20

10 29 46 62 76

E=19

D=17

C=16

B=14

M1

A= 10

A =12

E = 20

D = 16

M2

C = 15

B = 13

10 22 29

49 65 80 93

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

M1 + M2 M2 + M3

CV

Thời gian thực hiện

CV

M1

M2

M3

12

10

14 A

22

24

13

8

16 B

21

24

14

12

15 C

26

27

16

10

18 D

26

28

19

9

14 E

28

23

Thứ tự sắp xếp 2 1 A B A B 3 D C PA1 PA2 4 C D 5 E 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

1

2

3 Công suất

Nhà .máy A

20

21

120

22 B

22

25

80

27 C

24

28

100

30 Nhu cầu

90

70

140 bj

90

70

140 ai

20

21

22

120

22

25

27

80

24

28

30

100 Ui

Vj

Vùng

1

2

3 Công suất

Nhà .máy A

20

21

22

100 B

22

25

27

100 C

24

28

30

100 Nhu cầu

100 bj

100 ai

20

21

22

100

22

25

27

100

24

28

30

100 Ui

Vj

Cviệc

1

2

3 Công suất

C.nhân

A

20

21

1

22 B

22

25

1

27 C

24

28

1

30 Nhu cầu

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.

n x i j

Bước 3: Tương tự bước 2 thực hiện trên cột.

0 x i j

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.

 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)

j

i

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

+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)

B

C

A 1(3) A 2(3) D

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

Ta có thể xây dựng sơ đồ PERT như sau :

3

1

2

5

6

4 Đườ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

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 :

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

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

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

Kết thúc

Kết thúc sớm

Thời gian di động

Công việc

Bắt đầu sớm (ES) 0

Bắt đầu muộn (LS) 3

(EF) 2

muộn (LF) 5

(tháng) 3

A

B

0

3

0 C

2

5

3

6

3 D

3

6

0 E

3

5

7

2 F

6

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

5 5 A x x x

10 10 10 B x x x x x

3 C 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 7 8 4 5 6

5 5 A

10 10 10 B

3 C

2 2 2 D

10 10 E

5 5 F

8 G

Chi phí mỗitháng

15 15 13 10 10 10 7 7

Tổng chi phí dự án

59 74 87 10 20 30 37 44

Danh sách công việc

Thời gian

Côngviệc trước

A B

KHÔNG A

3 5

C D E

A B C

4 6 3

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

F G H I

C D, F G E, H

9 11 4 8

Sơ đồ GANTT

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

Danh saùch coâng vieäc

ST T

Thôøi gian

1 2 3 4 5 6 7 8 9

A B C D E F G H I

Coâng vieäc tröôùc None A A B C C D, F G E, H

3 5 4 6 3 9 11 4 8

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

STT

Danh saùch coâng vieäc

Thôøi gian bình thöôøng

Chi phí bình thöôøng

Chi phí ruùt ngaén

Thôøi gian ruùt ngaén

150 500 600 200 620 300 400 360

1 2 3 4 5 6 7 8 9

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

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

?

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





te

bma 4 6

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

m

a

b

A B C D E F G H I

Coâng vieäc tröôùc – 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

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

Ứ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:

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 nhanh

Bình thöôøng Khi laøm nhanh

Coâ ng vieä c

14 10 200 A

Baét ñaàu ngay

12 9 120 B

Baét ñaàu ngay

Sau A, B 4 3 310 C

Sau A, B 18 14 240 D

Sau C 3 3 E

Sau C 2 2 F

Sau D 1 1 G

Sau E, F, G 400 H 2 1

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:

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

Coâ ng vieä c

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:

Thôøi gian gia coâng (giôø/maùy)

Coâng vieäc 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:

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ờ.

Thôøi gian thöïc hieän (giôø)

I II III IV V

Coâng vieäc coâng nhaân

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)

II III IV V

30 20 10 30 40 Huøng

70 40 60 50 70 Thaûo

40 50 20 30 40 Laân

60 70 30 40 90 Caûnh

50 60 40 60 50 Hoøa

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 .