Backward capacity-filtering for electronics Fabs

In electronics Fabs such as semiconductor Fabs and liquid crystal display (LCD) Fabs, which are capital-intensive, finite-capacity planning is critical to achieving full-capacity production and on-time production. However, existing finite-capacity planning methods do not adequately reflect the actual capacity profiles of an electronics Fab. In this paper, we propose a new Fab-level capacity-filtering procedure to generate finite-capacity plan: a backward capacity-filtering procedure for generating finite-capacity release plan. When developing the Fab-level filtering procedures, we use stage-level capacity-filtering algorithms as a key building block. In this study, we enhance the previous capacity-filtering algorithms proposed by one of the authors in order to facilitate the practical requirements of electronics Fabs. We apply the proposed capacity-filtering method to a modern LCD–TFT Fab in Korea. Performance analyses demonstrate that the proposed method is superior to existing methods.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem

This paper considers the minimum-energy symmetric network connectivity problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.     

Group decision making on water resources based on analysis of individual rankings

In problems to do with managing water resources multiple decision makers are involved, each acting in their own right and using different value systems. In the literature on management science, several procedures are proposed in order to establish a collective preference based on the aggregation of different individual preferences. However, the well-known methods that focus on a single winner have some inconveniences that should be addressed. This paper is focused on a group decision making procedure based on the analysis of individual rankings with the aim of choosing an appropriate alternative for a water resources problem. This alternative is found to be the best compromise from the points of view of all actors involved in the decision problem. The structure of the method is set out as is its application to the water resources problem. A comparison with other methods is presented and discussed.     

On approximation of the fixed charge transportation problem

In this paper we present a new approximation for computing lower bound for the fixed charge transportation problem (FCTP). The lower bounds thus generated delivered 87% optimal solutions for 56 randomly generated small, up to 6×10 in size, problems in an experimental design. For somewhat larger, 10×10 and 10×15 size problems, the lower bounds delivered an average error of 5%, approximately, using a fraction of CPU times as compared to CPLEX to solve these problems. The proposed lower bound may be used as a superior initial solution with any other existing branch-and-bound method or tabu search heuristic procedure to enhance convergence to the optimal solution for large size problems which cannot be solved by CPLEX due to time constraints.     

Lot scheduling problems of multiple items in the shop with both receiving and delivery just in time

Abstract. This paper deals with lot scheduling problems of multiple items processed in the shop with either a single machine or heterogeneous machines, under the condition that parts to be processed must arrive at the production line at the right times in the right quantities, and that completed parts must be delivered at their due date. Each of the problems is divided into subproblems of lot sizing and scheduling the resulting lots. Solution procedures solving the subproblems are separately optimal. However, since one of the subproblems is not independent of the other, the proposed algorithms adopting these procedures are to be considered heuristic. An iterative procedure is provided to improve solutions. The performance measure used is that of minimizing the total actual flow time considering both receiving just in time and delivery just in time. Numerical examples are presented to show the implementation of the algorithms.     

Sufficient conditions for the optimality of the greedy algorithm in greedoids

Greedy algorithms are among the most elementary ones in theoretical computer science and understanding the conditions under which they yield an optimum solution is a widely studied problem. Greedoids were introduced by Korte and Lovász at the beginning of the 1980s as a generalization of matroids. One of the basic motivations of the notion was to extend the theoretical background behind greedy algorithms beyond the well-known results on matroids. Indeed, many well-known algorithms of a greedy nature that cannot be interpreted in a matroid-theoretical context are special cases of the greedy algorithm on greedoids. Although this algorithm turns out to be optimal in surprisingly many cases, no general theorem is known that explains this phenomenon in all these cases. Furthermore, certain claims regarding this question that were made in the original works of Korte and Lovász turned out to be false only most recently. The aim of this paper is to revisit and straighten out this question: we summarize recent progress and we also prove new results in this field. In particular, we generalize a result of Korte and Lovász and thus we obtain a sufficient condition for the optimality of the greedy algorithm that covers a much wider range of known applications than the original one.

     

Hybrid Evolutionary Algorithms for Graph Coloring

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.     

Stock Evaluation Using a Preference Disaggregation Methodology

This paper presents a real application of a multicriteria decision aid (MCDA) approach to portfolio selection based on preference disaggregation, using ordinal regression and linear programming (UTADIS method; UTilités Additives DIScriminantes). The additive utility functions that are derived through this approach have the extrapolation ability that any new alternative (share) can be easily evaluated and classified into one of several user-predefined groups. The procedure is illustrated with a case study of 98 stocks from the Athens stock exchange, using 15 criteria. The results are encouraging, indicating that the proposed methodology could be used as a tool for the analysis of the portfolio managers' preferences and choices. Furthermore, the comparison with multiple discriminant analysis (either using a stepwise procedure or not) illustrates the superiority of the proposed methodology over a well-known multivariate statistical technique that has been extensively used to study financial decision-making problems.     

Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

