问题:
我有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台机器以找到任务的最佳匹配,选择任务的最佳匹配必须是三台机器中的最优解,例如:
机器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毫秒来执行任务,并且寻找开始任务的最小时间,因为机器01(从9ms开始)和机器02(从8ms开始)都有7ms的空闲时间,所以机器02可以先开始执行任务,然后再执行机器01)。
(2)任务03在机器02上执行(我们寻找P毫秒来执行任务)。
(3)任务01在机器01上执行(我们寻找P毫秒来执行任务)。
特定的时间段被定义为关键时间,不能用于安排作业。这些时间段(例如5-9、7-8)存储在专用结构体
我主要是用C实现了整个算法,但我的结果与预期不同:
任务的执行应该是这样的:
任务05应该在7点结束。
任务01 {6, 2} // P/W = 3 此任务最后执行(3)
任务02 {7, 7} // P/W = 1 此任务首先执行(1)
任务03 {4, 2} // P/W = 2 此任务第二执行(2)
现在,为了执行任务(我有6个任务),我必须检查所有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毫秒来执行任务,并且寻找开始任务的最小时间,因为机器01(从9ms开始)和机器02(从8ms开始)都有7ms的空闲时间,所以机器02可以先开始执行任务,然后再执行机器01)。
(2)任务03在机器02上执行(我们寻找P毫秒来执行任务)。
(3)任务01在机器01上执行(我们寻找P毫秒来执行任务)。
特定的时间段被定义为关键时间,不能用于安排作业。这些时间段(例如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
< p >在通过 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]数组后,我发现负责存储不可用区域的变量发生了变化: 注意:此问题已解决。
更新03:(此问题已解决但出现了新问题)
当一个任务找不到必要的单位来开始时,我遇到了这种情况,我从未收到过这个消息“没有空闲时间来执行任务”,我应该为任务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;
更新04:
现在当没有空闲时间执行任务时,我可以看到被排除的任务,但输出结果不正确,因为我看到一个任务覆盖了另一个任务的时间段:
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;
}
Output:
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 |