首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 46 毫秒
1.
针对带缓冲与驻留约束的集束型设备调度问题,本文提出了一种基于分枝的搜索调度方法.首先,构造问题域的数学模型,在此基础上提出了一种全局搜索算法;然后,通过数学分析证明引出必要的引理,提出一个基于分枝搜索的算法;最后,进行了仿真实验和分析,结果表明本文提出的算法是有效且可行的,同时还表明了带缓冲模块的集束型设备在一定程度上能提高集束型设备的产能.  相似文献   

2.
针对半导体制造中有滞留时间约束的集束型装备,研究了临时晶网到达时的在线调度问题,描述了调度问题域.建立了问题的数学模型,并根据模型提出了两层调度方法.外层算法通过粒子群优化过程求解临时晶网的加工顺序;内层算法在给定加工顺序的基础上,采用前向和后向递推方法获得口,行解窄问,并从可行解窄问获得最优完工时间.从理论上证明了算...  相似文献   

3.
时间约束调度中功能单元的下限估算   总被引:1,自引:0,他引:1  
针对高层次综合中时间约束下的调度问题,提出了对功能单元的2种下限估算算法:单位长度调度法和最大网络流法.其主要思想是将原调度问题的不同约束放松,得到多项式可解的新问题,并使得新问题的最优解是原调度问题的下限值.将2种算法与已有的最小重叠法和整数线性规划给出的最优解做了理论和实验上的比较.实验结果表明:2种估算算法运行时间合理,并且单位长度调度法比最小重叠法更准确.最后总结了各种约束对下限估算准确性的影响.  相似文献   

4.
车间调度是智能制造领域中的核心问题之一,在经典流水车间调度中,所有工件按照相同的加工顺序在指定机床上加工.混合流水车间调度(HFS)作为流水车间调度的特例,相比前者增加了机床选择的灵活性,可以显著优化系统目标,但同时也增加了问题求解的难度.由于时间约束HFS相比基本HFS问题更贴近实际生产过程,近年来,综合考虑各类时间相关约束的HFS问题得到了深入研究.因此,本文围绕基本HFS、有限等待时间HFS、带准备时间HFS、模糊/随机加工时间HFS、多时间约束HFS、时间约束相关多目标HFS等问题开展研究.针对每一类时间约束HFS问题,按照问题规模对当前研究成果进行分类描述,按照确定性算法、启发式方法、元启发式方法、算法混合对相关成果进行算法分类,按照实际工业应用对文献进行归类分析.另一方面,围绕交货期、能耗、成本等3类性能指标,分析了在各类时间约束HFS问题中的多目标优化相关成果.最后详细分析了带时间约束HFS问题在问题层面、算法层面和应用层面存在的挑战性问题和未来研究的方向.  相似文献   

5.
在半导体晶圆制造中,违反驻留时间约束会导致晶圆损坏,同时,双组合设备涉及两个设备间的资源协调配合,使得调度更加复杂。本文考虑晶圆驻留时间约束,研究了配置全并行加工模块的双组合设备的稳态协同调度问题。首先,构建面向资源的Petri网模型,描述了具有驻留时间约束和全并行加工模块的双组合设备的稳态加工过程,提出控制策略防止系统发生死锁;其次,通过分析加工模块的负载和机械手的任务过程,得到了机械手无任务冲突的条件;针对任务冲突的情况,推导出系统的可调度条件,并开发了两个算法求解系统的稳态周期时间和可行的机械手调度方案;最后,通过实例来验证算法的可行性与有效性。  相似文献   

6.
针对进口集装箱卸船的岸桥与集卡集成调度问题,分别提出混合整数规划(MIP)模型和约束规划(CP)模型,目标是使得卸船完工时间最短,该问题是NP难题。通过OPL语言设计约束规划模型,利用其为调度问题提供的特殊构造,如区间变量、序列变量等进行建模,并采用"扩展操作任务"的概念来定义区间变量以提升求解效率。为评价解的质量,设计一个新的下界求解方法。使用不同规模的实例对约束规划模型和MIP模型进行测试,结果表明,在小规模实例中,CP模型求解性能略差于MIP模型,但对于中大规模实例,MIP模型无法在设定时限内找到解,而CP模型则能以较快的收敛速度得到高质量的解,目标距离下界的差距控制在2.19%~8.28%。  相似文献   

