作业调度方案C语言,2020-08-18 作业调度方案

#include

#include

#include

#include

#include

#include

#include

using namespace std;

long long qmi(int m, int k)

{

int res = 1, t = m;

while (k)

{

if (k&1) res = res * t;

t = t * t;

k >>= 1;

}

return res;

}

int read(){

int x = 0,f = 1;

char c = getchar();

while (c'9') {

if (c=='-') {

f = -1;

}

c = getchar();

}

while (c>='0'&&c<='9') {

x = x*10+c-'0';

c = getchar();

}

return x*f;

}

#define maxn 50

int n,m;

int ans = 0;

int worklist[maxn * maxn];//工作安排

int worknumber[maxn][maxn];//工作机器序号

int worktime[maxn][maxn];//加工时间

int cnt_now_work_step[maxn];//当前取到工件的工序牌号

int lasttime[maxn];//某个工件出现的最晚的时间(点)

bool timeline[maxn * maxn][maxn * maxn];//某一台机器在某一个时间(点)上是不是正在干活。

bool check_in_line(int begin_time_point, int end_time_length, int workid){//检查是否可以在生产线上

for (int time = begin_time_point; time <= end_time_length;time++)

if (timeline[workid][time])//若在产品线上

return false;

return true;

}

int main(){

cin >> m >> n;//m台机器加工n个工件

for (int i=1;i<=n*m;i++){

cin >> worklist[i];//工作安排

}

/*

其中前n行依次表示每个工件的每个工序所使用的机器号，

第1个数为第1个工序的机器号，

第2个数为第2个工序机器号，

等等。

*/

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

cin >> worknumber[i][j];

}

}

/*

后n行依次表示每个工件的每个工序的加工时间。

*/

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

cin >> worktime[i][j];

}

}

for (int i=1;i<=n*m;i++){//从1开始，一共有n*m个工作件

int nowitem = worklist[i];//当前工作的工作件

cnt_now_work_step[nowitem]++;//工序排号

int nownumber = worknumber[nowitem][cnt_now_work_step[nowitem]];//工作的机器序号

int costtime = worktime[nowitem][cnt_now_work_step[nowitem]];//花费的时间

for (int time = lasttime[nowitem]+1; ;time++)//扫描时间轴

if (check_in_line(time,time+costtime-1,nownumber)){//是否可以在线上

for (int marktime = time; marktime <= time+costtime-1 ;marktime++)//占据时间线

timeline[nownumber][marktime] = true;

lasttime[nowitem] = time + costtime - 1;//结尾时间

break;//打断时间扫描

}

}

for (int i=1;i<=n;i++)//机器数

ans = max(ans,lasttime[i]);//取最大的尾数

cout << ans << endl;

return 0;

}

/*

2 3

1 1 2 3 3 2

1 2

1 2

2 1

3 2

2 5

2 4

============

10

*/