回溯批处理作业调度

---

---

批处理作业调度

给定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;
} 

运行截图