Scalability and Communication in Parallel Low-Complexity Lossless Compression

Approximation schemes for optimal compression with static and sliding dictionaries which can run on a simple array of processors with distributed memory and no interconnections are presented. These approximation algorithms can be implemented on both small and large scale parallel systems. The sliding dictionary method requires large size files on large scale systems. As far as lossless image compression is concerned, arithmetic encoders enable the best lossless compressors but they are often ruled out because they are too complex. Storer extended dictionary text compression to bi-level images to avoid arithmetic encoders (BLOCK MATCHING). We were able to partition an image into up to a hundred areas and to apply the BLOCK MATCHING heuristic independently to each area with no loss of compression effectiveness. Therefore, the approach is suitable for a small scale parallel system at no communication cost. On the other hand, bi-level image compression seems to require communication on large scale systems. With regard to grey scale and color images, parallelizable lossless image compression (PALIC) is a highly parallelizable and scalable lossless compressor since it is applied independently to blocks of 8 × 8 pixels. We experimented the BLOCK MATCHING and PALIC heuristics with up to 32 processors of a 256 Intel Xeon 3.06 GHz processors machine () on a test set of large topographic bi-level images and color images in RGB format. We obtained the expected speed-up of the compression and decompression times, achieving parallel running times about 25 times faster than the sequential ones. Finally, scalable algorithms computing static and sliding dictionary optimal text compression on an exclusive read, exclusive write shared memory parallel machine are presented. On the same model, compression by block matching of bi-level images is shown which can be implemented on a full binary tree architecture under some realistic assumptions with no scalability issues.     

Colony and evolutionary dynamics of a two‐stage model with brood cannibalism and division of labor in social insects

Division of labor (DOL) is a major factor for the great success of social insects because it increases the efficiency of a social group where different individuals perform different tasks repeatedly and presumably with increased performance. Cannibalism plays an important role in regulating colony growth and development by regulating the number of individuals in a colony and increasing survival by providing access to essential nutrients and minimizing competition among colony mates. To understand the synergy effects of DOL and cannibalistic behavior on colony dynamic outcomes, we propose and study a compartmental two‐stage model using ecological and evolutionary game theory settings. Our analytical results of the ecological and evolutionary models suggest that: (1) A noncannibalistic colony can survive if the efficiency of energy investment reflecting the DOL is greater than the relative death rate of the older population. (2) A cannibalistic colony can die out if both the efficiency of energy investment and the relative cannibalism rate (where each is also reflecting the DOL) are too large; or if the relative cannibalism rate alone is too small. (3) From our numerical analysis, cannibalism can increase or reduce the colony's total population size, which greatly depends on the benefit of egg cannibalism increasing or decreasing of adult's lifespan. (4) A cannibalistic and noncannibalistic colony can experience bistability due to cooperative behavior. (5) In the evolutionary settings, DOL can prevent colony death and natural selection can preserve strong Allee effects by selecting the traits with the largest investment on brood care and the lowest cannibalism rate. (6) Evolutionary dynamics may increase the fitness of the colony, i.e., the successful production of workforce which results in the increase of total worker population size, colony survival, and reproduction. Our results suggest both cannibalism and DOLs are adaptive strategies that increase the size of the worker population, and therefore, persistence of the colony.     

Evaluation of the expected makespan of a set of non-resumable jobs on parallel machines with stochastic failures

In this paper we consider a production process at operative level on m$m$ identical parallel machines, which are subject to stochastic machine failures. To avoid long downtime of the machines, caused by unexpected failures, preventive maintenance activities are planned and conducted, but if a failure could not be averted a corrective maintenance has to be performed. Both maintenance activities are assumed to restore the machine to be “as good as new”. The maintenance activities, the number of jobs and their allocation to machines as well as their sequence have a large impact on the performance of the production process and the delivery dates.     

Part I Parallel architectures and algorithms

This paper provides an introduction to algorithms for fundamental linear algebra problems on various parallel computer architectures, with the emphasis on VLSI systolic array machines. To illustrate the basic concepts and key issues, we consider the problem of the parallel solution of a nonsingular linear systems derived from the finite difference/element discretisation of anN ^th order system of differential equations.     

Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.     

Optimal maintenance of two stochastically deteriorating machines with an intermediate buffer

