10
問題： 私は3台のマシンを持っていますが、各マシンは30ミリ秒の時間制限があり、各マシンは3つのゾーンでタスクを実行できません。 アルゴリズムのような最初のフィッティングを実装する
タスク01 {この設定でタスクを完了するための時間であるP（優先度）とW（重み） 6,2} // P/W = 3このタスクが実行された最後の（3）
タスク02 {7,7} // P/W = 1このタスクが最初に実行（1）
タスク03 { （2）
タスクを実行するためには、3つのマシンすべてをチェックしてタスクに最初に適合しているかどうかを確認する必要があります、仕事のためのフィット感を選ぶためには、それは3台のマシンで最適になります。例：
マシン01; | ----- 5 ---- 9 ------- 16-17-19-20 |
マシン02：| ---- 4-5--7-8 --------- 17-18-- |
マシン03：| ----- 5 --- 8--10 --- 13--15 --- 18-- | 01 01（9msから開始）と02（8msから開始）の両方が実行されているため、タスク02を実行するためにP msとタスクを開始する最小時間を探します。マシン02はタスクを最初に開始してからマシン01を起動することができます。
（2）タスク02はマシン02で実行されます（タスクを実行するためにP msが検索されます）。
（3）マシン01で実行されたタスク01（タスクを実行するためにP msを探します）。
特定の期間はクリティカルと定義されており、ジョブのスケジュールには使用できません。これらの期間（たとえば5-9,7-8）は専用の構造体z_indispoに格納されます。
bfeet structは、タスクの開始と魔法のマシンに格納するために使用されます。
私は主に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;
}
はUPDATE： 私は、各マシンに今2つしか使用できないゾーンを持っています。 cによりご注文後
p | 6 9 5 7 6
w | 3 3 2 7 4
_______________
c | 2 3 2 1 1
：
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 | 7 6 5 6 9
w | 7 4 2 3 3
_______________
c | 1 1 2 2 3
タスクの実行は次のようにする必要があります：
タスク04は7で終了し、Pはタスクを実行するのに必要な時間を表す。 J5
|________8_9__________16_17_____| ms
タスク03 14
UPDATE 02で終了する必要があり、6で終了すべきタスク05は、タスク01 7
J1 J3
|_______7_8_______________18_19_| ms
で終了すべきである：（この問題はを修正）
m [i] .t [count]配列を初期化した後、自分のプログラムで奇妙な動作が発生したことがわかりました。使用できないゾーンを格納するハット変数が変更されました。 注：この問題は修正されました。
UPDATE03：（この問題は固定ではなく、新たな問題で）
私はタスクが、私はこのメッセージを取得することはありません開始するために必要な団結を見つけることができない状況がある「空き時間がありませんタスクを実行するためには、9人のユニットがあり、すべてのマシンにそのような空き時間がないので、タスク2のためにそれを受け取る必要があります。このテストの責任コード：
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 |
まず、可能性変数の目的を理解するためのコメントを追加しますか？ _tache_、そして特に_bfeet_です。また、 '_machines'構造体には' int [19]; 'がありますが、20は最大時間（0-19のインデックスが付けられます）、' z_indispo zone [2];しかし3つの実際のクリティカルゾーン（I 'm [1] .zone [2]'を初期化しようとしています） – varevarao
なぜ5-9と7-8にクリティカルゾーンがありますか？ – Bytemain
明らかに、 '_z_indispo'構造体は、クリティカルゾーン（すなわち、利用不可能期間）を格納するために使用されます。アルゴリズムの観点からは、それらが存在し、そこに格納されていることだけを知る必要があります。私は間違っていますか？ – didierc