SIF*_*IFE 10 c algorithm job-scheduling
问题:我有3台机器,每台机器的时间限制为30毫秒,每台机器有3个区域,无法在那里执行任务.任务有P(优先级)和W(权重,这是在此设置中完成任务的时间),任务必须首先按优先级排序,从低到高依次为:
任务01 {6,2} // P/W = 3此任务最后执行(3)
任务02 {7,7} // P/W = 1此任务首先执行(1)
任务03 {4,2} // P/W = 2此任务执行第二(2)
现在,为了执行任务(我有6个),我必须检查所有3台机器,找到第一个适合任务,选择适合任务,它必须是3台机器中的最佳,例如:
机器01; | ----- 5 ---- 9 ------- 16-17--19-20 |
机器02:| ---- 4-5--7-8 --------- 17-18-- |
机器03:| ----- 5 --- 8--10 --- 13--15 --- 18-- |
(1)在机器02中执行任务02(我们寻找执行任务的P ms,以及启动任务的最短时间,因为机器01(从9毫秒开始)和02(从8毫秒开始)都有7毫秒空闲时间,机器02可以先启动任务然后机器01).
(2)在机器02中执行的任务03(我们寻找P ms来执行任务).
(3)在机器01中执行的任务01(我们寻找P ms来执行任务).
某些时间段被定义为关键时期,不能用于安排工作.这些时段(例如5-9,7-8)存储在专用结构中z_indispo.
该bfeet结构用于存储任务开始和巫婆机器.
我在C中实现了大部分整个算法,但我的结果与预期不同:
#include <stdio.h>
typedef struct _z_indispo {
int t1;
int t2;
} z_indispo;
typedef struct _machines {
int t[20]; // array represent time
z_indispo zone[2];
} machines;
typedef struct _tache {
int p;
int w;
int c; // p/w
int i; // Task number
} tache;
typedef struct _bfeet {
int t; // Store the time to of ending execution by a task
int m; // The machine responsible for executing a task.
} bfeet;
int main(int argc, char **argv)
{
machines m[4];
tache j[6];
tache j_tmp;
bfeet b[4];
int i = 0;
int n = 0;
int u = 0;
int k = 0;
int count = 0;
int trouver = 0;
int f_totale = 0;
int f[3] = {0};
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
/*
* Initialise all machines
* 0: Represent free time.
* -1: Represent critical zone range.
* -2: Represent a task already executed.
*/
for(i = 0; i< 3; ++i)
{
for(count = 0; count < 20; ++count)
{
if((count >= m[i].zone[0].t1 - 1 && count <= m[i].zone[0].t2 - 1) ||
(count >= m[i].zone[1].t1 - 1 && count <= m[i].zone[1].t2 - 1))
{
m[i].t[count] = -1;
}
else
{
m[i].t[count] = 0;
}
}
}
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
j[0].p = 5;
j[0].w = 2;
j[0].i = 1;
j[1].p = 9;
j[1].w = 3;
j[1].i = 2;
j[2].p = 6;
j[2].w = 3;
j[2].i = 3;
j[3].p = 6;
j[3].w = 4;
j[3].i = 4;
j[4].p = 7;
j[4].w = 7;
j[4].i = 5;
/*
* Calc C = P/W .
*/
for(count = 0; count < 5; ++count)
{
j[count].c = j[count].p / j[count].w;
}
/*
* Sort tasks from low to hight
*/
for(count = 0; count < 5; ++count)
{
for(k = 0; k < 5 - count; ++k)
{
if(j[k].c > j[k + 1].c)
{
j_tmp = j[k + 1];
j[k + 1] = j[k];
j[k] = j_tmp;
}
}
}
/*printf("|%2J |%2 P |%2 W | C |\n");
printf("_____________________\n");
for(count = 0; count < 5; ++count)
{
printf("|%-4d|%-4d|%-4d|%-4d|\n", j[count].i, j[count].p, j[count].w, j[count].c);
}
printf("\n");*/
/*
* Execute tasks
*/
while(n < 5)
{
for(count = 0; count < 3; ++count)
{
i = 0;
trouver = 0;
while(i <= 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
u = 0; // num of available indexs.
while(m[count].t[i] != -1 && m[count].t[i] != -2)
{
if(u == j[n].p)
break;
++u;
++i;
}
if(u < j[n].p)
{
while(m[count].t[i] == -1 && m[count].t[i] == -2) // bypass unfree unites
++i;
}
else if(u == j[n].p)
{
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
else
++i;
}
}
if(u < j[n].p)
printf("There is no free time to execute task %d", j[n].i);
else
{
// Find the minimum time in all machines to start a task
b[3].t = b[0].t;
b[3].m = b[0].m;
for(count = 0; count < 3; ++count)
{
if(b[3].t > b[count + 1].t)
{
b[3].t = b[count + 1].t;
b[3].m = b[count + 1].m;
}
}
// Put -2 to indicate that index is unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = (b[3].t + j[n].p);
else if(b[3].m == 1)
f[1] = (b[3].t + j[n].p);
else if(b[3].m == 2)
f[2] = (b[3].t + j[n].p);
printf("Task %d end at %-2d, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
printf("\n");
f_totale = f[0] + f[1] + f[2];
printf("F of machine 01: %d.\n", f[0]);
printf("F of machine 02: %d.\n", f[1]);
printf("F of machine 03: %d.\n", f[2]);
printf("Total F: %d.\n", f_totale);
printf("\n");
/*printf("\n");
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}*/
return 0;
}
更新: 我现在每台机器只有两个不可用区域.我还更新了代码以修复一些错误,但我仍然得到一个不同的输出,然后这个例子:我有这个不可用区域:
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
5个任务:
p | 6 9 5 7 6
w | 3 3 2 7 4
_______________
c | 2 3 2 1 1
订购后c:
p | 7 6 5 6 9
w | 7 4 2 3 3
_______________
c | 1 1 2 2 3
任务的执行应该是这样的:
J4
|_______7__9_____14_15__________| ms
任务04应该在7结束,P表示执行任务所需的时间.
J5
|________8_9__________16_17_____| ms
任务05应该在7结束.
J1 J3
|_______7_8_______________18_19_| ms
任务01应该在6结束,任务03应该在14结束.
更新02: (此问题修正)
我注意到我的程序中有一个奇怪的行为,在我初始化m [i] .t [count]数组后,我发现负责存储不可用区域的变量发生了变化:注意:此问题已修复.
UPDATE03: (这个问题固定的,而是与新的问题)
我有一个任务无法找到必要的单位开始的情况,我从来没有得到这个消息"没有空闲时间执行任务",我应该收到任务2,因为它有9个单位,所有机器没有那样的空闲时间.负责此测试的代码:
for(count = 0; count < 3; ++count) // search on all machines
{
i = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
u = 0; // num of available indexs.
while(m[count].t[i] != -1 && m[count].t[i] != -2)
{
if(u == j[n].p)
break;
++u;
++i;
}
if(u < j[n].p)
{
while(m[count].t[i] == -1 && m[count].t[i] == -2) // bypass unfree unites
++i;
}
else if(u == j[n].p)
{
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
else
++i;
}
}
/* u represent the number of continuous free time,
j[n].p represent the necessary time to execute the current task, n is the current task
if(u < j[n].p)
printf("There is no free time to execute task %d", j[n].i);
else
{
// Find the minimum time in all machines to start a task
b[3].t = b[0].t;
b[3].m = b[0].m;
UPDATE04:
现在我可以在没有空闲时间执行任务时看到排除的任务,但输出不正确,因为我看到任务覆盖了另一个任务的周期时间:
while(n < 5)
{
k = 0;
for(count = 0; count < 3; ++count)
{
i = 0;
u = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
//u = 0; // num of available indexs.
if(u == j[n].p)
break;
else
{
++u;
++i;
}
}
if(u != j[n].p)
{
if((m[count].t[i] == -1 || m[count].t[i] == -2))// bypass unfree unites
{
u = 0;
++i;
}
}
if(u == j[n].p)
{
++k;
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
}
if(u != j[n].p)
{
printf("There is no free time to execute task %d.\n", j[n].i);
}
else
{
// Find the minimum time in all machines to start a task
b[3] = b[0];
for(count = 0; count < 3; ++count)
{
if(b[count].t != 0)
if(b[3].t > b[count + 1].t)
{
b[3] = b[count + 1];
}
}
// Put -2 to indicate that index is unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = (b[3].t + j[n].p);
else if(b[3].m == 1)
f[1] = (b[3].t + j[n].p);
else if(b[3].m == 2)
f[2] = (b[3].t + j[n].p);
printf("Task %d end at %-2d, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
输出:
D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)
| 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 |
D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)
| 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 0 0 0 |
D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)
| 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 |
| J | P | W | C |
_____________________
|1 |5 |2 |2 |
|2 |7 |3 |2 |
|3 |8 |3 |2 |
|5 |17 |7 |2 |
|4 |16 |4 |4 |
Task 1 end at 5 , machine 1.
Task 2 end at 7 , machine 1.
Task 3 end at 8 , machine 1.
There is no free time to execute task 5.
There is no free time to execute task 4.
F of machine 01: 8.
F of machine 02: 0.
F of machine 03: 0.
Total F: 8.
D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)
| -2 -2 -2 -2 -2 -2 -2 -2 -1 0 0 0 0 -1 -1 0 0 0 0 0 |
D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)
| 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 0 0 0 |
D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)
| 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 |
我发现问题在于如何搜索机器中启动任务的最短启动时间：
....
// Find the minimum time in all machines to start a task
b[3] = b[0]; // this cause the problem
for(count = 0; count < 3; ++count)
{
if(b[count].t != 0)
if(b[3].t > b[count + 1].t)
{
b[3] = b[count + 1];
}
}
b[3]由于 start 可能指无法启动当前任务的机器，所以我做了一些更改：
// Find the minimum time in all machines to start a task
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
b[3] = b[count];
break;
}
}
for(count = 0; count < 3; ++count) // search for the first machines that can execute the current task
{
if(b[count].m != -1)
{
if((b[3].t > b[count + 1].t) && (b[count + 1].m != -1)) // make sure the next machine can start the current task
{
b[3] = b[count + 1];
}
}
}
完整的算法：
#include <stdio.h>
typedef struct _z_indispo {
int t1;
int t2;
} z_indispo;
typedef struct _machines {
int t[20]; // array represent time
z_indispo zone[2];
} machines;
typedef struct _tache {
int p;
int w;
int c; // p/w
int i; // Task number
} tache;
typedef struct _bfeet {
int t; // Store the time to of ending execution by a task
int m; // The machine responsible for executing a task.
} bfeet;
int main(int argc, char **argv)
{
machines m[4] = {0};
tache j[6];
tache j_tmp;
bfeet b[4] = {0};
int i = 0;
int n = 0;
int u = 0;
int k = 0;
int count = 0;
int trouver = 0;
int f_totale = 0;
int f[3] = {0};
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
/*
* Initialise all machines
* 0: Represent free time.
* -1: Represent critical zone range.
* -2: Represent a task already executed.
*/
for(i = 0; i< 3; ++i)
{
for(count = 0; count < 20; ++count)
{
if((count >= m[i].zone[0].t1 - 1 && count <= m[i].zone[0].t2 - 1) ||
(count >= m[i].zone[1].t1 - 1 && count <= m[i].zone[1].t2 - 1))
{
m[i].t[count] = -1;
}
else
{
m[i].t[count] = 0;
}
}
}
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
j[0].p = 5;
j[0].w = 2;
j[0].i = 1;
j[1].p = 7;
j[1].w = 3;
j[1].i = 2;
j[2].p = 4;
j[2].w = 1;
j[2].i = 3;
j[3].p = 6;
j[3].w = 4;
j[3].i = 4;
j[4].p = 7;
j[4].w = 7;
j[4].i = 5;
/*
* Calc C = P/W .
*/
for(count = 0; count < 5; ++count)
{
j[count].c = j[count].p / j[count].w;
}
/*
* Sort tasks from low to hight
*/
for(count = 0; count < 5; ++count)
{
for(k = 0; k < 5 - count; ++k)
{
if(j[k].c > j[k + 1].c)
{
j_tmp = j[k + 1];
j[k + 1] = j[k];
j[k] = j_tmp;
}
}
}
printf("|%2J |%2 P |%2 W | C |\n");
printf("_____________________\n");
for(count = 0; count < 5; ++count)
{
printf("|%-4d|%-4d|%-4d|%-4d|\n", j[count].i, j[count].p, j[count].w, j[count].c);
}
printf("\n");
/*
* Execute tasks
*/
while(n < 5)
{
k = 0;
for(count = 0; count < 3; ++count)
{
i = 0;
u = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // we find a free unite
{
while(m[count].t[i] == 0 && u != j[n].p && i < 20) // count a continues free time, quit when u equal the necessary time to execute the current task
{
++u;
++i;
}
if(u == j[n].p) // we found a free continues time
{
b[count].t = i - u; // save the starting index
b[count].m = count; // save the machine responsible for executing the current task
++k;
trouver = 1;
}
else if(u != j[n].p) // if we encounter zone unavailability or index reserved by another task
{
u = 0; // restart u counter
while((m[count].t[i] == -1 || m[count].t[i] == -2) && (i < 20)) // bypass reserved/unavailability index's
++i;
}
}
else
++i; // bypass reserved/unavailability index's
}
if(trouver != 1) // we mark this machine as it can't execute the current task
{
b[count].m = -1;
}
}
if(k == 0)
printf("There is no free time to execute task %d.\n", j[n].i);
else
{
// Find the minimum time in all machines to start a task
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
b[3] = b[count];
break;
}
}
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
if((b[3].t > b[count + 1].t) && (b[count + 1].m != -1))
{
b[3] = b[count + 1];
}
}
}
// Put -2 to indicate that index as unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = f[0] + (b[3].t + j[n].p) * j[n].w;
else if(b[3].m == 1)
f[1] = f[1] + (b[3].t + j[n].p) * j[n].w;
else if(b[3].m == 2)
f[2] = f[2] + (b[3].t + j[n].p) * j[n].w;
printf("Task %d end at %-3dms, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
printf("\n");
f_totale = f[0] + f[1] + f[2];
printf("F of machine 01: %d.\n", f[0]);
printf("F of machine 02: %d.\n", f[1]);
printf("F of machine 03: %d.\n", f[2]);
printf("Total F: %d.\n", f_totale);
printf("\n");
printf("\n");
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
return 0;
}