We consider a manufacturing system in which an input generating installation transfers a raw material to a subsequent production unit. Both machines deteriorate stochastically with usage and may fail. For each machine the deteriorating process is described by some known transition probabilities between different degrees of deterioration. A buffer has been built between the two machines in order to cope with unexpected failures of the installation. A discrete-time Markov decision model is formulated for the optimal preventive maintenance of both machines. The maintenance times are geometrically distributed and the cost structure includes operating costs, storage costs, maintenance costs and costs due to the lost production. It is proved that for fixed buffer content and for fixed deterioration degree of one machine, the average-cost optimal policy initiates a preventive maintenance of the other machine if and only if its degree of deterioration exceeds some critical level. We study, by means of numerical results, the effect of the variation of some parameters on the optimal policy and on the minimum average cost. For the case in which the maintenance times follow continuous distributions, an approximate discrete-time Markov decision model is proposed.     

Representation and analysis of transfer lines with machines that have different processing rates

A transfer line is a tandem production system, i.e. a series of machines separated by buffers. Material flows from outside the system to the first machine, then to the first buffer, then to the second machine, the second buffer, and so forth. In some earlier models, buffers are finite, machines are unreliable, and the times that parts spend being processed at machines are equal at all machines. In this paper, a method is provided to extend a decomposition method to large systems in which machines are allowed to take different lengths of time performing operations on parts. Numerical and simulation results are provided.     

How big is too big? Trading off the economies of scale of larger telecommunications network elements against the risk of larger outages

This paper builds a probabilistic model to analyze the risk–reward tradeoffs that larger telecommunications network elements present. Larger machines offer rewards in the form of cost savings due to economies of scale. But large machines are riskier because they affect more customers when they fail. Our model translates the risk of outages into dollar costs, which are random variables. This step enables us to combine the deployment cost and outage cost into a total cost. Once we express the decision makers’ preferences via a utility function, we can find the machine size that minimizes the total cost’s expected utility, thereby achieving an optimal tradeoff between reward and risk. The expected utility answers the question “how big is too big?”.     

Ant Colony Optimisation for Machine Layout Problems

Flexible machine layout problems describe the dynamic arrangement of machines to optimise the trade-off between material handling and rearrangement costs under changing and uncertain production environments. A previous study used integer-programming techniques to solve heuristically reduced versions of the problem. As an alternative, this paper introduces an ant colony optimisation (ACO) algorithm to generate good solutions. Experimental results are presented, with ACO obtaining better solutions than the reduction heuristic.     

Classification analysis for simulation of the duration of machine breakdowns

Machine failure can have a significant impact on the throughput of manufacturing systems, therefore accurate modelling of breakdowns in manufacturing simulation models is essential. Finite mixture distributions have been successfully used by Ford Motor Company to model machine breakdown durations in simulation models of engine assembly lines. These models can be very complex, with a large number of machines. To simplify the modelling we propose a method of grouping machines with similar distributions of breakdown durations, which we call the Arrows Classification Method, where the Two-Sample Cramér-von-Mises statistic is used to measure the similarity of two sets of the data. We evaluate the classification procedure by comparing the throughput of a simulation model when run with mixture models fitted to individual machine breakdown durations; mixture models fitted to group breakdown durations; and raw data. Details of the methods and results of the classification will be presented, and demonstrated using an example.     

On the Spectrum and Decay of Random Two-Dimensional Vorticity Distributions at Large Reynolds Number

The hypothesis is made that the vorticity distribution in a field of random two-dimensional vorticity (two-dimensional turbulence) develops discontinuities. The energy spectrum is then calculated and shown to behave like k^?4 for large values of the wave-number k. The rates of decay of mean square vorticity and velocity are estimated. An expression for the growth of length scale is obtained and it is noted that the size of turbulent trailing vortices is apparently well fitted by the formula.     

含不相关机的动态可重入柔性流水车间问题的混合DABC-GA算法

为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。     

Machine duplication and part subcontracting in the presence of alternative cell locations in manufacturing cell design

In this paper a model and a solution algorithm are reported to simultaneously deal with the processes of machine duplication and part subcontracting in the presence of two significant design issues in cellular manufacturing systems: (i) alternative cell locations; and (ii) the maximum number of machines assigned to a cell. As the problem, formulated as a polynomial programming model, is shown NP-hard in the strong sense, a higher-level heuristic algorithm based upon a concept known as ‘tabu search’ is presented. An example (small) problem is solved to demonstrate the functionality of the algorithm. Additionally, the small problem is solved for its optimal solution under different scenarios, both with linear single-row and linear double-row layout arrangements, and the solutions obtained are shown to match with those obtained with the heuristic algorithm. A comparison of six different versions of tabu search-based heuristics (TSH 1–TSH 6) is performed to investigate the impact of long-term memory and the use of fixed versus variable tabu-list sizes. A carefully constructed statistical experiment, based on randomised complete-block design, is used to test the performance on three different problem structures, classified as small, medium and large. The results show that TSH 6 with variable tabu-list size and long-term memory based on minimal frequencies is preferred for the single-row layout, while TSH 4 with variable tabu-list size and no long-term memory is preferred for the double-row layout. When subject to budgetary restrictions, the proposed approach can be used by parts manufacturing companies to determine which of the following three actions should be undertaken for each bottleneck part: bottleneck part left as in the initial solution, all the bottleneck machines connected to it are duplicated, or the part subcontracted.     

