A memetic algorithm for the team orienteering problem

The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 5 instances.     

Optimal preemptive scheduling on a fixed number of identical parallel machines

In this paper, we consider the preemptive scheduling problem on a fixed number of identical parallel machines. We present a polynomial-time algorithm for finding a minimal length schedule for an order class which contains properly interval orders.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

An MILP for scheduling problems in an FMS with one vehicle

This paper concerns the mathematical formulation and optimal solutions for the Flexible Manufacturing Systems Scheduling Problem (FMSSP) with one vehicle. This linear formulation differs from the previously published ones as it takes into account the maximum number of jobs allowed in the system, limited input/output buffer capacities, empty vehicle trips and no-move-ahead trips simultaneously. Our objective is to propose optimal solutions for small and medium-sized instances and to examine a number of commonly used assumptions and heuristics. Computational experiments are carried out on instances adapted from Bilge and Ulusoy [Bilge, Ü., Ulusoy, G., 1995. A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research 43, 1058–1070] and the following heuristics are evaluated: FIFO (First In First Out) rules for input/output buffer management; and FIFO, SPT (Shortest Processing Time), STT (Shortest Travel Time) and MOQS (Maximum Outgoing Queue Size) rules concerning the vehicle. The consequences of classical assumptions are also studied: ignoring empty trips, ignoring no-move-ahead constraints, and ignoring vehicle-disjunction constraints. The numerical experiments provide a set of optimal solutions and allow to evaluate the performances of heuristic search schemes.     

The project scheduling problem with production and consumption of resources: A list-scheduling based algorithm

The paper deals with algorithms for applying classical list scheduling to a project scheduling problem where the units of resources are produced or consumed at the occurrence of precedence-related events. It is shown that the feasibility variant of the project scheduling problem is NP-complete. Moreover, polynomial-time scheduling algorithms are devised for the three cases where the occurrence time sequence of all events or the consuming events or the producing events is given in advance. By enumerating these sequences (called linear orders), one obtains a list-scheduling based algorithm for minimizing the makespan of a project scheduling problem with production and consumption of resources.     

Subgraph extraction and metaheuristics for the maximum clique problem

The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of an order of all the vertices whereby those belonging to a maximum clique stay close enough to each other. Such an order can be identified via the extraction of a particular subgraph from the original graph. The problem can consequently be seen as a permutation problem that can be addressed efficiently by metaheuristics. We first design a memetic algorithm (MA) for this purpose. Computational experiments conducted on the DIMACS benchmark instances clearly show that our MA not only outperforms existing genetic approaches, but it also compares very well to state-of-the-art algorithms regarding the maximal clique size found after different runs. Furthermore, we show that a hybridization of MA with an iterated local search (ILS) improves the stability of the algorithm. This hybridization (MA-ILS) permits to find two distinct maximal cliques of size 79 and one of size 80 for the C2000.9 instance of the DIMACS benchmark.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

A Relation between Multiprocessor Scheduling and Linear Programming

The general non preemptive multiprocessor scheduling problem (NPMS) is NP-Complete, while in many specific cases, the same problem is Time-polynomial. A first connection between PMS and linear programming was established by Yannanakis, Sauer and Stone, who associated to any PMS instance some specific linear program. The main result inside this paper consists in a characterization of the partially ordered structures which allow the optimal values of any associated PMS instance to be equal to the optimal values of the corresponding linear programs.