Rescheduling to minimize makespan on a changing number of identical processors

We consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP-hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.     

Scheduling of parallel processors: A posterior bound on LPT sequencing and a two-step algorithm

This article considers the problem of scheduling parallel processors to minimize the makespan. The article makes two key contributions: (1) It develops a new lower bound on the makespan for an optimal schedule, and (2) it proposes an efficient two-step algorithm to find schedules of any desired accuracy, or percent above optimal. In addition, a posterior bound on LPT (longest processing time) sequencing is developed in the article. It is proved that this bound dominates the previously reported bounds on LPT sequencing.     

Minimizing the sum of absolute lateness in single-machine and multimachine scheduling

Kanet addressed the problem of scheduling n jobs on one machine so as to minimize the sum of absolute lateness under a restrictive assumption on their common due date. This article extends the results to the problem of scheduling n jobs on m parallel identical processors in order to minimize the sum of absolute lateness. Also, a heuristic algorithm for a more general version with no restriction on the common due date, for the problem of n-job single-machine scheduling is presented and its performance is reported.     

A note on allocating jobs to two machines

A recent article in this journal by Mehta, Chandrasekaran, and Emmons [1] described a dynamic programming algorithm for assigning jobs to two identical parallel processors in a way that minimizes the average delay of these jobs. Their problem has a constraint on the sequence of the jobs such that any group of jobs assigned to a processor must be processed in the order of the sequence. This note has two purposes. First, we wish to point out a relationship between this work and some prior work [2]. Second, we wish to point out that Mehta, Chandrasekaran, and Emmons formulation, slightly generalized, can be used to find the optimum assignment of jobs to two machines in a more general class of problems than they considered including a subclass in which the jobs are not constrained to be processed in a given sequence.     

Heuristics for minimizing mean tardiness for m parallel machines

The concept of parallel operations has been widely used in manufacturing and data processing. However, not many efficient methods have been proposed to reduce job tardiness. This article proposes an efficient heuristic to minimize the mean tardiness of a set of tasks with known processing times and due dates for single and m parallel machines. For the single-machine case, the proposed heuristic is compared with the well-known Wilkerson and Irwin algorithm; for the m parallel machine case, it is compared with an extension of the Wilkerson-Irwin algorithm. We also introduce a simple dispatching rule, and it is compared with some existing dispatching rules. The comprehensive simulation results show that the proposed heuristic performs better than the Wilkerson-Irwin algorithm at a significantly reduced computational time.     

A note on the optimal scheduling of two parallel processors

The problem of minimizing mean flow time of two parallel processors is discussed. Prior results are briefly reviewed. A dynamic programming algorithm is presented which minimizes mean flow time for a set of n preordered jobs on two nonequivalent parallel processors. The algorithm is illustrated with an example problem. The computational experience is presented which illustrates the efficiency of the algorithm.     

A nonidentical parallel processor scheduling problem

The problem considered in this article is a generalization of the familiar makespan problem, in which n jobs are allocated among m parallel processors, so as to minimize the maximum time (or cost) on any processor. Our problem is more general, in that we allow the processors to have (a) different initial costs, (b) different utilization levels before new costs are incurred, and (c) different rates of cost increase. A heuristic adapted from the bin-packing problem is shown to provide solutions which are close to optimal as the number of iterations is allowed to increase. Computational testing, over a large number of randomly generated problem instances, suggests that heuristic errors are, on average, very small.     

Asymptotically optimal component assembly plans in repairable systems and server allocation in parallel multiserver queues

T identical exponential lifetime components out of which G are initially functioning (and B are not) are to be allocated to N subsystems, which are connected either in parallel or in series. Subsystem i, i = 1,…, N, functions when at least K_i of its components function and the whole system is maintained by a single repairman. Component repair times are identical independent exponentials and repaired components are as good as new. The problem of the determination of the assembly plan that will maximize the system reliability at any (arbitrary) time instant t is solved when the component failure rate is sufficiently small. For the parallel configuration, the optimal assembly plan allocates as many components as possible to the subsystem with the smallest K_i and allocates functioning components to subsystems in increasing order of the K_i's. For the series configuration, the optimal assembly plan allocates both the surplus and the functioning components equally to all subsystems whenever possible, and when not possible it favors subsystems in decreasing order of the K_i's. The solution is interpreted in the context of the optimal allocation of processors and an initial number of jobs in a problem of routing time consuming jobs to parallel multiprocessor queues. © John Wiley & Sons, Inc. Naval Research Logistics 48: 732–746, 2001     

Hu's precedence tree scheduling algorithm: A simple proof

This article presents a simple proof of Hu's algorithm for scheduling in minimum time a set of tasks constrained by precedence tree constraints, each task requiring a unit time to complete, and where m processors are available.     

