Analysis of critical paths in a project network with fuzzy activity times

This paper proposes an approach to critical path analysis for a project network with activity times being fuzzy numbers, in that the membership function of the fuzzy total duration time is constructed. The basic idea is based on the extension principle and linear programming formulation. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy total duration time at α. By enumerating different values of α, the membership function of the fuzzy total duration time is constructed, and the fuzzy critical paths are identified at the same time. Moreover, by applying the Yager ranking method, definitions of the most critical path and the relative degree of criticality of paths are developed; and these definitions are theoretically sound and easy to use in practice. Two examples with activity times being fuzzy numbers of L-R and L-L types discussed in previous studies are solved successfully to demonstrate the validity of the proposed approach. Since the total duration time is completely expressed by a membership function rather than by a crisp value, the fuzziness of activity times is conserved completely, and more information is provided for critical path analysis.     

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.     

Solving fuzzy queueing decision problems via a parametric mixed integer nonlinear programming method

This paper proposes a mathematical programming method to construct the membership functions of the fuzzy objective value of the cost-based queueing decision problem with the cost coefficients and the arrival rate being fuzzy numbers. On the basis of Zadeh’s extension principle, three pairs of mixed integer nonlinear programs (MINLP) parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimal expected total cost per unit time at α, through which the membership function of the minimal expected total cost per unit time of the fuzzy objective value is constructed. To provide a suitable optimal service rate for designing queueing systems, the Yager’s ranking index method is adopted. Two numerical examples are solved successfully to demonstrate the validity of the proposed method. Since the objective value is completely expressed by a membership function rather than by a crisp value, it conserves the fuzziness of the input information, thus more information is provided for designing queueing systems. The successful extension of queueing decision models to fuzzy environments permits queueing decision models to have wider applications in practice.     

A bulk arrival queueing model with fuzzy parameters and varying batch sizes

This paper develops a nonlinear programming approach to derive the membership functions of the steady-state performance measures in bulk arrival queueing systems with varying batch sizes, in that the arrival rate and service rate are fuzzy numbers. The basic idea is based on Zadeh’s extension principle. Two pairs of mixed integer nonlinear programs (MINLP) with binary variables are formulated to calculate the upper and lower bounds of the system performance measure at possibility level α. From different values of α, the membership function of the system performance measure is constructed. For practice use, the defuzzification of performance measures is also provided via Yager ranking index. To demonstrate the validity of the proposed method, a numerical example is solved successfully.     

Solving multi-level multi-objective linear programming problems through fuzzy goal programming approach

In this paper, two new algorithms are presented to solve multi-level multi-objective linear programming (ML-MOLP) problems through the fuzzy goal programming (FGP) approach. The membership functions for the defined fuzzy goals of all objective functions at all levels are developed in the model formulation of the problem; so also are the membership functions for vectors of fuzzy goals of the decision variables, controlled by decision makers at the top levels. Then the fuzzy goal programming approach is used to achieve the highest degree of each of the membership goals by minimizing their deviational variables and thereby obtain the most satisfactory solution for all decision makers.     

A deteriorating multi-item inventory model with fuzzy costs and resources based on two different defuzzification techniques

Normally inventory models of deteriorating items, such as food products, vegetables, etc. involve imprecise parameters, like imprecise inventory costs, fuzzy storage area, fuzzy budget allocation, etc. In this paper, we aim to provide two defuzzification techniques for two fuzzy inventory models using (i) extension principle and duality theory of non-linear programming and (ii) interval arithmetic. On the basis of Zadeh’s extension principle, two non-linear programs parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimum average cost at α-level, through which the membership function of the objective function is constructed. In interval arithmetic technique the interval objective function has been transformed into an equivalent deterministic multi-objective problem defined by the left and right limits of the interval. This formulation corresponds to the possibility level, α = 0.5. Finally, the multi-objective problem is solved by a multi-objective genetic algorithm (MOGA). The model has been illustrated through a numerical example and solved for different values of possibility level, α through extension principle and for α = 0.5 via MOGA. As a particular case, the results have been obtained for the inventory model without deterioration. Results from two methods for α = 0.5 are compared.     

Parametric nonlinear programming approach to fuzzy queues with bulk service

This paper proposes a procedure to construct the membership functions of the performance measures in bulk service queuing systems with the arrival rate and service rate are fuzzy numbers. The basic idea is to transform a fuzzy queue with bulk service to a family of conventional crisp queues with bulk service by applying the α-cut approach. On the basis of α-cut representation and the extension principle, a pair of parametric nonlinear programs is formulated to describe that family of crisp bulk service queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, two fuzzy queues often encountered in transportation management are exemplified. Since the performance measures are expressed by membership functions rather than by crisp values, they completely conserve the fuzziness of input information when some data of bulk-service queuing systems are ambiguous. Thus the proposed approach for vague systems can represent the system more accurately, and more information is provided for designing queuing systems in real life. By extending to fuzzy environment, the bulk service queuing models would have wider applications.     

