作业调度方案

解题思路:题目链接：作业调度方案；这一题算是一个复杂模拟题目，在C语言网这个平台上的题目缺少了一些图片信息，详情可参考解题教程：模拟——作业调度方案；在做本题的时候，读懂题是很重要的，我也是读了好几遍，才理解题目的意思。

其实题目可以理解为：已知工件顺序，工件-工序所用机器和时间，问如何充分利用机器时间，来达到所有工件完成时间最少。这样理解，我们就清楚，必须对每台机器有一个时间线的记录，也就是程序中的变量timeline[Max][10000]；除此之外，你还要记录每个工件的最后完成时间，以用做工件工序顺序执行的时间依据，以及最后所有工件时间的比较得到最短调度时间；其次，还有个step[Max]变量，来标记每个工件现在操作的工序；check()函数用来查看机器时间线上是否有空余时间来完成工件-工序的操作，否，时间线后移，知道遭到合适的时刻来完成工件-工序操作。

注意事项:如果理不清，建议把代码粘贴，然后debug，一行一行，跟着程序捋一遍，大概就知道怎么解决这个问题了；最后建议，亲自再敲一遍，看看自己有什么遗忘点；

参考代码:

#include<stdio.h>
#define MAX 21
int nowitem;//当前的工件编号 
int worklist[MAX*MAX];//工件加工给定顺序
int workmac[MAX][MAX];//【工件编号，工件工序号】机器编号
int worktime[MAX][MAX];//【工件编号，工件工序号】花费时间
int lasttime[MAX];//【工件编号】每个工件最后做完时间 
int timeline[MAX][10000];//【机器编号，时间线长度】 
int step[MAX];//当前编号工件进行到的工序 ，初始时都为0 
int check(int st,int end,int mac)
{
    //找是否有空余的位置 
    for(int i=st;i<=end;i++)
    {
        if(timeline[mac][i]==1)
        return 0;
    }
    return 1;
}
int main()
{
    int n,m;
     scanf("%d %d",&m,&n);
     for(int i=1;i<=n*m;i++)
     {
         scanf("%d",&worklist[i]);
     }
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             scanf("%d",&workmac[i][j]);
         }
     }
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             scanf("%d",&worktime[i][j]);
         }
     }
     int mac,costtime;
     for(int i=1;i<=n*m;i++)
     {
         nowitem=worklist[i];//当前安排工件编号 
         step[nowitem]++; //工序号加一
        mac=workmac[nowitem][step[nowitem]];//机器号
        costtime=worktime[nowitem][step[nowitem]];//花费时间
        for(int t=lasttime[nowitem]+1;;t++)
        {
            if(check(t,t+costtime-1,mac)==1)
            {
                for(int j=t;j<=t+costtime-1;j++)
                {
                    timeline[mac][j]=1;
                }
                lasttime[nowitem]=t+costtime-1;
                break;
            }
         }       
     }
     int maxtime=-1;
     for(int i=1;i<=n;i++)
     {
         if(lasttime[i]>maxtime)
         maxtime=lasttime[i];
     }
     printf("%d\n",maxtime);
    return 0;
}