A parallel sequencing algorithm for minimizing total cost

The problem of sequencing jobs on parallel processors when jobs have different available times, due dates, penalty costs and waiting costs is considered. The processors are identical and are available when the earliest job becomes available and continuously thereafter. There is a processor cost during the period when the processor is available for processing jobs. The proposed algorithm finds the sequence (or sequences) with minimum total cost (sum of waiting, penalty and processor costs.). A proof of the algorithm and numerical results are given.     

Scheduling to a common due date on parallel uniform processors

We consider scheduling a set of jobs on parallel processors, when all jobs have a common due date and earliness and lateness are penalized at different cost rates. For identical processors, the secondary criteria of minimizing makespan and machine occupancy are addressed. The extension to different, uniform processors is also solved.     

A heuristic procedure for allocating tasks in fault-tolerant distributed computer systems

One way of achieving the increased levels of system reliability and availability demanded by critical computer-based control systems is through the use of fault-tolerant distributed computer systems. This article addresses the problem of allocating a set of m tasks among a set of n processors in a manner that will satisfy various task assignment, system capacity, and task scheduling constraints while balancing the workload across processors. We discuss problem background, problem formulation, and a known heuristic procedure for the problem. A new solution-improving heuristic procedure is introduced, and computational experience with the heuristics is presented. With only a modest increase in the amount of computational effort, the new procedure is demonstrated to improve dramatically solution quality as well as obtain near-optimal solutions to the test problems.     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

多机器人最大熵博弈协同定位算法

研究了多机器人观测到同一目标时的协同定位问题。建立了各个机器人相对观测一致程度的数学描述模型,进而提出用基于极大熵准则的最大熵博弈获取使相对观测一致程度最优的协同定位方式。针对博弈结果的多样性,相应地改变观测方程的雅克比矩阵,推导了可适应多机器人各种博弈结果的扩展Kalman滤波协同定位算法。仿真实验表明,方法可实现机器人团队在协同定位时有选择、更高效地共享相互间的观测信息;在保证协同定位精度提高的同时有效地消除了多机器人相对观测信息间的冲突。     

Scheduling of stochastic tasks on two parallel processors

We consider the problem of scheduling n tasks on two identical parallel processors. We show both in the case when the processing times for the n tasks are independent exponential random variables, and when they are independent hyperexponentials which are mixtures of two fixed exponentials, that the policy of performing tasks with longest expected processing time (LEPT) first minimizes the expected makespan, and that in the hyperexponential case the policy of performing tasks with shortest expected processing time (SEPT) first minimizes the expected flow time. The approach is simpler than the dynamic programming approach recently employed by Bruno and Downey.     

一种支持并行离散事件仿真建模和并行模型检验的建模语言

并行离散事件仿真(Parallel Discrete Event Simulation,PDES)模型的正确性和可信度对PDES应用的发展起着决定性作用.然而,现有的并行离散事件仿真开发环境都没有提供仿真模型检验功能.并行模型检验(Parallel Model Checking,PMC)方法以其完备性、高效性已经在工业...     

一种基于多核并行计算的目标分配算法设计

随着计算机多核处理器的高速发展,多核并行计算在各领域发展研究的重要性已逐渐突显,分析了当前典型的并行编程模型,在PCAM设计过程的基础上提出了多核并行算法的设计过程,运用OpenMP编程模型完成了一种目标分配算法的多核并行化设计,通过实验及性能分析,验证了并行目标分配算法相较于传统串行算法在计算效率上的优势。     

机动目标跟踪的非线性算法

卡尔曼滤波器对线性高斯滤波问题能提供最优解, 而对目标运动模型、观测方程等要求的非线性就不再适合,提出了一种机动目标自适应非线性粒子滤波算法-" 粒子滤波器"(Particle Filters PF)法, 这种方法不受线性化误差和高斯噪声假定的限制,适用于任何状态转换或测量模型, 分析比较了粒子滤波(PF)与扩展卡尔曼滤波算法(EKF) 的滤波精度、运算量等方面指标.给出了基于典型非线性模型的算法仿真, 仿真结果表明粒子滤波新方法优于EKF对机动目标跟踪.     

高超音速流场的隐式TVD格式并行计算

本文采用区域分割技术和拼接网格的并行策略，发展了一个适合于分布式存贮多机系统的ＴＶＤ隐式有限体积并行算法；并在ＰＶＭ并行环境下，对三维高超音速绕流流场实现了多机并行计算，通过负载平衡等方法得到了较高的加速比（在二处理机系统上加速比为１∶８４，在四处理机系统上为３∶４４）。     

Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP‐complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real‐life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000