Nhà quản lý doanhnghiệp muốn quá trình sản xuất của công ty đạt hiệu quả thì cần có những hành động dự báo, thiết kế quy trình và sắp xếp thứ tự công việc, phân công người hoặc nhómngười
CƠ SỞ LÝ THUYẾT
ĐIỀU ĐỘ SẢN XUẤT
Điều độ sản xuất là quá trình tổ chức và chỉ đạo triển khai lịch trình sản xuất theo kế hoạch đã thiết kế, nhằm đạt được mục tiêu sản xuất và kinh doanh của doanh nghiệp Để đảm bảo hiệu quả trong sản xuất, nhà quản lý cần thực hiện dự báo, thiết kế quy trình, sắp xếp thứ tự công việc và phân công nhiệm vụ cho từng cá nhân hoặc nhóm thực hiện trên mỗi máy trong dây chuyền sản xuất, từ đó đáp ứng tốt nhất tiến độ sản xuất.
Điều độ sản xuất là quá trình quản lý các hoạt động lập kế hoạch và thiết kế quy trình nhằm đảm bảo tiến độ dự án và phân công lao động hiệu quả với nguồn lực hạn chế Nó giúp giảm thiểu hao phí nguyên vật liệu, nhân lực và máy móc trong sản xuất, từ đó nâng cao chất lượng sử dụng nguồn lực, giải quyết các vấn đề trong sản xuất và rút ngắn thời gian sản xuất cũng như thời gian chờ đợi của khách hàng Quy trình điều độ sản xuất được thực hiện qua 5 bước cụ thể.
Lên lịch trình sản xuất bao gồm việc xác định số lượng và khối lượng công việc, thời gian hoàn thành, cũng như thời điểm bắt đầu và kết thúc các công việc Đồng thời, cần xác định thứ tự thực hiện các công việc để đảm bảo quy trình sản xuất diễn ra hiệu quả.
Dự trù số lượng máy móc, nguyên vật liệu và nhân lực cần thiết để hoàn thành khối lượng công việc được đặt ra trong lịch trình sản xuất.
Điều phối, phân chia công việc và thời gian hoàn thành cho từng bộ phận, từng lao động và từng thiết bị.
Để tối ưu hóa quy trình sản xuất trong nhà máy, cần sắp xếp thứ tự công việc tại từng khu vực và các máy móc một cách hợp lý Mục tiêu là giảm thiểu thời gian ngừng máy và thời gian chờ đợi trong quá trình chế biến sản phẩm, từ đó nâng cao hiệu quả sản xuất.
Thực hiện kiểm tra và giám sát định kỳ là cần thiết để phát hiện sớm các sự cố có thể ảnh hưởng đến tiến độ sản xuất và chất lượng sản phẩm Điều này giúp đưa ra các biện pháp xử lý kịp thời, đảm bảo quá trình sản xuất diễn ra suôn sẻ và đạt yêu cầu.
ĐIỀU ĐỘ DÂY CHUYỀN
Điều độ dây chuyền là mô hình thiết kế trong đó máy móc được sắp xếp theo chuỗi Các công việc được thực hiện bắt đầu từ máy đầu tiên, tiếp tục qua các máy trung gian, và kết thúc tại máy cuối cùng trước khi sản phẩm hoàn thành.
Trong một chuỗi công việc, các hoạt động có thể được phân chia và thực hiện trên những máy khác nhau Đối với quy trình điều độ theo chuyền với nhiều chuyển, việc thực hiện công việc trở nên đa dạng hơn Trong trường hợp này, không nhất thiết phải yêu cầu các máy liền kề hoạt động mà có thể sắp xếp các công việc tại các chuyền để đáp ứng nhu cầu sản xuất và giao hàng.
Một số giải thuật được áp dụng để giải quyết các bài toán về điều độ dây chuyển:
Giải thuật CDS - Campbell, Dudek, Smith
GIẢI THUẬT PALMER
Giải thuật PALMER được sử dụng để tối ưu hóa quy trình điều độ dây chuyền với số lượng máy lớn hơn hai (m>2) Bài toán giả định có n công việc độc lập chờ xử lý, mỗi công việc cần thực hiện qua m giai đoạn trên m máy Các điều kiện bao gồm thời gian chuẩn bị không phụ thuộc vào thời gian xử lý, nội dung công việc đã được xác định trước, các máy luôn trong trạng thái sẵn sàng và các công việc không có sự kết nối Mục tiêu chính của bài toán là tối thiểu hóa thời gian xử lý công việc.
Các bước thực hiện giải thuật:
Bước 1 Ứng với mỗi công việc j, xác định chỉ số: sj=(m-1)tj,m+(m-3)tj,m-1+(m-5)tj,m-2+ +(3-m)tj2+(1-m)tj,1
Bước 2 Kế hoạch điều độ thỏa: s[1]s[1] s[1]
GIẢI THUẬT CDS – CAMPELL, DUDEK, SMITH
Bài toán điều độ trên dây chuyền với m máy được thực hiện qua (m-1) giai đoạn bằng cách áp dụng giải thuật Johnson cho 2 máy nhằm xác định kế hoạch điều độ hiệu quả Giải thuật CDS sẽ khắc phục những hạn chế của giải thuật Johnson khi lập kế hoạch cho các công việc cần xử lý qua nhiều máy.
Các giai đoạn được thực hiện như sau:
Giai đoạn 1: Xác định t'j1=tj1và t'j2=tjm
Dùng giải thuật Johnson cho 2 máy để xác định kế hoạch điều độ.
Giai đoạn 2: Xác định t'j1=tj1+tj2và t'j2=tj,m-1+tjm
Dùng giải thuật Johson cho 2 máy để xác định kế hoạch điều độ.
Giai đoạn (m – 1): o t'j1=tj1+tj2+ +tj,m-1 o t'j2=tj2+ +tj,m-1+tj,m
Dùng giải thuật Johnson cho 2 máy để xác định kế hoạch điều độ.
ÁP DỤNG GIẢI QUYẾT YÊU CẦU BÀI TOÁN
YÊU CẦU BÀI TOÁN
Phân xưởng sản xuất hiện đang tiếp nhận 10 đơn hàng từ Phòng Kinh doanh cần hoàn thành Mỗi đơn hàng sẽ lần lượt được xử lý qua 4 máy, với thời gian xử lý tại mỗi máy được xác định cụ thể cho từng đơn hàng, theo bảng thời gian đã được cung cấp (đơn vị tính là giờ).
I II III IV V VI VII VIII IX X t j1 5 9 2 4 6 9 8 12 5 5 t j2 2 4 5 6 8 4 9 8 2 7 t j3 7 8 1 3 1 8 3 2 11 10 t j4 11 4 10 9 5 8 9 5 4 9
1 Với giải thuật PALMER Nhóm hãy xác định chỉ số S j và trật tự gia công tương ứng với trật vừa xác định?
2 Nhóm hãy vẽ sơ đồ Gantt của tất cả các máy ứng với trật tự được xác định trong câu 1.
3 Hãy xác định trật tự gia công theo GIẢI THUẬT CDS – Campbell, Dudek, Smith với thời gian MÁY I là (máy 1 + máy 2) và thời gian MÁY II là (máy 3 + máy 4). Nếu trật này khác với trật tự trong câu 1 Hãy vẽ lại sơ đồ Gantt của tất cả các máy.
4 So sánh sự khác biệt giữa 2 sơ đồ Gantt.
5 Những nhận xét chung/mở rộng vấn đề của nhóm về lời giải đạt được.
THỰC HIỆN BÀI TOÁN
1 Xác định trật tự giai công theo giải thuật PALMER
Theo giải thuật Palmer ta có công thức xác định chỉ số S j như sau: s j = (m - 1) tjm + (m - 3)t j, m-1 + (m - 5)t j, m-2 + ⋯ + (- m + 3)t j2 + (- m + 1)t j1
Mỗi đơn hàng lần lượt đi qua 4 máy nên m=4, khi đó ta có chỉ số sj như sau: s j = (4 - 1)t j4 + (4 - 3)t j3 + (-4 + 3)t j2 + (-4 + 1)t j1 = 3t j4 + t j3 - t j2 - 3t j1
Ta có chỉ số s j ứng với từng đơn hàng: s 1 = 3 × t 14 + t 13 – t 12 – 3 × t 11 = 3 × 11 + 7 – 2 – 3 × 5 = 23 s 2 = 3 × t 24 + t 23 – t 22 – 3 × t 21 = 3 × 4 + 8 – 4 – 3 × 9 = -11 s 3 = 3 × t 34 + t 33 – t 32 – 3 × t 31 = 3 × 10 + 1 – 5 – 3 × 2 = 20 s 4 = 3 × t 44 + t 43 – t 42 – 3 × t 41 = 3 × 9 + 3 – 6 – 3 × 4 = 12 s 5 = 3 × t 54 + t 53 – t 52 – 3 × t 51 = 3 × 5 + 1 – 8 – 3 × 6 = -10 s 6 = 3 × t 64 + t 63 – t 62 – 3 × t 61 = 3 × 8 + 8 – 4 – 3 × 9 = 1 s 7 = 3 × t 74 + t 73 – t 72 – 3 × t 71 = 3 × 9 + 3 – 9 – 3 × 8 = -3 s 8 = 3 × t 84 + t 83 – t 82 – 3 × t 81 = 3 × 5 + 2 – 8 – 3 × 12 = -27 s 9 = 3 × t 94 + t 93 – t 92 – 3 × t 91 = 3 × 4 + 11 – 2 – 3 × 5 = 6 s 10 = 3 × t 104 + t 103 – t 102 – 3 × t 101 = 3 × 9 + 10 – 7 – 3 × 5 = 15
Dựa trên chỉ số của 10 đơn hàng, thứ tự các chỉ số được sắp xếp từ lớn đến nhỏ là: s1 > s3 > s10 > s4 > s9 > s6 > s7 > s5 > s2 > s8 Từ thứ tự này, ta có thể xác định trật tự gia công của các đơn hàng như sau: I - III - X - IV - IX - VI - VII - V - II - VIII.
2 Sơ đồ gantt của trật tự đơn hàng theo giải thuật PALMER
Hình 1 Sơ đồ gantt theo giải thuật PALMER
3 Xác định trật tự gia công theo giải thuật CDS
Dùng giải thuật Johnson cho 2 máy để xác định kế hoạch điều độ:
I II III IV V VI VII VIII IX X t ji’ 7 13 7 10 14 13 17 20 7 12 t j2’ 18 12 11 12 6 16 12 7 15 19
Bước 2: Xóa các đơn hàng đã được xếp thứ tự khỏi danh sách đơn hàng chưa được xử lý và lặp lại quy trình từ bước 1 cho đến khi tất cả đơn hàng đều được sắp xếp hoàn chỉnh.
Bảng 1 Bảng sắp xếp kế hoạch điều độ theo giải thuật CDS
Giai đoạn Đơn hàng chưa sắp xếp thứ tự min{t j1’
;t j2’ } Đơn hàng được sắp xếp thứ tự
2 I, II, III, IV, VI, VII,
3 II, III, IV, VI, VII, tVIII2 = 7 VIII I x x x x x x x
4 II, III, IV, VI, VII,
5 II, III, IV, VI, VII,
6 II, IV, VI, VII, X tIV1 = 10 IV I IX III IV x x x x
7 II, VI, VII, X tVII2 = 12 VII I IX III IV x x x
8 II, VI, X tII2 = 12 II I IX III IV x x II
9 VI, X tX1 = 12 X I IX III IV X x II
10 VI tVI1 = 13 VI I IX III IV X VI
Xác định thời gian hoàn thành cho từng giai đoạn công việc là yếu tố quan trọng trong quản lý sản xuất và lập kế hoạch Thông tin về thời gian gia công trên mỗi máy không chỉ giúp hiểu rõ quy trình sản xuất mà còn hỗ trợ trong việc ưu tiên đơn hàng Ví dụ, với thời gian gia công trên máy I là 7 giờ cho ba đơn hàng I, III và IX, nhóm cần xem xét thời gian gia công trên máy II để xác định thứ tự ưu tiên Cụ thể, thời gian trên máy II lần lượt là 18 giờ cho đơn hàng I, 11 giờ cho III và 15 giờ cho IX, do đó thứ tự ưu tiên sẽ là I, IX, III, sắp xếp theo thời gian gia công trên máy II từ lớn đến nhỏ.
Nhóm đã ưu tiên xử lý các đơn hàng dựa trên thời gian hoàn thành của từng giai đoạn, yêu cầu sự tỉ mỉ trong việc thu thập và phân tích thông tin Việc tổ chức dữ liệu rõ ràng giúp dễ dàng hiểu mối quan hệ giữa các giai đoạn công việc Để xác định thứ tự ưu tiên, nhóm không chỉ dựa vào thời gian gia công mà còn xem xét mức độ ưu tiên của đơn hàng và khả năng vận hành của máy móc Thời gian hoàn thành là yếu tố quan trọng trong quy trình lập kế hoạch, giúp nhóm xây dựng chiến lược sản xuất hiệu quả Chẳng hạn, khi thời gian gia công trên máy II là 12 giờ cho hai đơn hàng II và VII, nhóm cần so sánh thời gian trên máy I để quyết định thứ tự ưu tiên.
17 giờ, từ đó thứ tự sẽ là II, VII (sắp xếp theo thời gian gia công từ ít đến nhiều trên máy I).
Nhóm không chỉ tập trung vào thông tin thời gian gia công mà còn chú trọng tổ chức và hệ thống hóa dữ liệu hiệu quả Điều này giúp tránh mất mát thông tin và đảm bảo mọi thành viên dễ dàng hiểu và sử dụng khi cần Khả năng tổ chức và quản lý thông tin của nhóm đã nâng cao độ chính xác và hiệu quả trong quá trình ra quyết định.
Phương pháp giải thuật CDS của Campbell, Dudek, và Smith đã giúp nhóm xác định thứ tự ưu tiên cho các đơn hàng trong quy trình sản xuất Qua đó, nhóm tính toán thời gian hoàn thành trên máy I và máy II, góp phần tối ưu hóa quy trình và đảm bảo các quyết định sản xuất được thực hiện một cách chính xác.
Vậy trật tự gia công theo giải thuật CDS: I - IX - III - IV - X - VI - II - VII - VIII -
Hình 2 Sơ đồ Gantt trật tự gia công theo giải thuật CDS → Makespan theo phương pháp CDS - Campbell, Dudek Smith là: 88 giờ
4 So sánh sự khác biệt giữa 2 sơ đồ gantt
Tiêu chí so sánh Giải thuật Palmer Giải thuật CDS
Trật tự gia công I – III – X – IV – IX – VI – VII
Thời gian trống Máy 2: 18 giờ (0 – 5, 27 – 30, 34
=> Tổng thời gian trống: 53 giờ
=> Tổng thời gian trống: 56 giờ
Tổng số lần chờ trên 4 Máy 2: 4 lần
Máy 2: 5 lầnMáy 3: 4 lần máy Máy 4: 1 lần
=> Tổng số lần chờ: 10 lần
=> Tổng số lần chờ: 10 lần
Chênh lệch thời điểm kết thúc của 4 máy
Giữa máy 1 và máy 4: 23 giờ Giữa máy 2 và máy 4: 15 giờ Giữa máy 3 và máy 4: 13 giờ
=> Tổng chênh lệch thời điểm kết thúc của 4 máy: 51 giờ
Giữa máy 1 và máy 4: 23 giờ Giữa máy 1 và máy 4: 13 giờ Giữa máy 1 và máy 4: 12 giờ
=> Tổng chênh lệch thời điểm kết thúc của 4 máy: 48 giờ
Giải thuật Palmer xác định trật tự gia công dựa trên chỉ số Sj của từng đơn hàng, xếp hạng các đơn hàng theo độ dốc của thời gian gia công Phương pháp này có thể tạo ra thứ tự không đồng đều, đặc biệt khi công việc được phân phối giữa các máy khác nhau Kết quả là lịch trình có thể dẫn đến tình trạng tập trung công việc tại một số máy nhất định.
Giải thuật CDS thực hiện phân tích chi tiết bằng cách chia bài toán thành các bài toán con với máy giả định, từ đó tối ưu hóa thứ tự gia công dựa trên thời gian hoàn thành của từng giai đoạn Phương pháp này giúp phân phối công việc một cách cân đối, giảm thiểu tình trạng quá tải và thời gian chờ trên các máy, tối ưu hóa hiệu quả quy trình sản xuất.
Thời gian nhàn rỗi trên các máy:
- Giải thuật Palmer ghi nhận tổng thời gian nhàn rỗi trên các máy là 56 giờ, trong khi
CDS chỉ có 53 giờ, cho thấy sự tối ưu hóa tài nguyên sản xuất hiệu quả Sự chênh lệch 3 giờ này giúp giảm thiểu thời gian máy nhàn rỗi và nâng cao hiệu suất tổng thể Bằng cách phân tích thứ tự gia công một cách linh hoạt, CDS có khả năng sắp xếp lịch trình hiệu quả, hạn chế tình trạng chờ đợi không cần thiết trên các máy.
Số lần chờ đợi trên 4 máy:
Cả hai giải thuật đều ghi nhận 10 lần chờ đợi trong quá trình gia công, nhưng cách phân bổ thời gian chờ lại khác nhau Giải thuật Palmer tạo ra lịch trình tập trung vào một số máy, dẫn đến thời gian chờ lâu hơn trên các máy khác Ngược lại, CDS phân phối thời gian chờ đều hơn, giúp các máy hoạt động liên tục và hiệu quả, giảm thiểu gián đoạn trong sản xuất.
Chênh lệch thời gian kết thúc giữa các máy:
Giải thuật CDS cho thấy khả năng cân bằng lịch trình công việc giữa các máy tốt hơn so với giải thuật Palmer, với tổng chênh lệch thời gian kết thúc chỉ là 48 giờ, trong khi của Palmer là 51 giờ Việc phân bổ đều công việc giúp giảm thiểu thời gian chờ đợi cuối cùng, đảm bảo các máy hoàn thành công việc gần như đồng thời, từ đó tối ưu hóa quá trình sản xuất và giảm thiểu lãng phí thời gian.
5 Nhận xét chung / mở rộng vấn đề về lời giải đạt được
5.1 Mở rộng vấn đề theo giải thuật CDS 1
Xét giai đoạn 1: t’j1 = tj1 và t’j2 = tj4
Bảng 2: Thời gian thực hiện CDS giai đoạn 1
Công việc j I II III IV V VI VII VII IX X t’j1 = tj1 5 9 2 4 6 9 8 12 5 5 t’j2 = tj4 11 4 10 9 5 8 9 5 4 9
→ Vậy trật tự gia công theo Johnson là: III - IV - I - X - VII - VI - V - VIII - IX - II
5.1.1 Sơ đồ Gantt mở rộng vấn đề theo giải thuật CDS 1
Hình 3: Sơ đồ Gantt theo giải thuật CDS 1
5.1.2 So sánh lời giải của 3 giải thuật PALMER, CDS 2 và CDS 1
Trật tự sắp xếp đơn hàng của 3 giải thuật:
PALMER: I - III - X - IV - IX - VI - VII - V - II - VIII
CDS 2: I - IX - III - IV - X - VI - II - VII - VIII - V
CDS 1: III - IV - I - X - VII - VI - V - VIII - IX - II
Bảng 3: So sánh tổng thời gian chờ, khoảng thời gian chờ và thời gian hoàn thành của 3 phương pháp PALMER, CDS 2 và CDS 1
Tổng thời gian chờ (giờ)
Tổng khoảng thời gian chờ
Tổng thời gian hoàn thành M (giờ)
So với giải thuật CDS giai đoạn 2, giải thuật CDS giai đoạn 1 mang lại kết quả tốt hơn về Makespan, với thời gian máy I (máy 1) và máy II (máy 4) cho Makespan nhỏ hơn (84 < 88) Ngoài ra, giải thuật CDS giai đoạn 1 cũng cho thời gian chờ ngắn hơn so với CDS giai đoạn 2, chứng tỏ hiệu quả vượt trội của phương pháp này.
Giải thuật CDS giai đoạn 1 mang lại kết quả tốt hơn so với phương pháp Palmer, với Makespan nhỏ hơn (84 so với 88) và thời gian chờ cũng thấp hơn (50 so với 53) Do đó, giải thuật CDS giai đoạn 1 được đánh giá là hiệu quả hơn.
5.2 Mở rộng vấn đề theo giải thuật CDS 3
Xét giai đoạn 3: t’j1 = tj1 + tj2 + tj3 t’j2 = tj2 + tj3 + tj4
Bảng 4: Thời gian thực hiện của CDS giai đoạn 3
I VIII IX X t’j1 = tj1 + tj2 + tj3 1
Vậy trật tự gia công theo Johnson là: III - IV - I - VII - X - VI - IX - II - VIII - V
5.2.1 Sơ đồ Gantt mở rộng vấn đề theo giải thuật CDS 3
Hình 4: Sơ đồ Gantt theo giải thuật CDS 3
5.2.2 So sánh lời giải của 3 giải thuật PALMER, CDS 2, CDS 1 và CDS 3
Trật tự sắp xếp đơn hàng của 4 giải thuật:
PALMER: I – III – X – IV – IX – VI – VII – V – II – VIII
CDS 2: I – IX – III – IV – X – VI – II – VII – VIII – V
CDS 1: III – IV – I – X – VII – VI – V – VIII – IX – II
CDS 3: III – IV – I – VII – X – VI – IX – II – VIII – V
Bảng 5: So sánh tổng thời gian chờ, khoảng thời gian chờ và thời gian hoàn thành của phương pháp PALMER, CDS 2, CDS 1 và CDS 3
Tổng thời gian chờ (giờ)
Tổng khoảng thời gian chờ
Tổng thời gian hoàn thành M (giờ)
So với lời giải theo giải thuật CDS giai đoạn 2 với thời gian máy I là
(máy 1 + máy 2) và thời gian máy II là (máy 3 + máy 4) thì giải thuật CDS giai đoạn 3 với thời gian máy I (máy 1 + máy 2 + máy 3) và thời gian máy
Sử dụng máy 2, máy 3 và máy 4 đã mang lại lời giải tốt hơn về Makespan, với giá trị nhỏ hơn là 86 so với 88 Bên cạnh đó, thuật toán CDS ở giai đoạn 3 cũng cho kết quả tốt hơn so với giai đoạn 2, với thời gian chờ giảm xuống còn 54 so với 56.
So với phương pháp Palmer, giải thuật CDS giai đoạn 3 mang lại kết quả tốt hơn với Makespan nhỏ hơn (86 so với 88) Mặc dù thời gian chờ của giải thuật CDS giai đoạn 3 cao hơn một chút so với phương pháp Palmer (54 so với 53), nhưng sự chênh lệch này không quá lớn.
So với lời giải theo giải thuật CDS giai đoạn 1 với thời gian máy I (máy
1) và thời gian máy II (máy 4) thì giải thuật CDS giai đoạn 3 với thời gian máy I (máy 1 + máy 2 + máy 3) và thời gian máy II (máy 2 + máy 3 + máy