作业调度问题深度搜索定界算法
深度搜索定界
设有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;}
分享到:
相关推荐
框架:pytorch/python 3.7 调度问题为:作业车间调度(JSP) 算法:Actor critic
该算法根据作业的分层优先级来产生作业队列,把队列中的同层作业从整体上看作是一位基因来处理,有效地对算法的进化方向进行规划,并通过对杂交和变异流程的改进,增强算法的搜索深度和广度。实验表明,相比于其他...
Python基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统设计源码+报告文档.zipPython基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统设计源码+报告文档.zip Python基于深度强化学习的...
基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统的研究源码+项目说明.zip基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统的研究源码+项目说明.zip基于深度强化学习的目的楼层预约调度...
为求解车间作业调度问题(JSSP),提出一种新颖的多小组协同学习的教学算法,实现小组间学习的协同及基于学习能力的深度和广度搜索策略.针对JSSP问题因其复杂度较高容易导致算法陷入局部最优的不足,引入学习小组协同学习...
关于蚁群算法和柔性作业车间调度问题不再赘述。 求解策略比较 如果用这篇文章中的方法,求解这个问题会很困难。因为同Job的不同工序是有先后顺序的,如果直接在上面这张表里搜索解,也就是说搜索出的是这张表里每一...
基于人工神经网络的作业车间调度算法.pdf
基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统的研究python源码+方案文档+项目说明.zip基于深度强化学习的目的楼层预约调度算法的多智能体电梯群控系统的研究python源码+方案文档+项目说明.zip基于...
本案例是一个10x10的车间调度问题,共有10个工件与10台机器,每个工件在每台机器上的加工顺序不同,程序的最终目标为最小化总的完工时间,资料是以工件的加工作业顺序来展现,每个工件都会经过10个加工作业,本资源...
电梯调度算法;强化学习;神经网络;深度强化学习;DQN 1.2本文的主要内容与章节安排 本部分在内容调整完以后最后写出。 .第二章 电梯调度本身要面临的环境 2.1 电梯群控系统概述 1.定义:在建筑设计中,通常将多台...
深度学习,神经网络学习资源,机器学习源码及案例,经典人工智能算法。 深度学习,神经网络学习资源,机器学习源码及案例,经典人工智能算法。 深度学习,神经网络学习资源,机器学习源码及案例,经典人工智能算法...
提出了一种数据驱动的作业车间调度算法,训练样本来源于基准实例和部分实际生产数据,通过特征函数来构建样本的特征数据并进行归一化处理,标签数据由调度任务和相应的调度规则的映射关系构成,以LSTM模型为主框架,...
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子...使用蚁群算法规划最优单车调度路径。
基于深度强化学习的资源调度研究python源码+项目说明.zip # deeprm_reforement_learning - 本项目基于[hongzimao/deeprm],原作者还著有论文[Resource Management with Deep Reinforcement Learning]...
基于深度学习的监督学习源码+项目说明(使用梯度下降、ALS、LFM算法,使用AngularJS2生成前端框架,数据库为MongoDB,使用ElasticSearch作为搜索服务器,Redis作为缓存数据库,其中包括Spark的离线统计服务、Azkaban...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
基于深度强化学习的云工作流调度python源码+详细注释+数据+项目说明(高分毕设).zip 关键词:有向无环图,工作流,深度强化学习,图神经网络; 蒙特卡洛树搜索 ## Installation It requires the following ...
经共生进化算法求解复杂柔性作业调度测试,定期大规模加入优势元素和随机元素能有效调整种群结构,既利用了前期种群进化收敛的结果又维持了种群进化全程的多样性。使进化算法可通过扩大搜索规模有效提高求解质量,将...