10

问题：我有 3 台机器，每台机器有 30 毫秒的时间限制，每台机器有 3 个区域不能在那里执行任务。任务有 P（优先级）和 W（权重，这是在此设置中完成任务的时间），任务必须首先按优先级排序，从低到高，如下所示：

Task 01 {6, 2} // P/W = 3 此任务最后执行 (3)

Task 02 {7, 7} // P/W = 1 这个任务首先执行 (1)

Task 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)Task 02 在机器 02 执行（我们寻找 P ms 执行任务，以及启动任务的最短时间，因为机器 01（从 9 ms 开始）和 02（从 8 ms 开始）都有 7 ms空闲时间，机器02可以先开始一个任务，然后机器01）。

(2)Task 03 在机器 02 中执行（我们寻找 P ms 来执行任务）。

(3)Task 01 在机器 01 中执行（我们寻找 P ms 来执行任务）。

某些时间段被定义为关键时间段，不能用于安排作业。这些周期（例如 5-9、7-8）存储在专用 structz_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

订购后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;

更新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;

}

输出：

   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 |
4

2 回答 2

4

我发现问题在于我如何在机器中搜索最小启动时间来启动任务：

....

// 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]因为 start 可能是指无法启动当前任务的机器，所以我做了一点改动：

// 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;
}
于 2013-01-23T01:27:46.187 回答
3

您的数组定义中存在持续的短一错误。基本上，C 数组是零索引的，所以如果你想访问array[n]，array必须至少用 size 定义n+1。例如你的机器结构应该是

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])。

于 2013-01-06T08:43:59.050 回答