On finding representative non-dominated points for bi-objective integer network flow problems

This paper proposes a new algorithm to find a representation of the set of all non-dominated points of the bi-objective integer network flow problem. The algorithm solves a sequence of ε-constraint problems with a branch-and-bound algorithm to find a subset of non-dominated points that represents the set of all non-dominated points well in the sense of coverage or uniformity. At each iteration of the algorithm, one non-dominated point, determined by solving one ε-constraint problem, is added to the representation until it is guaranteed that the representation has the desired quality. Computational experiments on different problem types show the efficacy of the algorithm.     

Bi-objective minimization of environmental impact and cost in utility plants

A methodology to minimize potential environmental impact and operating cost in the selection of the operating conditions of a steam and power plant is presented. A bi-objective mixed integer nonlinear programming problem is formulated and solved in GAMS. Different strategies are implemented successfully to generate the Pareto curve such as: minimum distance to the utopia point, ?-constraint, weighted sum and global criterion. An analysis of the Pareto curve allows the identification of two regions where it is cheaper and more expensive respectively, to reduce the potential environmental impact, providing relevant information to support a decision making process. The economical valorisation of greenhouse gases emissions reduction was also carried out, showing the region of the Pareto curve in which the income would compensate the increment in operating cost, leading to a reduction of the potential environmental impact with no extra cost.     

Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm

In this study, a bi-objective multi-start simulated-annealing algorithm (BMSA) is presented for permutation flowshop scheduling problems with the objectives of minimizing the makespan and total flowtime of jobs. To evaluate the performance of the BMSA, computational experiments were conducted on the well-known benchmark problem set provided by Taillard. The non-dominated sets obtained from each of the existing benchmark algorithms and the BMSA were compared, and then combined to form a net non-dominated front. The computational results show that more than 64% of the solutions in the net non-dominated front are contributed by the proposed BMSA. It is believed that these solutions can serve as new benchmarks for future research.     

ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design

Heuristics and metaheuristics are inevitable ingredients of most of the general purpose ILP solvers today, because of their contribution to the significant boost of the performance of exact methods. In the field of bi/multi-objective optimization, to the best of our knowledge, it is still not very common to integrate ILP heuristics into exact solution frameworks. This paper aims to bring a stronger attention of both the exact and metaheuristic communities to still unexplored possibilities for performance improvements of exact and heuristic multi-objective optimization algorithms.We focus on bi-objective optimization problems whose feasible solutions can be described as 0/1 integer linear programs and propose two ILP heuristics, boundary induced neighborhood search (BINS) and directional local branching. Their main idea is to combine the features and explore the neighborhoods of solutions that are relatively close in the objective space. A two-phase ILP-based heuristic framework relying on BINS and directional local branching is introduced. Moreover, a new exact method called adaptive search in objective space (ASOS) is also proposed. ASOS combines features of the ϵ-constraint method with the binary search in the objective space and uses heuristic solutions produced by BINS for guidance. Our new methods are computationally evaluated on two problems of particular relevance for the design of FTTx-networks. Comparison with other known exact methods (relying on the exploration of the objective space) is conducted on a set of realistic benchmark instances representing telecommunication access networks from Germany.     

Maintenance costs and makespan minimization for assembly permutation flow shop scheduling by considering preventive and corrective maintenance

The joint optimization of production scheduling and maintenance planning has a significant influence on production continuity and machine reliability. However, limited research considers preventive maintenance (PM) and corrective maintenance (CM) in assembly permutation flow shop scheduling. This paper addresses the bi-objective joint optimization of both PM and CM costs in assembly permutation flow shop scheduling. We also propose a new mixed integer linear programming model for the minimization of the makespan and maintenance costs. Two lemmas are inferred to relax the expected number of failures and CM cost to make the model linear. A restarted iterated Pareto greedy (RIPG) algorithm is applied to solve the problem by including a new evaluation of the solutions, based on a PM strategy. The RIPG algorithm makes use of novel bi-objective-oriented greedy and referenced local search phases to find non-dominated solutions. Three types of experiments are conducted to evaluate the proposed MILP model and the performance of the RIPG algorithm. In the first experiment, the MILP model is solved with an epsilon-constraint method, showing the effectiveness of the MILP model in small-scale instances. In the remaining two experiments, the RIPG algorithm shows its superiority for all the instances with respect to four well-known multi-objective metaheuristics.     

A bi-objective vehicle routing problem with time windows: A real case in Tenerife

This work is motivated by a real problem posed to the authors by a company in Tenerife, Spain. Given a fleet of vehicles, daily routes have to be designed in order to minimize the total traveled distance while balancing the workload of drivers. This balance has been defined in relation to the length of the routes, regarding to the required time. A bi-objective mixed-integer linear model for the problem is proposed and a solution approach, based on the scatter search metaheuristic, is developed. An extensive computational experience is carried out, using benchmark instances with 25, 50 and 100 customers, to test several components of the proposed method. Comparisons with the exact Pareto fronts for instances up to 25 customers show that the proposed methods obtain good approximations. For comparison purposes, an NSGA-II algorithm has also been implemented. Results obtained on a real case instance are also discussed. In this case, the solution provided by the method proposed in this paper improves the solution implemented by the company.     

A hybrid GA-AUGMECON method to solve a cubic cell formation problem considering different worker skills

Part quality and consequently customer satisfaction besides cost functions are two of the most important issues for any firm. Balancing between these two goals leads to full utilization from manufacturing resources. Formerly, in cubic cell formation problem, where a part on a machine can be processed by various workers, worker assignment was done just by minimizing inter-cell movement criterion; so, the workers assigned into the processing cell are mostly selected rather than outsider workers. But, it is rational for the ties to be broken by skills of different workers in performing a special part on the dedicated machine. In this paper, a bi-objective cubic cell formation is presented with two non-homogeneous objective functions in order to minimize the inter-cell movements and maximize a part quality index. Quality index for each part is represented through a cubic matrix containing integer values of 1–5 (representing very bad, bad, medium, well and very well), which qualifies the process of part on a specific machine by a specific worker. To solve the problem, a hybrid GA-augmented ε-constraint method (GA-AUGMEON) is developed to reduce time consuming difficulty of AUGMECON method. To validate the model and the GA-AUGMECON algorithm, some randomly generated examples in small and large size are solved.     

Heuristics for the bi-objective path dissimilarity problem

In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using the standard measures in multi-objective optimization. A new GRASP procedure is proposed and tested against the revised methods, and we show that it is able to create better approximations of efficient frontiers than existing methods.     

基于Pareto支配的双目标优化求解非线性双层规划问题

双层规划问题是一类具有双层递阶结构的系统优化问题。采用Pareto支配的双目标优化策略求解非线性双层规划问题。利用K-T条件把双层规划问题等价转化单层规划问题,进而结合约束部分建立可行性度量目标形成双目标规划问题。在基本的差分进化算法框架中融入非负的最小二乘曲线拟合判断候选解的可行性,构造基于动态概率的Pareto支配选择策略挑选下一代个体,解决种群容易陷入局部最优的缺陷。15个标准函数的测试结果对比显示,该算法在求解非线性双层规划问题中具有较好的全局寻优能力、较低的计算复杂度、较强的稳定性和适用性,可以获得全局最优解。     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.