首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 156 毫秒
1.
带约束的一维装箱问题近似算法的研究   总被引:1,自引:0,他引:1  
作为经典装箱问题的扩展,有色装箱问题在多处理器实时调度的过程中有很强的应用背景。论文提出了有色装箱问题的新算法-SCPF算法,按颜色分类,将相同颜色的物品分成一类。放置时按照相同颜色的物品首先放置的原则,将物品进行装箱。实验证明,该算法与文献犤3犦中的KC-A算法相比具有更好的装箱效果,使用的箱子数更少。并从理论上论证了该算法的性能比KC-A算法更好。  相似文献   

2.
局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.  相似文献   

3.
面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.  相似文献   

4.
有色装箱问题的在线近似算法   总被引:7,自引:0,他引:7  
有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC-A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC-A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC-A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC-FF表现出相对更好的实验效果。  相似文献   

5.
系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。  相似文献   

6.
作为对经典一维装箱问题的推广,提出一种A型变尺寸装箱问题(A-shaped Variable-sized BinPacking Problem,简称A SVBP),即在物品的装箱过程中,每样物品有高度和横截面积两个参数,并且箱子的大小不一。该问题在文件系统管理和日常生活中的运输等问题中有着广泛的应用背景。把装箱问题的经典算法以及遗传算法推广到A型变尺寸装箱问题,实验结果表明:按照本文提出的求解模式,离线情况下求解A型变尺寸装箱问题最终结果的质量取决于预先求解其退化为经典装箱问题时的算法,求解物品装箱序列时用首次适应混合遗传算法比用Next Fit算法、First Fit算法、Best Fit算法最终得到的结果要好。  相似文献   

7.
基于多元优化算法的三维装箱问题的研究   总被引:2,自引:0,他引:2  
用多元优化算法(Multi-variant optimization algorithm,MOA)实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中;局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化;通过递推的随机放置和局部调整优化,目标函数值逐步逼近最优值,从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真,得到理想的装箱效果,说明用多元优化算法实现三维装箱问题的有效性和可行性.  相似文献   

8.
同一尺寸货物三维装箱问题的一种启发式算法   总被引:5,自引:0,他引:5  
给出了集装箱装载同一尺寸长方体货物问题的一种启发式算法.该算法解决了许多三维装箱算法计算量大、排列不规则等缺点,同时用计算机编程实现该算法,并与国内主要装箱软件作了对比,最后给出了该算法的可行性与优势.  相似文献   

9.
使用混合人工鱼群算法求解装箱问题   总被引:1,自引:0,他引:1  
装箱问题在实际生产中应用非常广泛,在分析该问题特点的基础上提出了使用类CF近似算法和人工鱼群算法相结合的混合人工鱼群算法求解装箱问题,并给出了具体的算法步骤。跟遗传算法的对比试验结果表明该算法在求解装箱问题所得的结果优于遗传算法,具有良好的应用前景。  相似文献   

