The Markovian Two-echelon Repairable Item Provisioning Problem

A repairable-item provisioning system with two levels of repair is presented. Under the assumption that the machine time-to-failure and the repair times are exponentially distributed, a new algorithm is developed to compute the long-run average number of machines operating. Using the new algorithm we determine the optimal number of machines and repair channels at the two repair centres to minimize cost and meet a service-level constraint. The algorithm, which is based on Little's result in queueing theory and the theory of regenerative processes, is extremely efficient in terms of computer storage and execution time.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

Reliable parallel solution of bidiagonal systems

Summary. This paper presents a new efficient algorithm for solving bidiagonal systems of linear equations on massively parallel machines. We use a divide and conquer approach to compute a representative subset of the solution components after which we solve the complete system in parallel with no communication overhead. We address the numerical properties of the algorithm in two ways: we show how to verify the à posteriori backward stability at virtually no additional cost, and prove that the algorithm is à priori forward stable. We then show how we can use the algorithm in order to bound the possible perturbations in the solution components. Received March 13, 1998 / Revised version received December 21, 1999 / Published online June 20, 2001     

Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm

Recent simulations often use highly parallel machines with many processors, and they need many pseudorandom number generators with distinct parameter sets, and hence we need an effective fast assessment of the generator with a given parameter set. Linear generators over the two-element field are good candidates, because of the powerful assessment via their dimensions of equidistribution. Some efficient algorithms to compute these dimensions use reduced bases of lattices associated with the generator. In this article, we use a fast lattice reduction algorithm by Mulders and Storjohann instead of Schmidt’s algorithm, and show that the order of computational complexity is lessened. Experiments show an improvement in the speed by a factor of three. We also report that just using a sparsest initial state (i.e., consisting of all 0 bits except one) significantly accelerates the lattice computation, in the case of Mersenne Twister generators.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

Novel modifications of parallel Jacobi algorithms

We describe two main classes of one-sided trigonometric and hyperbolic Jacobi-type algorithms for computing eigenvalues and eigenvectors of Hermitian matrices. These types of algorithms exhibit significant advantages over many other eigenvalue algorithms. If the matrices permit, both types of algorithms compute the eigenvalues and eigenvectors with high relative accuracy. We present novel parallelization techniques for both trigonometric and hyperbolic classes of algorithms, as well as some new ideas on how pivoting in each cycle of the algorithm can improve the speed of the parallel one-sided algorithms. These parallelization approaches are applicable to both distributed-memory and shared-memory machines. The numerical testing performed indicates that the hyperbolic algorithms may be superior to the trigonometric ones, although, in theory, the latter seem more natural.     

Online scheduling with general machine cost functions

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed s. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.     

Ensuring population diversity in genetic algorithms: A technical note with application to the cell formation problem

The entropy-based measure has been used in previous works to compute the population diversity in solving the cell formation problem with the genetic algorithm. Population diversity is crucial to the genetic algorithm’s ability to continue fruitful exploration as it may be used in choosing an initial population, in defining a stopping criterion, in evaluating the population convergence, and in making the search more efficient throughout the selection of crossover operators or the adjustment of various control parameters (e.g., crossover or mutation rate, population size). We show in this note that, when a non-ordinal chromosome representation corresponding to the allocation of machines to cells is used, the current way of measuring the population diversity is inaccurate. Consequently, it leads to wrong conclusions when, at various iterations, carrying out fruitful exploration or an efficient search of the solution space is guided by the perceived population diversity degree. An alternative approach based on computing the distance and the similarity between chromosomes is discussed.     

Choiceless polynomial time

Turing machines define polynomial time (PTime) on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time (without presuming the presence of a linear order)? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines (formerly called evolving algebras). The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime.     

Sevast'yanov's algorithm for the flow-shop scheduling problem

We consider the flow-shop scheduling problem. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. We studied and implemented different versions of the algorithm of Sevast'yanov based on linear programming to solve this problem. Using CPLEX, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz-Enscore-Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines.     

带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

On the minimization of total weighted flow time with identical and uniform parallel machines

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.     

Wang’s B machines are efficiently universal,as is Hasenjaeger’s small universal electromechanical toy

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger’s machine simulates Hao Wang’s B machines, which were proved universal by Wang. Unfortunately, Wang’s original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger’s machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang’s B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger’s machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger’s machine is both small and fast. In another application of our result, we show that Hooper’s small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.     

Online scheduling with machine cost and rejection

In this paper we define and investigate a new scheduling model. In this new model the number of machines is not fixed; the algorithm has to purchase the used machines, moreover the jobs can be rejected. We show that the simple combinations of the algorithms used in the area of scheduling with rejections and the area of scheduling with machine cost are not constant competitive. We present a 2.618-competitive algorithm called OPTCOPY.     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

粒子群遗传混合算法求解考虑传输时间的FJSP

在某些生产制造场景中,工件在不同机器间的传输时间对车间调度的总拖期具有重要影响,本文基于此扩展了总拖期最小的柔性作业车间调度模型。针对问题模型的复杂性,采用粒子群优化算法和遗传算法的混合算法进行求解。在初始化过程以一定概率优选加工时间和传输时间短的机器并排除调度频繁的机器,使种群在保持多样性的前提下尽量选择优化结果好的个体;采用线性调整的方式动态改变交叉概率和变异概率的值,使种群在遗传算法的不同阶段具有不同的搜索强度;采用粒子群优化算法进行局部搜索,弥补了遗传算法局部搜索能力的不足。最后采用本文方法和其他方法求解柔性作业车间调度问题实例,并对比不同水平层次传输时间下的总拖期,验证了本文方法的有效性。