一个资源约束项目调度模型及其启发式算法研究

来源 :北京交通大学 | 被引量 : 3次 | 上传用户:qingqing4452638
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
针对某企业的生产需求,实际生产调度中存在位置限制及一些特殊的工序间关系约束,最小化最大完工时间是其最终的优化目标。由于该类问题与实际生产的效率与投入成本密切相关,因此其具有重要的研究价值。而目前的研究中并不存在解决此类问题的相关模型,因此本文通过对经典资源约束项目调度问题(Resource-constrained Project Scheduling Problem, RCPSP)的学习与研究,加入了工位约束及工序与资源间的约束,建立了一种特殊的资源约束项目调度问题模型。同时结合实际应用需求,提出了一个基于优先规则的构造型启发式算法。本文首先结合经典的资源约束项目调度问题详细分析了实际项目中存在的约束,重点阐述了在加入工位后,模型中的资源、工件与工序所受到的约束影响。接着结合已分析问题中的资源约束与工序约束,构建了一种特殊的资源约束项目调度问题,同时确定其问题目标为最小化最大完工时间,并提出了通用的问题模型。最后为了求解提出的新型问题模型,本文基于串行调度生成方案提出了一个求解目标为最小化最大完工时间的构造型启发式算法。在该算法中,主要使用了三种启发式规则,分别是:为工件选择最早可用且可加工工序数最多的工位、为工序配置最早可用且加工能力最强的可更新资源、在调度阶段中优先调度完工时间最早的工序。同时针对调度过程中可能产生的死锁问题,本文提出了相应的两种解决方法。结合实际生产数据,本文设计了实验方案,并对该实际算例进行了详细描述,将其作为本文提出的算法的输入数据,从而对该算法进行实验。实验结果表明该算法能够快速地构造问题的解,节省了大量的人力资源,并且可得到更优的调度方案。
其他文献
无线Mesh网络中节点倾向效仿高收益节点的行为,使网络在演化过程中自然形成具有协作能力的社团。有效利用社团协作服务能力是提高无线Mesh网络流媒体分发系统服务质量的有效
随着我国加入WTO和经济全球化的发展,中国的制造业企业面临更加激烈的市场竞争。推进信息技术的全面应用,加强企业资源的整合与管理,已经成为制造业企业生存和发展的必由之路。
随着企业信息化程度的提高,如何通过大量异构的数据源,为企业提供简单高效的数据访问能力,成为数据集成领域的研究重点。数据服务是面向服务体系结构在数据集成领域的应用,基
随着计算机技术、网络技术的快速发展,网络应用已从简单的信息交流发展到远程教学、视频点播、网络会议、数据分发和网络游戏等,这些应用不仅要求网络支持多播服务,而且对服
目前乒乓球机器人系统普遍存在两个难题:首先,乒乓球高速运动时,机器人较难在短时间内做出反应;其次,机器人无法识别来球类型(如下旋、上旋、无旋等),不能判断来球是否旋转以及
万维网地理信息系统(简称WebGIS)是Internet技术与GIS技术相结合的产物,为公众获取GIS数据和地理信息服务提供了一个有效的手段。但是从WebGIS的应用现状可以看出,这项技术远未
功能磁共振成像(fMRI)技术能够实时地对大脑神经功能活动进行成像,且由于其具有较高的空间分辨率、时间分辨率、无辐射损伤以及可在活体上重复进行检测等优势,已成为当今用于脑
软件构件技术是当前软件复用研究的焦点,被视为实现复用的关键因素之一。目前大多数开发的系统都存在难于进行业务扩展和系统升级等问题,因此,我们采用基于构件的软件开发方
随着国际互联网的普及和信息技术的发展,网络中的信息资源也在迅速增长,这些信息资源种类繁多、形式各异,存在于不同的信息系统中,这些特点给信息的消费带来很大的困难。为了
本文研究细分方法在图形学中的应用,细分方法近年来已成为图形学领域的一项重要研究内容。但是,要进一步拓广细分方法的应用范围(尤其在CAD领域),还有很多工作要做。本文先简单