准时化(JIT)思想下有关交货期窗口的单机调度问题

研究了有关交货期窗口的单机调度问题。在过去的１０年中,准时化的概念对中国工业的影响很大。早于或晚于交货期窗口的任务都不受欢迎,且将导致提前或拖期惩罚。如果任务的完工时间偏离了交货期窗口,就要受到固定的惩罚,惩罚量与提前或拖期完工无关。目标是极小化所有惩罚的和。设如果任务在交货期准时完工,则不受惩罚;目标就是寻找一个最优调度极小化提前和拖期任务的总数。给出了确定最优调度的多项式时间算法,最后的例子说     

模糊环境下再制造系统批量调度研究

针对再制造系统多种不确定因素,包括回收质量、准备时间、加工时间等,研究面向再制造系统的批量调度问题.考虑回收产品存在质量差异的情况,将回收品划分为几种质量不同的工件组类型,各工件组内所有工件的准备时间和加工时间相同,为了减小准备时间和子系统切换时间,将同一工件组内的工件分批量进行调度处理.在满足交货期、加工次序和机器有限等约束条件下,以加权完工时问最小化为目标,建立了模糊环境下的混合整数规划调度模型.该问题包含了工件分批次和调度顺序两个子问题,使用遗传算法进行求解,结合实际算例得出调度策略,验证了该模型在处理再制造生产调度问题上的有效性,并进一步分析了不同批量大小对再制造调度结果的影响.     

面向订单的生产计划与调度的综合优化

研究了一个多订单环境下的生产计划与调度集成优化问题,以实现准时生产为目标,综合考虑产品装配结构约束的订单任务计划与订单产品零部件的加工调度,采用直接面向客户订单的工序调度模式建立了计划和调度的综合优化整数规划模型.设计了带精英策略的蚁群算法作为该数学模型的求解方法,并通过对比试验为该算法选取最佳的搜索参数.实例仿真结果表明,所建模型的正确性以及蚁群算法求解该问题的可行性和有效性.     

产品可合并的多炉灶出餐调度模型与算法

为了解决在用餐高峰期餐饮企业外卖出餐速度慢的问题，根据餐厅外卖出餐中“多炉灶同时工作，订单包含多种菜品，相同订单同时取货，相同菜品可合并”的特点，构建订单完成时间满足率为目标的双层调度模型。双层模型的下层是以平行机调度为基础思路的多炉灶菜品包调度模型，可得到炉灶加工计划；上层是以背包问题为基础思路的订单选择模型，可确定订单完成时间。为了保证模型的求解效率，将静态模型扩展应用于动态调度的现实场景，设计针对性的遗传算法。算例实验结果表明，相比于最紧急菜品优先、最长加工时间优先、最热门菜品优先3种启发式策略，本模型的调度方法订单完成率最高，超时时间最短。     

多资源作业车间的混合自适应GA优化调度

针对多资源约束的车间调度问题,将启发式算法和自适应GA优化方法结合起来,提出了混合自适应GA方法,建立了多资源约束的车间优化调度模型.根据启发式调度算法中优先规则对调度目标的影响,设计了新的编码规则.采用正弦函数作为自适应因子,使得交叉概率和变异概率随群体的适应度自动改变,提高了运算的效率,克服了启发式算法和普通GA的缺陷.通过实例仿真并与其他算法比较结果表明,混合自适应GA算法可以很好的解决作业车间在机床、刀具等多种生产资源约束下的优化调度,并在评价指标上较其他算法更优.     

基于多重约束的飞机移动装配线作业调度优化

基于对飞机移动装配线作业多重约束的分析,建立了作业调度优化问题的整数规划模型,提出了组合优先规则WRST以及基于此规则的启发式算法.WRST综合考虑了最迟完成时间、资源以及空间稀缺度三个指标;而算法设计包括基于WRST规则的作业拓扑排序和作业资源分配两阶段.数值试验结果显示基于WRST规则的启发式算法求解质量高,求解速...     

基于公理设计的车间调度算法研究

车间调度问题是典型的NP难题,也是一种完全耦合的复杂系统.基于公理设计思想对车间调度系统进行了解耦设计,给出了相应的解耦思路及解耦矩阵,提出并实现了一种车间调度算法,并对算法的复杂性进行了分析.以实际车间生产调度作为研究对象,针对实际生产中零件紧急程度不一的情况,为待加工零件赋予不同的权值,并优先考虑调度加工工时较长的零件;采用以解耦设计为总目标,在满足约束条件的情况下,尽量优化压缩加工时间.对算法的复杂性进行了分析,该算法属于三次多项式复杂级,较优于一般的算法.通过2个实例计算和对比,验证了本算法的实用性和有效性.     