7.
在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.  相似文献   

8.
王凌  王晶晶 《控制与决策》2021,36(10):2350-2358
当今社会环境问题日益严重,能源成本日益提高,峰值能耗在生产制造中备受关注.针对带峰值能耗约束的流水线调度问题,即生产过程中各时间节点机器总功耗不得超过给定阈值,以最小化最大完工时间为目标,提出一种协同群智能算法.首先,协同多种解码方法产生多样化的可行调度,融合启发式方法与随机方法以初始化种群;其次,设计两类基于问题特性...  相似文献   

9.
基于设备故障的间歇化工过程反应型调度   总被引:4,自引:0,他引:4  
间歇化工过程生产中的不确定性因素很多,由于其不可预见性和多样性,不可能在产生原调度的同时给出不确定因素的最合适的处理方案,而是需要在不确定因素发生时结合过程的实际情形,来对原调度进行反应型调度.本文考察了设备故障的影响,根据设备故障的特点和所加工物料的性质,分故障产品重加工、故障工序继续加工和故障工序重加工三类加以分析和处理,建立了该问题的数学模型并用遗传算法来对该问题进行求解.文中给出设备故障反应型调度的算例,通过设备的维修时间、物料的处理方式以及故障发生时间对反应型调度的灵敏度分析揭示了基于设备故障的间歇化工过程反应型调度的实质.  相似文献   

10.
挖掘极大频繁页面集是WEB使用挖掘中的关键应用之一。由于一定时间段的会话中蕴含着用户的访问模式与访问动机,设计一种结点带有驻留时间,类似FP-tree的频繁页面树FPDT-tree结构;利用FPDT-tree结构存储双向驻留时间约束的会话数据库,简化挖掘过程中驻留时间阈值的设置。基于FPDT-tree提出算法MFPSM挖掘会话中的极大频繁页面集,实验结果表明,在时间约束环境中,通过决策者给出合适的时间约束阈值,该算法可以有效地缩短挖掘极大频繁页面集的时间。  相似文献   

11.
    
Multi-cluster tools are widely used in majority of wafer fabrication processes in semiconductor industry. Smaller lot production, thinner circuit width in wafers, larger wafer size, and maintenance have resulted in a large quantity of their start-up and close-down transient periods. Yet, most of existing efforts have been concentrated on scheduling their steady states. Different from such efforts, this work schedules their transient and steady-state periods subject to wafer residency constraints. It gives the schedulability conditions for the steady-state scheduling of dual-blade robotic multi-cluster tools and a corresponding algorithm for finding an optimal schedule. Based on the robot synchronization conditions, a linear program is proposed to figure out an optimal schedule for a start-up period, which ensures a tool to enter the desired optimal steady state. Another linear program is proposed to find an optimal schedule for a close-down period that evolves from the steady state period. Finally, industrial cases are presented to illustrate how the provided method outperforms the existing approach in terms of system throughput improvement.   相似文献   

12.
Peter Z. Revesz 《Constraints》1997,2(3-4):361-375
A genome map is an ordering of a set of clones according to their believed position on a DNA string. Simple heuristics for genome map assembly based on single restriction enzyme with complete digestion data can lead to inaccuracies and ambiguities. This paper presents a method that adds additional constraint checking to the assembly process. An automaton is presented that for any genome map produces a refined genome map where both the clones and the restriction fragments in each clone are ordered satisfying natural constraints called step constraints. Any genome map that cannot be refined is highly likely to be inaccurate and can be eliminated as a possibility.  相似文献   

13.
    
A treelike hybrid multi-cluster tool is composed of both single-arm and dual-arm cluster tools with a treelike topology. Scheduling such a tool is challenging. For a hybrid treelike multi-cluster tool whose bottleneck individual tool is process-bound, this work aims at finding its optimal one-wafer cyclic schedule. It is modeled with Petri nets such that a onewafer cyclic schedule is parameterized as its robots' waiting time. Based on the model, this work proves the existence of its onewafer cyclic schedule that features with the ease of industrial implementation. Then, computationally efficient algorithms are proposed to find the minimal cycle time and optimal onewafer cyclic schedule. Multi-cluster tool examples are given to illustrate the proposed approach. The use of the found schedules enables industrial multi-cluster tools to operate with their highest productivity.   相似文献   

14.
Resource Constraints for Preemptive Job-shop Scheduling   总被引:3,自引:0,他引:3  
This paper presents an experimental study of constraint propagation algorithms for preemptive scheduling. We propose generalizations of non-preemptive constraint propagation techniques (based on timetables, on disjunctive constraints, and on edge-finding) to preemptive and mixed problems, i.e., problems in which some activities can be interrupted and some cannot. Another approach relies on incremental flow-based techniques. We theoretically compare these approaches and present an experimental comparison based on a branch and bound procedure for the preemptive variant of the job-shop scheduling problem. We show that both edge-finding and flow-based techniques allow the resolution of hard problem instances, including the preemptive variant of the famous FT10.  相似文献   

15.
In a heterogeneous multi-cluster (HMC) system, processor allocation is responsible for choosing available processors among clusters for job execution. Traditionally, processor allocation in HMC considers only resource fragmentation or processor heterogeneity, which leads to heuristics such as Best-Fit (BF) and Fastest-First (FF). However, those heuristics only favor certain types of workloads and cannot be changed adaptively. In this paper, a temporal look-ahead (TLA) method is proposed, which uses an allocation simulation process to guide the decision of processor allocation. Thus, the allocation decision is made dynamically according to the current workload and system configurations. We evaluate the performance of TLA by simulations, with different workloads and system configurations, in terms of average turnaround time. Simulation results indicate that, with precise runtime information, TLA outperforms traditional processor allocation methods and has up to an 87% performance improvement.  相似文献   

16.
为了提高求解效率,对建模操作与特征依赖之间的对应关系进行分析,提出了一种确定最小特征相关集的方法.同时,使用最小特征相关集来选择与模型操作相关的约束方程,以降低求解的规模.将所提出的方法应用到HUST-CAID系统中,对建模过程中的约束关系变化进行求解.实验结果表明建模效率有所提高.  相似文献   

17.
孔峰  司戈  郭金亮 《控制与决策》2024,39(5):1620-1628
资源受限项目调度问题(RCPSP)是最具代表性的项目调度问题之一,针对实际情况中考虑资源投入的必要性,建立一种以资源投入为变量的基于广义资源日历约束的项目调度优化模型.首先,引入组合优先关系的概念对广义资源日历的概念和具体内容进行整合和完善,为了避免传统网络图在表示组合优先关系时出现的网络循环等弊端,使用节点表示活动开始和结束的瞬时状态改进节点网络图;其次,考虑活动优先关系、活动持续时间、不可更新资源总量和资源日历约束,以项目工期最短和项目成本最小为优化目标,运用CP优化器求解所建立的多目标优化模型;最后,通过设计仿真算例并进行数值实验验证模型的准确性和高效性.  相似文献   

18.
提出了计算资源共享平台中具有时间约束的工作流任务调度方法,该方法利用了非集中式的树型应用层覆盖网络拓扑结构,从而可以高效而快速的收集资源的可用信息。采用全局调度器与本地调度器结合的方式,通过定义资源的收集功能过程,使每个节点中的本地调度器能够把自身的资源可用信息提供给全局的调度器,工作流中任务的最后期限时间约束和任务的恢复时间以一种时间间隙的机制来完成。仿真结果表明,分治模式和解方程类的迭代模式的工作流任务能够在平台上成功调度运行,具有比较快的响应时间和低的通信负载。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号