Makespan minimization for m parallel identical processors

We introduce an algorithm, called TMO (Two-Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest-processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m-machine problem into a set of two-machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.     

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.     

Scheduling jobs to two machines subject to batch arrival ordering

The problem considered is to assign n jobs to two processors so as to minimize the total flow time, with the constraint that a predetermined partial ordering (induced by batch arrivals) must be preserved within the subset of jobs assigned to each processor. An efficient algorithm of time 0(n⁵) is developed, and computational experience is reported.     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

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.     

One machine sequencing to minimize mean flow time with minimum number tardy

The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing mean flow time with the minimum number of tardy jobs. A simple procedure is first proposed to schedule for minimum flow time with a specified subset of jobs on time. This is used in conjunction with Moore's Algorithm in a simple heuristic producing good and often optimal schedules. A branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

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.     

A new polynomial algorithm for maximum value flow with an efficient parallel implementation

A new algorithm is presented for finding maximal and maximum value flows in directed single-commodity networks. Commonly algorithms developed for this problem find a maximal flow by gradually augmenting (increasing) a feasible flow to a maximal flow. In the presented algorithm, at the beginning of each step or iteration, the flow on arcs is assigned to flow capacity. This may lead to an infeasible flow violating flow conservation at some nodes. During two passes of a MAIN step, consisting of a forward pass and a backward pass, the flow is reduced on some arcs to regain feasibility. The network is then pruned by omitting saturated arcs, and the process is repeated. The parallel implementation of the algorithm applies the two main steps at the same time to the same network. The outputs of the two steps are compared and the processing continues with the higher feasible flow. The algorithm is simple, intuitive, and efficient. © 1993 John Wiley & Sons, Inc.     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

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.     

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.     

高性能路由器并行转发技术

随着线路传输速率的快速提高,报文线速转发面临极大挑战。基于并行处理技术,提出分布式并行转发引擎结构,实现高速报文转发。针对并行转发引擎负载分配问题,设计AHDA(Adaptive Hashing DispatchAlgorithm)算法,该算法为综合考虑负载均衡和报文保序提供支持。模拟结果表明,AHDA算法均匀分配负载,保证很低的报文乱序率,对网络处理器规模具有良好的可扩展性。     

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

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

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

并行计算的数据重分配

为提高算法的并行计算性能 ,许多并行程序必须进行数据重分配。数据重分配是在并行计算过程中实现的 ,其开销影响算法的并行性能 ,高效的数据重分配对提高并行计算的性能有重要意义。本文阐述了数据重分配的环形算法 ;提出了数据重分配的蝶网算法 ,并证明了其正确性 ;设计了结构性数据交换方法 ;通过理论和数值实验分析了两种算法的性能     

基于丛生树的多流水线并行Hash连接的处理机分配算法

本文介绍了并行数据库中实现多流水线Ｈａｓｈ连接的处理机分配算法，该算法对于执行Ｈａｓｈ连接的丛生查询树可同时实现流水线内并行（ＩｎｔｒａｐｉｐｅｌｉｎｅＰａｒａｌｅｌ）和多流水线间的并行（ＩｎｔｒａｐｉｐｅｌｉｎｅＰａｒ－ａｌｅｌ     

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

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.     

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.