Water resources management under multi-parameter interactions: A factorial multi-stage stochastic programming approach

The paper proposes a factorial multi-stage stochastic programming (FMSP) approach to support water resources management under uncertainty. This approach was developed based on the conventional inexact multi-stage stochastic programming method. Five alternative inexact multi-stage stochastic programming algorithms in addition to the conventional algorithm were introduced and bundled to offer multiple decision options that reflect decision makers' perspectives and the complexities in system uncertainties. More importantly, factorial analysis, a multivariate inference method, was introduced into the modeling framework to analyze the potential interrelationships among a variety of uncertain parameters and their impacts on system performance. The proposed approach was applied to a water resources management case. The desired water-allocation schemes were obtained to assist in maximizing the total net benefit of the system. Multiple uncertain parameters and their interactions were examined, and those that had significant influences on system performance were identified. For example, the medium flow in the third planning period was the system objective's most influential factor. Any variation of this factor would significantly influence the acquisition of the total net benefit in the community. The significant interactions were also identified, such as the interaction between the agricultural sector's penalty and the medium flow in the third planning period. Through the analysis of multi-parameter interactions, the interrelationships among the uncertain parameters could be further revealed.     

Two-stage stochastic mixed-integer linear programming: The conditional scenario approach

In this paper we consider the two-stage stochastic mixed-integer linear programming problem with recourse, which we call the RP problem. A common way to approximate the RP problem, which is usually formulated in terms of scenarios, is to formulate the so-called Expected Value (EV) problem, which only considers the expectation of the random parameters of the RP problem. In this paper we introduce the Conditional Scenario (CS) problem which represents a midpoint between the RP and the EV problems regarding computational tractability and ability to deal with uncertainty. In the theoretical section we have analyzed some useful bounds related to the RP, EV and CS problems. In the numerical example here presented, the CS problem has outperformed both the EV problem in terms of solution quality, and the RP problem with the same number of scenarios as in the CS problem, in terms of solution time.     

A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming

This paper presents a hybrid genetic algorithm/mathematical programming heuristic for the n-job, m-machine flowshop problems with lot streaming. The number of sublots for each job and the size of sublots are directly addressed by the heuristic and setups may be sequence-dependent. A new aspect of the problem, the interleaving of sublots from different jobs in the processing sequence, is developed and addressed. Computational results from 12 randomly generated test sets of 24 problems each are presented.     

A multi-stage stochastic supply network design problem with financial decisions and risk management

In this paper, a multi-period supply chain network design problem is addressed. Several aspects of practical relevance are considered such as those related with the financial decisions that must be accounted for by a company managing a supply chain. The decisions to be made comprise the location of the facilities, the flow of commodities and the investments to make in alternative activities to those directly related with the supply chain design. Uncertainty is assumed for demand and interest rates, which is described by a set of scenarios. Therefore, for the entire planning horizon, a tree of scenarios is built. A target is set for the return on investment and the risk of falling below it is measured and accounted for. The service level is also measured and included in the objective function. The problem is formulated as a multi-stage stochastic mixed-integer linear programming problem. The goal is to maximize the total financial benefit. An alternative formulation which is based upon the paths in the scenario tree is also proposed. A methodology for measuring the value of the stochastic solution in this problem is discussed. Computational tests using randomly generated data are presented showing that the stochastic approach is worth considering in these types of problems.     

A hybrid genetic algorithm for train sequencing in the Korean railway

This article addresses the train-sequencing problem encountered in the Korean railway. It first presents a mixed integer programming model for the problem, in which the mileage must be balanced for each train route, while various field constraints must be satisfied, including overnight stay capacity and maintenance allocation restrictions. Then, it proposes a hybrid genetic algorithm as a solution approach to the problem. The proposed algorithm utilizes a modified elite group technique along with two heuristic procedures based on the mixed integer programming model. Finally, the proposed solution approach is tested with real-world data from the Korean railway. Numerical experiments under different conditions indicate that the proposed solution approach to the train-sequencing problem is promising.     

A note on the facility location problem with stochastic demands

In this research note that the single source capacitated facility location problem with general stochastic identically distributed demands is studied. The demands considered are independent and identically distributed random variables with arbitrary distribution. The unified a priori solution for the locations of facilities and for the allocation of customers to the operating facilities is found. This solution minimizes the objective function which is the sum of the fixed costs and the value of one of two different recourse functions. For each case the recourse function is given in closed form and a deterministic equivalent formulation of the model is presented. Some numerical examples are also given.     

