Punctuality and idleness in just-in-time scheduling

In scheduling problems with irregular cost functions, such as deviation functions in earliness–tardiness scheduling problems, optimal solutions usually contain some idleness periods during which no activity is processed. Then, minimizing the penalties for not delivering on time and minimizing the idleness cost are two complementary criteria for a schedule. A Dynamic Programming procedure, in which the states are represented by continuous two-dimensional piecewise linear functions, is proposed to compute the cost of the Pareto optimal schedules.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

Multi-objective optimization method for learning thresholds in a decision-theoretic rough set model

For decision-theoretic rough sets, a key issue is determining the thresholds for the probabilistic rough set model by setting appropriate cost functions. However, it is not easy to obtain correct cost functions because of a lack of prior knowledge and few previous studies have addressed the determination of learning thresholds and cost functions from datasets. In the present study, a multi-objective optimization model is proposed for threshold learning. In our model, we integrate an objective function that minimizes the decision cost with another that decreases the size of the boundary region. The ranges of the thresholds and two types of F_measure are used as constraints. In addition, a multi-objective genetic algorithm is employed to obtain the Pareto optimal set. We used 12 UCI datasets to validate the performance of our method, where the experimental results demonstrated the trade-off between the two objectives as well as showing that the thresholds obtained by our method were more intuitive than those obtained using other methods. The classification abilities of the solutions were improved by the F_measure constraints.     

Parallel machine scheduling problems considering regular measures of performance and machine cost

This research considers a broad range of scheduling problems in the parallel machines environment. Schedules are evaluated according to two independent components of the objective function: (1) machine cost consisting of a fixed cost and a variable cost; and (2) a regular measure of performance. This study is only one of a few that take the selection of machines among those available as a decision variable. For machine cost with concave functions, we derive the general characteristics of optimal solutions with respect to decisions on the number of machines to use and the way to load the machines. Our analysis is not restricted to the machine cost criterion, but may be extended to other measures with concave functions. Furthermore, we provide a Pareto efficient perspective in understanding the tradeoff between machine cost and any regular measure of performance.     

Online surrogate multiobjective optimization algorithm for contaminated groundwater remediation designs

This paper proposes an online surrogate model-assisted multiobjective optimization framework to identify optimal remediation strategies for groundwater contaminated with dense non-aqueous phase liquids. The optimization involves three objectives: minimizing the remediation cost and duration and maximizing the contamination removal rate. The proposed framework adopts a multiobjective feasibility-enhanced particle swarm optimization algorithm to solve the optimization model and uses an online surrogate model as a substitute for the time-consuming multiphase flow model for calculating contamination removal rates during the optimization process. The resulting approach allows decision makers to find a balance among the remediation cost, remediation duration and contamination removal rate for remediating contaminated groundwater. The new algorithm is compared with the nondominated sorting genetic algorithm II, which is an extensively applied and well-known algorithm. The results show that the Pareto solutions obtained by the new algorithm have greater diversity and stability than those obtained by the nondominated sorting genetic algorithm II, indicating that the new algorithm is more applicable than the nondominated sorting genetic algorithm II for optimizing remediation strategies for contaminated groundwater. Additionally, the surrogate model and Pareto optimal set obtained by the proposed framework are compared with those of the offline surrogate model-assisted multiobjective optimization framework. The results indicate that the surrogate model accuracy and Pareto front achieved by the proposed framework outperform those of the offline surrogate model-assisted optimization framework. Thus, we conclude that the proposed framework can effectively enhance the surrogate model accuracy and further extend the comprehensive performance of Pareto solutions.     

考虑加工效率变化的变速机干扰管理研究

在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。     

A survey of recent developments in multiobjective optimization

Multiobjective Optimization (MO) has many applications in such fields as the Internet, finance, biomedicine, management science, game theory and engineering. However, solving MO problems is not an easy task. Searching for all Pareto optimal solutions is expensive and a time consuming process because there are usually exponentially large (or infinite) Pareto optimal solutions. Even for simple problems determining whether a point belongs to the Pareto set is -hard. In this paper, we discuss recent developments in MO. These include optimality conditions, applications, global optimization techniques, the new concept of epsilon Pareto optimal solution, and heuristics.     

Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems

As indicated by the most widely accepted classification, the Multi-Objective Mathematical Programming (MOMP) methods can be classified as a priori, interactive and a posteriori, according to the decision stage in which the decision maker expresses his/her preferences. Although the a priori methods are the most popular, the interactive and the a posteriori methods convey much more information to the decision maker. Especially, the a posteriori (or generation) methods give the whole picture (i.e. the Pareto set) to the decision maker, before his/her final choice, reinforcing thus, his/her confidence to the final decision. However, the generation methods are the less popular due to their computational effort and the lack of widely available software. The present work is an effort to effectively implement the ε-constraint method for producing the Pareto optimal solutions in a MOMP. We propose a novel version of the method (augmented ε-constraint method - AUGMECON) that avoids the production of weakly Pareto optimal solutions and accelerates the whole process by avoiding redundant iterations. The method AUGMECON has been implemented in GAMS, a widely used modelling language, and has already been used in some applications. Finally, an interactive approach that is based on AUGMECON and eventually results in the most preferred Pareto optimal solution is also proposed in the paper.     

