A lot-sizing and scheduling model for multi-stage flow lines with zero lead times

We present a new model formulation for lot-sizing and scheduling of multi-stage flow lines which works without a fixed lead-time offset and still guarantees a feasible material flow. In the literature, multi-stage lot-sizing model formulations often use a fixed lead time offset of one period leading to increased planned lead times. Computational tests have shown that the total costs resulting from our new model formulation are at least 10% lower. Furthermore, we present a solution approach based on Fix-and-Relax and Fix-and-Optimize. Numerical results show that this solution approach generates high-quality solutions in moderate computational time.     

Effects of regulatory delays and uncertainty on pricing decisions

In this paper we introduce a simple decision rule that a single product firm may use for filing for a price change to offset variations of the marginal cost. We consider a regulatory body whose response to the price change request involves a time delay with an exponential distribution. Two possibilities regarding the response of the regulatory body are considered. In one case it is assumed to be a binary approval process in which the rate adjustment is either approved in its entirety or rejected. In the second case we consider a partial approval process with a more general distribution. Decision rules for each case are developed. Finally we derive a multi-stage decision rule in which filing decisions are continuously updated based on temporal variations of the cost function. The multi-stage pricing decision model assumes that marginal cost escalation satisfies a Markovian jump process.This work was completed while the authors were with Bell Laboratories, USA.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

Detecting Embedded Networks in LP Using GUB Structures and Independent Set Algorithms

In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two different approaches; the first is based on the notion of Markowitz merit count and the second exploits independent sets in the corresponding graphs. Our computational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorithms.     

A mixed R&D projects and securities portfolio selection model

The business environment is full of uncertainty. Allocating the wealth among various asset classes may lower the risk of overall portfolio and increase the potential for more benefit over the long term. In this paper, we propose a mixed single-stage R&D projects and multi-stage securities portfolio selection model. Specifically, we present a bi-objective mixed-integer stochastic programming model. Moreover, we use semi-absolute deviation risk functions to measure the risk of mixed asset portfolio. Based on the idea of moments approximation method via linear programming, we propose a scenario generation approach for the mixed single-stage R&D projects and multi-stage securities portfolio selection problem. The bi-objective mixed-integer stochastic programming problem can be solved by transforming it into a single objective mixed-integer stochastic programming problem. A numerical example is given to illustrate the behavior of the proposed mixed single stage R&D projects and multi-stage securities portfolio selection model.     

Tariff concessions in production sourcing

In this paper, we study a multi-stage production sourcing problem where tariff concessions can be exploited at the firm level using free trade agreements between countries. To solve the problem, an algorithm which embeds a very large-scale neighborhood (VSLN) search into a simulated annealing framework is developed. A numerical study is conducted to verify the effectiveness of the solution approach.     

Time Consistent Dynamic Risk Measures

We introduce the time-consistency concept that is inspired by the so-called “principle of optimality” of dynamic programming and demonstrate – via an example – that the conditional value-at-risk (CVaR) need not be time-consistent in a multi-stage case. Then, we give the formulation of the target-percentile risk measure which is time-consistent and hence more suitable in the multi-stage investment context. Finally, we also generalize the value-at-risk and CVaR to multi-stage risk measures based on the theory and structure of the target-percentile risk measure.     

Optimal yield improvement in multi-stage manufacturing systems

Multi-stage manufacturing systems producing some non-conforming items still present economic operational problems. A decomposition approach is presented to model multi-stage manufacturing systems with inspection stations. The concept of process improvement as developed is expressed in terms of a step-wise yield improvement path, along which the most profitable improvement stages are identified. It is shown that the model selects an ever increasing set of stations to improve, once the profitability of the best station-candidates reaches a level similar to that of some other station-candidates. The approach also extends the concept of an event (naturally connected to a time frame) by relating it to a dynamic profitability frame. From an operational perspective the findings suggest that a quality improvement project, initially undertaken by a cross-functional team at a multi-stage level, may be continued through concurrent projects, focusing on improving the quality of specific manufacturing stages. The research results may be directly extended to include integrated economic improvement-inspection decisions.     

Measurement and optimization of responsiveness in supply chain networks with queueing structures

In this paper we consider supply chains with multiple stages of serial or network structure. The supply chains are endogenous in the sense that they involve queues because each order’s lead-time is dependent on the orders already in the system. We define supply chain responsiveness as the probability of fulfilling customer orders within a promised lead-time and study the problems of measuring and optimizing supply chain responsiveness using queueing network models. We first consider a single-server multi-stage serial supply chain and find a closed form expression for the fulfilment time distribution. For the multi-server multi-stage problem, the closed form evaluation of the fulfilment time distribution becomes intractable due to the dependency of the lead-times in different stages. We circumvent this difficulty by proposing a novel FCFS discipline which enables a closed-form analysis. For the multi-server multi-stage Jackson-type supply chain network, to enable analysis, we convert the system into an equivalent single server single stage system with state-dependent rates. For each case, we present detailed numerical examples for both measurement and the optimization of supply chain responsiveness.     