面向Jobshop调度的时间映射算法

现实的Jobshop生产环境中的生产日历和班次等把设备资源的有效工作时间段分割成离散状态。为了降低调度在确定工序开始和结束时间时的计算复杂性,提出了一种时间映射算法。通过该算法实现了离散作业时间到整数连续区间和整数连续区间到离散作业时间的快速转换;并以遗传调度算法为例,研究了时间映射算法与调度算法的融合技术,实现了在连续整数区间上的调度。研究结果表明,相比未采用时间映射算法的调度算法,采用时间映射算法能大幅降低调度在确定工序开始和结束时间上的计算复杂性,计算时间降幅达到39.7%,从而提高了调度的计算效率。     

集装箱码头岸吊作业调度建模及调度策略研究

岸吊作业调度对集装箱码头整体运营效率具有重要影响.综合考虑岸吊实际作业中的特有约束,包括预定义顺序约束、依赖于作业次序的设备调整时间、岸吊干涉约束,建立岸吊作业调度问题的混合整数规划模型.针对混合装卸模式,使用启发式算法生成预定义作业顺序,在此基础上采用基于连续贝作业策略的启发式算法对问题进行求解.数据实验结果显示基于SPT规则和连续贝作业的启发式算法能有效利用混合装卸带来的时间节省,减少设备调整时间,对实际岸吊作业调度具有指导意义.     

生物计算网格中的在线调度技术研究

研究了在异构网格环境下的生物应用集成,定义了服务的提供者、部署者和使用者三种用户角色,设计了网格环境下的服务和资源整合机制,重点实现了用户管理以及作业调度控制等功能.根据计算资源的异构特点,设计了多种启发式调度算法.考虑到生物计算应用的不同类型,提出了自适应调度算法,该算法根据应用的特点动态选择启发式调度算法.实验表明,非阻塞调度优于阻塞调度方式;自适应调度算法比静态的在线调度算法有更好的性能,而在异构的网络中,带宽优先调度算法的性能比其他静态调度算法性能更好.     

An integrated scheduling algorithm with device dependence deferred constraint

针对目前综合调度中没有考虑设备有关延迟约束(DDC)影响调度效果的问题,提出了存在设备有关延迟约束的综合调度的算法.该算法在标准工序、设备有关延迟工序(DDP)和包含设备有关延迟约束的加工工艺树等概念的基础上,将等待延迟时间转化为设备有关延迟工序,使存在DDC的调度问题转变为较易解决的一般综合调度问题,再用拟关键路径法( ACPM)确定工序的调度次序,最后用前沿贪心规则确定工序的开始时间.为了使设备有关延迟工序影响的工序尽早开始,进一步提出了设备有关延迟工序配合调整的策略.实验表明,该调度算法能够有效解决存在设备有关延迟约束的综合调度问题,可在不提高算法复杂度的前提下,提高调度结果的精度并减少产品总的加工时间.     

基于改进粒子群算法的大规模定制生产调度问题研究

随着科学技术的飞速发展,物质生活得到了极大的丰富。客户不再被动地选择已有的商品,相反他们的需求趋于多样化和分散化,客户产品定制化的需求日益突出,促使了生产方式由原来的大批量生产向大规模定制的生产方式转变。本文针对大规模定制生产多品种、小批量以及快速响应的生产特性,以装配时的同时度以及基于交货期的准时度为目标函数建立调度模型并建立相关约束。针对标准粒子群算法的不足引入速度惩罚机制改进算法,最后通过实例验证了调度模型以及改进算法的有效性与合理性。     

考虑急件到达的单机鲁棒调度方法

实际生产过程中经常会有急件到达。由于急件的优先级最高,其到达容易扰乱初始调度,使实际调度性能恶化,影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题,研究了在有急件到达情况下的鲁棒调度方法,以降低急件对实际调度性能的影响。鉴于该调度问题是NP hard问题,根据工件释放时间和交货期的关系构造“金字塔”结构,获得该调度问题的占优性质。根据这些占优性质和急件到达特点,研究急件到达情景下的占优规则,据此求解急件到达情景下的占优调度集合,作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性,算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。      

基于混沌粒子群的资源受限项目调度问题