Distributed computation of Pareto solutions inn-player games

The problem of computing Pareto optimal solutions with distributed algorithms is considered inn-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

A path following method for box-constrained multiobjective optimization with applications to goal programming problems

We propose a path following method to find the Pareto optimal solutions of a box-constrained multiobjective optimization problem. Under the assumption that the objective functions are Lipschitz continuously differentiable we prove some necessary conditions for Pareto optimal points and we give a necessary condition for the existence of a feasible point that minimizes all given objective functions at once. We develop a method that looks for the Pareto optimal points as limit points of the trajectories solutions of suitable initial value problems for a system of ordinary differential equations. These trajectories belong to the feasible region and their computation is well suited for a parallel implementation. Moreover the method does not use any scalarization of the multiobjective optimization problem and does not require any ordering information for the components of the vector objective function. We show a numerical experience on some test problems and we apply the method to solve a goal programming problem.     

Supply chain coordination with controllable lead time and asymmetric information

This paper considers coordinated decisions in a decentralized supply chain consisting of a vendor and a buyer with controllable lead time. We analyze two supply chain inventory models. In the first model we assume the vendor has complete information about the buyer’s cost structure. By taking both the vendor and the buyer’s individual rationalities into consideration, a side payment coordination mechanism is designed to realize supply chain Pareto dominance. In the second model we consider a setting where the buyer possesses private cost information. We design the coordination mechanism by using principal-agent model to induce the buyer to report his true cost structure. The solution procedures are also developed to get the optimal solutions of these two models. The results of numerical examples show that shortening lead time to certain extent can reduce inventory cost and the coordination mechanisms designed for both symmetric and asymmetric information situations are effective.     

Stochastic Optimization over a Pareto Set Associated with a Stochastic Multi-Objective Optimization Problem

We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-objective Optimization Problem, whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation method in order to approach this problem. We prove that the Hausdorff–Pompeiu distance between the weakly Pareto sets associated with the Sample Average Approximation problem and the true weakly Pareto set converges to zero almost surely as the sample size goes to infinity, assuming that our Stochastic Multi-objective Optimization Problem is strictly convex. Then we show that every cluster point of any sequence of optimal solutions of the Sample Average Approximation problems is almost surely a true optimal solution. To handle also the non-convex case, we assume that the real objective to be minimized over the Pareto set depends on the expectations of the objectives of the Stochastic Optimization Problem, i.e. we optimize over the image space of the Stochastic Optimization Problem. Then, without any convexity hypothesis, we obtain the same type of results for the Pareto sets in the image spaces. Thus we show that the sequence of optimal values of the Sample Average Approximation problems converges almost surely to the true optimal value as the sample size goes to infinity.     

Generalized viscosity approximation methods in multiobjective optimization problems

In this paper, we consider an extend-valued nonsmooth multiobjective optimization problem of finding weak Pareto optimal solutions. We propose a class of vector-valued generalized viscosity approximation method for solving the problem. Under some conditions, we prove that any sequence generated by this method converges to a weak Pareto optimal solution of the multiobjective optimization problem.     

Routing,ship size,and sailing frequency decision-making for a maritime hub-and-spoke container network

This study formulates a two-objective model to determine the optimal liner routing, ship size, and sailing frequency for container carriers by minimizing shipping costs and inventory costs. First, shipping and inventory cost functions are formulated using an analytical method. Then, based on a trade-off between shipping costs and inventory costs, Pareto optimal solutions of the two-objective model are determined. Not only can the optimal ship size and sailing frequency be determined for any route, but also the routing decision on whether to route containers through a hub or directly to their destination can be made in objective value space. Finally, the theoretical findings are applied to a case study, with highly reasonable results. The results show that the optimal routing, ship size, and sailing frequency with respect to each level of inventory costs and shipping costs can be determined using the proposed model. The optimal routing decision tends to be shipping the cargo through a hub as the hub charge is decreased or its efficiency improved. In addition, the proposed model not only provides a tool to analyze the trade-off between shipping costs and inventory costs, but it also provides flexibility on the decision-making for container carriers.     

Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem

In this article we consider the boolean optimization problem of finding the set of Pareto optimal solutions. The vector objectives are the positive cuts of linear functions to the non-negative semi-axis. Initial data are subject to perturbations, measured by the l ₁-norm in the parameter space of the problem. We present the formula expressing the extreme level (stability radius) of such perturbations, for which a particular solution remains Pareto optimal.     

Stability and accuracy functions for a multicriteria Boolean linear programming problem with parameterized principle of optimality “from Condorcet to Pareto”

A multicriteria Boolean programming problem with linear cost functions in which initial coefficients of the cost functions are subject to perturbations is considered. For any optimal alternative, with respect to parameterized principle of optimality “from Condorcet to Pareto”, appropriate measures of the quality are introduced. These measures correspond to the so-called stability and accuracy functions defined earlier for optimal solutions of a generic multicriteria combinatorial optimization problem with Pareto and lexicographic optimality principles. Various properties of such functions are studied and maximum norms of perturbations for which an optimal alternative preserves its optimality are calculated. To illustrate the way how the stability and accuracy functions can be used as efficient tools for post-optimal analysis, an application from the voting theory is considered.