An analytical method for cost analysis in multi-stage supply chains: A stochastic network model approach

This paper studies the cost distribution characteristics in multi-stage supply chain networks. Based on the graphical evaluation and review technique, we propose a novel stochastic network mathematical model for cost distribution analysis in multi-stage supply chain networks. Further, to investigate the effects of cost components, including the procurement costs, inventory costs, shortage costs, production costs and transportation costs of supply chain members, on the total supply chain operation cost, we propose the concept of cost sensitivity and provide corresponding algorithms based on the proposed stochastic network model. Then the model is extended to analyze the cost performance of supply chain robustness under different order compensation ability scenarios and the corresponding algorithms are developed. Simulation experiment shows the effectiveness and flexibility of the proposed model, and also promotes a better understanding of the model approach and its managerial implications in cost management of supply chains.     

Task scheduling with and without communication delays: A unified approach

The problem of scheduling directed acyclic task graphs on an unbounded number of processors is considered. We present a single algorithm which is applicable to several special cases, thus effecting a unified approach to task scheduling independent of the task graph. We start by considering multi-stage dags and present an algorithm that computes a schedule in O(Nq log q) time, where N is the number of stages, and q is the maximum number of edges between any two stages of the graph. We show that the schedule produced by the algorithm is optimal when: (i) all communication delays are zero or, (ii) the precedence graph is an in-tree or an out-tree and communication times are small or, (iii) the task graph is densely connected and communication costs and processing costs are unity. For multi-stage dags with small communication times we show that the makespan of the schedule generated by our algorithm is less than twice that of the optimal. We also bound the makespan for the case when communication times are arbitrary. We then show how the algorithm may be applied to schedule arbitrary dags and derive the performance bounds for this case. Finally, we present the results of tests we carried out with randomly generated task graphs. These seem to indicate that, on the average, the algorithm performs substantially better than theoretical worst case predictions.     

Bounding multi-stage stochastic programs from above

The purpose of this paper is to present general approaches for bounding some multi-stage stochastic programs from above. The results are based on restricting the solution set, such that the remaining multi-stage stochastic program is easy to solve. An example where the methods can be applied is presented.Supported in part by NATO Collaborative Research Grant No. 0785/87.     

A multi-stage financial hedging approach for the procurement of manufacturing materials

This paper addresses the problem of mitigating procurement risk that arises from volatile commodity prices by proposing a hedging strategy within a multi-stage time frame. The proposed multi-stage hedging strategy requires a commodity futures position to be correctly initialised and rebalanced with adequate volumes of short/long positions, so as to reduce the volatility in the total procurement cost that would otherwise be generated by varying commodity spot prices. The novelty in the approach is the introduction of the rebalancing of commodity futures position at defined intermediate stages. To obtain an efficient or near optimal multi-stage hedging strategy, a discrete-time stochastic control model (DSCM) is developed. Numerical experiments and Monte Carlo simulation are used to show that the proposed multi-stage hedging strategy compares favourably with the minimal-variance hedge and the one-stage hedge. A close-form optimal solution is also presented for the case when procurement volume and price are independent.     

基于期货、期权与现货组合的采购决策和风险控制研究

针对企业大宗原材料采购容易受到上游价格和下游需求的不确定性影响这一问题,本文以制造商(或分销商)多阶段采购决策为研究对象,建立了包含期货、期权和现货三种采购方式的多阶段组合采购决策模型,以此来应对采购中的价格风险和库存风险.结合某钢构厂原材料采购问题,采用蒙特卡罗仿真方法进行求解.通过对比组合方式与现货方式的求解结果,证明了组合采购方式能够在各种采购环境下为采购商带来更高更稳定的利润,所提出的组合采购决策模型能够有效的规避风险.     

乳制品安全监管中的多阶段进化博弈分析

乳制品安全风险存在于生产与组织的多个阶段。在各个阶段中,政府监管部门虽统一监管,但由于采取的监管策略不同,使其与厂商之间的博弈情景存在差异,这将影响风险控制的成果。为探索多阶段监管的有效途径,找寻降低监管风险的方法,本文分析了乳制品安全监管中的多阶段进化博弈。首先阐述多阶段厂商监管的相关组织关系,构建进化博弈模型;其次基于模型进行进化博弈分析,分别得出了不同监管情景下的演化稳定策略,识别了多阶段策略选择的稳定条件;最后归纳了进化博弈分析结果,通过模拟仿真以及案例分析加以验证。     

