Link tải luận văn miễn phí cho ae

gồm 1 bản word và 1 sile thuyết trình


I, Bài toán phân công công việc
1, Nội dung bài toán
Một đề án gồm n công việc và các việc sẽ được thực hiên bởi m máy như nhau.
Giả sử biết thời gian để 1 máy thực hiện viêc thứ j là tj
Yêu cầu: Tìm phương án phân công sao cho thời gian hoàn thành toàn bộ công việc là thấp nhất.
Mẫu số liệu : n=10, m=3
tj = 4 9 5 2 7 6 10 8 7 5
2, Giải thuật: được viết dưới dạng thủ tục tương tự như thuật toán nhưng không đòi hỏi các tiêu chuẩn như thuật toán.
- Tính đúng: chấp nhận các giải thuật đơn giản, có thể cho kết quả đúng hay gần đúng nhưng có khả năng thành công cao hơn.
- Để có thể được chấp nhận, giải thuật phải thể hiện một giải pháp hợp lý nhất có thể trong tình huống hiện tại bằng cách:
+ Tận dụng mọi thông tin hữu ích
+ Sử dụng tri thức, kinh nghiệm trực giác của con người
+ Tự nhiên, đơn giản nhưng cho kết quả chấp nhận được
è Giải thuật Heuristic
Giải thuật cho bài toán phân công đơn giản:
Chọn việc J chưa phân công có thời gian thực hiện cao nhất phân công cho máy có thời gian làm việc thấp nhất
for(k=0;k<n;k++)
{
Chọn việc J chưa phân công có thời gian thực hiện cao nhất.
Chọn máy M có thời gian làm việc thấp nhất
Bố trí việc J cho máy M.
Chọn việc J chưa phân công có thời gian thực hiện cao nhất phân công cho máy có thời gian làm việc thấp nhất
for(k=0;k<n;k++)
{
Chọn việc J chưa phân công có thời gian thực hiện cao nhất.
Chọn máy M có thời gian làm việc thấp nhất
Bố trí việc J cho máy M.
}
n=10, m=3

II, Chương trình
// Bai toan phan cong cong viec: n Viec chia cho m May
// Bai tap lon

#include<iostream.h>
#include<conio.h>

#define MAX 20

typedef struct
{
int bot;//bien dem chi phan tu tiep theo cua array
int sum; //tong thoi gian may da lam
int array[MAX]; //mang cac cong viec may da lam
}MAY;

void NhapMang(int a[], int n)
{
for(int i=0; i<n; i++)
{
cin>>a[i];
}
}

void XuatMang(int a[], int n)
{
for(int i=0; i<n; i++)
{
cout<<a[i]<<"\t";
}
cout<<endl;
}

void Swap(int &a, int &b)//Hoan vi cong viec
{
int tmp;
tmp=a;
a;
b=tmp =b;
}

void GiamDan(int a[], int n)// Sap xep cong viec theo thu tu giam dan cua thoi gian

{
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i]<a[j])
{
Swap(a[i], a[j]);
}
}
}
}

void GanMangBangKhong(int a[], int n)//Khoi dong cac may de lam viec
{
for(int i=0; i<n; i++)
{
a[i]=0;
}
}
// Tim ra may co tg lam tong cong viec it nhat
int MinDong(MAY may[], int m)
{
int minwhere=0;
for(int i=1; i<m; i++)
{
if(may[i].sum<may[minwhere].sum)
{
minwhere=i;
}
}
return minwhere;
}

int ChiaViec(int viec[], int n, int m)
{
MAY may[MAX];
int min,max;

for(int k=0; k<m; k++)
{
GanMangBangKhong(may[k].array, MAX);
may[k].bot=0;
may[k].sum=0;
}

for(int i=0; i<n; i++)
{
//tim ra may co tg lam viec ngan nhat, lay vi tri may do ra
min=MinDong(may, m);
//gan cong viec tiep theo vao may do
may[min].array[may[min].bot++]=viec[i];
//cong tg cua cong viec do vao tong tg lam viec (sum) cua may do
may[min].sum=may[min].sum+viec[i];
}

max=may[0].sum;

for(int j=0; j<m; j++)
{
cout<<"May "<<j+1<<" :\t";
XuatMang(may[j].array, may[j].bot);
cout<<endl;
//tim ra tong tg lon nhat cua cac may
if(may[j].sum>max)
max=may[j].sum;
}
return max;
}

void main()
{
int n,m;
int arrayviec[MAX];
char ch;
cout<<"\t\t\tn Cong viec chia cho m May"<<endl
<<"\t\t\t\t\t\t\t\t Bai tap lon";
do
{
cout<<endl<<"So cong viec: ";
cin>>n;
cout<<"Thoi gian tung cong viec "<<endl;
NhapMang(arrayviec, n);
cout<<"Nhap vao so may xu ly cong viec: ";
cin>>m;
cout<<endl;
XuatMang(arrayviec, n);
GiamDan(arrayviec, n);
cout<<"Thoi gian de lam xong cac cong viec la: "<<ChiaViec(arrayviec, n, m)<<endl;
cout<<endl<<"Ban co muon lam tiep khong ? (y/n)";
cout.flush();
ch=getche();
}while(ch=='y' || ch=='Y');
}


bRy149NTp24Zmud

---