Local search neighbourhoods for dealing with a novel nurse rostering model

A novel nurse rostering model is developed to represent real world problem instances more accurately. The proposed model is generic in the sense that it allows modelling of essentially different problem instances. Novel local search neighbourhoods are implemented to take advantage of the problem properties represented by the model. These neighbourhoods are used in a variable neighbourhood search and in an adaptive large neighbourhood search algorithm. The performance of the solution method is evaluated empirically on real world data. The proposed model is open to further extensions for covering personnel planning problems in different sectors and countries.     

VLSN search algorithms for partitioning problems using matching neighbourhoods

In this paper, we propose a general paradigm to design very large-scale neighbourhood search algorithms for generic partitioning-type problems. We identify neighbourhoods of exponential size, called matching neighbourhoods, comprised of the union of a class of exponential neighbourhoods. It is shown that these individual components of the matching neighbourhood can be searched in polynomial time, whereas searching the matching neighbourhood is NP-hard. Matching neighbourhood subsumes a well-known class of exponential neighbourhoods called cyclic-exchange neighbourhoods. Our VLSN algorithm is implemented for two special cases of the partitioning problem; the covering assignment problem and the single source transportation problem. Encouraging experimental results are also reported.     

Search Heuristics for Resource Constrained Project Scheduling

We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics.     

Kinetic analysis of polyhedral block system using an improved potential-based penalty function approach for explicit discontinuous deformation analysis

The complexity of polyhedral block systems (e.g., small blocks, flat blocks with small angles, edges, or faces) poses challenges in the kinetic analysis of rock block systems. This paper proposed an improved potential-based penalty function approach within an explicit three-dimensional (3D) discontinuous deformation analysis (DDA) framework for efficient and robust kinetic analysis of rock block systems. An explicit formulation of 3D DDA based on velocity verlet algorithm is first derived. A novel definition of potential function is then proposed with details of the key algorithms for overlap judgment of convex polyhedron, construction of intersection polyhedron and numerical integral for computation of contact force. The improved potential-based penalty function method is robust and efficient for complex convex polyhedral shapes. Several benchmark and application examples verify the feasibility, accuracy and robustness of the proposed methods in solving contact of polyhedral block systems.     

Valuation of project portfolios: An endogenously discounted method

Real options analysis (ROA) has been developed to value assets in which managerial flexibilities create significant value. The methodology is ideal for the valuation of projects in which frequent adjustments (e.g. investment deferral, project scope changes, etc) are necessary in response to the realization of market and technological uncertainties. However, ROA has no practical application when valuing portfolios of multiple concurrent projects sharing resources, as the size of the problem grows exponentially with the number of projects and the length of the time horizon. In this paper an extension of ROA suitable for the valuation of project portfolios with substantial technological uncertainty (e.g. R&D portfolios) is proposed. The method exploits the distributed decision making strategy encountered in most organizations to decompose the portfolio valuation problem into a decision-making sub-problem and a set of single project valuation sub-problems that can be sequentially solved. Discrete event simulation is used for the first sub-problem, while a tailored ROA based strategy is used for the set of valuation sub-problems. A case study from the pharmaceutical industry is used to compare the decision tree analysis (DTA) method and the proposed method.     

The contact problem for a piecewise-homogeneous plane with a semi-infinite inclusion

A piecewise-homogenous elastic plate, reinforced with a semi-infinite inclusion, which intersects the interface at a right angle and is loaded with shear forces is considered. The contact stresses along the contact line are determined and the behaviour of the contact stresses in the neighbourhood of singular points is established. Using methods of the theory of analytical functions and integral transformations the problem is reduced to a system of singular integro-differential equations on the semi-axis. The solution is presented in explicit form.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

Variable neighbourhood structures for cycle location problems

