带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

Scatter search for trainees to software project requirements stable allocation

In this paper, we study a centralized, stable matching scheme, which allocates trainees to software project requirements, to minimize retraining and relocation costs when the preference lists of the project requirements may contain ties of arbitrary lengths. This particular trainees’ assignment problem is important because the allocation decisions not only influence the costs but also impact software project deliverables and intern attrition rates. It is also an NP-hard problem because of the inclusion of the ties, and the costs in the stable allocation model. We, therefore, have designed a GRASP-based scatter search method, to solve the large size instances of our assignment problem efficiently. The GRASP method uses randomized algorithms to generate initial trial solutions. A repair heuristic based on regret minimization idea is designed to convert an unstable solution to a stable solution during an improvement phase. Computational experiments suggest that the proposed algorithm significantly reduces run time compared to the CPLEX, and produces solutions that are at an average 4.5% away from the best CPLEX solutions for the large size problem instances. Moreover, our scatter search method consistently provides better quality solutions than the two state of the art methods from the prior literature.     

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations

The irregular strip packing problem consists of cutting a set of convex and non-convex two-dimensional polygonal pieces from a board with a fixed height and infinite length. Owing to the importance of this problem, a large number of mathematical models and solution methods have been proposed. However, only few papers consider that the pieces can be rotated at any angle in order to reduce the board length used. Furthermore, the solution methods proposed in the literature are mostly heuristic. This paper proposes a novel mixed integer quadratically-constrained programming model for the irregular strip packing problem considering continuous rotations for the pieces. In the model, the pieces are allocated on the board using a reference point and its allocation is given by the translation and rotation of the pieces. To reduce the number of symmetric solutions for the model, sets of symmetry-breaking constraints are proposed. Computational experiments were performed on the model with and without symmetry-breaking constraints, showing that symmetry elimination improves the quality of solutions found by the solution methods. Tests were performed with instances from the literature. For two instances, it was possible to compare the solutions with a previous model from the literature and show that the proposed model is able to obtain numerically accurate solutions in competitive computational times.     

Large neighborhood search for LNG inventory routing

Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. Due to the capital intensive nature of LNG projects, the optimal design of LNG supply chains is extremely important from a profitability perspective. Motivated by the need for a model that can assist in the design analysis of LNG supply chains, we address an LNG inventory routing problem where optimized ship schedules have to be developed for an LNG project. In this paper, we present an arc-flow formulation based on the MIP model of Song and Furman (Comput. Oper. Res., 2010). We also present a set of construction and improvement heuristics to solve this model efficiently. The heuristics are evaluated based on a set of realistic test instances that are very large relative to the problem instances seen in recent literature related to this problem. Extensive computational results indicate that the proposed methods are computationally efficient in finding optimal or near optimal solutions and are substantially faster than state-of-the-art commercial optimization software.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

Scheduling tests in automotive R&D projects

In automotive R&D projects a major part of development cost is caused by tests which utilize expensive experimental vehicles. In this paper, we introduce an approach for scheduling the individual tests such that the number of required experimental vehicles is minimized. The proposed approach is based on a new type of multi-mode resource-constrained project scheduling model with minimum and maximum time lags as well as renewable and cumulative resources. We propose a MILP formulation, which is solvable for small problem instances, as well as several variants of a priority-rule based method that serve to solve large problem instances. The developed solution methods are examined in a comprehensive computational study. For a real-world problem instance it is shown that the introduced approach may enhance the current methods applied in practice.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

Optimization guided lower and upper bounds for the resource investment problem

The resource investment problem deals with the issue of providing resources to a project such that a given deadline can be met. The objective is to make the resources available in the cheapest possible way. For each resource, expenses depend on the maximum amount required during the course of the project. In this paper we develop two lower bounds for this NP-hard problem using Lagrangean relaxation and column generation techniques, respectively. Both procedures are capable of yielding feasible solutions as well. Hence, we also have two optimization guided heuristics. A computational study consisting of a set of 3210 instances compares both approaches and allows insight into the performance.     

Dismantling of nuclear power plants at optimal NPV

Today, worldwide far more than 100 nuclear power plants, which have been decommissioned in the recent years, are waiting for their complete dismantling. Since the dismantling of a single reactor causes costs of up to one billion Euros and lasts up to 15 years, the elaboration of a scheduling approach helping to optimize the net present value of a dismantling project seems to be worthwhile. In this paper we present a resource-constrained project scheduling approach optimizing the total discounted disbursements of dismantling a nuclear power plant. For the corresponding NP-hard optimization problem, we introduce an appropriate project scheduling model with minimum and maximum time lags, renewable and cumulative resources as well as multiple execution modes. To solve this model, we introduce a relaxation-based enumeration approach that delivers optimal solutions for problem instances containing up to 50 activities.     

Computing the metric dimension of graphs by genetic algorithms

In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.     

Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.     

Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost can be reduced significantly when such methods are used. Experimental testing with benchmark instances is used to assess the merit of our proposed procedure.     

A branch-and-bound-based local search method for the flow shop problem

It is well-known that exact branch and bound methods can only solve small or moderately sized ????-hard combinatorial optimization problems. In this paper, we address the issue of embedding an approximate branch and bound algorithm into a local search framework. The resulting heuristic has been applied to the problem of finding a minimum makespan in the permutation flow shop problem. Computational experiments carried out on a large set of benchmark problems show that the proposed method consistently yields optimal or near-optimal solutions for instances with up to 200 jobs and 10 machines. In particular, for 19 instances, the heuristic produces solutions that outperform the best known ones.     

Multi-objective decision analysis for competence-oriented project portfolio selection

This paper develops a multi-objective optimization model for project portfolio selection taking employee competencies and their evolution into account. The objectives can include economic gains as well as gains expressed in terms of aggregated competence increments according to pre-defined profiles. In order to determine Pareto-optimal solutions, the overall problem is decomposed into a master problem addressing the portfolio selection itself, and a slave problem dealing with a suitable assignment of personnel to the work packages of the selected projects over time. We provide an asymptotic approximation of the problem by a linearized formulation, which allows an efficient and exact solution of the slave problem. For the solution of the master problem, we compare the multi-objective metaheuristics NSGA-II and P-ACO. Experimental results both for synthetically generated test instances and for real-world test instances, based on an application case from the E-Commerce Competence Center Austria, are presented.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem

This paper introduces two-dimensional loading time-dependent vehicle routing problem and proposes a bi-objective mathematical model. This problem assesses the process of distributing the rectangular-shaped demanded items over an urban environment; it does not, however, allow items to be loaded on top of each other. In addition to the above assumptions, the presented model also satisfies the first-in-first-out property in the time-dependent vehicle routing problem. Given the NP-hard nature of the problem, a method called elitist non-dominated sorting local search is developed to obtain its solutions. To evaluate the performance of the proposed algorithm, the solutions of this algorithm for small-scale problem instances are compared with the results of an exact method. For the medium-scale problem instances, results of NSGA-II and SPEA2 are used as the basis of comparison. The computational results demonstrate the good performance of the proposed method.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

Heuristics and metaheuristics for the maximum diversity problem

This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances. This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.