首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Scheduling problems can be viewed as a set of temporal metric and disjunctive constraints and so they can be formulated in terms of CSP techniques. In the literature, there are CSP-based methods which sequentially interleave search efforts with the application of consistency enforcing mechanisms and variable/ordering heuristics. Therefore, the number of backtrackings needed to obtain a solution is reduced. In this paper, we propose a new method that effectively integrates the CSP process into a limited closure process: not by interleaving them but rather as a part of the same process. Such an integration allows us to define more informed heuristics. These heuristics are used to limit the complete closure process to a maximum number of disjunctions, thereby reducing its complexity while at the same time reducing the search space. Some open disjunctive solutions can be maintained in the CSP process, limiting the number of backtrackings necessary, and avoiding having to know all the problem constraints in advance. Our experiments with flow-shop and job-shop instances show that this approach obtains a feasible solution/optimal solution without having to use backtracking in most cases. We also analyze the behaviour of our algorithm when some constraints are known dynamically and we demonstrate that it can provide better results than a pure CSP process.  相似文献   

2.
赵霁  王建国 《计算机工程》2004,30(24):156-158
针对半导体制造行业,提出了一种仿真调度方法来辅助调度员进行生产作业计划的编制,系统的实用性占据首要地位。方法采用了人机交互策略,使得调度员能够实时地监控车间设备的生产情况,方便对各台设备进行任务分配,并能形象地仿真调度结果。  相似文献   

3.
一种实时多任务调度方法的设计   总被引:1,自引:0,他引:1  
在实时多任务系统中,当子任务的参数部分或全部相同、或子任务间存有某些约束关系时,仅由参数确定优先级会造成子任务的优先级难以区分或引起误操作,针对上述问题提出了一种以任务的关键性、价值密度为主,加入任务间约束关系的名为关键性一价值密度一任务约束的实时多任务调度方法,并给出了优先级设计规则。通过在一远程监控系统中的应用证实,该方法能体现实时任务的关键性、价值密度和任务间简单约束关系,避免了优先级相同和误操作现象,特别当任务过载时能使任务有序执行。  相似文献   

4.
This paper represents a first attempt at a systematic study of sensitivity analysis for scheduling problems. Because schedules contain both combinatorial and temporal structures, scheduling problems present unique issues for sensitivity analysis. Some of the issues that we discuss have not been considered before. Others, while studied before, have not been explored in the context of scheduling. The applicability of these issues is illustrated using well-known scheduling models. We provide fast methods to determine when a previously optimal schedule remains optimal. Other methods restore an optimal schedule after a parameter change. The value of studying the sensitivity of an optimal sequence instead of the sensitivity of an optimal schedule is demonstrated. We show that, for some problems, sensitivity analysis results depend on the positions of jobs with changed parameters. We identify scheduling problems where performing additional or different computations during optimization facilitates sensitivity analysis. To improve the robustness of an optimal schedule, selection among multiple optimal schedules is considered. We discuss which types of sensitivity analysis questions are intractable because the scheduling problem itself is intractable. We also study how heuristic error bounds vary when the data of a scheduling problem is continuously modified. Although we focus on scheduling problems, several of the issues we discuss and our classification scheme can be extended to other optimization problems.  相似文献   

5.
具有依赖关系的周期任务实时调度方法   总被引:1,自引:0,他引:1  
随着多核技术在嵌入式领域的快速发展,越来越多的功能被集成在同一个平台上,任务之间的关系越来越复杂.而当前大多数的实时周期任务的调度模型都是不考虑任务之间关系的相互独立的任务模型.文中则针对具有依赖关系的周期任务,提出了一种基于ST(Simple-Tree)的实时周期任务调度模型,通过该模型来维护任务之间的依赖关系.此外,为了有效地提高系统利用率以及降低死限丢失率,文中还提出了可延迟时间越短越优先的调度方法并和RM算法、EDF算法进行仿真实验比较,结果表明该方法具有较高的核利用率和较低的死限丢失率.  相似文献   