Variable neighbourhood search is a metaheuristic used mainly to tackle combinatorial optimization problems. Its performance depends on having a good variable neighbourhood structure: that is, a sequence of neighbourhoods that are ideally pairwise disjoint and contain feasible solutions further and further from a given feasible solution. This article defines a variable neighbourhood structure with these properties that is new for cycle location problems. It find bounds for the neighbourhood sizes and shows how to iterate over then when the cycle is a circuit. It tests the structure and iteration method using variable neighbourhood search on a range of median cycle problems and finds a neighbourhood size beyond which there is, on average, no benefit in applying local search. This neighbourhood size is found not to depend on problem size or bound on circuit length.     

A computational study of hybrid approaches of metaheuristic algorithms for the cell formation problem

In this paper we solve the 0–1 cell formation problem where the number of cells is fixed a priori and where the objective is to maximize the overall efficiency of a production system by grouping together machines providing service to similar parts into a subsystem (denoted cell). Three different methods are introduced and compared numerically. The first local search method is an implementation of simulated annealing (SA) where the definition of the neighbourhood is specific to the application and requires using a diversification and intensification strategies. The second local search method is an adaptive simulated annealing method where the neighbourhood is selected randomly at each iteration. The procedure is adaptive in the sense that the probability of selecting a neighbourhood is updated during the process. The third method is a hybrid method (HM) of a population-based method and a local search method. To improve the solution obtained with HM, we apply a SA method afterward. The best variants are very efficient to solve the 35 benchmark problems commonly used in the literature.     

A reliable algorithm to solve 3D frictional multi-contact problems: Application to granular media

We present in this paper an improved non-smooth Discrete Element Method (DEM) in 3D based on the Non-Smooth Contact Dynamics (NSCD) method. We consider a three-dimensional collection of rigid particles (spheres) during the motion of which contacts can occur or break. The dry friction is modeled by Coulomb’s law which is typically non-associated. The non-associativity of the constitutive law poses numerical challenges. By adopting the use of the bi-potential concept in the framework of the NSCD DEM, a faster and more robust time stepping algorithm with only one predictor-corrector step where the contact and the friction are coupled can be devised. This contrasts with the classical method where contact and friction are treated separately leading to a time stepping algorithm that involves two predictor-corrector steps. The algorithm has been introduced in a 3D version of the NSCD DEM software MULTICOR. Numerical applications will show the robustness of the algorithm and the possibilities of the MULTICOR software for solving three-dimensional problems.     

On the stability of alternating‐direction explicit methods for advection‐diffusion equations

Alternating‐Direction Explicit (A.D.E.) finite‐difference methods make use of two approximations that are implemented for computations proceeding in alternating directions, e.g., from left to right and from right to left, with each approximation being explicit in its respective direction of computation. Stable A.D.E. schemes for solving the linear parabolic partial differential equations that model heat diffusion are well‐known, as are stable A.D.E. schemes for solving the first‐order equations of fluid advection. Several of these are combined here to derive A.D.E. schemes for solving time‐dependent advection‐diffusion equations, and their stability characteristics are discussed. In each case, it is found that it is the advection term that limits the stability of the scheme. The most stable of the combinations presented comprises an unconditionally stable approximation for computations carried out in the direction of advection of the system, from left to right in this case, and a conditionally stable approximation for computations proceeding in the opposite direction. To illustrate the application of the methods and verify the stability conditions, they are applied to some quasi‐linear one‐dimensional advection‐diffusion problems. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Numerical investigation of a liquid displacing a gas in thin porous layers

This article deals with a liquid displacing a gas in a thin heterogeneous porous material, which occurs e.g. during the filling process of a lithium-ion battery with an electrolyte. The investigation is based upon the local volume-averaged Navier-Stokes equations, using a Volume-of-Fluid method to treat the interface. For the flow the wall effect and capillary forces have to be considered. Capillary rise experiments are used to determine the permeability. Since the layers are thin and the characteristic size of the particles is comparatively large, friction with the electrode is taken into account with respect to the mobility of the contact line. The implemented models are validated against analytical results, showing a good agreement. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A continuous-time search model with job switch and jumps