The paper presents a general method of designing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints. The core of the method is a simple deterministic procedure of rounding of linear relaxations (referred to as pipage rounding). With the help of the method we design approximation algorithms with better performance guarantees for some well-known problems including MAXIMUM COVERAGE, MAX CUT with given sizes of parts and some of their generalizations.     

基于杂合遗传算法的工艺路线可变Job Shop调度研究

提出一种将遗传算法与启发式规则、模拟退火法等搜索方法结合在一起的杂合遗传算法,用于求解工艺路线可变的JobShop调度问题。通过对某双极型集成电路封装企业的JobShop调度仿真,结果表明算法是有效和可行的。     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

An Information-Maximizing Interactive Procedure for Scenario Probability Elicitation

Various approaches have been proposed for determining scenario probabilities to facilitate long-range planning and decision making. These include microlevel approaches based on the analysis of relevant underlying events and their interrelations and direct macrolevel examination of the scenarios. The determination of a unique solution demands excessive consistency and time requirements on the part of the expert and often is not guaranteed by these procedures. We propose an interactive information maximizing scenario probability query procedure (IMQP) that exploits the desirable features of existing methods while circumventing their drawbacks. The approach requires elicitation of cardinal probability assessments and bounds for only marginal and first-order conditional events, as well as ordinal probability comparisons (probability orderings or rankings) of carefully selected scenario subsets determined using concepts of information theory. Guidelines for implementation based on simulation results are also developed. A goal program for handling inconsistent ordinal probability responses is also integrated into the procedure. The results of behavioral experimentation (which compared our approach to Expert Choice and showed that the IMQP was viable) compared favorably in terms of ease of use and time requirements, and works best for problems with a large number of scenarios. Design modifications to IMQP learned from the experiments, such as incorporating interactive graphics, are also in progress.     

Tracking and outperforming large stock-market indices

Enhanced index-tracking funds aim to achieve a small target excess return over a given financial benchmark index with minimum additional risk relative to this index, i.e., a minimum tracking error. These funds are attractive to investors, especially when the index is large and thus well diversified. We consider the problem of determining a portfolio for an enhanced index-tracking fund that is benchmarked against a large stock-market index subject to real-life constraints that may be imposed by investors, stock exchanges, or investment guidelines. In the literature, various solution approaches have been proposed to enhanced index tracking that are based on different linear and quadratic tracking-error functions. However, it remains an open question which tracking-error function should be minimized to determine good enhanced index-tracking portfolios. Moreover, the existing approaches may neglect real-life constraints such as the minimum trading values imposed by stock exchanges or may not devise good feasible portfolios within a reasonable computational time when the index is large. To overcome these shortcomings, we propose novel mixed-integer linear and quadratic programming formulations and novel matheuristics. To address the open question, we minimize different tracking-error functions by applying the proposed matheuristics and exact solution approaches based on the proposed mixed-integer programming formulations in a computational experiment using a set of problem instances based on large stock-market indices with up to more than 9,000 constituents. The results of our study suggest that minimizing the so-called tracking error variance, which is a quadratic function, is preferable to minimizing other tracking-error functions.     

More-for-less algorithm for fixed-charge transportation problems

The more-for-less (MFL) phenomenon in distribution problems occurs when it is possible to ship more total goods for less (or equal) total cost, while shipping the same quantity or more from each origin and to each destination. This paradox occurs often in fixed-charge transportation problems (FCTPs), and further analysis could bring significant reduction in costs. The MFL phenomenon for FCTPs has received minimal attention in the literature despite the fact that existing analytical algorithms, such as branch and bound, are limited to small problems due to excessive computational effort. In this paper, we develop a simple heuristic algorithm to identify the demand destinations and the supply points to ship MFL in FCTPs. The proposed method builds upon any existing basic feasible solution. It is easy to implement and can serve as an effective tool for managers for solving the more-for-less paradox for large distribution problems.     

Human Salmonellosis: Estimation of Dose-Illness from Outbreak Data

