平行机物流排序的近似算法

本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究“满足一致性条件”和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.     

Scheduling linearly shortening jobs under precedence constraints

We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.     

Notes on “A bicriteria flowshop scheduling with a learning effect”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling with a learning effect, Applied Mathematical Modelling 32 (2008) 1719–1733] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model.     

Scheduling open shops with parallel machines to minimize total completion time

This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms.     

Parallel direct methods for solving the system of linear equations with pipelining on a multicore using OpenMP

Recent developments in high performance computer architecture have a significant effect on all fields of scientific computing. Linear algebra and especially the solution of linear systems of equations lie at the heart of many applications in scientific computing. This paper describes and analyzes three parallel versions of the dense direct methods such as the Gaussian elimination method and the LU form of Gaussian elimination that are used in linear system solving on a multicore using an OpenMP interface. More specifically, we present two naive parallel algorithms based on row block and row cyclic data distribution and we put special emphasis on presenting a third parallel algorithm based on the pipeline technique. Further, we propose an implementation of the pipelining technique in OpenMP. Experimental results on a multicore CPU show that the proposed OpenMP pipeline implementation achieves good overall performance compared to the other two naive parallel methods. Finally, in this work we propose a simple, fast and reasonably analytical model to predict the performance of the direct methods with the pipelining technique.     

Solving a kind of boundary-value problem for ordinary differential equations using Fermi—The next generation CUDA computing architecture

The aim of this paper is to show that a special kind of boundary value problem for solving second-order ordinary differential equations can be efficiently solved on modern heterogeneous computer architectures based on CPU and GPU Fermi processors. Such a problem reduces to the problem of solving a large tridiagonal system of linear equations with an almost Toeplitz structure. The considered algorithm is based on the recently developed divide and conquer method for solving linear recurrence systems with constant coefficients.     

A note on symmetry reduction for circular traveling tournament problems

The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We exemplify this benefit by modifying the DFS∗ algorithm of Uthus et al. (2009) and show that speedups can approximate factor 4n.     

A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times

In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances.     

Application of parallel computing to speed up chemometrics for GC×GC-TOFMS based metabolic fingerprinting

Parallel computing was tested regarding its ability to speed up chemometric operations for data analysis. A set of metabolic samples from a second hand smoke (SHS) experiment was analyzed with comprehensive two-dimensional gas chromatography time-of-flight mass spectrometry (GC × GC-TOFMS). Data was further preprocessed and analyzed. The preprocessing step comprises background correction, smoothing and alignment of the chromatographic signal. Data analysis was performed by applying t-test and partial least squares projection to latent structures discriminant analysis (PLS-DA). The optimization of the algorithm for parallel computing led to a substantial increase in performance. Metabolic fingerprinting showed a discrimination of the samples and indicates a metabolic effect of SHS.