6.
A Hybrid Method for the Planning and Scheduling   总被引:1,自引:0,他引:1  
We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.  相似文献   

7.
用遗传算法与自适应神经网络混合方法解Job-shop调度问题   总被引:2,自引:0,他引:2  
提出一种用遗传算法结合基于约束满足的自适应神经网络进行Job—shop调度问题求解的混合方法。遗传算法被用来进行迭代寻优。当前代经交叉和变异后生成的染色体对应非可行解,由自适应神经网络运算后得到可行解,对应的染色体作为新一代染色体。仿真表明该算法是快速有效的  相似文献   

8.
Semi-Online Algorithms for Parallel Machine Scheduling Problems   总被引:7,自引:0,他引:7  
G. Dósa  Y. He 《Computing》2004,72(3-4):355-363
This paper considers two semi-online versions of scheduling problem P2||Cmax where one type of partial information is available and one type of additional algorithmic extension is allowed simultaneously. For the semi-online version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5/4. We also show that it does not help that the buffer length is greater than 1. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6/5.The second author is supported by TRAPOYT of China, National Natural Science Foundation of China (10271110). Corresponding author: Y. He.  相似文献   

9.
面向订单的服装企业生产计划调度   总被引:3,自引:0,他引:3  
现代服装企业主要以订单的形式生产,其生产计划调度主要靠手工安排。根据服装加工企业的运作一般特点,建立了生产计划调度的数学模型,并采用遗传算法来求解,从而实现企业的生产计划安排。仿真结果表明模型和算法是可行的,满足企业的计划目标。  相似文献   

10.
提出了一种新的基于分块的图像去噪方法.主要思想是,首先将原图像分成若干个相等的小块,然后对每个子块进行去噪,并且结合原对偶方法对新方法进行了验证.数值实验证明,该方法具有很好的效果,可以提高一倍左右的运算速度,并且图像恢复质量也有一定的提高;特别是对大型问题,新方法可以大幅度的提高去噪效率.  相似文献   

11.
针对拉格朗日松弛方法解决不同车间调度问题时,对问题的依赖性强,算法实现复杂的情况,通过分析拉格朗日方法解决不同车间调度问题的特点,提出了拉格朗日算法面向时象的设计方法,并开发了通用的类模块;面向对象的模块关系和类层次使得算法可扩展性强,便于改进。仿真结果表明,用户可以方便地实现拉格朗日方法对多种车间调度问题的仿真,大大提高了代码的可重用性和软件的通用性。  相似文献   

12.
为解决大规模交易中复杂事务密集访问引起的关键事务调度性能低下问题,文中通过研究交易事务的分类特点和结构特征,提出了一种基于虚拟截止期和时间戳排序的双级调度策略,通过分割长撮合事务和确定合理的步长因子,保证关键事务的优先调度,模拟和测试结果表明,在不产生事务延迟的条件下,交易事务的处理速率为1970事务/秒,平均响应时间为0.5ms,满足大规模电子交易的需要.  相似文献   

13.
介绍了Petri网的基本概念和定步长时间推进仿真算法,在此基础上提出了事件调度的仿真算法,并以一个制造系统的Petri网模型为例进行了说明,通过分析两种算法的仿真结果,验证了调度法仿真效率高于定步长仿真法。  相似文献   

14.
This paper presents a two-phased network dual steepest-edge method for solving capacitated multicommodity network problems. In the first phase, an advanced starting solution in concert with a dual steepest-edge method is applied to solve each capacitated single-commodity network problem. At each iteration, either the primal infeasibility is improved or the dual objective value is inceased. In the second phase, the steepest-edge selection criterion is used to determine the leaving infeasible coupling constraint. By maintaining dual feasibility while improving the dual objective value, the number of infeasible coupling constraints is monotonically reduced to zero. The finite convergency property of this algorithm is shown. Finally, this algorithm is coded using Pascal language and tested in several problems. Results show this algorithm is promising.  相似文献   

