An adaptive search for the response time variability problem

The Response Time Variability Problem (RTVP) is an NP-hard combinatorial scheduling problem, which has recently been reported and formalised in the literature. This problem has a wide range of real-world applications in mixed-model assembly lines, multi-threaded computer systems, broadcast of commercial videotapes and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. We propose a greedy but adaptive heuristic that avoids being trapped into a poor solution by incorporating a look ahead strategy suitable for this particular scheduling problem. The proposed heuristic outperforms the best existing methods, while being much faster and easier to understand and to implement.     

Parallel variable neighbourhood search algorithms for job shop scheduling problems

^** Email: msevkli{at}fatih.edu.tr^*** Corresponding author. Email: mehmetaydin{at}acm.org, mehmet.aydin{at}beds.ac.uk Variable neighbourhood search (VNS) is one of the most recentmetaheuristics used for solving combinatorial optimization problemsin which a systematic change of neighbourhood with a local searchis carried out. However, as happens with other metaheuristics,it takes a long time to reach some useful solutions while solvingsome sort of hard combinatorial problems such as job shop scheduling(JSS). Parallelization is one of the most considerable policiesto overcome this matter. In this paper, firstly, a number ofVNS algorithms are examined for JSS problems and then four differentparallelization policies are taken into account to determineefficient parallelization for VNS algorithms. The experimentationreveals the performance of various VNS algorithms and the efficiencyof policies to follow in parallelization. In the end, the unilateral-ringtopology, a noncentral parallelization method, is found as themost efficient policy.     

Double variable neighbourhood search with smoothing for the molecular distance geometry problem

We discuss the geometrical interpretation of a well-known smoothing operator applied to the Molecular Distance Geometry Problem (MDGP), and we then describe a heuristic approach based on Variable Neighbourhood Search on the smoothed and original problem. This algorithm often manages to find solutions having higher accuracy than other methods. This is important as small differences in the objective function value may point to completely different 3D molecular structures.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

A variable neighbourhood search algorithm for the constrained task allocation problem

A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.     

Intelligent variable neighbourhood search for the minimum labelling spanning tree problem

Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some effective heuristics have been proposed and analyzed. In a currently ongoing project, we investigate an intelligent optimization algorithm to solve the problem. It is obtained by the basic Variable Neighbourhood Search heuristic with the integration of other complements from machine learning, statistics and experimental algorithmics, in order to produce high-quality performance and to completely automate the resulting optimization strategy. Computational experiments show that the proposed metaheuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time.     

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.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Hyper-heuristic approaches for the response time variability problem

We propose two classes for the implementation of hyper-heuristic algorithms. The first is based on constructive heuristics, whereas the second uses improvement methods. Within the latter class, a general framework is designed for the use of local search procedures and metaheuristics as low-level heuristics. A dynamic scheme to guide the use of these approaches is also devised. These ideas are tested on an NP-hard scheduling problem known as the response time variability problem (RTVP). An intensive computational experiment shows, especially in the second class where the new best results are found, the effectiveness of the proposed hyper-heuristics.     

Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs

In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deterioration date, then the jobs will require extra time for successful completion. In this paper, a single-machine total completion time problem with step-deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound is developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for a near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems with up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean deviations from the optimum value of less than 0.3%.     

A modified variable time step method for solving ice melting problem

A modified numerical method was used by authors for solving 1D Stefan problem. In this paper a modified method is proposed with difference formulae and different methods of calculating the variable time step, which are deduced from Taylor series expansions of different conditions at the boundary. Also an extrapolation formula for the solution at the first point at the right of the computational domain is proposed. The numerical results are compared with those obtained from other methods.     

Variable neighbourhood search for the minimum labelling Steiner tree problem

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

Polynomial algorithms for solving the vector sum problem

The problem is investigated of weighted sum maximization of a given finite set of vectors from the finite-dimensional vector space ? ^k . Polynomial algorithms solving it are presented and analyzed in the case when a finite polyhedral norm or the l ₂ norm is defined on ? ^k .     

Adaptive perturbed neighbourhood search for the expanding capacity multiple-choice knapsack problem

In this paper, we develop a perturbed reactive-based neighbourhood search algorithm for the expanding constraint multiple-choice knapsack problem. It combines reactive tabu search with some specific neighbourhood search strategies to approximately solve the problem. The tests were conducted on randomly generated instances and executed in comparable benchmark scenarios to those of the literature. The results outperform those of the Cplex solver and demonstrate the high quality of the two approach versions.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints

This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated VRP (CVRP) and the VRP with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW.     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

Genetic algorithms for solving the discrete ordered median problem

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.