Optimization models and a GA-based algorithm for stochastic time-cost trade-off problem

In real-life projects, both the trade-off between the project cost and the project completion time, and the uncertainty of the environment are considerable aspects for decision-makers. However, the research on the time-cost trade-off problem seldom concerns stochastic environments. Besides, optimizing the expected value of the objective is the exclusive decision-making criterion in the existing models for the stochastic time-cost trade-off problem. In this paper, two newly developed alternative stochastic time-cost trade-off models are proposed, in which the philosophies of chance-constrained programming and dependent-chance programming are adopted for decision-making. In addition, a hybrid intelligent algorithm integrating stochastic simulations and genetic algorithm is designed to search the quasi-optimal schedules under different decision-making criteria. The goal of the paper is to reveal how to obtain the optimal balance of the project completion time and the project cost in stochastic environments.     

Experimental evaluation of simulated annealing algorithms for the time-cost trade-off problem

This paper evaluates variants of a simulated annealing algorithm which solve the total cost minimization problem in activity networks in the case that discrete time-cost execution modes are allowed on the project activities. This problem is a special case of the well known discrete time-cost trade-off problem (DTCTP). Based on a sample of randomly generated activity networks, formal tests of statistical significance are utilized to test both the quality of solutions and the time efficiency of algorithms versus problem factors. A procedure issued from the extreme values statistics is also applied on problem instances in order to determine, on the one hand, the confidence interval estimate of the optimum solution for each algorithm and, on the other hand, when to stop the running of an algorithm.     

New models for shortest path problem with fuzzy arc lengths

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

New MILP models for the permutation flowshop problem

Two new mixed-integer linear programming (MILP) models for the regular permutation flowshop problem, called TBA and TS3, are derived using a combination of JAML (job-adjacency, machine-linkage) diagrams and variable substitution techniques. These new models are then compared to the incumbent best MILP models (Wilson, WST2, and TS2) for this problem found in the flowshop sequencing literature. We define the term best to mean that a particular model or set of models can solve a common set of test flowshop problems in significantly less time than other competing models. In other words, the two new MILP models (TBA and TS3) become the challengers to the current incumbent best models (Wilson, WST2, TS2.). Both new models are shown to require less time, on average, than the current best models for solving this set of problems; and the TS3 model is shown to solve these problems in statistically significantly less time than the other four models combined.     

New insights on integer-programming models for the kidney exchange problem

In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs.     

New models and algorithms for the cyclic inventory routing problem

This is a summary of the author’s PhD thesis supervised by El-Houssaine Aghezzaf and defended on 4 December 2006 at the Universiteit Gent. The thesis is written in English and is electronically available from http://ir18.ugent.be/birger.raa/. This work studies the problem of finding optimal three-way cost trade-offs between vehicle fleet costs, distribution costs and holding costs in the cyclic replenishment of a set of customers with constant demand rates from a single depot.      

New computational results on the discrete time/cost trade-off problem in project networks

We describe a new exact procedure for the discrete time/cost trade-off problem in deterministic activity-on-the-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single resource (money) committed to it. The objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. The procedure uses a horizon-varying approach based on the iterative optimal solution of the problem of minimising the sum of the resource use over all activities subject to the activity precedence constraints and a project deadline. This optimal solution is derived using a branch-and-bound procedure which computes lower bounds by making convex piecewise linear underestimations of the discrete time/cost trade-off curves of the activities to be used as input for an adapted version of the Fulkerson labelling algorithm for the linear time/cost trade-off problem. Branching involves the selection of an activity in order to partition its set of execution modes into two subsets which are used to derive improved convex piecewise linear underestimations. The procedure has been programmed in Visual C ++ under Windows NT and has been validated using a factorial experiment on a large set of randomly generated problem instances.     

Time-cost trade-off analysis of project networks in fuzzy environments

This paper proposes a novel approach for time-cost trade-off analysis of a project network in fuzzy environments. Different from the results of previous studies, in this paper the membership function of the fuzzy minimum total crash cost is constructed based on Zadeh’s extension principle and fuzzy solutions are provided. A pair of two-level mathematical programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy minimum total crash cost at α. By enumerating different values of α, the membership function of the fuzzy minimum total crash cost is constructed, and the corresponding optimal activity time for each activity is also obtained at the same time. An example of time-cost trade-off problem with several fuzzy parameters is solved successfully to demonstrate the validity of the proposed approach. Since the minimum total crash cost is expressed by a membership function rather than by a crisp value, the fuzziness of parameters is conserved completely, and more information is provided for time-cost trade-off analysis in project management. The proposed approach also can be applied to time-cost trade-off problems with other characteristics.     

Mean-semivariance models for fuzzy portfolio selection

This paper discusses portfolio selection problem in fuzzy environment. In the paper, semivariance is originally presented for fuzzy variable, and three properties of the semivariance are proven. Based on the concept of semivariance of fuzzy variable, two fuzzy mean-semivariance models are proposed. To solve the new models in general cases, a fuzzy simulation based genetic algorithm is presented in the paper. In addition, two numerical examples are also presented to illustrate the modelling idea and the effectiveness of the designed algorithm.     

