Permutation decoding for binary codes from lattice graphs

By finding explicit PD sets, we show that permutation decoding can be used for the binary code obtained from the row span over the field F₂ of an adjacency matrix of the lattice graph L₂(n) for any n?5.     

Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines

In this paper, we study the permutation flow shop scheduling problems with deteriorating jobs on no-idle dominant machines. The objective is to minimize one of the two regular performance criteria, namely, makespan and total completion time. For each objective, the following dominant machines constraint: idm, ddm, idm–ddm and ddm–idm are considered. We present a polynomial time solution algorithm for each of the four cases.     

Topological permutation entropy

Permutation entropy quantifies the diversity of possible ordering of the successively observed values a random or deterministic system can take, just as Shannon entropy quantifies the diversity of the values themselves. When the observable or state variable has a natural order relation, making permutation entropy possible to compute, then the asymptotic rate of growth in permutation entropy with word length forms an alternative means of describing the intrinsic entropy rate of a source. Herein, extending a previous result on metric entropy rate, we show that the topological permutation entropy rate for expansive maps equals the conventional topological entropy rate familiar from symbolic dynamics. This result is not limited to one-dimensional maps.     

Unbiased Recursive Partitioning: A Conditional Inference Framework

Recursive binary partitioning is a popular tool for regression analysis. Two fundamental problems of exhaustive search procedures usually applied to fit such models have been known for a long time: overfitting and a selection bias towards covariates with many possible splits or missing values. While pruning procedures are able to solve the overfitting problem, the variable selection bias still seriously affects the interpretability of tree-structured regression models. For some special cases unbiased procedures have been suggested, however lacking a common theoretical foundation. We propose a unified framework for recursive partitioning which embeds tree-structured regression models into a well defined theory of conditional inference procedures. Stopping criteria based on multiple test procedures are implemented and it is shown that the predictive performance of the resulting trees is as good as the performance of established exhaustive search procedures. It turns out that the partitions and therefore the models induced by both approaches are structurally different, confirming the need for an unbiased variable selection. Moreover, it is shown that the prediction accuracy of trees with early stopping is equivalent to the prediction accuracy of pruned trees with unbiased variable selection. The methodology presented here is applicable to all kinds of regression problems, including nominal, ordinal, numeric, censored as well as multivariate response variables and arbitrary measurement scales of the covariates. Data from studies on glaucoma classification, node positive breast cancer survival and mammography experience are re-analyzed.     

Use of the bootstrap and permutation methods for a more robust variable importance in the projection metric for partial least squares regression

Bio-pharmaceutical manufacturing is a multifaceted and complex process wherein the manufacture of a single batch hundreds of processing variables and raw materials are monitored. In these processes, identifying the candidate variables responsible for any changes in process performance can prove to be extremely challenging. Within this context, partial least squares (PLS) has proven to be an important tool in helping determine the root cause for changes in biological performance, such as cellular growth or viral propagation. In spite of the positive impact PLS has had in helping understand bio-pharmaceutical process data, the high variability in measured response (Y) and predictor variables (X), and weak relationship between X and Y, has at times made root cause determination for process changes difficult. Our goal is to demonstrate how the use of bootstrapping, in conjunction with permutation tests, can provide avenues for improving the selection of variables responsible for manufacturing process changes via the variable importance in the projection (PLS-VIP) statistic. Although applied uniquely to the PLS-VIP in this article, the generality of the aforementioned methods can be used to improve other variable selection methods, in addition to increasing confidence around other estimates obtained from a PLS model.     

On edge-primitive graphs of order twice a prime power

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In this paper, edge-primitive graphs of order twice a prime power are completely determined.     

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean [J.C. Bean, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal of Computing 6(2) (1994) 154–160] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard [E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278–285], and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. [J.P. Watson, L. Barbulescu, L.D. Whitley, A.E. Howe, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing 14(2) (2002) 98–123]. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves [J. Liu, C.R. Reeves, Constructive and composite heuristic solutions to the P∥∑C_i scheduling problem, European Journal of Operational Research 132 (2001) 439–452], and Rajendran and Ziegler [C. Rajendran, H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155(2) (2004) 426–438]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.