Bayesian analysis of hybrid life tests with exponential failure times

Summary A hybrid life test procedure is discussed from the Bayesian viewpoint. A total ofn items is placed on test, failed items are either not replaced or are replaced, and the test is terminated either when a pre-chosen number,K, of items have failed, or when a pre-determined time on test has been reached. Posterior and predictive distributions are obtained under the assumption of an exponential failure distribution, and point and interval estimates are given for the mean life and the life of an untested item. The results are applied to a numerical example.     

On the sum minimization version of the online bin covering problem

Given a set of m identical bins of size 1, the online input consists of a (potentially infinite) stream of items in (0,1]. Each item is to be assigned to a bin upon arrival. The goal is to cover all bins, that is, to reach a situation where a total size of items of at least 1 is assigned to each bin. The cost of an algorithm is the sum of all used items at the moment when the goal is first fulfilled. We consider three variants of the problem, the online problem, where there is no restriction of the input items, and the two semi-online models, where the items arrive sorted by size, that is, either by non-decreasing size or by non-increasing size. The offline problem is considered as well.     

Monitoring process for attributes with quality deterioration and diagnosis errors

The aim of this paper is to present an online economical quality-control procedure for attributes in a process subject to quality deterioration after random shift and misclassification errors during inspections. The process starts in control (State I) and, in a random time, it shifts to out of control (State II). Once at State II, the non-conforming fraction increases according to a non-decreasing function ψ(z), where z is the number of items produced after a shift. The monitoring procedure consists of inspecting a single item at every m produced items, which is examined r times independently to decide its condition. Once an inspected item is declared non-conforming, the process is stopped and adjusted. A direct search technique is used to find the optimum parameters which minimize the expected cost function. The proposed model is illustrated by a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.     

A note on a variant of the online open end bin packing problem

We study the minimum variant of the online open end bin packing problem. Items are presented one by one, and an item can be packed into a bin while the resulting total size of items excluding the minimum size item of the bin will be below 1. We design an improved online algorithm whose asymptotic competitive ratio does not exceed 1.180952381, and we prove a new lower bound of 1.1666666 on the asymptotic competitive ratio of any online algorithm.     

Statistical group testing with queueing involved

We consider a queueing model in which items wait to undergo group testing in batches of sizem. However, if fewer thanm items are present at the beginning of a service, items are tested singly. Ifm or more items are waiting at such an epoch, a group of sizem is tested and, if the group passes the test, allm items leave the system. When a group is found to contain at least one defective item, them items in it are retested individually. An algorithm is developed to compute many steady-state probabilities related to this queue. Comparisons of these probabilities are used to assess the effect of the group sizem on the behavior of the queue of items waiting for testing.This research was supported in part by Grant Nr. ECS-8601203 from the National Science Foundation.     

The software library numeralgo

The software library numeralgo of netlib collects the packages that authors submitted together with their paper to the journal Numerical Algorithms. The items of the library are named as na x, where x stands for a sequential number identifying a specific package. In the first section, a survey of the old packages will be reported. In the next section, we list the new software related to the papers published in this issue. In the last section, we describe the netlib repository and how to obtain an item of the library numeralgo. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Gain-Loss Model: Bias of the Parameter Estimates

The gain-loss model is a formal model developed within Knowledge Space Theory. It consists of five parameters (initial probabilities of the skills, effects of learning objects on gaining and losing skills, careless error and lucky guess probabilities of the items) that are estimated by maximum likelihood. Three simulation studies show that high values of both initial and final probabilities of an item lead to a systematic overestimation of the lucky guess parameter of that item. A re-parameterization of the model is proposed, in which a joint probability of lucky guess is introduced.     

An efficient randomized group testing procedure to determine the number of defectives

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In this paper, we present an efficient randomized group testing procedure that determines the exact number of defectives in a sample set with high success probability.     

A decision-theoretic approach to some screening problems

