Đề cương môn quản lý công nghiệp - Trường Đại học bách khoa - Đại học đà nẵng.
Hãylậpbảngđiềuđộgia côngsaochokhoảngthờigiangiacônglànhỏ nhất?
Đề cương môn quản lý công nghiệp - Trường Đại học bách khoa - Đại học đà nẵng.
Tài liệu gồm16 trang , giúp bạn tham khảo, ôn tập và đạt kết quả cao.
Môn: Quản lý công nghiệp 15 tài liệu
Trường: Trường Đại học Bách khoa, Đại học Đà Nẵng 642 tài liệu
Tác giả:
Preview text:
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT Chương 5
LẬP LỊCH TRÌNH SẢN XUẤT
5.1. Mục tiêu của lập lịch trình sản xuất
Trong quá trình sản xuất hoặc thực hiện các dịch vụ, chúng ta cần tiến hành nhiều
công việc khác nhau. Điều này đòi hỏi sự điều hành, sắp xếp sao cho khoa học, hợp lý,
chặt chẽ vào những lúc cao điểm và ngay cả những lúc rảnh rỗi.
Lập lịch trình sản xuất nhằm mục tiêu đảm bảo sao cho các công việc được thực
hiện với hiệu quả cao nhất, cụ thể là:
Đáp ứng kỳ hạn giao hàng cho khách hàng;
Tối thiểu hóa sự chậm trễ trong công việc;
Tối thiểu hóa thời gian phản ứng hay đáp ứng;
Tối thiểu hóa thời gian hoàn thành;
Tối thiểu hóa giờ làm thêm;
Tối đa hóa mức sử dụng máy móc hoặc lao động;
Tối thiểu hóa thời gian không hoạt động hay không được sử dụng;
Tối thiểu hóa hàng tồn kho dở dang.
5.2. Nguyên tắc sắp xếp thứ tự các công việc trên một máy (dây chuyền)
Xếp thứ tự các công việc là quy định thứ tự công việc nào được làm trước, công việc
nào được làm sau trên mỗi máy, chẳng hạn: Có 10 bệnh nhân đưa vào bệnh viện, thì
nên xếp người nào được chữa trước, người đến trước được chữa trước hay người bệnh
nguy cấp được chữa trước.
Xếp thứ tự công việc trên một máy là một bài toán đơn giản. Có n công việc gia
công trên một máy. Mỗi công việc có một thời gian gia công (sản xuất) và một thời
hạn hoàn thành theo yêu cầu được quy định trước. Vấn đề đặt ra là phải bố trí làm sao
cho n công việc này được làm nối tiếp nhau để cho ta đạt được kết quả tối ưu. Có
nghĩa là các công việc này cần được sắp xếp thành một lịch trình chặt chẽ và khoa học,
đặc biệt là khi có nhiều công việc chồng chéo trong những thời kỳ cao điểm.
Muốn sắp xếp tối ưu các công việc trên một máy ta phải dựa vào 4 nguyên tắc ưu tiên sau đây:
(1) Công việc đặt hàng trước, bố trí làm trước (First come, first served - FCFS);
(2) Công việc có thời hạn giao hàng sớm nhất, bố trí làm trước (Earliest Due Date - EDD);
(3) Công việc có thời gian thực hiện ngắn nhất, bố trí làm trước (Shortest Processing Time - SPT);
(4) Công việc có thời gian thực hiện dài nhất, bố trí làm trước (Longest Processing Time-LPT).
Ví dụ sau đây sẽ cho ta so sánh các nguyên tắc vừa nêu: 79
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Ví dụ 5.1: Một xí nghiệp cơ khí có nhận 5 hợp đồng cắt tôn cho bên ngoài. Thời
gian gia công (sản xuất) và thời hạn hoàn thành được cho trong bảng 5.1 sau: Bảng 5.1 Thời gian gia công
Thời hạn hoàn thành Công việc (ngày) (ngày thứ ...) A 6 8 B 2 6 C 8 18 D 3 15 E 9 23
Hãy xác định thứ tự các công việc được gia công theo nguyên tắc: FCFS, EDD, SPT & LPT.
Để so sánh các nguyên tắc trên, ta cần tính các chỉ tiêu hiệu quả sau: Ta có:
Tổng dòng thời gian = Tổng thời gian sản xuất + Tổng thời gian chờ đợi
Các chỉ tiêu hiệu quả được tính theo công thức:
Thời gian bình quân để thực hiện (hoàn tất) công việc (Ttb):
Ttb = Tổng dòng thời gian/ Số công việc (5.1)
Số công việc bình quân chờ đợi trong hệ thống (Ntb):
Ntb = Tổng dòng thời gian/Tổng thời gian sản xuất (5.2)
Số ngày trễ hạn bình quân của mỗi công việc (TRtb):
TRtb = Tổng số ngày trễ hạn/Số công việc (5.3)
5.2.1. Xếp thứ tự các công việc theo nguyên tắc FCFS
Với nguyên tắc này, thứ tự thực hiện các công việc này là: A – B – C – D – E.
Do công việc A phải làm mất 6 ngày, xong A mới gia công B. Vậy B phải chờ
mất 6 ngày. Thời gian thực hiện B mất 2 ngày, do đó thời điểm hoàn thành công việc B là:
6 ngày chờ + 2 ngày gia công = ngày thứ 8
Vì thời hạn hoàn thành theo yêu cầu đối với B là ngày thứ 6, nên công việc đã
trễ mất 8 – 6 = 2 ngày.
Theo cách tính trên với các công việc còn lại C, D, E ta lập được bảng 5.2 sau đây:
Bảng 5.2: Lịch trình sản xuất theo nguyên tắc FCFS 80
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT Thời hạn
Thời điểm hoàn Thời gian Thời gian Công hoàn thành thành (dòng chậm trễ việc gia công theo yêu cầu thời gian) (ngày) (ngày) (ngày thứ…) (ngày thứ…) A 6 8 6 - B 2 6 8 2 C 8 18 16 - D 3 15 19 4 E 9 23 28 5 ∑ 28 77 11
Với các số liệu trong bảng 5.2, ta tính được các chỉ tiêu hiệu quả sau:
Thời gian bình quân để hoàn thành công việc = 77/5 = 15,4 ngày.
Số công việc bình quân chờ đợi trong hệ thống = 77/28 =2,75 công việc.
Số ngày trễ hạn bình quân = 11/5 = 2,2 ngày.
5.2.2. Xếp thứ tự các công việc theo nguyên tắc EDD
Theo nguyên tắc này thì công việc nào có thời điểm hoàn thành sớm nhất sẽ được
ưu tiên thực hiện trước, do đó ta có thứ tự thực hiện là: B – A – D – C – E.
Bảng 5.3: Lịch trình sản xuất theo nguyên tắc EDD Thời hạn
Thời điểm hoàn Thời gian Thời gian Công hoàn thành thành (dòng chậm trễ việc gia công theo yêu cầu thời gian) (ngày) (ngày) (ngày thứ…) (ngày thứ…) B 2 6 2 - A 6 8 8 - D 3 15 11 - C 8 18 19 1 E 9 23 28 5 ∑ 28 68 6
Các chỉ tiêu hiệu quả được tính:
Thời gian bình quân để hoàn thành công việc = 68/5 = 13,6 ngày.
Số công việc bình quân chờ đợi trong hệ thống = 68/28 =2,42 công việc.
Số ngày trễ hạn bình quân = 6/5 = 1,2 ngày.
5.2.3. Xếp thứ tự các công việc theo nguyên tắc SPT 81
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Theo nguyên tắc này, công việc nào có thời gian gia công ngắn nhất được ưu tiên
làm trước, do đó ta có thứ tự thực hiện là: B – D – A – C – E.
Bảng 5.4: Lịch trình sản xuất theo nguyên tắc SPT Thời hạn
Thời điểm hoàn Thời gian Thời gian Công hoàn thành thành (dòng chậm trễ việc gia công theo yêu cầu thời gian) (ngày) (ngày) (ngày thứ…) (ngày thứ…) B 2 6 2 - D 3 15 5 - A 6 8 11 3 C 8 18 19 1 E 9 23 28 5 ∑ 28 65 9
Các chỉ tiêu hiệu quả được tính như sau:
Thời gian bình quân để hoàn thành công việc = 65/5 = 13 ngày.
Số công việc bình quân chờ đợi trong hệ thống = 65/28 = 2,32 công việc.
Số ngày trễ hạn bình quân = 9/5 = 1,8 ngày.
5.2.4. Xếp thứ tự các công việc theo nguyên tắc LPT
Theo nguyên tắc này, ta chọn các công việc có thời gian gia công dài nhất bố trí làm
trước, thứ tự gia công các công việc sẽ là: E – C – A – D – B:
Bảng 5.5: Lịch trình sản xuất theo nguyên tắc LPT Thời hạn Thời Thời điểm hoàn gian Thời gian Công hoàn thành thành (dòng chậm trễ việc gia công theo yêu cầu thời gian) (ngày) (ngày) (ngày thứ…) (ngày thứ…) E 9 23 9 - C 8 18 17 - A 6 8 23 15 D 3 15 26 11 B 2 6 28 22 ∑ 28 103 48
Các chỉ tiêu hiệu quả được tính như sau:
Thời gian bình quân để hoàn thành công việc = 103/5 = 20,6 ngày.
Số công việc bình quân chờ đợi trong hệ thống = 103/28 =3,68 công việc.
Số ngày trễ hạn bình quân = 48/5 = 9,6 ngày.
Dưới đây là bảng tóm tắt các chỉ tiêu hiệu quả của 4 nguyên tắc trên: 82
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Bảng 5.6: Tóm tắt các chỉ tiêu hiệu quả của 4 nguyên tắc
Thời gian bình
Số công việc bình Nguyên
Số ngày trễ hạn tắc
quân để hoàn tất
quân chờ đợi trong bình quân
công việc (ngày) hệ thống 1. FCFS 15,4 2,75 2,2 2. EDD 13,6 2,42 1,2 3. SPT 13 2,32 1,8 4. LPT 20,6 3,68 9,6
Qua bảng 5.6 ta nhận thấy:
Nguyên tắc LPT có các chỉ tiêu hiệu quả kém nhất.
Nguyên tắc SPT có 2 chỉ tiêu đầu vượt trội, tức thời gian bình quân để hoàn tất
công việc = 13 ngày (min) và số công việc bình quân chờ đợi trong hệ thống = 2,32 (min).
Nguyên tắc EDD có chỉ tiêu thứ 3 vượt trội hơn cả, số ngày trễ hạn bình quân =
1,2 (min). Như vậy trong 4 nguyên tắc trên thì nguyên tắc SPT có lợi hơn cả.
Theo kinh nghiệm thực tế, người ta rút ra những nhận xét như sau:
Nguyên tắc theo thời gian thực hiện ngắn nhất SPT được coi là kỹ thuật tốt nhất
để giảm thiểu dòng thời gian và giảm thiểu số công việc bình quân chờ đợi trong
hệ thống. Tuy nhiên, mặt hạn chế của nguyên tắc này là đẩy những công việc có
thời gian thực hiện dài xuống dưới, điều này dễ làm cho các khách hàng quan
trọng phật ý, dẫn đến việc có thể gây ra những thay đổi, biến động đối với các
công việc dài hạn, tuy vậy nguyên tắc này thường được dùng nhiều nhất.
Nguyên tắc đặt hàng trước, bố trí làm trước FCFS tuy có các chỉ tiêu hiệu quả
không cao, nhưng không vì vậy mà coi nó là nguyên tắc kém nhất. Bởi vì ưu
điểm của nó là làm hài lòng các khách hàng, thể hiện tính công bằng, đây là yếu
tố hết sức quan trọng trong các hệ thống dịch vụ.
Nguyên tắc công việc có thời gian thực hiện dài nhất LPT thường ít khi được sử
dụng, nó thường được áp dụng khi:
Các hợp đồng chưa chắc chắn.
Khi các công việc có thời gian thực hiện xấp xỉ bằng nhau.
Dựa vào kết quả các chỉ tiêu tính được, ta thấy nguyên tắc ưu tiên sắp xếp công
việc theo thời gian thực hiện ngắn nhất có nhiều chỉ tiêu trội hơn.
5.3. Phương pháp phân giao công việc trên nhiều đối tượng 83
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
5.3.1. Phương pháp Johnson bố trí thứ tự thực hiện các công việc trên 2 máy
Điều độ công việc làm trên hai máy sẽ không đơn giản như một máy, mà tùy theo
cách điều độ chúng ta sẽ kết thúc công việc ở các thời điểm khác nhau.
Do hai máy có chức năng khác nhau nên có hai giai đoạn liên kết nhau theo trình tự:
Công việc nào cũng phải được làm trên máy 1 trước rồi mới chuyển sang máy 2.
Mục tiêu bố trí các công việc là làm sao để tổng thời gian thực hiện các công việc
đó là bé nhất. Nhưng vì thời gian thực hiện mỗi công việc trên mỗi máy là cố định (do
khối lượng công việc và công suất của máy quyết định). Nên để có được tổng thời gian
thực hiện các công việc min, ta phải bố trí các công việc sao cho tổng thời gian ngừng
việc trên các máy là bé nhất.
Để bố trí các công việc trên 2 máy ta dùng nguyên tắc Johnson. Nguyên tắc Johnson
được thực hiện theo các bước sau:
Bước 1: Sắp xếp các công việc theo thứ tự có thời gian thực hiện nhỏ nhất tăng dần;
Bước 2: Áp dụng nguyên tắc Johnson.
Theo thứ tự đã xếp ở bước 1, ta lần lượt bố trí như sau:
Công việc nào có thời gian thực hiện nhỏ nhất ở máy 1 (cột số 1) thì bố trí bên trái (ở đầu);
Công việc nào có thời gian thực hiện nhỏ nhất ở máy 2 (cột số 2) thì bố trí bên phải (ở cuối).
Bước 3: Khi một công việc đã được sắp xếp rồi thì ta loại trừ, chỉ xét những công việc còn lại;
Bước 4: Vẽ biểu đồ thời gian và tính tổng thời gian thực hiện các công việc.
Ví dụ 5.2: Mỗi ngày bệnh viện Nhân Dân cần giặt bảy loại khăn khác nhau, bệnh
viện chỉ có 1 máy giặt và 1 máy sấy. Thời gian giặt và sấy trên hai máy đó được cho theo bảng 5.7 như sau:
Bảng 5.7: Thời gian thực hiện các công việc trên 2 máy Thời Thời Loại gian giặt gian sấy khăn (Phút) (Phút) A 30 50 B 55 35 C 100 80 D 40 10 E 110 90 F 45 55 G 120 100
Yêu cầu: Hãy sắp xếp thứ tự các công việc để tổng thời gian thực hiện là nhỏ nhất? Bài giải: 84
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Bước 1: Xếp các công việc theo thứ tự thời gian tăng dần: Thời Thời Loại gian giặt gian sấy khăn (Phút) (Phút) D 40 10 A 30 50 B 55 35 F 45 55 C 100 80 E 110 90 G 120 100
Bước 2: Sắp xếp theo nguyên tắc Johnson: A F G E C B D Máy giặt 30 45 120 110 100 55 40 Máy sấy 50 55 100 90 80 35 10
Bước 3: Vẽ sơ đồ các công việc và xác định tổng thời gian: A= F= Máy giặt G=120 E=110 C=100 B=55 D=40 30 45 Máy sấy A=50 F=55 G=100 E=90 C=80 B=35 D= 10 30 80 135 195 295 305 395 405 485 520 530
Nhìn vào biểu đồ thời gian ta thấy:
Tổng thời gian thực hiện tất cả các công việc trên 2 máy = 530 phút (tức 8 giờ 50 phút) là ít nhất;
Máy sấy được huy động sau máy giặt là 30 phút;
Máy giặt được giải phóng sau 500 phút (tức 8 giờ 20 phút);
Máy sấy được giải phóng sau 530 phút (tức 8 giờ 50 phút);
Máy sấy sau công việc F phải chờ mất 60 phút, sau công việc G và E đều phải chờ 10 phút.
Đây là phương án tối ưu có tổng thời gian hoàn thành tất cả các công việc trên 2
máy là ngắn nhất (8 giờ 50 phút)
Trường hợp bố trí trên 3 máy thì có thể ứng dụng phương pháp Johnson nếu thoả
mãn cả 2 điều kiện sau:
(1) Thời gian gia công ngắn nhất trên máy 1 bằng hoặc dài hơn thời gian dài nhất trên máy 2; 85
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
(2) Thời gian gia công ngắn nhất trên máy 3 bằng hoặc dài hơn thời gian dài nhất trên máy 2.
Khi đó ta sẽ gộp 3 máy thành 2 máy theo nguyên tắc sau: gộp thời gian gia công của
máy 1 với máy 2 thành máy I; Máy 2 và máy 3 thành máy II rồi bố trí như có 2 máy.
Ví dụ 5.3: Có 4 công việc phải thực hiện lần lượt trên 3 máy mới xong, và có thời gian cho theo bảng 5.8 như sau:
Bảng 5.8: Thời gian thực hiện các công việc trên 3 máy
Thời gian thực hiện các công việc (giờ) Công việc Máy 1 (t1) Máy 2 (t2) Máy 3 (t3) A 13 5 9 B 5 3 7 C 6 4 5 D 7 2 6
Bước 1: Xét bài toán có thỏa nguyên tắc Johnson không? t1 min t2 max; t3 min t2 max.
Theo thông tin được cung cấp ta có t1 min = t2 max và t3 min = t2 max.
Như vậy, điều kiện của nguyên tắc Johnson đối với 3 máy đã được thoả mãn
Bước 2: Lập ma trận mới bằng cách lấy t1 + t2 và t2 + t3 Công việc t1 + t2 t2 + t3 A 18 14 B 8 10 C 10 9 D 9 8
Bước 3: Sắp xếp các công việc theo thứ tự thời gian nhỏ nhất tăng dần. Công việc t1 + t2 t2 + t3 D 9 8 B 8 10 C 10 9 A 18 14
Bước 4: Sắp xếp thứ tự thực hiện các công việc theo nguyên tắc Johnson 86
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT CV B A C D Máy Máy 1 5 13 6 7 Máy 2 3 5 4 2 Máy 3 7 9 5 6
Bước 5: Vẽ biểu đồ và tính tổng thời gian thực hiện các công việc 5 18 24 31 Máy 1 B =5 A =13 C=6 D=7 B= D= Máy 2 A=5 C=4 3 2 Máy 3 B =7 A=9 C=5 D=6 0 8 15 23 32 37 43
Tổng thời gian thực hiện các công việc nhỏ nhất là 43 giờ.
5.3.2. Sử dụng bài toán Hungary trong phân giao n công việc cho n đối tượng
Trong trường hợp sắp xếp hoặc phân giao n công việc cho n máy hoặc n người với
điều kiện mỗi máy hoặc mỗi người chỉ đảm nhận một công việc cũng có rất nhiều
phương án sắp xếp khác nhau. Trong trường hợp này có thể xác định được phương án
sắp xếp tối ưu giữa các phương án đó. Phương án tối ưu đó có thể là phương án có
tổng thời gian thực hiện nhỏ nhất hoặc cung cấp sản phẩm, dịch vụ nhanh nhất, tuỳ
thuộc vào mục tiêu cụ thể đặt ra trong khi sắp xếp. Trong một số trường hợp mục tiêu
đặt ra là tổng thời gian thực hiện của tất cả các đối tượng là ngắn nhất nhưng trong các
trường hợp khác mục tiêu lại là giảm thời gian ứ đọng khi thực hiện các công việc.
Để xác định được phương án tối ưu ta dùng thuật toán Hungary. Thuật toán này
được thực hiện theo trình tự sau:
Bước 1: Đối với mỗi hàng, tìm số nhỏ nhất trong hàng đó rồi trừ nó cho từng yếu tố có
trong hàng (sẽ sinh ra một ma trận chi phí mới có cùng một đáp số như ma trận ban đầu);
Bước 2: Đối với mỗi cột của ma trận, tìm số nhỏ nhất trong cột đó (có thể là số
không) và lấy số đó trừ đi cho từng yếu tố có trong cột. Một lần nữa ta lại có một ma
trận mới có cùng một đáp số với ma trận ban đầu;
Bước 3: Cố gắng tìm một đáp số có tổng chi phí bằng không
(3a) Xem xét từng hàng một của ma trận, nếu trong hàng không có một số không
nào hoặc có nhiều số không thì ta bỏ qua hàng đó. Nếu trong hàng có đúng một số
không thì ta khoanh tròn số không đó rồi gạch một đường thẳng xuyên suốt cột;
(3b) Xét từng cột một của ma trận, nếu trong cột có đúng một số không thì ta
khoanh tròn số không đó lại, rồi gạch một đường thẳng xuyên suốt hàng. Nếu điều kiện
không được thỏa mãn thì bỏ qua cột đó; 87
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
(3c) Lập lại bước (3a) và (3b) cho đến khi không còn có thể khoanh tròn con số không nào nữa.
Nếu số số không khoanh tròn bằng số đáp áp cần tìm thì bài toán đã giải xong, nếu
số số không khoanh tròn chưa bằng số đáp án cần tìm ta phải thực hiện tiếp bước 4.
Bước 4: Ta tạo thêm số không bằng cách:
(4a) Tìm ra số chưa bị gạch nhỏ nhất;
(4b) Lấy các số không nằm trên các đường thẳng trừ đi số nhỏ nhất đó;
(4c) Lấy số nhỏ nhất đó cộng vào các số nằm trên giao điểm của các đường thẳng;
(4d) Chép lại các số bị gạch bởi một đường thẳng.
Sau đó ta lại bố trí công việc như đã trình bày ở bước 3, cứ tiếp tục như vậy cho đến
khi nào số không khoanh tròn bằng số đáp án cần tìm thì bài toán mới giải xong.
Các công việc sẽ được bố trí vào các ô có số không khoanh tròn. Như vậy chúng ta
sẽ có tổng thời gian thực hiện hoặc chi phí thực hiện các công việc là tối thiểu.
a) Bài toán 1 mục tiêu
Ví dụ 5.4: Có 3 công việc X – 25, Y – 47, Z – 72, và có 3 máy A, B, C. Thời gian
thực hiện các công việc trên các máy cho như bảng sau:
Bảng 5.9: Thời gian thực hiện các công việc trên các máy
Đơn vị tính: giờ Máy A Máy B Máy C X – 25 11 14 6 Y – 47 8 10 11 Z – 72 9 12 7
Tìm phương án bố trí các công việc trên các máy sao cho tổng thời gian thực hiện là nhỏ nhất? Bài giải:
Bước 1: Chọn trong mỗi hàng 1 số min, lấy các số trong hàng trừ đi số min đó. Máy A Máy B Máy C X – 25 5 8 0 Y – 47 0 2 3 Z – 72 2 5 0
Bước 2: Chọn trong mỗi cột 1 số min, lấy các số trong hàng trừ đi số min đó. Máy A Máy B Máy C X – 25 5 6 0 Y – 47 0 0 3 Z – 72 2 3 0 88
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Bước 3: Bố trí công việc vào các ô số 0 duy nhất của hàng và cột
Chọn hàng nào có 1 số 0, khoanh tròn số 0 đó, kẻ đường thẳng xuyên suốt cột.
Chọn cột nào có 1 số 0, khoanh tròn số 0 đó, kẻ đường thẳng xuyên suốt hàng. Máy A Máy B Máy C X – 25 5 6 0 Y – 47 0 0 3 Z – 72 2 3 0
Bước 4: Số 0 được khoanh tròn chưa bằng số đáp án cần tìm, do đó ta chọn trong
các số không nằm trên các đường thẳng 1 số min, lấy các số 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. Máy A Máy B Máy C X – 25 3 4 0 Y – 47 0 0 3 + 2 = 5 Z – 72 0 1 0
Bước 5: Bố trí công việc vào các ô số 0 duy nhất của hàng và cột. Máy A Máy B Máy C X – 25 3 4 0 Y – 47 0 0 3 + 2 = 5 Z – 72 0 1 0
Như vậy, cách phân công công việc cho các máy tối ưu như sau:
Công việc X – 25 bố trí vào máy C mất 6 giờ.
Công việc Y – 47 bố trí vào máy B mất 10 giờ.
Công việc Z – 72 bố trí vào máy A mất 9 giờ.
Như vậy, tổng thời gian tối thiểu thực hiện các công việc là 25 giờ.
Trong thực tế chúng ta gặp trường hợp phân giao công việc sao cho tổng lợi nhuận
thu được là tối đa. Để tìm được phương án phân giao tối ưu vẫn sử dụng phương pháp
giải trên. Tuy nhiên, cần phải đổi dấu toàn bộ các số liệu trong bảng phân việc, sau đó
vận dụng bài toán Hungary giải bình thường.
b) Bài toán 2 mục tiêu
Trong trường hợp bài toán phân công công việc được đặt ra với hai mục tiêu:
Tổng chi phí hoặc thời gian thực hiện công việc là tối thiểu.
Chi phí thực hiện công việc hoặc thời gian thực hiện từng công việc không
được vượt quá 1 mức nào đó thì chúng ta chỉ cần loại bỏ các số hạng bằng hoặc
vượt quá mức đã qui định bằng cách thay chúng bằng dấu X, sau đó tiến hành giải bình thường. 89
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Ví dụ 5.5: Có 4 công việc cần phân cho 4 công nhân có tay nghề cao là An, Bình,
Chính, Dương với thời gian thực hiện được cho như trong bảng 5.10:
Bảng 5.10: Thời gian thực hiện 4 công việc của 4 công nhân
Đơn vị tính: Giờ CV I II III IV Công nhân An 70 100 110 130 Bình 40 110 140 80 Chính 30 50 90 45 Dương 60 30 50 70
Yêu cầu: Hãy bố trí các công việc cho bốn nhân viên trên sao cho thỏa mãn đồng thời 2 điều kiện sau:
Tổng thời gian thực hiện chúng là min;
Thời gian thực hiện mỗi công việc < 110 giờ. Bài giải:
Bước 1: Loại bỏ các số hạng 110 giờ, thay vào vị trí đó 1 dấu chéo X. I II III IV An 70 100 X X Bình 40 X X 80 Chính 30 50 90 45 Dương 60 30 50 70
Bước 2: Chọn trong mỗi hàng 1 số min, lấy các số trong hàng trừ đi số min đó. I II III IV An 0 30 X X Bình 0 X X 40 Chính 0 20 60 15 Dương 30 0 20 40
Bước 3: Chọn trong mỗi cột 1 số min, lấy các số trong hàng trừ đi số min đó. I II III IV An 0 30 X X Bình 0 X X 25 Chính 0 20 40 0 Dương 30 0 0 25 90
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Bước 4: Bố trí công việc vào các ô số 0 duy nhất của hàng và cột. I II III IV An 0 30 X X Bình 0 X X 25 Chính 0 20 40 0 Dương 30 0 0 25
Bước 5: Số 0 được khoanh tròn chưa bằng số đáp án cần tìm, do đó ta chọn trong
các số không nằm trên các đường thẳng 1 số min, lấy các số 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. I II III IV An 0 10 X X Bình 0 X X 25 Chính 0 0 20 0 Dương 30 + 20 0 0 25 + 20
Bước 6: Bố trí công việc vào các ô số 0 duy nhất của hàng và cột. I II III IV An 0 10 X X Bình 0 X X 25 Chính 0 0 20 0 Dương 30+20 0 0 25+20
Bước 7: Số số 0 được khoanh tròn chưa bằng số đáp án cần tìm, nên ta phải tạo
thêm số 0 như bước 5, rồi tiếp tục như bước 6. Ta có số 0 khoanh tròn bằng số đáp
án cần tìm và bài toán đã giải xong. I II III IV An 0 0 X X Bình 0 X X 15 Chính 0+10 0 20 0 Dương 50+10 0 0 50
Như vậy, phân công công việc tối ưu trong tình huống này là:
Anh An bố trí làm công việc II mất 100 giờ < 110 giờ
Anh Bình bố trí làm công việc I mất 40 giờ < 110 giờ
Anh Chính bố trí làm công việc IV mất 45 giờ < 110 giờ
Anh Dương bố trí làm công việc III mất 50 giờ < 110 giờ
Tổng thời gian tối thiểu để thực hiện các công việc là 235 giờ. 91
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
CÂU HỎI ÔN TẬP CHƯƠNG 5
1. Lập lịch trình sản xuất là gì? Mục tiêu của lập lịch trình sản xuất là gì?
2. Trình bày các nguyên tắc sắp xếp thứ tự các công việc trên 1 máy (dây chuyền)?
3. Trình bày các bước của phương pháp Johnson trong sắp xếp thứ tự các công việc trên 2 máy (dây chuyền)?
4. Để áp dụng nguyên tắc Johnson trong sắp xếp thứ tự các công việc trên 3 máy cần
phải thoả những điều kiện nào? Trình tự áp dụng nguyên tắc Johnson trong sắp xếp
các công việc trên 3 máy như thế nào?
5. Trình bày các bước của phương pháp Hungary trong phân giao n công việc cho n máy (công nhân)? BÀI TẬP CHƯƠNG 5
Bài 1: Một công ty xây dựng nhận được 6 hợp đồng xây nhà sau đây: Thời gian xây Thời hạn bàn giao Nhà (ngày) (ngày thứ…) A 6 22 B 12 14 C 14 30 D 2 18 E 10 25 F 4 34 Yêu cầu:
1. Theo anh (chị) công ty nên dùng cách nào giữa 2 cách điều độ theo nguyên tắc
đến trước làm trước FCFS và nguyên tắc thời hạn sớm nhất EDD?
2. Công ty muốn xét thêm nguyên tắc thời gian thi công ngắn nhất SPT và thời
gian thi công dài nhất LPT. Vậy anh (chị) hãy tính toán và cho lời khuyên?
Bài 2: Hãy dùng nguyên tắc Johnson để xác định thứ tự gia công tối ưu cho các công
việc làm trên 2 máy sau đây: 92
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Đơn vị tính: giờ Công việc Máy 1 Máy 2 A 6 12 B 3 7 C 18 9 D 15 14 E 16 8 F 10 15
Bài 3: Các công việc có tuần tự và thời gian gia công trên 3 máy được cho trong bảng sau:
Đơn vị tính: giờ Công việc Máy 1 Máy 2 Máy 3 A 22 8 10 B 18 6 5 C 16 3 3 D 20 12 17 E 15 14 12
Yêu cầu: Hãy lập bảng điều độ gia công sao cho khoảng thời gian gia công là nhỏ nhất?
Bài 4: Mỗi ngày bệnh viện Nhân Dân cần giặt bảy loại khăn khác nhau, bệnh viện chỉ có
1 máy giặt và 1 máy sấy. Thời gian giặt và sấy trên hai máy đó được cho theo bảng sau: Thời Thời Loại gian giặt gian sấy khăn (Phút) (Phút) A 30 50 B 55 35 C 100 80 D 40 10 E 110 90 F 45 55 G 120 100 Yêu cầu:
1. Hãy dùng nguyên tắc Johnson để xác định thứ tự các công việc sao cho tối ưu nhất?
2. Nếu hàng ngày bắt đầu giặt lúc 8 giờ sáng thì khi nào công việc giặt sấy xong?
Bài 5: Mỗi ngày phân xưởng cơ khí có 4 thợ giỏi đều có thể đứng được cả 4 loại máy
phay là phay giường (G), phay đứng (Đ), phay ngang (N), phay răng (R) nhưng do
mức lương và trình độ thành thạo của các anh khác nhau nên chi phí đứng máy được phân bố như sau: 93
Chương 5: Lập lịch trình sản xuất
QUẢN TRỊ SẢN XUẤT
Chi phí máy phay (1000đồng/giờ) Công nhân Giường Đứng Ngang Răng An 25 30 15 20 Bình 25 10 5 15 Công 30 10 25 10 Dân 20 15 10 5
Theo anh (chị) nên phân công nhân nào đứng máy nào cho kinh tế nhất?
Bài 6: Mỗi ngày Công ty VICODEC đóng tại Nha Trang muốn phân 3 sinh viên tốt
nghiệp Đại học Thủy sản là Giang, Sơn, Vinh về 3 cơ sở nuôi tôm của công ty ở Cam
Ranh, Sông Cầu và Thuận Nam. Chi phí để ổn định chỗ ở cho mỗi sinh viên ở từng địa
điểm là khác nhau. Biết chi phí để ổn định chỗ ở cho 3 sinh viên này tại 3 cơ sở Cam
Ranh, Sông Cầu và Thuận Nam như sau: Nơi công tác Cam Ranh Sông Cầu Thuận Nam Sinh viên Giang 800.000 đ 1.100.000 đ 1.200.000 đ Sơn 500.000 đ 1.600.000 đ 1.300.000 đ Vinh 500.000 đ 1.000.000 đ 2.300.000 đ Yêu cầu:
1. Theo anh (chị) nên phân sinh viên nào đến địa điểm nào cho kinh tế?
2. Vì một lý do nào đó Vinh báo cáo anh ta không thể về Sông Cầu. Trong trường hợp
này phân công công việc sẽ như thế nào?
3. Giả định cùng thời điểm đó công ty mới vừa khai trương một nhà máy chế biến Hải
sản ở Phan Rang nên muốn phân 1 trong 3 sinh viên nói trên đến Phan Rang nếu xét
thấy kinh tế hơn. Biết rằng Vinh không thể về Sông Cầu và chi phí để ổn định chỗ ở
cho Giang đi Phan Rang 1.000.000 đ, Sơn đi Phan Rang 800.000 đ, Vinh đi Phan
Rang 1.800.000 đ. Nếu cần cử 1 sinh viên đi Phan Rang thì nên cử ai đi? 94