共查询到20条相似文献，搜索用时 0 毫秒
1.
Mohamed Haouari Anis Gharbi Mahdi Jemmali 《International Transactions in Operational Research》2006,13(6):529-548
We address the problem of minimizing makespan on identical parallel machines. We propose new lower bounding strategies and heuristics for this fundamental scheduling problem. The lower bounds are based on the so‐called lifting procedure. In addition, two optimization‐based heuristics are proposed. These heuristics require iteratively solving a subset‐sum problem. We present the results of computational experiments that provide strong evidence that the new proposed lower and upper bounds consistently outperform the best bounds from the literature. 相似文献
2.
Maged M. Dessouky 《Computers & Industrial Engineering》1998,34(4):793-806
We consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 100,000 iterations with n≤80 and m≤3. For larger values of m, the heuristics provided approximate solutions close to the optimal values. 相似文献
3.
4.
M. Y. Mashor 《International journal of systems science》2013,44(1):53-63
This paper presents a new recursive hybrid algorithm for training a radial basis function (RBF) network. The algorithm consists of a proposed clustering algorithm to position the RBF centres and the Givens least-squares algorithm to estimate the weights. This paper begins with a discussion about the problems of clustering in positioning RBF centres. Then a new clustering algorithm called adaptive fuzzy c-means clustering algorithm is proposed to reduce the problems. The capability of the proposed algorithm was tested to model three data sets: one simulated and two real data sets. It was found that the algorithm provided good performance. The performance of the algorithm was then compared with adaptive k-means, non-adaptive k-means and non-adaptive fuzzy cmeans clustering algorithms. Overall performance of the RBF network that used the proposed clustering algorithm was found to be much better than those that used other clustering algorithms. Simulation results also revealed that the algorithm was not sensitive to initial centres. 相似文献
5.
面向流程工业的批在线调度问题 总被引：2，自引：0，他引：2
从钢铁生产热轧流程中提炼出了在同构并行机上的批在线调度问题,它是流程工业中MES的重要环节。从理论上给出算法并研究了算法的性能。工件以批的形式到达,目标函数是使工件的最大完成时间最小。当一个批到达时,将这一批中的工件分成若干组,要求在同一组中的工件可以具有不同的开始加工时间但必须具有相同的完成时间。通过将批调度与在线调度的结合,给出了最坏情况比（竞争率）分别为m／（1＋（m-1）ε）,m（1-ε）／（1-ε）,m／（1＋gε）的批在线调度算法。 相似文献
6.
Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times 总被引：4，自引：0，他引：4
Monaldo Mastrolilli 《Journal of Scheduling》2003,6(6):521-531
We consider the problem of scheduling n independent jobs on m identical machines that operate in parallel. Each job must be processed without interruption for a given amount of time on any one of the m machines. In addition, each job has a release date, when it becomes available for processing, and, after completing its processing, requires an additional delivery time. The objective is to minimize the time by which all jobs are delivered. In the notation of Graham et al. (1979), this problem is noted P|r
j|Lmax. We develop a polynomial time approximation scheme whose running time depends only linearly on n. This linear complexity bound gives a substantial improvement of the best previously known polynomial bound (Hall and Shmoys, 1989). Finally, we discuss the special case of this problem in which there is a single machine and present an improved approximation scheme. 相似文献
7.
一种求解同等并行机调度的混合量子衍生进化规划算法 总被引：1，自引：0，他引：1
针对带顺序相关建立时间的同等并行机调度问题的求解,提出一种新的混合量子衍生进化规划算法.该算法通过定义新的量子个体来表示调度问题中的工件排序,并定义了针对调度问题的量子旋转角,使个体向更好的解靠近.同时,针对并行机问题本身,改进了个体的编码方式和新的变异方法.为了验证算法的有效性和收敛性,采用不同规模的算例进行仿真实验.结果表明,即使在小种群情况下,算法所得解均优于基本进化规划求得的解. 相似文献
8.
禁忌搜索方法解最小化拖期任务数的并行多机调度问题 总被引：3，自引：0，他引：3
禁忌搜索方法（ＴＳ）是一种将人工智能技术引入管理中的一种高于一般启发式算法的智能化“超启发式”算法，它能有效地解决大型组合优化问题。本文用ＴＳ方法解决最小化拖期任务数的并行多机调度问题，并同目前最好的启发式作了比较，大量实验表明了ＴＳ方法的有效性。 相似文献
9.
针对最小化完工时间的等同和非等同并行多机调度一类问题,提出了一种递阶遗传算法。该算法根据问题的特点,采用一种递阶编码方案,此编码与调度方案一一对应。用递阶遗传算法优化并行多机调度不需设计专门的遗传算子,操作简单。计算结果表明,递阶遗传算法是有效的,能适用于大规模等同和非等同并行多机调度问题。 相似文献
10.
We study a real‐world scheduling problem arising in the context of a rolling ingots production. First we review the production process and discuss peculiarities that have to be observed when scheduling a given set of production orders on the production facilities. We then show how to model this scheduling problem using prescribed time lags between operations, different kinds of resources, and sequence‐dependent changeovers. A branch‐and‐bound solution procedure is presented in the second part. The basic principle is to relax the resource constraints by assuming infinite resource availability. Resulting resource conflicts are then stepwise resolved by introducing precedence relationships among operations competing for the same resources. The algorithm has been implemented as a beam search heuristic enumerating alternative sets of precedence relationships. 相似文献
11.
Sandeep N. Bhatt Gianfranco Bilardi Kieran T. Herley Geppino Pucci Abhiram Ranade 《Journal of Parallel and Distributed Computing》1998,51(2):75-88
The list marking problem involves marking the nodes of an ℓ-node linked list stored in the memory of a (p, n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish anΩ(min{ℓ, n/p}) randomized lower bound for ℓ-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tight
bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values. 相似文献
Full-size image
12.
为使总加权成套订单延迟数最小,提出了一类新的目标排序问题-并行机带调整时间加权成套订单数问题.多个工件来自多个订单,分属多个不同组类.每个订单有一个权值,每个工件有确定的加工时间、交货期,且需在多台并行机上加工.每个工件只需在任一台机器上加工一次,只有所有属于某一订单的工件都在各自交货期内完工才称此订单成套完工.建立了问题的数学模型,设计了一种启发式遗传算法.通过算例分析及对随机产生的数据进行验证得出,遗传算法对于大中型成套订单问题是十分有效的. 相似文献
13.
The subset sum problem is a simple and fundamental NP‐hard problem that is found in many real world applications. For the particular application motivating this paper (combination weighers) a solution is required to the subset sum problem that is within a small tolerance level, and can be computed quickly. We propose four techniques for solving this problem. The first two techniques are based on an efficient number partitioning algorithm. These techniques can solve small problems very efficiently when the solution uses approximately half the available items. The next technique is an enumeration technique that is capable of solving small problems very efficiently. The last technique is a modified enumeration technique that improves a good solution in a structured manner. These techniques were found to perform efficiently on large and small problems and can outperform other techniques currently proposed in the literature under certain conditions. 相似文献
14.
Bayi Cheng Shanlin Yang Xiaoxuan Hu Kai Li 《International journal of systems science》2014,45(3):571-578
15.
针对并行机多目标调度问题,以完工时间和总延迟时间最小为目标函数建立了数学模型,从而将具有解决复杂组合优化问题的非劣排序遗传算法NSGA2应用于求解多目标并行机调度问题。文中详细描述了用NSGA2算法求解并行机调度问题的步骤,并通过Matlab仿真,表明YhqNSGA2算法求解多目标并行机调度问题的可行性和有效性。 相似文献
16.
Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset. 相似文献
17.
在各种生产制造系统中都广泛存在着同等并行机调度. 本文提出了一种新的耦合瞬态混沌神经网络来求解同等并行机调度问题. 通过引入新的换位矩阵将该问题的混合整数规划模型转化为耦合瞬态神经网络的计算结构. 同时, 提出了新的计算能量函数, 使其能够包含所有约束和目标. 此外, 采用时变惩罚参数, 克服了能量函数中各惩罚项之间的权衡问题. 最后, 将该算法应用于求解 3 种不同规模的随机问题并进行仿真, 每种规模随机测试 100 次. 结果显示, 该算法能在合理的时间内收敛, 并求解出这些随机问题. 相似文献
19.
针对在特殊工艺约束下,非等同并行多机总完工时间最小和总拖后惩罚最小双目标调度问题（BOSP）,设计了一个双目标调度模型,进而构造了一个基于向量组编码的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快。同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型此类调度问题。 相似文献
20.
The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the Brucker–Garey–Johnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker– Garey–Johnson algorithm. 相似文献