Lập lịch trình công việc (scheduling)

11 BÀI 4. LẬP LỊCH TRÌNH CÔNG VIỆC (SCHEDULING) 1. Khái quát vê ̀ lập lịch trình công việc 2. Sơ đồ Gantt 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính 4. Xác định trình tự công việc 5. Trình tự công việc qua hai trung tâm 6. Trình tự công việc có tính đến thời gian thiết đặt máy móc 2 1. Khái quát về lập lịch trình công việc − Lập lịch trình công việc liên quan đến việc tính toán thời gian cho việc sử dụng các nguồn lực của tô ̉ chức. Cụ thê ̉, nó tập trung vào hai vấn đê ̀: 9Phân công công việc. 9Xác định trình tự công việc. − Mục đích của việc lập lịch trình công việc là đạt được sự hiệu quả trong việc sử dụng các nguồn lực va ̀ giảm thiểu thời gian của quá trình sản xuất hoặc thời gian chờ đợi của khách hàng. 9Nguồn lực: nhân viên, máy móc, cơ sở hạ tầng. 3 1. Khái quát về lập lịch trình công việc (tiếp) CÔNG SUẤT KẾ HOẠCH TRUNG HẠN LẬP LỊCH TRÌNH CÔNG VIỆC Quyết định dài hạn liên quan đến quy mô của cơ sở hạ tầng, máy móc thiết bị. Các quyết định liên quan đến việc sử dụng chụng va ̀ kết hợp các nguồn lực như nhân sự, kho bãi, hợp đồng thuê ngoài⇒ đáp ứng nhu cầu trung hạn. Các quyết định liên quan đến trình tự va ̀ khối lượng công việc hàng ngày. Đây là bước cuối cùng trước khi đạt được sản phẩm đầu ra thực sự. 4 1. Khái quát về lập lịch trình công việc (tiếp) − Nhiệm vụ lập lịch trình công việc phu ̣ thuộc cơ bản vào khối lượng sản phẩm đầu ra của hê ̣ thống: 9Hê ̣ thống khối lượng đầu ra cao (dây chuyền chuyên môn hóa cao). 9Hê ̣ thống khối lượng đầu ra trung bình (sản xuất theo lô, ngắt quãng). 9Hê ̣ thống khối lượng đầu ra thấp (các phân xưởng sản xuất theo từng yêu cầu cụ thê ̉). 25 1. Khái quát về lập lịch trình công việc (tiếp) − Hê ̣ thống khối lượng đầu ra cao. 9⇒ Phân công khối lượng công việc tới các trạm công việc cụ thê ̉. 9Mục đích: dòng công việc đi qua hê ̣ thống là hiệu quả nhất ⇒ các trạm công việc có thời gian xấp xỉ bằng nhau ⇒ hiệu dụng cao với lao động va ̀ thiết bị. 9⇒ Bản chất lặp đi lặp lại ⇒ trình tự công việc được xác định ngay từ khâu thiết kê ́, ít phải quan tâm vê ̀ sau. 9⇒ Đa ̃ mô ta ̉ trong bài Bố trí mặt bằng. 6 1. Khái quát về lập lịch trình công việc (tiếp) − Hệ thống khối lượng đầu ra trung bình. 9 ⇒ Yêu cầu đối với khối lượng đầu ra không đu ̉ lớn⇒ sản xuất theo những lô hàng có quy mô vừa phải. 9 Hai vấn đê ̀ cần quan tâm: ¾Kích thước lô hàng sản xuất, ¾ Thời gian tới hạn cho mỗi sản phẩm. • Thời gian tới hạn = số lượng hiện có/mức sử dụng. • Sản phẩm A có thời gian tới hạn là 4 tuần; B: 1,2 tuần; C: 2,5 tuần⇒ thứ tự công việc sẽ là B - C - A − Hệ thống khối lượng đầu ra thấp. ⇒ Phức tạp vì yêu cầu công việc là không biết trước. Các phần sau đây sẽ mô ta ̉ chi tiết hệ thống này. up p H DSQ −= 2 0 7 2. Sơ đô ̀ Gantt (hai loại) − Sơ đồ khối lượng công việc và sơ đồ trình tự công việc. − Sơ đồ khối lượng công việc. − :Không nhàn rỗi (bảo dưỡng, sửa chữa) − Trong nhiều trường hợp, có thê ̉ đê ̉ một khoảng thời gian trống (dự phòng khi công việc kéo dài hơn dự kiến). Một số trường hợp khác, có thể dồn công việc lại đê ̉ giải phóng hẳn một trung tâm. D C B A Thứ 6Thứ 5Thứ 4Thứ 3Thứ 2Trung tâm công việc Công việc10 Công việc 7Công việc 6Công việc 1 Công việc 3 Công việc 7Công việc 3 Công việc 4Công việc 1 8 2. Sơ đô ̀ Gantt (tiếp) − Sơ đồ trình tự công việc. − Sơ đồ Gantt là một công cụ trực quan, đơn giản trong việc lập lịch trình công việc. Tuy nhiên cả hai loại sơ đô ̀ đều không đê ̀ cập tới yếu tố chi phí. Sản xuất Nhân sự Máy móc Mặt bằng Chuẩn bị 7654321 Tháng Công việc Lập dự án Phê duyệt Giải phóng MB Xây dựng Đặt mua Lắp đặt Vận hành thử Đào tạoTuyển dụng 39 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính − Nhiệm vụ: phân công các công việc tới các nguồn lực (máy móc, người xử lý) − Mục đích: tìm phương án cực tiểu hóa chi phí. − Giả định: mỗi công việc chỉ được phân tới một máy duy nhất (không có máy nào xử lý hai công việc và ngược lại). − Ví dụ: 9121054 67533 1011762 42681Công việc DCBA Máy 10 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính (tiếp) − Bước 1. Lấy các hàng trừ đi giá trị nhỏ nhất trong hàng đó, từ đó tạo ra một bảng mới. − Bước 2. Từ bảng mới, lấy các cột trừ đi giá trị nhỏ nhất trong cột ⇒ tạo ra một bảng mới khác. 47504 34203 45102 20461Công việc DCBA Máy 27404 14103 25002 00361Công việc DCBA Máy 11 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính (tiếp) − Bước 3. Kiểm tra xem đó có phải là sự phân công công việc tối ưu chưa. Bằng cách: vẽ một số lượng tối thiểu các đường thẳng đi qua tất cả cá giá trị 0. Nếu số lượng này bằng số hàng, đó là giải pháp tối ưu. Trong trườnghowpj này, chuyển đến bước 6. 27404 14103 25002 00361Công việc DCBA Máy 12 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính (tiếp) − Bước 4. Nếu số lượng các đường thẳng nhỏ hơn số hàng, ⇒ cần điều chỉnh: 9 Lấy tất cả các số của vùng không chứa giá trị 0 trừ đi giá trị nhỏ nhất của vùng đó. 9 Cộng giá trị nhỏ nhất vừa tìm được vào giá trị nằm trên giao điểm các đường thẳng. − Bước 5. Lặp lại bước 3, bước 4 cho tới khi bảng tối ưu xuất hiện. 16304 03003 25012 00371Công việc DCBA Máy 16304 03003 25012 00371Công việc DCBA Máy 413 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính (tiếp) − Bước 6. Thực hiện việc phân công. Bắt đầu với những hàng, những cột có duy nhất một giá trị 0 và triển khai cho các hàng các cột tiếp theo. − Trong giải pháp trên: công việc 1 ⇒ máy C; công việc 2 ⇒ máy B; công việc 3 ⇒ máy D; công việc 4 ⇒ máy A. − Tổng chi phí = 2 + 7 + 6 + 5 = 20. Tại sao?? − Khi số liệu là lợi nhuận?? 16304 03003 25012 00371Công việc DCBA Máy 14 4. Xác định trình tự công việc − Mục đích: xác định trình tự tiến hành các công việc đang chờ được xử lý tại một phân xưởng/trung tâm − Các nguyên tắc: 9 FCFS (first come, first served): đến trước, xử lý trước. ⇒ Xử lý công việc theo thứ tự đến của chúng. 9SPT (shortest processing time): thời gian xử lý ngắn nhất. ⇒ Các công việc có thời gian xử lý ngắn nhất được tiến hành trước. 15 4. Xác định trình tự công việc (tiếp) 9DD (due date): ngày đến hạn. ⇒ Các công việc có thời gian đến hạn (thời gian giao hàng cho khách) ngắn nhất được xử lý trước. 9S/O (slack per operation): thời gian trì hoãn cho phép trên mỗi hoạt động. ⇒ Đòi hỏi phải tính thời gian trì hoãn cho phép trên mỗi hoạt động. ⇒ Công việc nào có thời gian trì hoãn cho phép trên mỗi hoạt động ngắn nhất sẽ được xử lý trước. 16 4. Xác định trình tự công việc (tiếp) − Ví dụ: thời gian xử lý và ngày đến hạn của 6 công việc đang chờ tại một trung tâm được cho như dưới đây. Xác định trình tự xử lý theo: FCFS; SPT; DD. 1812F 155E 1710D 44C 168B 72A Thời gian đến hạn (ngày)Thời gian xử lý (ngày)Công việc 517 4. Xác định trình tự công việc (tiếp) − Nguyên tắc FCFS. ⇒ Trình tự: A-B-C-D-E-F − Thời gian hoàn thiện trung bình = 120/6 = 20 ngày. − Thời gian muộn trung bình = 54/6 = 9 ngày. 5412041Tổng 23184112F 1415295E 7172410D 104144C 016108B 0722A Số ngày muộn (5) = (3) – (4) Ngày đến hạn (4) Dòng thời gian (3) Thời gian xử lý (2) Công việc (1) 18 4. Xác định trình tự công việc (tiếp) − Nguyên tắc SPT. ⇒ Trình tự: A-C-E-B-D-F − Thời gian hoàn thiện trung bình = 108/6 = 18 ngày. − Thời gian muộn trung bình = 40/6 = 6,67 ngày. 4010841Tổng 23184112F 12172910D 316198B 015115E 2464C 0722A Số ngày muộn (5) = (3) – (4) Ngày đến hạn (4) Dòng thời gian (3) Thời gian xử lý (2) Công việc (1) 19 4. Xác định trình tự công việc (tiếp) − Nguyên tắc DD. ⇒ Trình tự: C-A-E-B-D-F − Thời gian hoàn thiện trung bình = 110/6 = 18,33 ngày. − Thời gian muộn trung bình = 38/6 = 6,33 ngày. 3811041Tổng 23184112F 12172910D 316198B 015115E 0762A 0444C Số ngày muộn (5) = (3) – (4) Ngày đến hạn (4) Dòng thời gian (3) Thời gian xử lý (2) Công việc (1) 20 4. Xác định trình tự công việc (tiếp) − So sánh ba phương án. − Một vài nhận xét. 9SPT luôn vượt trội xét trên khía cạnh cực tiểu dòng thời gian ⇒ thời gian hoàn thiện trung bình là nhỏ nhất ⇒ công việc tồn đọng trong quy trình là nhỏ nhất (đẩy nhanh công việc ra khỏi hệ thống). 6,3318,33DD 6,6718SPT 9 (ngày)20 (ngày)FCFS Thời gian muộn trung bình Thời gian hoàn thiện trung bìnhNguyên tắc 621 4. Xác định trình tự công việc (tiếp) − Một vài nhận xét (tiếp). 9 SPT cũng tạo ra thời gian muộn tương đối nhỏ vì đối với các công việc có thời gian xử lý dài thì thời gian hẹn giao hàng cho khách cũng thường kéo dài hơn. 9 Nhược điểm của SPT là các công việc có thời gian xử lý dài thường phải chờ (đặc biệt khi các công việc ngắn liên tục được đưa vào hệ thống). Điều này có khắc phục bằng cách: sau một thời gian nhất định, các công việc dài phải được đưa vào xử lý. 9 DD có ưu điểm xét trên khía cạnh cực tiểu thời gian muộn của khách. 22 4. Xác định trình tự công việc (tiếp) − Một vài nhận xét (tiếp). 9 Nhược điểm chính của DD là không xét đến thời gian xử lý. Như vậy, một số công việc có thể phải chờ rất lâu (trong khi, nếu được xử lý, nó sẽ được giải phóng nhanh chóng khỏi hệ thống). 9 Nhược điểm của FCFS là không hề xét đến yếu tố thời gian trong trình tự xử lý ⇒ giải phóng công việc chậm, thời gian chờ của khách dài. Tuy nhiên, nó có ưu điểm là đảm bảo được tính công bằng ⇒ thường được sử dụng trong những hệ thống dịch vụ liên quan trực tiếp đến khách hàng. 9 ⇒ Mỗi nguyên tắc có điểm mạnh riêng ⇒ nhà quản lý cần cân nhắc và lựa chọn nguyên tắc phù hợp nhất với hoàn cảnh cụ thể của doanh nghiệp. 23 4. Xác định trình tự công việc (tiếp) − Ví dụ về nguyên tắc S/O. Thời gian xử lý được xem như thời gian xử lý còn lại. 18 15 17 4 16 7 Thời gian đến hạn (ngày) 2 4 2 5 6 3 Số các hoạt động còn lại 12F 5E 10D 4C 8B 2A Thời gian xử lý còn lại (ngày) Công việc 24 4. Xác định trình tự công việc (tiếp) − Như vậy, trình tự theo S/O: C-B-A-E-D-F. − Căn cứ vào trình tự này, ta có thể tính được thời gian hoàn thiện trung bình và thời gian muộn trung bình. ⇒ So sánh với các nguyên tắc khác. 2 4 2 5 6 3 Số các hoạt động còn lại (5) 18 15 17 4 16 7 Thời gian đến hạn (3) 12 5 10 4 8 2 Thời gian xử lý còn lại (2) F E D C B A Công việc (1) 53,006 42,5010 63,507 100 21,338 31,675 Thứ tự (7) Tỷ số (6) = (4)/(5) Thời gian trì hoãn cho phép (4) = (3) – (2) 725 5. Trình tự công việc qua hai trung tâm − Kỹ thuật này được sử dụng nhằm cực tiểu hóa thời gian hoàn thiện một nhóm công việc được tuần tự xử lý qua hai trung tâm hoặc hai máy. Nó cũng cực tiểu thời gian nhàn rỗi tại hai trung tâm. − Một số giả định: 9 Tất cả các công việc phải tuân theo trình tự hai bước. 9 Thời gian xử lý công việc phải độc lập với trình tự xử lý công việc. Hiểu như thế nào?? 26 5. Trình tự công việc qua hai trung tâm (tiếp) − Các bước để xác định trình tự tối ưu: 9 Bước 1. Lên danh sách các công việc và thời gian tại mỗi trung tâm. 9 Bước 2. Lựa chọn công việc có thời gian ngắn nhất. Nếu thời gian này rơi vào trung tâm 1, công việc đó được xử lý đầu tiên; nếu thời gian này rơi vào trung tâm 2, công việc đó dược xử lý cuối cùng. 9 Bước 3. Loại bỏ công việc vừa phân công ra khỏi những tính toán tiếp theo. 9 Bước 4. Lặp lại bước 2, bước 3 cho đến khi các công việc được phân công hết. 27 5. Trình tự công việc qua hai trung tâm (tiếp) − Ví dụ: một nhóm 6 công việc được tuần tự xử lý qua 2 trung tâm. Thời gian cho như bên dưới. Hãy xác định trình tự xử lý tối ưu. 1512F 86E 72D 98C 34B 55A Trung tâm 2Trung tâm 1 Thời gian xử lý (giờ) tại Công việc 28 5. Trình tự công việc qua hai trung tâm (tiếp) − Công việc D có thời gian ngắn nhất (2 giờ) rơi vào trung tâm 1 ⇒ Công việc D được xử lý đầu tiên; Loại bỏ D ra khỏi những tính toán tiếp theo. − Công việc B có thời gian ngắn nhất tiếp theo (3 giờ) rơi vào trung tâm 2 ⇒ Công việc B được xử lý cuối cùng; Loại bỏ B ra khỏi những tính toán tiếp theo. BD 654321 829 5. Trình tự công việc qua hai trung tâm (tiếp) − Các công việc còn lại: − Công việc có thời gian ngắn nhất tiếp theo là A (5 giờ) và bằng nhau tại cả hai trung tâm. ⇒ Tùy ý phân A cuối cùng hoặc đầu tiên. Giả sử phân A cuối cùng. Công việc 1512F 86E 98C 55A Trung tâm 2Trung tâm 1 BAD 654321 30 5. Trình tự công việc qua hai trung tâm (tiếp) − Sau khi loại bỏ A, các công việc còn lại như sau: − Công việc có thời gian ngắn nhất tiếp theo là E (6 giờ) rơi vào trung tâm 1. ⇒ E được xử lý đầu tiên tiếp theo. − Lặp lại các bước trên, ta có trình tự: Công việc 1512F 86E 98C Trung tâm 2Trung tâm 1 BAED 654321 BAFCED 654321 31 5. Trình tự công việc qua hai trung tâm (tiếp) − Tính thời gian hoàn thiện và thời gian nhàn rỗi. − Trình tự trên cho tổng thời gian xử lý nhỏ nhất. Tỷ lệ thời gian nhàn rỗi tại trung tâm 2 = 4/51 = 7,84%. BACE FDTrung tâm 2 BAFCEDTrung tâm 1 Thời gian 0 2 8 16 28 33 37 0 2 9 17 26 28 43 48 51Thời gian Thời gian nhàn rỗi Nhàn rỗi hoặc bảo dưỡng 32 6. Trình tự công việc có tính đến thời gian thiết đặt máy móc − Các phần trước đều giả định rằng, thời gian thiết đặt máy móc là độc lập với trình tự xử lý công việc. − Trong nhiều trường hợp, giả định này không đúng. Phần này sẽ xét đến trình tự công việc khi thời gian thiết đặt máy là phụ thuộc vào trình tự xử lý với mục tiêu là cực tiểu hóa thời gian thiết đặt máy. -352C 4-12B 26-3ANếu công việc đứng trước là CBA Thời gian thiết đặt máy của các công việc theo sau tương ứngThời gian thiết đặt máy (giờ) 933 6. Trình tự công việc có tính đến thời gian thiết đặt máy móc (tiếp) − Trình tự B – A – C là tốt nhất. Ví dụ trên là đơn giản vì chỉ có 6 lựa chọn (3!). Trong những trường hợp khác, có thể cần sự hỗ trợ của máy tính (VD: 6! = 720 phương án). 62 + 3 + 1C – B – A 132 + 5 + 6C – A – B 112 + 4 + 5B – C – A 52 + 1 + 2B – A – C 83 + 2 + 3A – C – B 133 + 6 + 4A – B – C TổngThời gian thiết đặt máyTrình tự 34 Tóm tắt lại bài học 1. Khái quát về lập lịch trình công việc 2. Sơ đồ Gantt ⇒ phân công công việc và trình tự công việc. 3. Phân công công việc dựa trên phương pháp quy hoạch tuyến tính ⇒ cho giải pháp tối ưu khi phân bổ công việc về các nguồn lực. 4. Xác định trình tự công việc: FCFS; SPT; DD; S/O ⇒ tùy theo hoàn cụ thể mà lựa chọn tiêu chí thích hợp. 5. Trình tự công việc qua hai trung tâm ⇒ cực tiểu tổng thời gian xử lý và thời gian nhàn rỗi. 6. Trình tự công việc có tính đến thời gian thiết đặt máy móc ⇒ cực tiểu thời gian thiết đặt máy khi yếu tố này phụ thuộc vào trình tự công việc. 35 Một số câu hỏi − Có máy loại sơ đồ Gantt? Tác dụng của từng loại? − Giả định của việc phân công công việc theo phương pháp quy hoạch tuyến tính là gì? Mục đích của việc phân công này?? − FCFS, SPT, DD, S/O là gì?? Chỉ ra ưu, nhược điểm của mỗi nguyên tắc. − Mục đích của việc xác định trình tự công việc qua hai trung tâm là gì? Giả định cần lưu ý?? − Yêu cầu cơ bản của việc xác định trình tự khi thời gian thiết đặt máy phụ thuộc vào trình tự này là gì?