作业调度问题深度搜索定界算法
作业调度问题深度搜索定界算法
深度搜索定界
设有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?
Pascal代码实现：http://blog.csdn.net/jq0123/archive/2006/06/05/773593.aspx
本文用C++实现，方便C/C++读者。
上界定得很松:
g_dMaxTime = g_dRestJobTime;
所以速度会慢一点。
可以应用迭代加深使搜索更快。
即开始时将上界定为最紧：
g_dRestJobTime / g_nProcessor
搜索不成功再迭代放宽上界。
没有保存作业分配方案，只有时间值。
/*
http://it.pjschool.com.cn/Article/ArticleShow.asp?ArticleID=231
http://blog.csdn.net/jq0123/archive/2006/06/05/773593.aspx
深度搜索定界
例2：设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?
说明：本题有两重搜索法，搜索处理机和搜索作业，当m，n较大时，搜索处理机不可能？搜索作业容易确定上下界，容易剪支。
若输入文件是：
3 6
11 7 5 5 4 7
输出结果如下：
7 7
5 5 4
11
time=14
*/
#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <iterator>
#include <numeric>
using namespace std;
// input parameters
int g_nProcessor;
int g_nJob;
typedef vector<double> D_VEC;
D_VEC g_vJobTime;
// end of input parameters
// search state
double g_dMaxTime;
typedef vector<bool> BOOL_VEC;
BOOL_VEC g_vJobDone;
int g_iCurProc; // as search depth
D_VEC g_vProcUsedTime;
double g_dRestJobTime;
// end of search state
void PrepareSearch()
{
g_dRestJobTime = accumulate(g_vJobTime.begin(), g_vJobTime.end(), 0.0);
g_dMaxTime = g_dRestJobTime;
g_vJobDone = BOOL_VEC(g_nJob, false);
g_iCurProc = 0;
g_vProcUsedTime = D_VEC(g_nProcessor, 0);
}
void ReadParams()
{
ifstream cin("input.txt");
cin >> g_nProcessor >> g_nJob;
double dTime;
for (int i = 0; i < g_nJob; i++)
{
cin >> dTime;
g_vJobTime.push_back(dTime);
}
}
bool AddJob(int iJob)
{
g_vProcUsedTime[g_iCurProc] += g_vJobTime[iJob];
g_dRestJobTime -= g_vJobTime[iJob];
}
void DelJob(int iJob)
{
g_vProcUsedTime[g_iCurProc] -= g_vJobTime[iJob];
g_dRestJobTime += g_vJobTime[iJob];
}
/*
Return false if add job bounce the limit：
1. g_vProcUsedTime[] descend
2. g_vProcUsedTime[1] less than MaxTime
*/
bool CanAddJob(int iJob)
{
double dNewTime = g_vProcUsedTime[g_iCurProc] + g_vJobTime[iJob];
if (0 == g_iCurProc)
return dNewTime < g_dMaxTime;
else
return dNewTime <= g_vProcUsedTime[g_iCurProc - 1];
}
// Assign nFromJob..MAX to current processor
// Go next proc if all job tried.
void SearchFromJob(int iFromJob)
{
if (g_nProcessor == g_iCurProc)
{
// all proc assigned, update max time
if (g_dRestJobTime > 0) return;
if (g_dMaxTime > g_vProcUsedTime[0])
g_dMaxTime = g_vProcUsedTime[0];
cout << "(DEBUG)MaxTime: " << g_dMaxTime << endl; // debug
return;
}
/* / debug
cout << "CurProc " << g_iCurProc
<< " : search From job " << iFromJob << endl;
cout << "Job done list: ";
copy(g_vJobDone.begin(), g_vJobDone.end(),
ostream_iterator<int>(cout, " "));
cout << endl;
cout << "Proc used time: ";
copy(g_vProcUsedTime.begin(), g_vProcUsedTime.end(),
ostream_iterator<double>(cout, " "));
cout << endl;
*/
for (int i = iFromJob; i < g_nJob; i++)
{
if (g_vJobDone[i]) continue;
if (!CanAddJob(i)) continue;
AddJob(i);
g_vJobDone[i] = true;
SearchFromJob(i + 1);
g_vJobDone[i] = false;
DelJob(i);
}
// current proc assigned, search from next proc
int nProcRest = g_nProcessor - 1 - g_iCurProc;
double dMaxRestTime = nProcRest * g_vProcUsedTime[g_iCurProc];
if (dMaxRestTime < g_dRestJobTime)
return; // stop this branch
g_iCurProc++;
SearchFromJob(0);
g_iCurProc--;
}
int main(int argc, char *argv[])
{
ReadParams();
PrepareSearch();
SearchFromJob(0);
cout << "Max time: " << g_dMaxTime << endl;
system("PAUSE");
return EXIT_SUCCESS;
}