A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand

This paper describes an employee scheduling system for retail outlets; it is a constraint-based system that exploits forecasts and stochastic techniques to generate schedules meeting the demand for sales personnel. Uncertain scenarios due to fluctuating demand are taken into account to develop a stochastic operational optimization of staffing levels. Mathematically, the problem is stated as a mixed-integer linear programming problem. Simulations with store data belonging to a major Swiss retailer show the effective performance of the proposed approach. The schedule quality is assessed through comparison with a deterministic scheduling package, which has been used at several outlets in Switzerland.     

A stochastic programming model for production planning of perishable products with postponement

This study addresses the production planning problem for perishable products, in which the cost and shortage of products are minimised subject to a set of constraints such as warehouse space, labour working time and machine time. Using the concept of postponement, the production process for perishable products is differentiated into two phases to better utilise the resources. A two-stage stochastic programming with recourse model is developed to determine the production loading plan with uncertain demand and parameters. A set of data from a toy company shows the benefits of the postponement strategy: these include lower total cost and higher utilisation of resources. The impact of unit shortage cost under different probability distribution of economic scenarios on the total cost is analyzed. Comparative analysis of solutions with and without postponement strategies is also performed.     

A hybrid biased random key genetic algorithm approach for the unit commitment problem

This work proposes a hybrid genetic algorithm (GA) to address the unit commitment (UC) problem. In the UC problem, the goal is to schedule a subset of a given group of electrical power generating units and also to determine their production output in order to meet energy demands at minimum cost. In addition, the solution must satisfy a set of technological and operational constraints. The algorithm developed is a hybrid biased random key genetic algorithm (HBRKGA). It uses random keys to encode the solutions and introduces bias both in the parent selection procedure and in the crossover strategy. To intensify the search close to good solutions, the GA is hybridized with local search. Tests have been performed on benchmark large-scale power systems. The computational results demonstrate that the HBRKGA is effective and efficient. In addition, it is also shown that it improves the solutions obtained by current state-of-the-art methodologies.     

A Bayesian approach to statistical inference in stochastic DEA

Stochastic DEA can deal effectively with noise in the non-parametric measurement of efficiency but unfortunately formal statistical inference on efficiency measures in not possible. In this paper, we provide a Bayesian approach to the problem organized around simulation techniques that allow for finite-sample inferences on efficiency scores. The new methods are applied to efficiency analysis of the Greek banking system for the period 1993–1999. The results show that the majority of the Greek banks operate close to best market practices.     

Two-sided assembly line balancing: A genetic algorithm approach

A two-sided assembly line balancing problem is typically found in plants producing large-sized high-volume products, e.g. buses and trucks. The features specific to the assembly line are described in this paper, which are associated with those of: (i) two-sided assembly lines; (ii) positional constraints; and (iii) balancing at the operational time. There exists a large amount of literature in the area of line balancing, whereby it has mostly dealt with one-sided assembly lines. A new genetic algorithm is developed to solve the problem, and its applicability and extensibility are discussed. A genetic encoding and decoding scheme, and genetic operators suitable for the problem are devised. This is particularly emphasized using problem-specific information to enhance the performance of the genetic algorithm (GA). The proposed GA has a strength that it is flexible in solving various types of assembly line balancing problems. An experiment is carried out to verify the performance of the GA, and the results are reported.     

The shift minimisation personnel task scheduling problem: A new hybrid approach and computational insights

Assigning scheduled tasks to a multi-skilled workforce is a known NP-complete problem with many applications in health care, services, logistics and manufacturing. Optimising the use and composition of costly and scarce resources such as staff has major implications on any organisation׳s health. The present paper introduces a new, versatile two-phase matheuristic approach to the shift minimisation personnel task scheduling problem, which considers assigning tasks to a set of multi-skilled employees, whose working times have been determined beforehand. Computational results show that the new hybrid method is capable of finding, for the first time, optimal solutions for all benchmark instances from the literature, in very limited computation time. The influence of a set of problem instance features on the performance of different algorithms is investigated in order to discover what makes particular problem instances harder than others. These insights are useful when deciding on organisational policies to better manage various operational aspects related to workforce. The empirical hardness results enable to generate hard problem instances. A set of new challenging instances is now available to the academic community.     

The falling tide algorithm: A new multi-objective approach for complex workforce scheduling