Summary Suppose an item is acceptable if its measurement on the variable of interestY isY≦u. It may be expensive (or impossible) to measureY, and a correlated variableX exists which is relatively inexpensive to measure and is used to screen items, i.e., to declare them acceptable ifX≦w. We examine two situations in both of whichl acceptable items are needed. (i) Before use of the item,Y is measured directly to ensure acceptability: ShouldX be used for screening purposes before theY measurement or not? (ii)Y cannot be measured directly before use, but screening is possible to determine the items that are to be used. We assume thatX andY have a bivariate normal distribution for which the parameters are known. Some comments are made about the case when the parameters are not known.     

A pegging approach to the precedence-constrained knapsack problem

The knapsack problem (KP) is generalized to the case where items are partially ordered through a set of precedence relations. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be packed in the knapsack. However, each item can be accepted only when all the preceding items have been included in the knapsack. The knapsack problem with these additional constraints is referred to as the precedence-constrained knapsack problem (PCKP). To solve PCKP exactly, we present a pegging approach, where the size of the original problem is reduced by applying the Lagrangian relaxation followed by a pegging test. Through this approach, we are able to solve PCKPs with thousands of items within a few minutes on an ordinary workstation.     

Undecidability of automorphism groups

We give a simple (and easy to apply) technique that gives the undecidability of the theory of many automorphism groups: Let G be a group of automorphisms of a structure. Suppose that is not the identity and has no non-singleton finite orbits. If the centraliser of g is transitive on the support of g and satisfies a further technical condition, then the subgroup generated by g is equal to the double centraliser of g. Thus if G contains such an element g that is conjugate to all its positive powers, then one can interpret addition and multiplication of natural numbers in the theory of G using the parameter g; consequently, G has undecidable theory. Received: 9 October 2000 / in final form: 2 October 2001 / Published online: 29 April 2002     

Diagnostic errors and repetitive sequential classifications in on-line process control by attributes

The procedure of on-line process control by attributes, known as Taguchi’s on-line process control, consists of inspecting the mth item (a single item) at every m produced items and deciding, at each inspection, whether the fraction of conforming items was reduced or not. If the inspected item is non-conforming, the production is stopped for adjustment. As the inspection system can be subject to diagnosis errors, one develops a probabilistic model that classifies repeatedly the examined item until a conforming or b non-conforming classification is observed. The first event that occurs (a conforming classifications or b non-conforming classifications) determines the final classification of the examined item. Proprieties of an ergodic Markov chain were used to get the expression of average cost of the system of control, which can be optimized by three parameters: the sampling interval of the inspections (m); the number of repeated conforming classifications (a); and the number of repeated non-conforming classifications (b). The optimum design is compared with two alternative approaches: the first one consists of a simple preventive policy. The production system is adjusted at every n produced items (no inspection is performed). The second classifies the examined item repeatedly r (fixed) times and considers it conforming if most classification results are conforming. Results indicate that the current proposal performs better than the procedure that fixes the number of repeated classifications and classifies the examined item as conforming if most classifications were conforming. On the other hand, the preventive policy can be averagely the most economical alternative rather than those ones that require inspection depending on the degree of errors and costs. A numerical example illustrates the proposed procedure.     

Determining targets for multi-stage adaptive tests using integer programming

This paper considers a multi-stage adaptive test (MST) where the testlets at each stage are determined prior to the administration. The assembly of a MST requires target information and target response functions for the MST design. The targets are chosen to create tests with accurate scoring and high utilization of items in an operational pool. Forcing all MSTs to have information and response function plots to be within an interval about the targets will yield parallel MSTs, in the sense that standardized paper-and-pencil tests are considered parallel. The objective of this paper is to present a method to determine targets for the MST design based on an item pool and an assumed distribution of examinee ability. The approach is applied to a Skills Readiness Inventory test designed to identify logical reasoning deficiencies of examinees. This method can be applied to obtain item response theory targets for a linear test as this is a special case of a MST.     