Stochastic single machine scheduling problem as a multi-stage dynamic random decision process

In this work, we study a stochastic single machine scheduling problem in which the features of learning effect on processing times, sequence-dependent setup times, and machine configuration selection are considered simultaneously. More precisely, the machine works under a set of configurations and requires stochastic sequence-dependent setup times to switch from one configuration to another. Also, the stochastic processing time of a job is a function of its position and the machine configuration. The objective is to find the sequence of jobs and choose a configuration to process each job to minimize the makespan. We first show that the proposed problem can be formulated through two-stage and multi-stage Stochastic Programming models, which are challenging from the computational point of view. Then, by looking at the problem as a multi-stage dynamic random decision process, a new deterministic approximation-based formulation is developed. The method first derives a mixed-integer non-linear model based on the concept of accessibility to all possible and available alternatives at each stage of the decision-making process. Then, to efficiently solve the problem, a new accessibility measure is defined to convert the model into the search of a shortest path throughout the stages. Extensive computational experiments are carried out on various sets of instances. We discuss and compare the results found by the resolution of plain stochastic models with those obtained by the deterministic approximation approach. Our approximation shows excellent performances both in terms of solution accuracy and computational time.

     

多阶段应急决策的方案链选择方法

针对多阶段不同情景下多指标多任务的应急决策问题,提出了一种方案链选择方法。在该方法中,首先给出了决策方案链的概念,并对多阶段多指标多任务的应急决策问题进行了描述;然后根据相邻阶段的子方案之间的相容性,构建了相容性关系矩阵;进一步地,在考虑相邻阶段子方案之间相容性的情形下,以各阶段的子方案的综合评价值最大为目标,建立了应急决策的方案链选择的优化模型。通过求解模型,得到应急决策的最优方案链。最后,通过一个算例说明了该方法的可行性和有效性。     

Analysis of a class of dynamic programming models for multi-stage uncertain systems

Uncertainty theory is a new branch of mathematics concerned with the analysis of subjective indeterminacy. This paper deals with the optimal control problem for a multi-stage dynamic system in an indeterminate environment. Firstly, we formulate a practical uncertain control model based on the critical value criterion and present recursion equations for this model based on Bellman’s Principle. A special linear model is shown to illustrate how the recursion equations operate to obtain the analytical solution. Furthermore, we demonstrate a hybrid intelligent algorithm to evaluate and approximate the optimal solutions of more general cases. Finally, a discrete version of the production-inventory problem is discussed and numerically analyzed to illuminate the effectiveness of the methodology.     

Multi-stage portfolio selection problem with dynamic stochastic dominance constraints

We study the multi-stage portfolio selection problem where the utility function of an investor is ambiguous. The ambiguity is characterized by dynamic stochastic dominance constraints, which are able to capture the dynamics of the random return sequence during the investment process. We propose a multi-stage dynamic stochastic dominance constrained portfolio selection model, and use a mixed normal distribution with time-varying weights and the K-means clustering technique to generate a scenario tree for the transformation of the proposed model. Based on the scenario tree representation, we derive two linear programming approximation problems, using the sampling approach or the duality theory, which provide an upper bound approximation and a lower bound approximation for the original nonconvex problem. The upper bound is asymptotically tight with infinitely many samples. Numerical results illustrate the practicality and efficiency of the proposed new model and solution techniques.

     

Multi-attribute decision making based on a novel IF point operator

Intuitionistic fuzzy (IF) point operators transform an intuitionistic fuzzy set to a fuzzy set, or an intuitionistic fuzzy set with a smaller degree of hesitance. The purpose of which is to empower the operations of intuitionistic fuzzy sets with traditional fuzzy set methodologies. In the present paper, a new IF point operator is proposed. Different from the existing IF point operators, the new approach includes two parametric functions with respect to the number of iterations. It is proved that the newly proposed method could be degenerated to the traditional IF point operators. Meanwhile, the new IF point operator can extend our horizons in the exploration of the relationship between fuzzy sets and intuitionistic fuzzy sets. Specifically, a special case of the new IF point operator would be entitled as the memoryless multi-stage voting method, with which the decision makers are assumed to be affected only by the outcomes of the latest round of voting. It is proved that the memoryless multi-stage voting method converges to the limit produced by the infinite number of iterations much faster than the traditional voting method. Furthermore, a numerical example is employed to demonstrate the validity and performance of the memoryless multi-stage voting approach.