A survey of surface mount device placement machine optimisation: Machine classification

The optimisation of a printed circuit board assembly line is mainly influenced by the constraints of the surface mount device (SMD) placement machine and the characteristics of the production environment. This paper surveys the characteristics of the various machine technologies and classifies them into five categories (dual-delivery, multi-station, turret-type, multi-head and sequential pick-and-place), based on their specifications and operational methods. Using this classification, we associate the machine technologies with heuristic methods and discuss the scheduling issues of each category of machine. We see the main contribution of this work as providing a classification for SMD placement machines and to survey the heuristics that have been used on different machines. We hope that this will guide other researchers so that they can subsequently use the classification or heuristics, or even design new heuristics that are more appropriate to the machine under consideration.     

Enhanced artificial bee colony for training least squares support vector machines in commodity price forecasting

The importance of optimizing machine learning control parameters has motivated researchers to investigate for proficient optimization techniques. In this study, a Swarm Intelligence approach, namely artificial bee colony (ABC) is utilized to optimize parameters of least squares support vector machines. Considering critical issues such as enriching the searching strategy and preventing over fitting, two modifications to the original ABC are introduced. By using commodities prices time series as empirical data, the proposed technique is compared against two techniques, including Back Propagation Neural Network and by Genetic Algorithm. Empirical results show the capability of the proposed technique in producing higher prediction accuracy for the prices of interested time series data.     

Reversibility and dependence in a U-shaped production line

We deal with a U-shaped production line with multiple machines and a multifunction worker. The worker visits machines in a cyclic fashion and operates an item on each machine. The operation consists of detaching the processed item from the machine, sending it to the next machine, putting the new item on the machine and switching it on. Walking times of the worker and processing and operation times are i.i.d. random variables for each machine. We show that the sum of the firstn cycle times is stochastically the same as that in the reversed system where machines are arranged in the reversed order. We give examples where the distributions of waiting and cycle times depend on the machines, called starting ones, where the worker begins operation at time 0. A sufficient condition is derived under which the limiting expected waiting and cycle times do not depend on the starting machines.     

A Two-Level Production Control Model with Target Amount Rescheduling

This paper deals with the problem of two-level production control with disturbances. A production system is considered with several machines on the lower level and a section on the upper one. Each machine produces a given target amount by a given due date (common to all machines). Each machine has several possible speeds, which are subject to disturbances. On the machine level, at the routine control point, decision-making centres on introducing the proper speed and determining the next control point. It is assumed that all the target amounts are transferable; i.e. a part of each target amount can be processed by any other machine. In a case when it is realized, for a certain machine, that the target cannot be completed on time, the section reschedules the remaining target amounts among the machines. New target amounts are determined for the machines so that the overall target can be accomplished on time. A stochastic optimization formulation is presented, followed by a heuristic solution and simulation results.     

Power Aspects of Rheonomic Multibody Systems

Flexible manufacturing systems are characterized by machines with some or all mechanical degrees of freedom actively controlled resulting in the necessary prescribed motion of the production process or rheonomic constraints, respectively. Due to the high nonlinearity of large displacement motions inverse dynamics is a standard control concept well established in robotics and walking machines. It is shown that inverse dynamics results in high energy consumption and requires large power supply. For autonomous robots and walking machines the power supply adds to the weight, and additional weight needs more power again. Finally, actively controlled walking machines are very heavy devices not comparable to the lightweight design of passive walking mechanisms. It is proposed to use local energy storage by springs to overcome the drawback of inverse dynamics. The design principles for reduced energy consumption are outlined with simple mechanical models and will include nonlinear characteristics of the springs to improve further the local energy storage capacity.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

Average Cost Optimality for an Unreliable Two-Machine Flowshop with Limited Internal Buffer

We consider a production planning problem in a two-machine flowshop subject to breakdown and repair of machines and subject to nonnegativity and upper bound constraints on work-in-process. The objective is to choose machine production rates over time to minimize the long-run average inventory/backlog and production costs. For sufficiently large upper bound on the work-in-process, the problem is formulated as a stochastic dynamic program. We then establish a verification theorem and a partial characterization of the optimal control policy if it exists.