A subquadratic algorithm for constructing approximately optimal binary search trees

An algorithm is presented which constructs an optimal binary search tree for an ordered list of n items, and which requires subquadratic time if there is no long sublist of very low frequency items. For example, time = O(n^1.6) if the frequency of each item is at least /n for some constant > 0. A second algorithm is presented which constructs an approximately optimal binary search tree. This algorithm has one parameter, and exhibits a trade-off between speed and accuracy. It is possible to choose the parameter such that time = O(n^1.6) and error = o(1).     

An efficient algorithm for mining high utility itemsets with negative item values in large databases

Utility itemsets typically consist of items with different values such as utilities, and the aim of utility mining is to identify the itemsets with highest utilities. In the past studies on utility mining, the values of utility itemsets were considered as positive. In some applications, however, an itemset may be associated with negative item values. Hence, discovery of high utility itemsets with negative item values is important for mining interesting patterns like association rules. In this paper, we propose a novel method, namely HUINIV (High Utility Itemsets with Negative Item Values)-Mine, for efficiently and effectively mining high utility itemsets from large databases with consideration of negative item values. To the best of our knowledge, this is the first work that considers the concept of negative item values in utility mining. The novel contribution of HUINIV-Mine is that it can effectively identify high utility itemsets by generating fewer high transaction-weighted utilization itemsets such that the execution time can be reduced substantially in mining the high utility itemsets. In this way, the process of discovering all high utility itemsets with consideration of negative item values can be accomplished effectively with less requirements on memory space and CPU I/O. This meets the critical requirements of temporal and spatial efficiency for mining high utility itemsets with negative item values. Through experimental evaluation, it is shown that HUINIV-Mine outperforms other methods substantially by generating much less candidate itemsets under different experimental conditions.     

基于IRT的一种多级评分模型的参数估计

基于项目反应理论,文章先将双参数Logistic模型中的答对概率视为被试的得分率,采用最小二乘估计法先后对多级评分模型中的项目参数和能力参数进行估计,再根据已知条件将所得的结果加以迭代,提出了一种实用性很强的参数估计方法.     

FIFO Versus LIFO Issuing Policies for Stochastic Perishable Inventory Systems

We consider an inventory system for perishable items in which the arrival times of the items to be stored and the ones of the demands for those items form independent Poisson processes. The shelf lifetime of every item is finite and deterministic. Every demand is for a single item and is satisfied by one of the items on the shelf, if available. A demand remains unsatisfied if it arrives at an empty shelf. The aim of this paper is to compare two issuing policies: under FIFO (‘first in, first out’) any demand is satisfied by the item with the currently longest shelf life, while under LIFO (‘last in, first out’) always the youngest item on the shelf is assigned first. We determine the long-run net average profit as a function of the system parameters under each of the two policies, taking into account the revenue earned from satisfied demands, the cost of shelf space, penalties for unsatisfied demands, and the purchase cost of incoming items. The analytical results are used in several numerical examples in which the optimal input rate and the maximum expected long-run average profit under FIFO and under LIFO are determined and compared. We also provide a sensitivity analysis of the optimal solution for varying parameter values.     

The Linear Ordering Problem with cumulative costs

The optimization problem of finding a permutation of a given set of items that minimizes a certain cost function is naturally modeled by introducing a complete digraph G whose vertices correspond to the items to be sorted. Depending on the cost function to be used, different optimization problems can be defined on G. The most familiar one is the min-cost Hamiltonian path problem (or its closed-path version, the Traveling Salesman Problem), arising when the cost of a given permutation only depends on consecutive node pairs. A more complex situation arises when a given cost has to be paid whenever an item is ranked before another one in the final permutation. In this case, a feasible solution is associated with an acyclic tournament (the transitive closure of an Hamiltonian path), and the resulting problem is known as the Linear Ordering Problem (LOP).     

Exact and approximate methods for a one-dimensional minimax bin-packing problem

One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the ‘weights’ of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.