c – 实现第一拟合算法

问题：
我有3台机器,每台机器都有30ms的时间限制,每台机器有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(从机器01(从9ms开始)和02(从8ms开始)都有7ms的时间,我们寻找P ms来执行任务以及启动任务的最小时间空闲时间,机器02可以首先启动一个任务,然后机器01).

(2)任务03在机器02中执行(我们查找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(" |nn");
    }

    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,m[i].t[count]);

        }

        printf(" |nn");
    }*/

    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,b[3].m + 1);
}

++n;

}

输出：

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,3)
|  0  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0 -1 -1  0  0  0 |

   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,3)
| -2 -2 -2 -2 -2 -2 -2 -2 -1  0  0  0  0 -1 -1  0  0  0  0  0 |

   D(2,3)
|  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0  0  0  0 -1 -1  0 |

typedef struct _machines {
    int t[20];
    z_indispo zone[2];
} machines;