| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 649 人关注过本帖
标题:多处理机调度问题
取消只看楼主 加入收藏
shaojinkuang
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2008-6-9
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:1 
多处理机调度问题
具体问题:设有n个工作,在m个处理机上可以并行运行,每个工作在每个处理机上预测时间都不一样,求最优调度时间,也就是最短时间,(也就是最后一个工作在处理机上停止的截止日期最短)我想的是用动态规划做此题目,但是写着写着就成了回溯了,虽然能达到程序最后目标,但是如果m或者n值增大的话,就程序性能急剧下降了,时间耗费太久了,以下是代码,这个肯定是枚举的了,m,n小还可以,但是增大就不行了,正在尝试用动态规划写,但是有点问题,看有人能做出来不

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

#define n 3
#define m 2
//int w[n][m]={{6,2,4},{4,7,5},{5,6,6},{9,10,3}};
int matrix[n][m]={{2,5},{3,1},{9,2}};
class node
{
      public:
             node(int value,int index)
             {
                      this->value=value;
                      this->index=index;
             }
      public:
              int value;
              int index;
};
class Task
{
      private:
              vector<node> v;
              int bestw;
              int best[n];
              int savex[n];
              int *load;
      public:
             void initTask();
             void backtrack(int i);
             void printsave();  
             int getValue(vector<node> v,int number);     
};
void Task::initTask()
{
     bestw=1000;
     int i;
     load=new int[m];
     for(i=0;i<m;i++)
     {
                     
                     load[i]=0;
     }
     for(i=0;i<n;i++)
     {
                     best[i]=-1;
     }
     int j;
     for(i=0;i<n;i++)
     {
                     for(j=0;j<m;j++)
                     {
                            cout<<matrix[i][j]<<" ";         
                     }
                     cout<<endl;
     }
}
int Task::getValue(vector<node> v,int number)
{
    int k;
    int value;
    for(k=0;k<v.size();k++)
    {
                           node d=v[k];
                           load[d.index]+=d.value;
    }
    value=0;
    for(k=0;k<m;k++)
    {
                    if(load[k]>value)
                    {
                                     value=load[k];
                    }
    }
    for(k=0;k<m;k++)
    {
                    load[k]=0;
    }
    return value;
}

void Task::backtrack(int i)
{
     if(i==n)
     {
             int value=getValue(v,i);
             if(value<bestw||bestw==-1)
             {
                                    int j;
                                    bestw=value;
                                    for(j=0;j<n;j++)
                                    {
                                                    savex[j]=best[j];
                                    }
             }
             return;
     }
     for(int k=0;k<m;k++)
     {
             best[i]=k;
             node temp(matrix[i][k],k);
             v.push_back(temp);
             backtrack(i+1);
             v.pop_back();
             best[i]=-1;
     }
}
void Task::printsave()
{
     cout<<"最小bestw是:"<<bestw<<endl;
     for(int k=0;k<n;k++)
     {
             cout<<"第"<<k+1<<"任务由第"<<savex[k]+1<<"虚拟机处理"<<endl;
     }
}
int main(int argc, char *argv[])
{
    Task c1;
    c1.initTask();
    c1.backtrack(0);
    c1.printsave();
    system("PAUSE");
    return EXIT_SUCCESS;
}
搜索更多相关主题的帖子: 时间 include 动态 
2012-07-16 15:16
shaojinkuang
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2008-6-9
收藏
得分:0 
看来我要把我的帖子删除了,发现很多人有需要这方向的问题
2012-08-22 14:16
快速回复:多处理机调度问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.034713 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved