实现类似首次适应算法的算法

Question

问题： 我有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）存储在专用结构体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 |

- SIFE

---

@Phpdevpad 关键区域意味着任务不能在该范围内执行。 - SIFE

@SIFE：当然，但在首次适配算法中，我们也从1台机器开始，而不是3台。我不确定应该优化什么？ - Micromega

@Phpdevpad 在这个算法中，我必须在最短的时间内完成一个任务。 - SIFE

这里的具体问题是什么？是您不知道正确的算法是什么吗？还是您知道算法，但实现方式不同？如果是后者，那么调试器似乎是第一个需要尝试的工具。 - Oliver Charlesworth

@wildplasser 是的。 当“trouver”等于1或“i”等于20时，“i”将保持不变。 - SIFE

Answer 1

我发现问题出在我查找机器开始任务的最小起始时间上：

....

// 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];
        }
}

b[3] 作为起点可能指的是无法启动当前任务的机器，因此我做了一些小改动:

// 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];
                    }
                }
            }

完整算法如下：

#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;
}

- SIFE

Answer 2

你的数组定义中存在持久性的短一错误。基本上，C语言数组是从0开始索引的，因此如果你想访问array[n]，那么array的大小至少要定义为n+1。例如，你的machine结构体应该是：

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

由于您访问了machine.t [20]和machine.zone [1]，因此出现了问题。

这将解决您第二次更新中的问题（内存被践踏是超出数组末尾索引的一个很好的指标）。一旦您通过类似的方式修复main()中的数组初始化（例如，您正在访问b [3] .t，但由于您通过bfeet b [3]定义它，因此它仅具有索引b [0] ，b [1]和b [2]），第一个问题可能会得到解决（或者至少您会在解决方案的道路上更进一步）。

- Martin DeMello