设有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短? 本文用C++实现，方便C/C++读者。
深度搜索定界
设有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=231http://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 611 7 5 5 4 7输出结果如下：7 75 5 411time=14 */#include <cstdlib>#include <iostream>#include <vector>#include <fstream>#include <iterator>#include <numeric>using namespace std;// input parametersint g_nProcessor;int g_nJob;typedef vector<double> D_VEC;D_VEC g_vJobTime;// end of input parameters// search statedouble g_dMaxTime;typedef vector<bool> BOOL_VEC;BOOL_VEC g_vJobDone;int g_iCurProc; // as search depthD_VEC g_vProcUsedTime;double g_dRestJobTime;// end of search statevoid 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[] descend2. 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;}
京公网安备 11010802021500号