We study a new search problem in continuous time. In the traditional approach, the basic formulation is to maximize the expected (discounted) return obtained by taking a job, net of search cost incurred until the job is taken. Implicitly assumed in the traditional modeling is that the agent has no job at all during the search period or her decision on a new job is independent of the job situation she is currently engaged in. In contrast, we incorporate the fact that the agent has a job currently and starts searching a new job. Hence we can handle more realistic situation of the search problem. We provide optimal decision rules as to both quitting the current job and taking a new job as well as explicit solutions and proofs of optimality. Further, we extend to a situation where the agent’s current job satisfaction may be affected by sudden downward jumps (e.g., de-motivating events), where we also find an explicit solution; it is rather a rare case that one finds explicit solutions in control problems using a jump diffusion.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

A co-opetitive framework for the hub location problems in transportation networks

In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented.     

The double travelling salesman problem with multiple stacks – Formulation and heuristic solution approaches

This paper introduces the double travelling salesman problem with multiple stacks and presents four different metaheuristic approaches to its solution. The double TSP with multiple stacks is concerned with determining the shortest route performing pickups and deliveries in two separated networks (one for pickups and one for deliveries) using only one container. Repacking is not allowed, instead each item can be positioned in one of several rows in the container, such that each row can be considered a LIFO (last in, first out) stack, but no mutual constraints exist between the rows. Two different neighbourhood structures are developed for the problem and used with each of three local search metaheuristics. Additionally some simpler removal and reinsertion operators are used in a Large neighbourhood search framework. Finally some computational results are given along with lower bounds on the objective value.     

A Tutorial on Computational Cluster Analysis with Applications to Pattern Discovery in Microarray Data

Microarrays offer unprecedented possibilities for the so-called omic, e.g., genomic and proteomic, research. However, they are also quite challenging data to analyze. The aim of this paper is to provide a short tutorial on the most common approaches used for pattern discovery and cluster analysis as they are currently used for microarrays, in the hope to bring the attention of the Algorithmic Community on novel aspects of classification and data analysis that deserve attention and have potential for high reward. R. Giancarlo is partially supported by Italian MIUR grants PRIN “Metodi Combinatori ed Algoritmici per la Scoperta di Patterns in Biosequenze” and FIRB “Bioinformatica per la Genomica e la Proteomica” and Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”. D. Scaturro is supported by a MIUR Fellowship in the Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”.     

Regularization of 2D frictional contacts for rigid body dynamics

Classic rigid body mechanics does not provide frictional forces acting in a 2D contact interface between two bodies during sticking. This is due to the statical undeterminacy related with this problem. Many technical systems, e.g. disk clutches, have such surface-to-surface contacts and it is sometimes desirable to treat them as rigid body systems despite the 2D contact. Alternatively it is possible to model the systems using elastic instead of rigid bodies, but this might lead to certain drawbacks. Here a new regularization model of such 2D contacts between rigid bodies is proposed. It is derived from a material model for elasto-plasticity in continuum mechanics. Only dry friction is taken into account. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parametric approaches to fractional programs

The fractional program P is defined by maxf(x)/g(x) subject tox∈X. A class of methods for solving P is based on the auxiliary problem Q(λ) with a parameter λ: maxf(x)?λg(x) subject tox∈X. Starting with two classical methods in this class, the Newton method and the binary search method, a number of variations are introduced and compared. Among the proposed methods. the modified binary search method is theoretically interesting because of its superlinear convergence and the capability to provide an explicit interval containing the optimum parameter value \(\bar \lambda \) . Computational behavior is tested by solving fractional knapsack problems and quadratic fractional programs. The interpolated binary search method seems to be most efficient, while other methods also behave surprisingly well.     

A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem

This paper is concerned with the development of intelligent decision support methodologies for nurse rostering problems in large modern hospital environments. We present an approach which hybridises heuristic ordering with variable neighbourhood search. We show that the search can be extended and the solution quality can be significantly improved by the careful combination and repeated use of heuristic ordering, variable neighbourhood search and back-tracking. The amount of computational time that is allowed plays a significant role and we analyse and discuss this. The algorithms are evaluated against a commercial Genetic Algorithm on commercial data. We demonstrate that this methodology can significantly outperform the commercial algorithm. This paper is one of the few in the scientific nurse rostering literature which deal with commercial data and which compare against a commercially implemented algorithm.