Heuristic concentration: Two stage solution construction

By utilizing information from multiple runs of an interchange heuristic we construct a new solution that is generally better than the best local optimum previously found. This new, two stage, approach to combinatorial optimization is demonstrated in the context of the p-median problem. Two layers of optimization are superimposed. The first layer is a conventional heuristic the second is a heuristic or exact procedure which draws on the concentrated solution set generated by the initial heuristic. The intention is to provide an alternative heuristic procedure which, when dealing with large problems, has a higher probability of producing optimal solutions than existing methods. The procedure is fairly general and appears to be applicable to combinatorial problems in a number of contexts.     

Optimal Batch Sizes for a Two-Stage Production System

A 2-stage production model is considered in which items are processed in batches at both stages. Items processed at Stage 1 are stored until needed at Stage 2 and new batches are processed at Stage 1 only when necessary to meet second stage demand. It is shown that in an optimal policy the batch size at the first stage must be an integer multiple of second stage batch size. This can be used in an analytical derivation of the optimum batch sizes.     

Two‐stage algorithms for covering array construction

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory.     

Approximate solution for two stage open networks with Markov-modulated queues minimizing the state space explosion problem

Analytical solutions for two-dimensional Markov processes suffer from the state space explosion problem. Two stage tandem networks are effectively used for analytical modelling of various communication and computer systems which have tandem system behaviour. Performance evaluation of tandem systems with feedbacks can be handled with these models. However, because of the numerical difficulties caused by large state spaces, considering server failures and repairs at the second stage employing multiple servers has not been possible. The solution proposed in this paper is approximate with a high degree of accuracy. Using this approach, two stage open networks with multiple servers, break downs, and repairs at the second stage as well as feedback can be modelled as three-dimensional Markov processes and solved for performability measures. Results show that, unlike other approaches such as spectral expansion, the steady state solution is possible regardless of the number of servers employed.     

Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

A two-stage prognosis model in condition based maintenance

We often observe in practice that the life of a piece of production equipment can be divided into two stages. The first stage is referred to as the normal working stage where no significant deviation from the normal operating state is observed. The second stage is called the failure delay period, since a defect may be initiated, and progressively develop into an actual failure, i.e., the equipment is in a defective stage but still working during this stage. With the help of condition monitoring, hidden defects already present in the equipment may be detected, but for maintenance planning purposes, the prediction of the initiation point of the second stage, and more importantly, the residual life thereafter is important. This paper reports on the development of a probability model to predict the initiation point of the second stage and the remaining life based on available condition monitoring information. The method for model parameters estimation is discussed and applied to real data.     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

Production and location on a network under demand uncertainty

The Hakimi theorem is fundamental in location theory. It says that the set of nodes and market-places necessarily contains a profit-maximizing location when the transportation costs are concave in distance. The purpose of this letter is to discuss the validity of this theorem in the context of a two-stage stochastic model of the location of a firm on a network. In the first stage, the firm chooses its location and production level before knowing the exact demands. In the second stage, it observes the realization of the random variables representing the demands and decides upon the distribution of its production. It is shown that the Hakimi theorem still holds in this model when the firm is risk-neutral. On the other hand, in the case of a risk-averse firm, it ceases to be true in that all the points of the network must be considered to obtain an optimal location.     

An analysis of setup cost reduction in a two stage system

This paper investigates the impact of investing in setup cost reduction in a two stage manufacturing process. Closed form relationships are developed for the cases of investment in primary stage setup cost reduction, investment in finishing stage setup cost reduction, and simultaneous investment in setup cost reduction in both stages. Numerical results are presented which compare each of the models to the basic model. These results indicate that when investment in both stages is feasible, it is most effective to simultaneously invest in setup cost reduction. Failing this, the next best alternative is to invest in setup cost reduction in the finishing stage.     

On the cutting stock problem under stochastic demand

This paper addresses the one-dimensional cutting stock problem when demand is a random variable. The problem is formulated as a two-stage stochastic nonlinear program with recourse. The first stage decision variables are the number of objects to be cut according to a cutting pattern. The second stage decision variables are the number of holding or backordering items due to the decisions made in the first stage. The problem’s objective is to minimize the total expected cost incurred in both stages, due to waste and holding or backordering penalties. A Simplex-based method with column generation is proposed for solving a linear relaxation of the resulting optimization problem. The proposed method is evaluated by using two well-known measures of uncertainty effects in stochastic programming: the value of stochastic solution—VSS—and the expected value of perfect information—EVPI. The optimal two-stage solution is shown to be more effective than the alternative wait-and-see and expected value approaches, even under small variations in the parameters of the problem.     