Fuzzy profit measures for a fuzzy economic order quantity model

Changing economic conditions make the selling price and demand quantity more and more uncertain in the market. The conventional inventory models determine the selling price and order quantity for a retailer’s maximal profit with exactly known parameters. This paper develops a solution method to derive the fuzzy profit of the inventory model when the demand quantity and unit cost are fuzzy numbers. Since the parameters contained in the inventory model are fuzzy, the profit value calculated from the model should be fuzzy as well. Based on the extension principle, the fuzzy inventory problem is transformed into a pair of two-level mathematical programs to derive the upper bound and lower bound of the fuzzy profit at possibility level α. According to the duality theorem of geometric programming, the pair of two-level mathematical programs is transformed into a pair of conventional geometric programs to solve. By enumerating different α values, the upper bound and lower bound of the fuzzy profit are collected to approximate the membership function. Since the profit of the inventory problem is expressed by the membership function rather than by a crisp value, more information is provided for making decisions.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

Measuring performances of multiple-channel queueing systems with imprecise data: a membership function approach

This paper proposes a mixed integer nonlinear programming (MINLP) approach to measure the system performances of multiple-channel queueing models with imprecise data. The main idea is to transform a multiple-channel queue with imprecise data to a family of conventional crisp multiple-channel queues by applying the α-cut approach in fuzzy theory. On the basis of α-cut representation and the extension principle, two pairs of parametric MINLP are formulated to describe the family of crisp multiple-channel queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, a real-world case of multiple-channel fuzzy queue is investigated successfully. Since the performance measures are expressed by membership functions rather than by crisp values, the fuzziness of input information is completed conserved. Thus, the results obtained from the proposed approach can represent the system more accurately, and more information is provided for system design in practice.     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

A knapsack intersection hierarchy

We introduce a knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs. In level t of the hierarchy, all valid cuts are added for the integer hull of the intersection of all t-row relaxations. This model captures the maximum possible strength of t-row cuts, an approach often used by solvers for small t. We investigate the integrality gap of the strengthened formulations on the all-or-nothing flow problem in trees (also called unsplittable flow on trees).     

Application of Fuzzy Linear Programming in Production Planning

In this paper, a new fuzzy linear programming based methodology using a specific membership function, named as modified logistic membership function is proposed. The modified logistic membership function is first formulated and its flexibility in taking up vagueness in parameters is established by an analytical approach. This membership function is tested for its useful performance through an illustrative example by employing fuzzy linear programming. The developed methodology of FLP has provided a confidence in applying to real life industrial production planning problem. This approach of solving industrial production planning problem can have feed back within the decision maker, the implementer and the analyst. In such case this approach can be called as IFLP (Interactive Fuzzy Linear Programming). There is a possibility to design the self organizing of fuzzy system for the mix products selection problem in order to find the satisfactory solution. The decision maker, the analyst and the implementer can incorporate their knowledge and experience to obtain the best outcome.     

军械物资供应系统中的多目标运输问题

建立了军械物资运输问题的模糊多目标线性规划模型，运用一种解模糊函数和一种基于线性隶属函数的模糊规划算法求其调和解。方法简便、有效，可为部队军械物资的运输供应高效化提供科学依据。     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

Fuzzy variables

The purpose of this study is to explore a possible axiomatic framework from which a rigorous theory of fuzziness may be constructed. The approach we propose is analogous to the sample space concept of probability theory. A fuzzy variable is a mapping from an abstract space (called the pattern space) onto the real line. The membership function is obtained as the extension of a special type of capacity (called a scale) from the pattern space to the real line via the fuzzy variable. In essence we are proposing an entirely new definition of a fuzzy set on the line as a mapping to the line rather than on the line. The current definition of a transformation of a fuzzy set is obtained as a derived result of our model. In addition, we derive the membership function of sums and products of fuzzy sets and present an example which reinforces the credibility of our approach.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.     

Solving a multiobjective possibilistic problem through compromise programming

Real decision problems usually consider several objectives that have parameters which are often given by the decision maker in an imprecise way. It is possible to handle these kinds of problems through multiple criteria models in terms of possibility theory.Here we propose a method for solving these kinds of models through a fuzzy compromise programming approach.To formulate a fuzzy compromise programming problem from a possibilistic multiobjective linear programming problem the fuzzy ideal solution concept is introduced. This concept is based on soft preference and indifference relationships and on canonical representation of fuzzy numbers by means of their α-cuts. The accuracy between the ideal solution and the objective values is evaluated handling the fuzzy parameters through their expected intervals and a definition of discrepancy between intervals is introduced in our analysis.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Linear programming with multiple fuzzy goals

This paper describes the use of fuzzy set theory in goal programming (GP) problems. In particular, it is demonstrated how fuzzy or imprecise aspirations of the decision maker (DM) can be quantified through the use of piecewise linear and continuous functions. Models are then presented for the use of fuzzy goal programming with preemptive priorities, with Archimedean weights, and with the maximization of the membership function corresponding to the minimum goal. Examples are also provided.