StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I found that the problem was in how I search for the minimum starting time in the machines to start task:</p> <pre><code>.... // 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]; } } </code></pre> <p><code>b[3]</code> as start could refer to a machine that can't start the current task, so I made a little change:</p> <pre><code>// 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]; } } } </code></pre> <p>The complete algorithm:</p> <pre><code>#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; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload