Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

Iterated greedy local search methods for unrelated parallel machine scheduling

This work deals with the parallel machine scheduling problem which consists in the assignment of n jobs on m   parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machine problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (_Cmax)$(C_{\text{max}})$. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.     

Shorted operators of partitioned matrices and application

In this paper, our main objective is to study the effect of appending/deleting a column/row on the shorted operators. It turns out that for matrices A and B for which the shorted operator S(A|B) exists, S(A₁|B₁) of the matrix A₁=[A:a] with respect to the matrix B₁=[B:b], when it exists, is obtained by appending a suitable column to S(A|B). Moreover, if S(A₁|B₁) exists, then S(A|B) exists and is obtained from S(A₁|B₁) by dropping its last column. In the process, we study the effect of appending/deleting a column/row on the space pre-order and the parallel sum of parallel summable matrices. Finally, we specialize to the case of and matrices and study the effect of bordering (by an additional column and a row) on the shorted operator. We conclude the paper with an application to Linear Models with singular dispersion structure.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems

This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time. We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P||∑w _j T _j problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||∑w _j T _j have been solved to optimality.     

A polynomial time algorithm for solving a quality control station configuration problem

We study unreliable serial production lines with known failure probabilities for each operation. Such a production line consists of a series of stations; existing machines and optional quality control stations (QCS). Our aim is to simultaneously decide where and if to install the QCSs along the line and to determine the production rate, so as to maximize the steady state expected net profit per time unit from the system.We use dynamic programming to solve the cost minimization auxiliary problem where the aim is to minimize the time unit production cost for a given production rate. Using the above developed O(N²) dynamic programming algorithm as a subroutine, where N stands for the number of machines in the line, we present an O(N⁴) algorithm to solve the Profit Maximization QCS Configuration Problem.     

An ILS heuristic for the traveling tournament problem with predefined venues

The Traveling Tournament Problem with Predefined Venues (TTPPV) is a single round robin variant of the Traveling Tournament Problem, in which the venue of each game to be played is known beforehand. We propose an Iterated Local Search (ILS) heuristic for solving real-size instances of the TTPPV, based on two types of moves. Initial solutions are derived from an edge coloring algorithm applied to complete graphs. We showed that canonical edge colorings should not be used as initial solutions in some situations. Instead, the use of Vizing’s edge coloring method lead to considerably better results. We also establish that the solution space defined by some commonly used neighborhoods in the sport scheduling literature is not connected in the case of single round robin tournaments, which explains the hardness of finding high quality solutions to some problem instances. Computational results show that the new ILS heuristic performs much better than heuristics based on integer programming and that it improves the best known solutions for benchmark instances.     

Local search for multiprocessor scheduling: how many moves does it take to a local optimum?

We analyze two local search algorithms for multiprocessor scheduling. The first algorithm is a job interchange algorithm for identical parallel machines due to Finn and Horowitz (Bit 19 (1979) 312). We construct instances for which this algorithm takes a quadratic number of iterations. This contradicts the original analysis of Finn and Horowitz who claimed a linear number of iterations.The second algorithm adds an additional rule to the Finn and Horowitz algorithm. Even for n jobs on m uniformly related machines, this modified algorithm takes only O(nm) iterations.     

A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem

The aim of the Single Container Loading Problem (SCLP) is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. We propose a new block building approach that constructs packings by placing one block (of boxes) at a time until no more boxes can be loaded. The key to obtaining high quality solutions is to select the right block to place into the right free space cuboid (or residual space) in the container. We propose a new heuristic for evaluating the fitness of residual spaces, and use a tree search to decide the best residual space-block pair at each step. The resultant algorithm outperforms the best known algorithms based on the 1600 commonly used benchmark instances even when given fewer computational resources. We also adapted our approach to address the full support constraint. The computational results for the full support support variant on the 1600 instances similarly show a significant improvement over existing techniques even when given substantially fewer computational resources.     

Memetic techniques for examination timetabling

