批处理作业调度
给定n个作业的集合J={J1,J2,…,Jn}。每一个作业有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2,…n，j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和f=F21+F22+…+F2n称为该作业调度的完成时间和。
批处理作业调度问题要求，对于给定的n个作业，制定最佳的作业调度方案，使其完成时间和最小。
tji 机器1 机器2
作业1 2 1
作业2 3 1
作业3 2 3
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；
它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。
分析：
首先，题目就很难懂。t代表作业很容易理解，这道题涉及到全排列，若有n个作业，程序中是需要n个作业的全排列形式的，特地温习了全排列。
根据全排列出的每一种情况，计算f1和f2。f1是不会闲下来的，处理完第一个作业，接着第二个，第三个。。。。直到最后；f2则不同，当第二个作业在机器一上完成时，并不一定它接着在机器二上加工，可能第一个作业在机器二上耗时特别多，那么作业二还得等作业一完成后，再去到机器二上加工。
#include<stdio.h>
#define n 3 //3个作业
int minTime=10000; //所有调度中最少的时间
int sumTime=0; //某一个调度的时间
int a[n]={0,1,2}; //为n个作业编一个号，便于后期的全排列，a[1]=1意思是：第二个执行的是作业编号为1的作业
int runtime[n][2]={2,1,3,1,2,3};
int besta[n]={0}; //最优的作业编号排列
int f1=0,f2[n]={0}; //分别记录第一个工作和第二个工作的时间
void traceback(int t){
if(t==n){
if(sumTime<minTime){
minTime=sumTime;
for(int i=0;i<n;i++)
besta[i]=a[i];
}
return;
}
for(int i=t;i<n;i++){
int temp=a[t];
a[t]=a[i];
a[i]=temp;
f1+=runtime[a[t]][0]; //第一个工作结束时的时间
if(t==0)
f2[t]=f1+runtime[a[t]][1];
else
f2[t]=f1>f2[t-1]?(f1+runtime[a[t]][1]):(f2[t-1]+runtime[a[t]][1]);
sumTime+=f2[t];
if(sumTime<minTime)
traceback(t+1);
sumTime-=f2[t];
f1-=runtime[a[t]][0];
temp=a[t];
a[t]=a[i];
a[i]=temp;
}
}
int main(){
putchar('\n');
traceback(0); //t代表第几个执行的作业
printf("最少时间：%d\n",minTime);
for(int i=0;i<n;i++){
printf("%d\t",besta[i]+1);
}
return 0;
}
运行截图
