Minimizing mean weighted execution time loss on identical and uniform processors

The problem of minimizing mean weighted execution time loss was formulated by the present author in 1984; there the preemptive case for identical as well as for a fixed number of uniform processors was solved via a linear programming approach. In this paper, we propose a strongly polynomial algorithm based on a network flow technique, which minimizes the above criterion for an arbitrary number of identical as well as uniform processors. The upper bounds on the number of preemptions in both cases are also given.     

Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning

We address an unrelated parallel machine scheduling problem with R-learning, an average-reward reinforcement learning (RL) method. Different types of jobs dynamically arrive in independent Poisson processes. Thus the arrival time and the due date of each job are stochastic. We convert the scheduling problems into RL problems by constructing elaborate state features, actions, and the reward function. The state features and actions are defined fully utilizing prior domain knowledge. Minimizing the reward per decision time step is equivalent to minimizing the schedule objective, i.e. mean weighted tardiness. We apply an on-line R-learning algorithm with function approximation to solve the RL problems. Computational experiments demonstrate that R-learning learns an optimal or near-optimal policy in a dynamic environment from experience and outperforms four effective heuristic priority rules (i.e. WSPT, WMDD, ATC and WCOVERT) in all test problems.     

Minimizing resource consumption on uniform parallel machines with a bound on makespan

With the crucial issue of environmental protection, managing natural resources efficiently and/or reducing the amount of carbon emissions have become more important than ever. In this paper, we introduce a uniform parallel machine scheduling problem where the objective is to minimize resource consumption given that the maximum completion time does not exceed a certain level. We show that the problem is strongly NP-hard. A tight lower bound and a particle swarm optimization algorithm are then developed. Finally, some computational results are provided.     

Minimizing the normalized sum of square for workload deviations on m parallel processors

In many organizations, it is desirable to distribute workload as equally as possible among a group of employees or machines. This paper proposes a performance measure, that we call the Normalized Sum of Square for Workload Deviations (NSSWD), and studies the problem of how to schedule a set of n jobs on m parallel identical processors in order to minimize the NSSWD. The NSSWD criterion is relevant where uniformity of wear to machines or of workload to employees is desirable. An algorithm, called Workload Balancing (WB), is proposed for solving this problem. Moreover, we perform a simulation experiment to evaluate WB against several well-known heuristics in the literature. Lastly, we discuss the computational results obtained from the simulation experiment.     

Lattice gases and parallel processors

This paper introduces the notion of lattice gas as a new medium to perform fluid dymanics simulations. After giving the definition of lattice gases, the results of statistical analyses of their macroscopic behaviour are reviewed. It is shown that Navier-Stokes equations can be simulated. Some information is given concerning the algorithms and their possible adaptation to parallel hard-ware, including cellular automata. Finally the construction of a specialized machine for lattice gas simulations will be presented.     

Languages for vector and parallel processors

This paper first considers the major developments which have occurred in the design of high level languages for sequential machines. These developments illustrate how languages which were independent of the hardware eventually evolved. Two major types of language for vector and parallel processors have evolved, namely, detection of parallelism languages and expression of machine parallelism languages. The disadvantages and advantages of each type of languages are examined. A third type of language is also considered which reflects neither the compiler's detection mechanism nor the underlying hardware. The syntax of this language enables the parallel nature of a problem to be expressed directly. The language is thus appropriate for both vector and array processors.     

Scheduling on parallel processors with varying processing times

In this paper, we construct the pseudopolynomial dynamic programming algorithm that optimally solves the parallel identical processor scheduling problem to minimize the maximum job completion times (makespan) under varying processing times. They can be described by an arbitrary monotonic function dependent on the number of previously processed jobs, which can model learning or aging effects. Beside the canonical dynamic programming algorithm, we provide its efficient parallel fast version, which solves moderate problem instances of the problem within reasonable time and memory usage. Additionally, on the basis of the constructed algorithm, a fully polynomial time approximation scheme for the considered problem is provided.     

基于均值改进控制策略的昂贵约束并行代理优化算法

针对具有黑箱特性的昂贵约束优化问题及工程中计算资源利用率不高问题,提出了新的基于均值改进控制策略的并行代理优化算法.该算法为了减少仿真建模计算负担,选取Kriging近似模型对目标函数和约束函数进行近似估计.在Kriging模型基础上,利用均值改进与新增试验样本间的不等关系构建具有距离特性的控制函数.算法的均值改进控制...     

The NUMA with clusters of processors for parallel join

A number of hybrid systems have been proposed to combine the advantages of shared nothing and shared everything concepts for computing relational join operations. Most of these proposed systems, however, presented a few analytical results and have produced limited or no implementations on actual multiprocessors. In this paper, we present a parallel join algorithm with load-balancing for a hybrid system that combines both shared-nothing and shared-everything architectures. We derive an analytical model for the join algorithm on this architecture and validate it using both hardware/software simulations and actual experimentations. We study the performance of the join on the hybrid system for a wide range of system parameter values. We conclude that the hybrid system outperforms both shared-nothing and shared-everything architectures     

Minimizing total tardiness on parallel machines with preemptions

The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule that minimizes the sum of tardiness, i.e., we consider problem Q∣r _j ,p _j =p, pmtn∣∑T _j whose complexity status was open. Recently, Tian et al. (J. Sched. 9:343–364, 2006) proposed a polynomial algorithm for problem 1∣r _j ,p _j =p, pmtn∣∑T _j . We show that both the problem P∣ pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem P∣r _j ,p _j =p, pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates, i.e., for problem Q∣p _j =p, pmtn∣∑T _j .     

Evaluating parallel processors for real-time applications

Increasing acceptance of the necessity for high-order parallelism in order to progress digital processing still leaves open the large question of what machine architectures are best for which class of problem.

To help answer this, we are investigating and comparing the use of both SIMD and MIMD architectures for programmable processing in real-time systems. A distributed array machine, Mil-DAP (derived from the original ICL DAP) has been developed and benchmarked on radar, image processing, and on terrain modelling problems. Multi-transputer arrays have been applied to an overlapping set of problems in image processing, FFT and terrain-based computation.

The results are compared and preliminary conclusions drawn.     

Minimizing costs in round robin tournaments with place constraints

In this paper we consider a general sports league scheduling problem and propose solution algorithms for it. The objective is to find a feasible schedule for a round robin tournament with minimum number of breaks and minimum total costs where additionally place constraints are taken into account. We present a “first-break, then-schedule” approach which uses an enumerative procedure to generate home-away patterns and integer programming for finding corresponding schedules. Computational results are presented for leagues with up to 14 teams.     

Floating-point processors join forces in parallel processingarchitectures

The hardware architecture and software capabilities of the TMS320C40 floating-point digital signal processor are described. The C40 operates at 275 million operations per second (MOPS) and transfers data at a rate of 320 Mbytes/s with a 40-ns cycle time. A key architectural feature of the C40 for parallel computing is the six parallel bidirectional communication ports that permit direct connection and communication between processors in a parallel system. Examples illustrating the use of the C40 in a parallel processing environment are discussed