In this paper, we investigate the effectiveness of combining the main components of the memetic algorithms (MAs) on the quality of solutions produced for Uncapacitated Examination Timetabling Problem (UETP). These components are recombination, randomness, and neighbourhood structures. The Harmony Search Algorithm (HSA), which is a variation of MA, is used to perform different combinations of these components. It has three main components: Memory Consideration using the recombination, Random Consideration using the randomness and Pitch Adjustment using the neighbourhood structures (or local search). The combinations among MA components are evaluated using 17 different scenarios each of which reflects a combination of one, two or three components. The results show that the system that combines the three components (recombination, randomness, and neighbourhood structures) provides the best results. Furthermore, the best results obtained from the convergence scenarios were compared with 22 other methods that used a de facto dataset defined by Carter et al. (in Journal of the Operational Research Society 74:373–383, 1996) for UETP. The results exceed those produced by the previous methods in 2 out of 12 datasets.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem

The Flexible Job-Shop Scheduling Problem is concerned with the determination of a sequence of jobs, consisting of many operations, on different machines, satisfying several parallel goals. We introduce a Memetic Algorithm, based on the NSGAII (Non-Dominated Sorting Genetic Algorithm II) acting on two chromosomes, to solve this problem. The algorithm adds, to the genetic stage, a local search procedure (Simulated Annealing). We have assessed its efficiency by running the algorithm on multiple objective instances of the problem. We draw statistics from those runs, which indicate that this Memetic Algorithm yields good and low-cost solutions.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

Local analytic solutions of the generalized Dhombres functional equation II

We study local analytic solutions f of the generalized Dhombres functional equation f(zf(z))=φ(f(z)), where φ is holomorphic at w₀≠0, f is holomorphic in some open neighborhood of 0, depending on f, and f(0)=w₀. After deriving necessary conditions on φ for the existence of nonconstant solutions f with f(0)=w₀ we describe, assuming these conditions, the structure of the set of all formal solutions, provided that w₀ is not a root of 1. If |w₀|≠1 or if w₀ is a Siegel number we show that all formal solutions yield local analytic ones. For w₀ with 0<|w₀|<1 we give representations of these solutions involving infinite products.     

Indefinite locally conformal Kähler manifolds

We study the basic properties of an indefinite locally conformal Kähler (l.c.K.) manifold. Any indefinite l.c.K. manifold M with a parallel Lee form ω is shown to possess two canonical foliations F and Fc, the first of which is given by the Pfaff equation ω=0 and the second is spanned by the Lee and the anti-Lee vectors of M. We build an indefinite l.c.K. metric on the noncompact complex manifold Ω₊=(Λ₊?Λ₀)/Gλ (similar to the Boothby metric on a complex Hopf manifold) and prove a CR extension result for CR functions on the leafs of F when M=Ω₊ (where is −²|z₁|−?−²|zs|+²|zs+1|+?+²|zn|>0). We study the geometry of the second fundamental form of the leaves of F and Fc. In the degenerate cases (corresponding to a lightlike Lee vector) we use the technique of screen distributions and (lightlike) transversal bundles developed by A. Bejancu et al. [K.L. Duggal, A. Bejancu, Lightlike Submanifolds of Semi-Riemannian Manifolds and Applications, vol. 364, Kluwer Academic, Dordrecht, 1996].     

Traces of the discrete Hilbert transform with quadratic phase

For the function $H:\mathbb{R}^2 \mapsto \mathbb{C}$ , $H: = (p.v.)\sum\nolimits_{n \in \mathbb{Z}\backslash \{ 0\} } {\tfrac{{\exp \left\{ {\pi i\left( {tn^2 + 2xn} \right)} \right\}}} {{2\pi in}}}$ of two real variables (t, x) ∈ ?², we study the uniform moduli of continuity and the variations of the restrictions H| _t and H| _x onto the lines parallel to the coordinate axes x = 0 and t = 0. Smoothness of such restrictions is primarily determined by the Diophantine approximation of the fixed parameter. Generalized (weak) variations are also studied, and it is shown in particular that sup _x w₄[H| _x ] < ∞ where w₄ denotes the weak quartic variation. Previously it was known that uniformly in the parameter t ∈ ?, the restriction H| _t is a function of bounded weak quadratic variation in the variable x, i.e., sup _t w₂[H| _t ] < ∞. The function H has multiple applications: in the study of the spectra of uniform convergence (P.L. Ul’yanov’s problem), in the incomplete Gaussian sums (where it plays the role of the generating function), in the partial differential equations of mathematical physics (in the Cauchy problem for the Schrödinger equation), and in quantum optics (Talbot’s phenomenon).