15.
张晓平  刘全利  王伟 《控制工程》2007,14(4):430-433
考虑SystemC解决大规模集成电路硬件建模问题的优势,运用事件驱动下进程交互仿真策略,提出了一种基于SystemC仿真平台的生产调度问题建模方法,并将该方法应用于求解经典的Job Shop调度问题。仿真实例表明基于SystemC的仿真建模方法对于求解Job Shop调度问题可以达到令人满意的效果,从而验证该方法应用于实际生产调度问题建模的可行性。  相似文献   

16.
A simulation-based scheduling method for minimizing the due-date-deviation is proposed on the basis of the combination of the BFHS (backward/forward hybrid simulation) method and the parameter-space-search-improvement method. A new schedule generation method named the BFHS/type-D is first developed, in which the information generated during the backward simulation is utilized to control operation-onset timings and job priorities in the forward simulation. Then, after investigation of the backward-simulation characteristics, two parameters are proposed to manipulate the simulation process systematically in relation to due-date-deviation. Furthermore, the best schedule with respect to due-date-deviation is searched for on the space spanned by the two parameters. Finally, the effectiveness and efficiency of the proposed method are demonstrated, not only on a simple job-shop model, but also on a practical large-scale system.  相似文献   

17.
J. N. Hooker 《Constraints》2006,11(2-3):139-157
We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.  相似文献   

18.
Tabu Search Algorithms for Cyclic Machine Scheduling Problems   总被引:2,自引:0,他引:2  
Tabu search algorithms are developed for solving a large class of cyclic machine scheduling problems with the objective to minimize the cycle time. Neighborhoods are derived which generalize the block-approach based neighborhoods which have been successfully applied to noncyclic job-shop problems. For a variant of this neighborhood opt-connectivity is proved.The tabu-search procedure is applied to cyclic job-shop scheduling problems. Computational results are presented.Supported by INTAS, Project 00-217.Supported by Cusanuswerk.  相似文献   

19.
陶继平  徐文艳  王豪 《控制工程》2007,14(5):566-568
在基于拉格朗日松弛法(LR)的优化调度算法中,对偶问题的求解广泛采用的一种方法是次梯度法:在这个方法中,为了得到一个次梯度方向,相应松弛问题的所有的子问题都必须精确求解,当问题规模较大时求解时间过长。讨论了逐步次梯度法求解对偶问题的具体实现方法。将对偶函数化为多个子项和的形式,每求解一个子问题,就构造对应对偶函数一个子项的次梯度,逐步沿这些次梯度方向更新乘子。仿真结果显示,其收敛速度较原始的次梯度法有明显的提高:  相似文献   

20.
In recent years, constraint satisfaction techniques have been successfully applied to disjunctive scheduling problems, i.e., scheduling problems where each resource can execute at most one activity at a time. Less significant and less generally applicable results have been obtained in the area of cumulative scheduling. Multiple constraint propagation algorithms have been developed for cumulative resources but they tend to be less uniformly effective than their disjunctive counterparts. Different problems in the cumulative scheduling class seem to have different characteristics that make them either easy or hard to solve with a given technique. The aim of this paper is to investigate one particular dimension along which problems differ. Within the cumulative scheduling class, we distinguish between highly disjunctive and highly cumulative problems: a problem is highly disjunctive when many pairs of activities cannot execute in parallel, e.g., because many activities require more than half of the capacity of a resource; on the contrary, a problem is highly cumulative if many activities can effectively execute in parallel. New constraint propagation and problem decomposition techniques are introduced with this distinction in mind. This includes an O(n2) edge-finding algorithm for cumulative resources (where n is the number of activities requiring the same resource) and a problem decomposition scheme which applies well to highly disjunctive project scheduling problems. Experimental results confirm that the impact of these techniques varies from highly disjunctive to highly cumulative problems. In the end, we also propose a refined version of the edge-finding algorithm for cumulative resources which, despite its worst case complexity in O(n3) , performs very well on highly cumulative instances.  相似文献   

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

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