We present a hybrid approach of goal programming and meta-heuristic search to find compromise solutions for a difficult employee scheduling problem, i.e. nurse rostering with many hard and soft constraints. By employing a goal programming model with different parameter settings in its objective function, we can easily obtain a coarse solution where only the system constraints (i.e. hard constraints) are satisfied and an ideal objective-value vector where each single goal (i.e. each soft constraint) reaches its optimal value. The coarse solution is generally unusable in practise, but it can act as an initial point for the subsequent meta-heuristic search to speed up the convergence. Also, the ideal objective-value vector is, of course, usually unachievable, but it can help a multi-criteria search method (i.e. compromise programming) to evaluate the fitness of obtained solutions more efficiently. By incorporating three distance metrics with changing weight vectors, we propose a new time-predefined meta-heuristic approach, which we call the falling tide algorithm, and apply it under a multi-objective framework to find various compromise solutions. By this approach, not only can we achieve a trade off between the computational time and the solution quality, but also we can achieve a trade off between the conflicting objectives to enable better decision-making.     

A hybrid approach to sequencing jobs using heuristic rules and neural networks

A hybrid approach to solve job sequencing problems using heuristic rules and artificial neural networks is proposed. The problem is to find a job sequence for a single machine that minimizes the total weighted tardiness of the jobs. Two different cases are considered: (1) when there are no setups, and (2) when there are sequence-dependent setup times. So far, successful heuristic rules for these cases are: apparent tardiness cost (ATC) rule proposed by Vepsalainen and Morton for the former case, and an extended version of the ATC rule (ATCS) proposed by Lee, Bhaskaran, and Pinedo for the latter. Both approaches utilize some look-ahead parameters for calculating the priority index of each job. As reported by Bhaskaran and Pinedo, the proper value of the look-ahead parameter depends upon certain problem characteristics, such as due-date tightness and due-date range. Thus, an obvious extension of the ATC or the ATCS rule is to adjust the parameter values depending upon the problem characteristics: this is known to be a difficult task. In this paper, we propose an application of a neural network as a tool to ‘predict’ proper values of the look-ahead parameters. Our computational tests show that the proposed hybrid approach outperforms both the ATC rule with a fixed parameter value and the ATCS using the heuristic curve-fitting method.     

A hybrid genetic algorithm for the batch sequencing problem on identical parallel machines

The batch sequencing problem (BSP) has been the focus of much research thanks to its practical applicability and NP-hard nature. This study aims to solve an extension of the problem from single machine case to parallel machine case. A dispatching rule called the EDD (Earliest Due Date)-Greedy heuristic and a pure genetic algorithm (GA) are proposed, and then combine them through an insertion method called the Gene Bank Strategy. Several test cases of up to 12 machines and 60 jobs are randomly generated and solved. Those experiments show that the introduced hybrid GA can provide far better results than its two component algorithms that can also independently solve the problem.     

Multi-horizon Markowitz portfolio performance appraisals: A general approach

This article extends the analysis of multi-horizon mean-variance portfolio analysis in the Morey and Morey [Mutual fund performance appraisals: a multi-horizon perspective with endogenous benchmarking. Omega 1999;27:241–58] article in several ways. First, instead of either proportionally contracting risk dimensions or proportionally expanding return dimensions, a more general efficiency measure simultaneously attempts to reduce risk and to expand return over all time periods. Second, a duality relation is established between this generalized multi-horizon efficiency measure and an indirect mean-variance utility function, underscoring the natural interpretation of this generalized efficiency measure in terms of investor's preferences. Furthermore, the need to properly apply time discounting in multi-horizon mean-variance portfolio problems is argued for. An empirical illustration based on the original mutual fund data set in Morey and Morey [Mutual fund performance appraisals: a multi-horizon perspective with endogenous benchmarking. Omega 1999;27:241–58] is added to contrast the new and the original approaches.     

A genetic algorithm approach to developing the multi-echelon reverse logistics network for product returns

Traditionally, product returns have been viewed as an unavoidable cost of doing business, forfeiting any chance of cost savings. As cost pressures continue to mount in this era of economic downturns, a growing number of firms have begun to explore the possibility of managing product returns in a more cost-efficient manner. However, few studies have addressed the problem of determining the number and location of centralized return centers (i.e., reverse consolidation points) where returned products from retailers or end-customers were collected, sorted, and consolidated into a large shipment destined for manufacturers’ or distributors’ repair facilities. To fill the void in such a line of research, this paper proposes a nonlinear mixed-integer programming model and a genetic algorithm that can solve the reverse logistics problem involving product returns. The usefulness of the proposed model and algorithm was validated by its application to an illustrative example dealing with products returned from online sales.