1 题目

n个作业{1, 2, …, n}要在两台机器上处理,每个作业必须先由机器1处理,然后再由机器2处理,机器1处理作业i所需时间为ai,机器2处理作业i所需时间为bi(1≤i≤n),要求确定这n个作业的最优处理顺序,使得从第1个作业在机器1上处理开始,到最后一个作业在机器2上处理结束所需时间最少。

2 代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#define MAX 10
#define MACHINE 2
using namespace std;

int n;
int M[MAX][MACHINE];
int a[MAX][MACHINE];
int b[MAX][MACHINE];
int bestx[MAX];
int best_ans;
int y[MAX][MACHINE];

struct Node
{
    int s,f1,f2,sf2,bb,*x;
    bool operator < (const Node &node) const
    {
        return bb > node.bb;
    }
};

//优先队列
priority_queue<Node> pq;

void initNode(Node &node, int n)
{
    node.x = new int[n];
    for(int i=0; i<n; i++)
    {
        node.x[i] = i;
    }
    node.s = 0;
    node.f1 = 0;
    node.f2 = 0;
    node.sf2 = 0;
    node.bb = 0;
}

void newNode(Node &node, Node E, int Ef1, int Ef2, int Ebb, int n)
{
    node.x = new int[n];
    for(int i=0; i<n; i++)
    {
        node.x[i] = E.x[i];
    }
    node.f1 = Ef1;
    node.f2 = Ef2;
    node.sf2 = E.sf2 + Ef2;
    node.bb = Ebb;
    node.s = E.s + 1;
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}


void sort()
{
    int *c = new int[n];
    for(int j=0; j<2; j++)
    {
        for(int i=0; i<n; i++)
        {
            b[i][j] = M[i][j];
            c[i] = i;
        }
        for(int i=0; i<n-1; i++)
        {
            for(int k=n-1; k>i; k--)
            {
                if(b[k][j]<b[k-1][j])
                {
                    swap(b[k][j], b[k-1][j]);
                    swap(c[k], c[k-1]);
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            a[c[i]][j] = i;
        }
    }
    delete []c;
}

int bound(Node E, int &f1, int &f2, int y[MAX][MACHINE])
{
    for(int k=0; k<n; k++)
    {
        for(int j=0; j<=1; j++)
        {
            y[k][j] = 0;
        }
    }

    for(int k=0; k<=E.s; k++)
    {
        for(int j=0; j<2; j++)
        {
            y[a[E.x[k]][j]][j] = 1;
        }
    }

    f1 = E.f1 + M[E.x[E.s]][0];
    f2 = ((f1>E.f2)?f1:E.f2) + M[E.x[E.s]][1];
    int sf2 = E.sf2 + f2;
    int s1 = 0, s2 = 0;
    int k1 = n - E.s,  k2 = n - E.s;
    int f3 = f2;

    for(int j=0; j<n; j++)
    {
        if(!y[j][0])
        {
            k1--;
            if(k1 == n-E.s-1)
                f3 = (f2>f1+b[j][0])?f2:f1+b[j][0];
            s1 += f1 + k1 * b[j][0];
        }
    }

    for(int j=0; j<n; j++)
    {
        if(!y[j][1])
        {
            k2--;
            s1 += b[j][1];
            s2 += f3 + k2 * b[j][1];
        }
    }
    return sf2 + (s1>s2?s1:s2);
}

int flowShop()
{
    sort();
    Node E;
    initNode(E, n);
    best_ans = 1000000;
    while(E.s<=n)
    {
        if(E.s==n)
        {
            if(E.sf2 < best_ans){
                best_ans = E.sf2;
                int i;
                for(i=0; i<n; i++)
                    bestx[i] = E.x[i];
                delete []E.x;
            }
        }
        else
        {
            for(int i=E.s; i<n; i++)
            {
                swap(E.x[E.s], E.x[i]);
                int f1, f2;
                int bb = bound(E, f1, f2, y);
                if(bb<best_ans)
                {
                    Node node;
                    newNode(node, E, f1, f2, bb, n);
                    pq.push(node);
                }
                swap(E.x[E.s], E.x[i]);
            }
            delete []E.x;
        }

        if(pq.empty())
            break;
        E = pq.top();
        pq.pop();
    }
    return best_ans;
}

void init(int nn, int MM[MAX][MAX])
{
    n = nn;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<2; j++)
        {
            M[i][j] = MM[i][j];
        }
    }
}

int main()
{
    int nn;
    int MM[MAX][MAX]={0};
    printf("请输入作业的数量:");
    scanf("%d", &nn);
    printf("请输入每个作业在机器1的处理时间和在机器2的处理时间:");
    for(int i=0; i<nn; i++)
    {
        for(int j=0; j<=1; j++)
        {
            scanf("%d", &MM[i][j]);
        }
    }
    init(nn, MM);
    int best = flowShop();
    printf("最少完成时间和:%d\n", best);
    printf("最优调度:\n");
    for(int i=0; i<n; i++)
        printf("%d ", bestx[i]+1);

    printf("\n");
    return 0;
}

 /*
    int nn = 3;
    int M1[3][2] = {
        {2, 1},
        {3, 1},
        {2, 3}
    };
    */
0
Posted in ACM

Leave a Comment:

电子邮件地址不会被公开。