10.
求解矩形条带装箱问题的动态匹配启发式算法   总被引:2,自引:0,他引:2  
矩形条带装箱问(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法--动态匹配算法--与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.时2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效.  相似文献   

11.
Refined Harmonic (RH) is one of the best on-line bin packing algorithms. The algorithm was first proposed by Lee&;Lee in 1985 and the upper bound of the worst-case performance ratio has been proved to be 1.63596 … In this paper, it is proved that 1.63596… is also the lower bound. The average performance of RH is also studied for the first time. It is shown that the average-case performance ratio of RH is 1.28243…under the uniform distribution.  相似文献   

12.
受启动空间约束的装箱问题   总被引:1,自引:0,他引:1  
提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.  相似文献   

13.
We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.  相似文献   

14.
In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf 1 andf 2 be two linear combinations of random variables {N i } i=1 k where theN i 's have a joint multinomial distribution for eachn i=1 k ,N i . LetE(f 1) ≠ O andE(f 2)≠ 0. Then limn E(max(f 1,f 2 ))/n = lim n →∞ max(E(f 1),E(f 2))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.  相似文献   

15.
An on-line algorithm for variable-sized bin packing   总被引:4,自引:0,他引:4  
J. Csirik 《Acta Informatica》1989,26(8):697-709
Summary An on-line algorithm for variable-sized bin packing with an asymptotical worst-case ratio of <1.7 is given. The method is derived from the Harmonic Fit proposed by Lee and Lee. It is proven that, if it is allowed to choose any bin sizes, then with an appropriately chosen second bin size we can have an asymptotical worst-case ratio of 1.4, even with the same algorithm and two bin sizes.Part of this work was carried out when the author was visiting the Institut für Informatik und angewandte Mathematik, Berne, SwitzerlandThis paper has been supported by Grant OTKA Nr. 1135 from the Hungarian Academy of Sciences  相似文献   

16.
Allocating fixed-priority periodic tasks on multiprocessor systems   总被引:2,自引:0,他引:2  
In this paper, we study the problem of allocating a set of periodic tasks on a multiprocessor system such that tasks are scheduled to meet their deadlines on individual processors by the Rate-Monotonic scheduling algorithm. A new schedulability condition is developed for the Rate-Monotonic scheduling that allows us to develop more efficient on-line allocation algorithms. Two on-line allocation algorithms—RM-FF and RM-BF are presented, and shown that their worst-case performance, over the optimal allocation, is upper bounded by 2.33 and lower bounded by 2.28. Then RM-FF and RM-BF are further improved to form two new algorithms: Refined-RM-FF (RRM-FF) and Refined-RM-BF (RRM-BF), both of which have a worst-case performance bound of 2. We also show that when the maximum allowable utilization of a task is small, the worst-case performance of all the new algorithms can be significantly improved. The worst-case performance bounds of RRM-FF and RRM-BF are currently the best bounds in the class of on-line scheduling algorithms proposed to solve the same scheduling problem. Simulation studies show that the average-case performance of the newly proposed algorithms is significantly superior to those in the existing literature.  相似文献   

17.
Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.  相似文献   

18.
The problem of downlink data transmission scheduling in wireless networks is studied. It is pointed out that every downlink data transmission scheduling algorithm must have two components to solve the two subproblems of power assignment and transmission scheduling. Two types of downlink data transmission scheduling algorithms are proposed. In the first type, power assignment is performed before transmission scheduling. In the second type, power assignment is performed after transmission scheduling. The performance of two algorithms of the first type which use the equal power allocation method are analyzed. It is shown that both algorithms exhibit excellent worst-case performance and asymptotically optimal average-case performance under the condition that the total transmission power is equally allocated to the channels. In general, both algorithms exhibit excellent average-case performance. It is demonstrated that two algorithms of the second type perform better than the two algorithms of the first type due to the equal time power allocation method. Furthermore, the performance of our algorithms are very close to the optimal and the room for further performance improvement is very limited. It is shown that all the above algorithms can be extended to schedule downlink data transmissions with parallel channels. It is also shown that the simple sequential scheduling algorithm is optimal if the total transmission power is equally allocated to the channels. As an extra contribution, an M/G/1 queueing model for the FCFS queueing discipline is established, and it is observed that increasing the number of channels has more impact on the reduction of the average response time than increasing the total transmission power.  相似文献   

19.
A two-parallel-machine scheduling problem with machine-dependent availabilities where one machine is subject to tool changes and the other is subject to periodic maintenance is considered. The objective is to determine the start time of each tool change activity and schedule all the jobs to the two machines such that the makespan is minimized. Due to the NP-hardness of the non-approximability of the problem, there does not exist any polynomial time approximation algorithm with a worst-case ratio less than 2 for the problem unless P=NP. To solve small sized and moderate sized instances of the problem, a mixed 0–1 programming model is proposed. To solve large sized instances of the problem, nine heuristic algorithms that employ two classical dispatching rules, two assignment mechanisms and a post-optimization procedure are proposed. To evaluate the performance of the algorithms, some machine setting featured lower bounds are provided. Computational experiment shows that the average-case relative error ratio of the heuristic algorithm that based on the classical LPT rule, two assignment procedures and a post-optimization procedure is less than 8%, which implies that it is promising for problem and suitable for real-world application.  相似文献   

20.
周期性任务调度的装箱算法   总被引:4,自引:0,他引:4  
朱智林  时晨  韩俊刚  陈平 《计算机应用》2006,26(3):679-0681
针对基于时间触发的CAN控制系统,给出了确定周期性任务表中的基本周期的两种策略,提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法,分析了这四种不同算法的时间复杂度和最坏渐近性能比,最后对不同规模下的四种算法进行了仿真比较,结果表明文中给出的四种算法效果均优于经典的一维装箱算法。  相似文献   

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

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