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];