Harvesting discrete nonlinear age and stage structured populations

A natural extension of age structured Leslie matrix models is to replace age classes with stage classes and to assume that, in each time period, the transition from one stage class to the next is incomplete; that is, diagonal terms appear in the transition matrix. This approach is particularly useful in resource systems where size is more easily measured than age. In this linear setting, the properties of the models are known; and these models have been applied to the analysis of population problems. A more applicable setting is to assume that the reproduction, survival, and transition parameters in the model are density dependent. The behavior of such models is determined by the form of this density dependence. Here, we focus on models in which the parameters depend on the value of an aggregated variable, defined to be the weighted sum of the number of individuals in each stage class. In forestry models, for example, this aggregated variable may represent a basal area index; in fisheries models, it may represent a spawning stock biomass. Current age structured nonlinear stock-recruitment fisheries models are a special case of the models considered here. Certain results that apply to age structured models can be extended to this broader class of models. In particular, the questions addressed relate to the minimum number of age classes that need to be harvested to obtain maximum sustainable yield policies and to managing resources under nonequilibrium and stochastic conditions. Application of the model to problems in fisheries, forestry, pest, and wildlife management is also discussed.The author would like to thank R. G. Haight for comments and discussions relating to the material presented here. This work was supported by NSF Grant DMS-85-11717.     

Tuning a parametric Clarke–Wright heuristic via a genetic algorithm

Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.     

Extracting compact fuzzy rules for nonlinear system modeling using subtractive clustering,GA and unscented filter

This paper presents a two stage procedure for building optimal fuzzy model from data for nonlinear dynamical systems. Both stages are embedded into Genetic Algorithm (GA) and in the first stage emphasis is placed on structural optimization by assigning a suitable fitness to each individual member of population in a canonical GA. These individuals represent coded information about the structure of the model (number of antecedents and rules). This information is consequently utilized by subtractive clustering to partition the input space and construct a compact fuzzy rule base. In the second stage, Unscented Filter (UF) is employed for optimization of model parameters, that is, parameters of the input–output Membership Functions (MFs).     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

Solving the Problem of Rerostering Nurse Schedules with Hard Constraints: New Multicommodity Flow Models

The problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time.     

Cooperation by indirect revelation through strategic behavior

The paper deals with a one-shot prisoners' dilemma when the players have an option to go to court but cannot verify their testimonies. To solve the problem a second stage is added to a game. At the first stage the players are involved in the prisoners' dilemma and at the second stage they play another game in which their actions are verifiable. In such a setup the information about the actions chosen at the prisoners' dilemma stage can be revealed through strategic behavior of the players during second stage. A mechanism for such revelation in the extended game is described. It provides an existence of a unique sequential equilibrium, which may be obtained by an iterative elimination of dominated strategies and has a number of desirable properties.     

Waiting time analysis for a tandem queue with correlated service

The effect on overall waiting time including service is investigated when there is positive correlation between the first and second stage service times in a two stage tandem system. The importance of understage waiting (or “buffer”) space is underlined. The analysis is an application of the authors' work reported in [1].     

A Hybrid Logistic Model for Case-Control Studies

For logistic regression in case-control studies, when risk factors associated with the outcome are exceedingly rare in the control group, the estimation of parameters in the model becomes difficult. In this paper, we propose a two-stage hybrid method to achieve this. In the first stage, we model the risk due to the rare factor, and in the second stage we model the residual risk due to the other factors using standard logistic model.     

Global stability for an HIV-1 infection model including an eclipse stage of infected cells

We consider the mathematical model for the viral dynamics of HIV-1 introduced in Rong et al. (2007) [37]. One main feature of this model is that an eclipse stage for the infected cells is included and cells in this stage may revert to the uninfected class. The viral dynamics is described by four nonlinear ordinary differential equations. In Rong et al. (2007) [37], the stability of the infected equilibrium has been analyzed locally. Here, we perform the global stability analysis using two techniques, the Lyapunov direct method and the geometric approach to stability, based on the higher-order generalization of Bendixson?s criterion. We obtain sufficient conditions written in terms of the system parameters. Numerical simulations are also provided to give a more complete representation of the system dynamics.