鉴于基本粒子群算法易陷入局部最优,提出一种将混沌算法嵌入基本粒子群的混沌粒子群算法,并将其用于求解典型的资源受限项目调度问题。采用基于优先值的粒子编码方式和串行调度方案,分别用基本粒子群算法和混沌粒子群算法对实例求解。并且比较了2种算法求解多资源受限项目调度问题的性能。结果表明:混沌粒子群算法在距最优值的平均偏差和达到最优值的次数百分比等性能上要优于基本的粒子群算法,并且混沌粒子群具有更好的收敛性。但是,混沌粒子群算法在计算达到最优工期的平均时间上略比基本粒子群算法逊色。     

基于仿真的急诊室动态调度研究

针对急诊室患者就诊全流程,建立了包含诊室阶段和检查阶段两个决策模块的仿真模型。在诊室阶段分别采用初诊完全优先、复诊完全优先和基于初诊患者期望超期时间的阈值策略,在检查阶段分别采用检查时间最短优先、等报告时间最长优先和基于禁忌搜索的重调度策略,仿真数据参考医院实际数据及文献中的数据。仿真结果表明:诊室阶段采用阈值策略能够平衡初复诊患者的等待时间,检查阶段采用基于禁忌搜索的重调度策略能够显著降低患者检查滞留时间,诊室阶段调度策略对检查滞留时间影响较大。该结论为多阶段带反馈机制的协同调度问题提供了新的研究思路。     

基于优先规则的船舶分段空间调度算法

为有效解决船舶分段的空间调度问题,提出了一种基于优先规则的求解算法。首先利用优先规则和禁忌搜索算法产生可行的分段调度序列,再采用一种启发式定位策略——最下最左填满策略对产生的调度序列进行解码,以评估调度序列的优劣。算法不断迭代,最终可得到近似最优解。对船厂的实际生产数据进行了实证分析,并与现有的算法进行了对比,验证了所提出的算法在空间调度问题上的有效性和优越性。     

时间依赖网络城市物流车辆调度的模型及算法

在城市配送中,车辆在不同时间段通过相同路径的行驶时间可能不同,时间依赖网络能更好地刻画城市物流车辆调度的实际特征,解决时间依赖条件下的城市物流车辆调度优化问题具有更强的实际应用意义。文在分析时间依赖网络车辆行驶时间的基础上,综合考虑顾客及物流公司两方面要求,以总配送时间、使用车辆数最小及客户满意度最大为目标,建立多目标时间依赖网络城市物流车辆调度模型;设计了遗传算法对该模型进行求解,并进行了算例研究,算例分析表明本模型在城市物流车辆调度方面是合理可行的,设计的算法是有效的。     

多层级装配作业车间分批调度算法设计与分析

多层级装配作业车间调度是一类包含加工与装配的双阶段调度问题，装配产品具有不同的树状结构，且各层级的装配工序需要直属零部件完工方可执行。分批调度可以提高车间生产流动性，故而被运用在作业车间调度等领域。装配作业车间分批调度需要解决关联零部件及其下属子批的进度协同性问题，为此建立了多层级装配作业车间的分批优化调度模型，以最小化拖期成本与库存持有成本为优化目标。出于求解效率考虑，构建基于遗传算法与优先分派规则的混合求解算法以应对批量划分与排序两个子问题。最后，设计仿真实验验证分批调度算法的有效性，并分析评估在8种作业分派规则、3类分批策略下混合算法对于差异化产品结构的适应性。通过分析实验结果发现，等量分批策略可以在给定条件下有效提升混合算法的调度性能。     

考虑人格因素的软件项目调度模型与算法

软件项目的成功离不开对技能型人力资源的合理调度，而项目团队中员工的人格特质往往会影响其执行任务的效果。研究了多技能条件下考虑人格因素的软件项目调度问题，旨在满足技能、优先关系等约束条件下，将具有不同技能和人格特质的员工进行有效调度，从而最小化项目总成本。建立了该问题的混合整数线性规划模型，设计了基于双重优先规则的启发式调度算法。基于全因子试验设计构建基准数据集，利用计算实验分析了所提算法的性能。将所提算法同CPLEX和遗传算法进行了对比，结果表明所提算法在求解效率和效果上均具备优秀的竞争力。     

用混合量子算法求解模糊柔性作业车间调度问题

针对模糊环境下柔性作业车间的调度问题,以最小化最大完工时间、最小化成本和最小化惩罚值为目标,建立调度问题数学模型,提出了混沌量子粒子群算法。针对实际生产交货期模糊的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;针对量子个体的更新,提出了改进的量子旋转角计算方法;针对种群可能局部早熟收敛和后期多样性丢失的问题,利用混沌机制的遍历性,提出混沌局部优化策略;通过四个经典的调度算例验证了所提出算法能降低早熟概率和提高迭代搜索效率,与其他算法比较可以获得更多的非支配解。