?? 機器調度.cpp
字號:
#include <stdio.h>
#include <malloc.h>
#define MAXTASK 100
#define MAXMACH 100
#define LT(A,B) ((A) < (B))
#define EQ(A,B) ((A) == (B))
#define LQ(A,B) ((A) <= (B))
#define GT(A,B) ((A) > (B))
typedef struct{ //任務所需時間
int ti;
int num;
}TaskType;
typedef struct{ //分配給機器的時刻
int sch;
int num;
}MachType;
typedef struct{ //任務的數據結構
int tasknum;
TaskType *task;
}HeapType;
typedef struct{ //機器的數據結構
int machnum;
MachType *machine;
}BitType;
void HeapAdjust (HeapType &H,int s,int m){
//已經H.task[s..m]中記錄的時間除H.task[s].ti之外均滿足堆的定義,本函數調整H.task[s]
//的時間,使H.task[s..m]成為一個大頂堆
TaskType rc;
int j;
rc=H.task[s];
for(j=2*s; j<=m; j*=2){//沿ti較大的孩子結點向下篩選
if( j<m && LT(H.task[j].ti,H.task[j+1].ti) ) ++j;//j為ti較大的記錄的下標
if( !LT(rc.ti,H.task[j].ti) ) break; //rc應插入在位置s上
H.task[s]=H.task[j];
s=j;
}
H.task[s]=rc; //插入
}
void BitAdjust (BitType &B,int s,int m){
//已經B.machine[s..m]中記錄的時間除B.machine[s].sch之外均滿足堆的定義,本函數調整B.machine[s]
//的時間,使B.machine[s..m]成為一個小頂堆
MachType rc;
int j;
rc=B.machine[s];
for(j=2*s;j<=m;j*=2){//沿sch較小的孩子結點向下篩選
if(j<m && GT(B.machine[j].sch , B.machine[j+1].sch)) ++j;
if(LT(rc.sch, B.machine[j].sch)) break;
B.machine[s]=B.machine[j];
s=j;
}
B.machine[s]=rc;
}
void Heap(BitType &B,int s,int m){
MachType rc;
int j;
rc=B.machine[s];
for(j=2*s; j<=m; j*=2){//沿ti較大的孩子結點向下篩選
if( j<m && LT(B.machine[j].sch,B.machine[j+1].sch) ) ++j;//j為ti較大的記錄的下標
if( !LT(rc.sch,B.machine[j].sch) ) break; //rc應插入在位置s上
B.machine[s]=B.machine[j];
s=j;
}
B.machine[s]=rc; //插入
}
void HeapSort( HeapType &H){
int i;
for( i=H.tasknum/2 ; i>0 ; --i) //把H.task[1..H.tasknum]建成大頂堆
HeapAdjust(H,i,H.tasknum);
}
void BitSort( BitType &B){
int i;
for(i=B.machnum/2 ;i>0 ; --i) //把B.task[1..B.tasknum]建成小頂堆
BitAdjust(B,i,B.machnum);
}
int LPT(HeapType &H,BitType &B){
//任務調度算法
int i,j;
int machine[MAXTASK][MAXMACH];//machine[i]為第i臺機器被分配的任務
for(i=0;i<=B.machnum;i++) //初始化數組machine
for(j=0;j<=H.tasknum;j++)
machine[i][j]=0;
if(H.tasknum <= B.machnum){
//作業數n<=機器數m,則將作業i分配到機器i上
//最短調度長度等于n個作業中處理時間最大值
for(i=1;i<=H.tasknum;i++){
B.machine[i].sch=H.task[i].ti;
machine[i][0]=H.task[i].num;
}
B.machine[0].sch=B.machine[1].sch;
for(i=2;i<=H.tasknum;i++){// 查找其中的最大值
if(GT(B.machine[i].sch,B.machine[0].sch))
B.machine[0].sch=B.machine[i].sch;
}
B.machine[1].sch=B.machine[0].sch;
}
else {
for(i=H.tasknum;i>=1;--i){//分配任務
HeapSort(H);//把任務按時間排成大頂堆
BitSort(B); //把機器按時刻表排成小頂堆
B.machine[1].sch=B.machine[1].sch+H.task[1].ti;//將H的堆頂任務分配給B的堆頂機器
for(j=0;machine[B.machine[1].num][j];j++) ;
machine[B.machine[1].num][j]=H.task[1].num;
H.task[1]=H.task[i];//把排在最后的任務置堆頂(即把堆頂任務刪除)
H.task[i].ti=0;
H.tasknum--;//任務數少一
}
for(i=B.machnum/2;i>=1;i--)//任務全部分配完時,再一次大頂堆排序
Heap(B,i,B.machnum);
}
printf("scheme dispather:\n");
printf("machine\t\ttask\n");
for(i=1;i<=B.machnum && machine[i][0];i++){
printf("NO.%d: \t",i);
for(j=0;machine[i][j];j++)
printf("%d ",machine[i][j]);
printf("\n");
}
return B.machine[1].sch;
}
void main(){
HeapType H;
BitType B;
printf("input the amount of machines:");
scanf("%d",&B.machnum);
fflush(stdin);
B.machine=(MachType *)malloc((B.machnum+1) * sizeof(MachType));
for(int i=1;i<=B.machnum;i++){
B.machine[i].sch=0; //初始化機器的時刻
B.machine[i].num=i;
}
printf("input the amount of tasks:");
scanf("%d",&H.tasknum);
fflush(stdin);
H.task=(TaskType *)malloc((H.tasknum+1)*sizeof(TaskType));
for(i=1;i<=H.tasknum;i++){
H.task[i].num=i;
printf("NO.%d task:",i);
scanf("%d",&H.task[i].ti);
}
printf("\n");
printf("the least time of the job scheduling:%d\n",LPT(H,B));
fflush(stdin);
getchar();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -