Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 10. Phân công n công việc cho m máy - Nguyên lý thứ tự

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Bài 10. Phân công n công việc cho m máy - Nguyên lý thứ tự

Bài gửi  admin on Sat Jan 08, 2011 1:30 pm

BÀI TOÁN PHÂN CÔNG CÔNG VIỆC


BÀI TOÁN
Có m máy hoạt động cùng công suất, có n việc với thời gian thực hiện là khác nhau. Hãy phân công n việc vào m máy sao cho thời gian hoàn thành là nhanh nhất.
PHƯƠNG PHÁP
Sử dụng nguyên lý thứ tự sắp xếp các công việc tăng dần theo thời gian và sắp nó vào m máy.
CHƯƠNG TRÌNH MẪU
Code:
(*PHAN CONG CONG VIEC*)
NhapCongViec[n_] := Module[{P, i, temp},
         P = {};
         i = 1;
         While[i ≤ n,
                 temp = Input["Nhap thoi gian cong viec thu " <> ToString[i]];
                 If[temp > 0,
                      P = Append[P, {temp, i}];
                      i++;
                   ];
           ];
         Return[P];
      ];
PhanCong[m_, n_, P_] := Module[{T, i, J, temp, delta, T1, KQ, k},
         T = Table[0, {i, m}];
         J = Table[{}, {i, m}];
         i = 1;
         While[i ≤ n,
              delta = ∞;
              KQ = {};
              For[j = 1, j ≤ m, j++,
                   temp = T;
                   temp[[j]] += P[[i, 1]];
                   KQ = Append[KQ, temp];
                   If[delta > Max[temp] - Min[temp],
                        delta = Max[temp] - Min[temp];
                        T1 = temp;
                        k = j;
                     ];
                ];
              Print["Cong viec thu ", P[[i, 2]], " duoc sap vao cac may:"];
              Print[KQ];
              Print["Chon phuong an: ", T1];
              J[[k]] = Append[J[[k]], P[[i, 2]]];
              T = T1;
              i++;
           ];
         Print["Thoi gian de hoan thanh cong viec: ", Max[T]];
         For[i = 1, i  ≤ m, i++, Print["    May thu ", i, " thuc hien cac viec: ", J[[i]]]];
         Return[{T, J}];
      ];
Clear[n, m, P];
n = Input["Nhap so cong viec"];
m = Input["Nhap so may"];
P = NhapCongViec[n];
P = Sort[P];
Print["So may m = ", m];
Print["Cac thoi gian va cong viec:"];
Print[P];
PhanCong[m, n, P];

    Hôm nay: Tue Dec 11, 2018 8:15 pm