Note that there are some explanatory texts on larger screens.

plurals
  1. POImplementing first fit like algorithm
    primarykey
    data
    text
    <p>Problem: I have 3 machines, each machine have a limit of 30 ms time, each machine have 3 zones that a task can't be executed there. The tasks have a P (priority) and W (weight, which is the time to complete the task in this setup), tasks must be first ordered by a priority, from lower to higher like this:</p> <p>Task 01 {6, 2} // P/W = 3 this task executed last (3)</p> <p>Task 02 {7, 7} // P/W = 1 this task executed first (1)</p> <p>Task 03 {4, 2} // P/W = 2 this task executed second (2)</p> <p>Now, in order to execute a tasks(I have 6), I must check all 3 machines to find the first fit to the task, to chose a fit for task, it must be the optimal in the 3 machines, example:</p> <p>Machine 01; |-----5----9-------16-17--19-20|</p> <p>Machine 02: |----4-5--7-8---------17-18--|</p> <p>Machine 03: |-----5---8--10---13--15---18--|</p> <p>(1)Task 02 executed in machine 02 (We look for P ms to execute task, and the minimum time to start a task, since both machine 01 (starting from 9 ms) and 02 (starting from 8 ms) have a 7 ms free time, machine 02 can start a task first then the machine 01).</p> <p>(2)Task 03 executed in machine 02 (We look for P ms to execute task).</p> <p>(3)Task 01 executed in machine 01 (We look for P ms to execute task).</p> <p>Certain periods of time are defined as critical, and cannot be used to schedule a job. These periods (for instance 5-9, 7-8), are stored in the dedicated struct <code>z_indispo</code>.</p> <p>The <code>bfeet</code> struct is used to store in witch the task start and in witch machine.</p> <p>I implemented mostly the entire algorithm in C, but my results are different than expected:</p> <pre><code>#include &lt;stdio.h&gt; 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&lt; 3; ++i) { for(count = 0; count &lt; 20; ++count) { if((count &gt;= m[i].zone[0].t1 - 1 &amp;&amp; count &lt;= m[i].zone[0].t2 - 1) || (count &gt;= m[i].zone[1].t1 - 1 &amp;&amp; count &lt;= m[i].zone[1].t2 - 1)) { m[i].t[count] = -1; } else { m[i].t[count] = 0; } } } for(i = 0; i&lt; 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 &lt; 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 &lt; 5; ++count) { j[count].c = j[count].p / j[count].w; } /* * Sort tasks from low to hight */ for(count = 0; count &lt; 5; ++count) { for(k = 0; k &lt; 5 - count; ++k) { if(j[k].c &gt; 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 &lt; 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 &lt; 5) { for(count = 0; count &lt; 3; ++count) { i = 0; trouver = 0; while(i &lt;= 20 &amp;&amp; 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 &amp;&amp; m[count].t[i] != -2) { if(u == j[n].p) break; ++u; ++i; } if(u &lt; j[n].p) { while(m[count].t[i] == -1 &amp;&amp; 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 &lt; 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 &lt; 3; ++count) { if(b[3].t &gt; 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 &lt; 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&lt; 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 &lt; 20; ++count) { printf("%3d", m[i].t[count]); } printf(" |\n\n"); }*/ return 0; } </code></pre> <p><strong>UPDATE:</strong> I have now only two unavailability zones in each machine. I also updated the code to fix some errors, but I still get a different output then this example: I have this unavailability zones:</p> <pre><code>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; </code></pre> <p>5 tasks:</p> <pre><code>p | 6 9 5 7 6 w | 3 3 2 7 4 _______________ c | 2 3 2 1 1 </code></pre> <p>After ordering by <code>c</code>:</p> <pre><code>p | 7 6 5 6 9 w | 7 4 2 3 3 _______________ c | 1 1 2 2 3 </code></pre> <p>The execution of tasks should be like this:</p> <pre><code> J4 |_______7__9_____14_15__________| ms </code></pre> <p>Task 04 should end at 7, P represent the time necessary to execute a task.</p> <pre><code> J5 |________8_9__________16_17_____| ms </code></pre> <p>Task 05 should end at 7.</p> <pre><code> J1 J3 |_______7_8_______________18_19_| ms </code></pre> <p>Task 01 should end at 6, task 03 should end at 14.</p> <p><strong>UPDATE 02:</strong> (<em>This problem fixed</em>)</p> <p>I noticed a strange behavior in my program, after I initializing m[i].t[count] array, I found that variables responsible for storing unavailability zones changed: NOTE: This problem fixed.</p> <p><strong>UPDATE03:</strong> (<em>This problem fixed but with new issue</em>)</p> <p>I have situation when a task can't find the necessary unites to start, I never get this message "There is no free time to execute task ", witch I should receive it for task 2, since it has 9 unites, and all machines have no such of free time like that. The code responsible for this test: </p> <pre><code> for(count = 0; count &lt; 3; ++count) // search on all machines { i = 0; trouver = 0; while(i &lt; 20 &amp;&amp; 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 &amp;&amp; m[count].t[i] != -2) { if(u == j[n].p) break; ++u; ++i; } if(u &lt; j[n].p) { while(m[count].t[i] == -1 &amp;&amp; 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 &lt; 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; </code></pre> <p><strong>UPDATE04:</strong></p> <p>Now I can see excluded task when there is no free time to execute a task, however, the output is not right, because I see a task override the period time on another task:</p> <pre><code>while(n &lt; 5) { k = 0; for(count = 0; count &lt; 3; ++count) { i = 0; u = 0; trouver = 0; while(i &lt; 20 &amp;&amp; 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 &lt; 3; ++count) { if(b[count].t != 0) if(b[3].t &gt; 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 &lt; 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; </code></pre> <p>} </p> <p><strong>Output:</strong></p> <pre><code> 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 | </code></pre>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance

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