The quantification of the relationship between the amount of microbial organisms ingested and a specific outcome such as infection, illness, or mortality is a key aspect of quantitative risk assessment. A main problem in determining such dose-response models is the availability of appropriate data. Human feeding trials have been criticized because only young healthy volunteers are selected to participate and low doses, as often occurring in real life, are typically not considered. Epidemiological outbreak data are considered to be more valuable, but are more subject to data uncertainty. In this article, we model the dose-illness relationship based on data of 20 Salmonella outbreaks, as discussed by the World Health Organization. In particular, we model the dose-illness relationship using generalized linear mixed models and fractional polynomials of dose. The fractional polynomial models are modified to satisfy the properties of different types of dose-illness models as proposed by Teunis et al . Within these models, differences in host susceptibility (susceptible versus normal population) are modeled as fixed effects whereas differences in serovar type and food matrix are modeled as random effects. In addition, two bootstrap procedures are presented. A first procedure accounts for stochastic variability whereas a second procedure accounts for both stochastic variability and data uncertainty. The analyses indicate that the susceptible population has a higher probability of illness at low dose levels when the combination pathogen-food matrix is extremely virulent and at high dose levels when the combination is less virulent. Furthermore, the analyses suggest that immunity exists in the normal population but not in the susceptible population.     

SOLUTION PROCEDURES WITH LIMITED SAMPLE DATA FOR THE OPTIMAL REPLACEMENT PROBLEM

Recently we have developed solution procedures for the optimal replacement problem when the distribution of the time-to-failure (ttf) is partially specified by the first two moments, partial and complete. However, we have later learned, using Monte-Carlo simulation, that when moments are unknown and have to be estimated from sample data, the most accurate procedure developed therein is in practice extremely sensitive to sampling fluctuations. In this paper we modify the procedure to render it less susceptible to sampling variation. In addition, we introduce a new solution procedure that requires specification of only the median and the partial means of the ttf distribution. For both procedures, it is demonstrated that when the moments required for the distribution fitting are known, highly accurate optimal solutions are obtained. Conversely, when the moments are unknown and sample estimates based on small samples are used, both procedures result in stable solutions (low mean-squared-errors).     

Dual Objective Segmentation to Improve Targetability: An Evolutionary Algorithm Approach**

Cluster‐based segmentation usually involves two sets of variables: (i) the needs‐based variables (referred to as the bases variables), which are used in developing the original segments to identify the value, and (ii) the classification or background variables, which are used to profile or target the customers. The managers’ goal is to utilize these two sets of variables in the most efficient manner. Pragmatic managerial interests recognize the underlying need to start shifting from methodologies that obtain highly precise value‐based segments but may be of limited practical use as they provide less targetable segments. Consequently, the imperative is to shift toward newer segmentation approaches that provide greater focus on targetable segments while maintaining homogeneity. This requires dual objective segmentation, which is a combinatorially difficult problem. Hence, we propose and examine a new evolutionary methodology based on genetic algorithms to address this problem. We show, based on a large‐scale Monte Carlo simulation and a case study, that the proposed approach consistently outperforms the existing methods for a wide variety of problem instances. We are able to obtain statistically significant and managerially important improvements in targetability with little diminution in the identifiability of value‐based segments. Moreover, the proposed methodology provides a set of good solutions, unlike existing methodologies that provide a single solution. We also show how these good solutions can be used to plot an efficient Pareto frontier. Finally, we present useful insights that would help managers in implementing the proposed solution approach effectively.     

Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem

In this work three genetic algorithms are presented for the permutation flowshop scheduling problem with total tardiness minimisation criterion. The algorithms include advanced techniques like path relinking, local search and a procedure to control the diversity of the population. We also include a speed up procedure in order to reduce the computational effort needed for the local search technique, which results in large CPU time savings. A complete calibration of the different parameters and operators of the proposed algorithms by means of a design of experiments approach is also given. We carry out a comparative evaluation with the best methods that can be found in the literature for the total tardiness objective, and with adaptations of other state-of-the-art methods originally proposed for other objectives, mainly makespan. All the methods have been implemented with and without the speed up procedure in order to test its effect. The results show that the proposed algorithms are very effective, outperforming the remaining methods of the comparison by a considerable margin.     

MODIFIED STEPPING-STONE METHOD AS A TEACHING AID FOR CAPACITATED TRANSPORTATION PROBLEMS

This paper extends the standard stepping-stone method to the case of capacitated transportation problems. The purpose is to offer an alternative to network-oriented or simplex-based methods (such as the out-of-kilter and upper-bounding techniques) often used in handling the capacitated transportation problem but generally beyond the scope of introductory decision sciences courses. The proposed procedure is based on the simple stepping-stone method and requires only a few modifications in the cost/assignment matrix and some alterations in the pivoting rules. As such, it is much easier to understand and apply than the above-mentioned solution algorithms. It therefore can serve as an effective tool for teaching capacitated transportation problems. Two numerical examples illustrate applications of the proposed method, procedures for sensitivity analysis, and comparisons with linear programming.