Concepts and fuzzy models for behavior-based robotics

In this paper, we propose a modeling paradigm that uses fuzzy sets to represent concepts on which control modules of a behavior-based autonomous robot operate. The primitives defined in the modeling paradigm are expressive enough to represent the knowledge needed by planning, coordination, and reactive control of a multi-robot control system. At the same time, it provides a well-founded tool to represent in a compact way the data interpretations needed to reason effectively about what is happening in the world and what is desired to happen. This modeling paradigm makes the design of behavior, planning, and coordination modules easy, since its primitives are simple and expressive. Moreover, it provides a sound framework to deal with uncertainty in sensing and world modeling.     

Optimal procedures for the discrete time/cost trade-off problem in project networks

We describe two algorithms, based on dynamic programming logic, for optimally solving the discrete time/cost trade-off problem (DTCTP) in deterministic activity-on-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single nonrenewable resource committed to it. The first algorithm is based on a procedure proposed by Bein, Kamburowski and Stallmann for finding the minimal number of reductions necessary to transform a general network to a series-parallel network. The second algorithm minimizes the estimated number of possibilities that need to be considered during the solution procedure. Both procedures have been programmed in C and tested on a large set of representative networks to give a good indication of their performance, and indicate the circumstances in which either algorithm performs best.     

Robust scheduling and robustness measures for the discrete time/cost trade-off problem

Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.     

An exact algorithm for the fuzzy p-median problem

In this paper we propose a fuzzy version of the classical p-median problem. We consider a fuzzy set of constraints so that the decision-maker will be able to take into account solutions which provide significantly lower costs by leaving a part of the demand uncovered. We propose an algorithm for solving the problem which is based on Hakimi's works and we compare the crisp and the fuzzy approach by means of an example.     

An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method.     

Doppler tomography problem for vortex models

We consider a special field model in the two-dimensional Doppler tomography problem and prove its unique solvability. A numerical method is proposed for solving the problem and some examples are shown demonstrating its efficiency. __________ Translated from Prikladnaya Matematika i Informatika, No. 22, pp. 12–30, 2005.     

Three fuzzy goal programming models for index portfolios

Studies show that most actively managed mutual funds struggle to beat the market, driving an increase in the popularity of index investing. Index investing instruments, including index funds and Exchange-traded Funds, aim to track market performance. This study pursues both tracking error minimization and excess return maximization, two conflicting objectives, to construct an index portfolio. In the real-world financial environment, the desires and expectations of decision makers are generally imprecise. This study applies fuzzy theory to deal with imprecise objectives. This study represents minimizing tracking error and maximizing excess return as ‘fuzzy goals’ to improve traditional goal programming, which is suitable for handling multiple conflicting objectives, but subject to establishing crisp goals. Three fuzzy goal programming (FGP) models that track indexes are compared and discussed, and the results show that through certain membership functions and tracking models, an index tracking portfolio with a tracking error lower than the 0050 index fund, and a similar excess return to 0050 index fund can be constructed using additive type FGP. max-min type FGP underperforms the additive type FGP in index fund construction.     

On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.     

New models for the robust shortest path problem: complexity, resolution and generalization

In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients.     

Fuzzy identification problem for continuous extremal fuzzy dynamic system

This work deals with the problems of the Continuous Extremal Fuzzy Dynamic System (CEFDS) optimization and briefly discusses the results developed by Sirbiladze (Int J Gen Syst 34(2):107–138, 2005a; 34(2):139–167, 2005b; 34(2):169–198, 2005c; 35(4):435–459, 2006a; 35(5):529–554, 2006b; 36(1): 19–58, 2007; New Math Nat Comput 4(1):41–60, 2008a; Mat Zametki, 83(3):439–460, 2008b). The basic properties of extended extremal fuzzy measures and Sugeno’s type integrals are considered and several variants of their representation are given. Values of extended extremal conditional fuzzy measures are defined as a levels of expert knowledge reflections of CEFDS states in the fuzzy time intervals. The notions of extremal fuzzy time moments and intervals are introduced and their monotone algebraic structures that form the most important part of the fuzzy instrument of modeling extremal fuzzy dynamic systems are discussed. A new approach in modeling of CEFDS is developed. Applying the results of Sirbiladze (Int J Gen Syst 34(2) 107–138, 2005a; 34(2):139–167, 2005b), fuzzy processes with possibilistic uncertainty, the source of which are expert knowledge reflections on the states on CEFDS in extremal fuzzy time intervals, are constructed (Sirbiladze in Int J Gen Syst 34(2):169–198, 2005c). The dynamics of CEFDS’s is described. Questions of the ergodicity of CEFDS are considered. A fuzzy-integral representation of a continuous extremal fuzzy process is given. Based on the fuzzy-integral model, a method and an algorithm are developed for identifying the transition operator of CEFDS. The CEFDS transition operator is restored by means of expert data with possibilistic uncertainty, the source of which is expert knowledge reflections on the states of CEFDS in the extremal fuzzy time intervals. The regularization condition for obtaining quasi-optimal estimator of the transition operator is represented by the theorems. The corresponding calculating algorithm is provided. The results obtained are illustrated by an example in the case of a finite set of CEFDS states.