A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

An empirical comparison of heuristic methods for creating maximally diverse groups

This research identifies, describes, and empirically contrasts five heuristics for forming maximally diverse groups of any specified size from a given population. Diversity is based upon multiple criteria specified by the decision maker. The problem has immediate application in academic or training settings where it may be desired to create class sections, or project groups within classes, such that students are immersed in a diverse environment. Furthermore this research has an even broader utility, as the problem is mathematically identical to an eclectic set of applications ranging from final exam scheduling to VLSI design. Here we consider five different heuristics, drawn from student-workgroup assignment and final exam scheduling applications. The methods are tested on a ‘real-world’ data set and evaluated on the criteria of solution quality and computational resources.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Tailoring hyper-heuristics to specific instances of a scheduling problem using affinity and competence functions

Hyper-heuristics are high level heuristics which coordinate lower level ones to solve a given problem. Low level heuristics, however, are not all as competent/good as each other at solving the given problem and some do not work together as well as others. Hence the idea of measuring how good they are (competence) at solving the problem and how well they work together (their affinity). Models of the affinity and competence properties are suggested and evaluated using previous information on the performance of the simple low level heuristics. The resulting model values are used to improve the performance of the hyper-heuristic by tailoring it not only to the specific problem but the specific instance being solved. The test case is a hard combinatorial problem, namely the Hybrid Flow Shop scheduling problem. Numerical results on randomly generated as well as real-world instances are included.     

Adapting Branch-and-Bound for Real-World Scheduling Problems

Many sequencing and scheduling problems can be formulated as 0-1 integer programs and, in theory, solved using a branch-and-bound approach. In practice, real-world instances of these problems are usually solved using heuristics. In this paper we demonstrate the benefits of incorporating an intuitive, user-controlled variable-tolerance into a depth-first branch-and-bound algorithm. The tolerance comprises two components: a variable depth tolerance and a variable breadth tolerance. A sample scheduling problem is thoroughly analysed to illustrate empirically parameter impact on solution quality and execution time. Then, results based on several real-world problems are discussed.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

Real-time split-delivery pickup and delivery time window problems with transfers

In this research we present the design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets. In the SDPDTWP each shipment is constrained with the earliest possible pickup time from the origin and the latest acceptable delivery time to a destination. Split-deliveries occur when two or more vehicles service the same origin or destination. The proposed heuristics were applied to both static and real-time data sets. The heuristics computed a solution, in a few seconds, for a static problem from the literature, achieving an improvement of 60% in distance in comparison to the published solution. In the real-time SDPDTWP problems, requests for pickup and delivery of a package, breakdown of a truck or insertion of a truck can occur after the vehicle has left the origin and is enroute to service the customers. Thirty data sets, each consisting of one to seven real-time customer or truck events, were used to test the efficiency of the heuristics. The heuristics obtained solutions to real-time data sets in under five seconds of CPU time.      

Problem difficulty of real instances of convoy planning

Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.     

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.     

A cooperative hyper-heuristic search framework

In this paper, we aim to investigate the role of cooperation between low level heuristics within a hyper-heuristic framework. Since different low level heuristics have different strengths and weaknesses, we believe that cooperation can allow the strengths of one low level heuristic to compensate for the weaknesses of another. We propose an agent-based cooperative hyper-heuristic framework composed of a population of heuristic agents and a cooperative hyper-heuristic agent. The heuristic agents perform a local search through the same solution space starting from the same or different initial solution, and using different low level heuristics. The heuristic agents cooperate synchronously or asynchronously through the cooperative hyper-heuristic agent by exchanging the solutions of the low level heuristics. The cooperative hyper-heuristic agent makes use of a pool of the solutions of the low level heuristics for the overall selection of the low level heuristics and the exchange of solutions. Computational experiments carried out on a set of permutation flow shop benchmark instances illustrated the superior performance of the cooperative hyper-heuristic framework over sequential hyper-heuristics. Also, the comparative study of synchronous and asynchronous cooperative hyper-heuristics showed that asynchronous cooperative hyper-heuristics outperformed the synchronous ones.     

Time lag size in multiple operations flow shop scheduling heuristics

This paper considers a multistage flow shop where jobs require multiple operations at each stage and a finish-to-start time lag between any two consecutive operations of a job: the next operation of a job cannot start until the time lag after the former operation of that job has elapsed. The effect of the size of this time lag is considered when studying the effectiveness of solution approaches for this problem. Since the problem of minimizing the makespan is shown to be NP-hard even for the two-stage case, we present a lower bound based heuristic approach that is used to construct several heuristic procedures. These heuristics use lower bounds on the minimum makespan to solve the problem. The effectiveness of these heuristics is empirically evaluated for various time lag sizes by solving a large number of randomly generated problems. We show that the relative performance of the heuristics depends on the size of the time lag. If the ratio of mean time lag and mean processing time is 20% or more, heuristics that construct an active schedule perform less well than heuristics that construct a non-delay schedule. The opposite holds true if this ratio is smaller. The performance of the widely used Shortest Processing Time heuristic (SPT) deteriorates quickly if the size of the time lags increases. We propose instead to use the Earliest Finish Time heuristic (EFT) in case time lags are present. EFT performs much better in this case and is identical to SPT if all time lags are zero. The use of the lower bound based heuristics results in an improvement of the makespan performance of up to 50% as compared with the performance of some simple dispatching heuristics that take the presence of multiple operations and time lags into account. This effect increases with the size of the time lags.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

Solution of real-world postman problems

The paper presents the results of a study performed by the Deutsche post endowed chair of optimization of distribution networks in collaboration with Deutsche Post World Net with the aim of improving the planning of letter mail delivery. Modelling and solution methods for real-world postman problems are presented which extend one of the most general postman problems studied in the literature, the windy rural postman problem, with regard to several aspects. The discussed extensions include turn and street crossing restrictions, cluster constraints, the option to have alternative service modes (including ‘zigzag deliveries’), and the use of public transport to reach the postal district. The solution method is based on a transformation to the asymmetric TSP and uses non-standard neighbourhood search techniques. Extensive computational experiments show that the solution method clearly and consistently outperforms standard TSP heuristics on real-world instances.     

Pricing substitutable flights in airline revenue management

We develop a Markov decision process formulation of a dynamic pricing problem for multiple substitutable flights between the same origin and destination, taking into account customer choice among the flights. The model is rendered computationally intractable for exact solution by its multi-dimensional state and action spaces, so we develop and analyze various bounds and heuristics. We first describe three related models, each based on some form of pooling, and introduce heuristics suggested by these models. We also develop separable bounds for the value function which are used to construct value- and policy-approximation heuristics. Extensive numerical experiments show the value- and policy-approximation approaches to work well across a wide range of problem parameters, and to outperform the pooling-based heuristics in most cases. The methods are applicable even for large problems, and are potentially useful for practical applications.     

Exact and heuristic approaches for the index tracking problem with UCITS constraints

Index tracking aims at determining an optimal portfolio that replicates the performance of an index or benchmark by investing in a smaller number of constituents or assets. The tracking portfolio should be cheap to maintain and update, i.e., invest in a smaller number of constituents than the index, have low turnover and low transaction costs, and should avoid large positions in few assets, as required by the European Union Directive UCITS (Undertaking for Collective Investments in Transferable Securities) rules. The UCITS rules make the problem hard to be satisfactorily modeled and solved to optimality: no exact methods but only heuristics have been proposed so far. The aim of this paper is twofold. First, we present the first Mixed Integer Quadratic Programming (MIQP) formulation for the constrained index tracking problem with the UCITS rules compliance. This allows us to obtain exact solutions for small- and medium-size problems based on real-world datasets. Second, we compare these solutions with the ones provided by the state-of-art heuristic Differential Evolution and Combinatorial Search for Index Tracking (DECS-IT), obtaining information about the heuristic performance and its reliability for the solution of large-size problems that cannot be solved with the exact approach. Empirical results show that DECS-IT is indeed appropriate to tackle the index tracking problem in such cases. Furthermore, we propose a method that combines the good characteristics of the exact and of the heuristic approaches.     

Parallel hyperheuristics for the frequency assignment problem

This work presents a set of approaches used to deal with the frequency assignment problem (FAP), which is one of the key issues in the design of GSM networks. The used formulation of FAP is focused on aspects which are relevant for real-world GSM networks. A memetic algorithm, together with the specifically designed local search and variation operators, are presented. The memetic algorithm obtains good quality solutions but it must be adapted for each instance to be solved. A parallel hyperheuristic-based model was used to parallelize the approach and to avoid the requirement of the adaptation step of the memetic algorithm. The model is a hybrid algorithm which combines a parallel island-based scheme with a hyperheuristic approach. The main operation of the island-based model is kept, but the configurations of the memetic algorithms executed on each island are dynamically mapped. The model grants more computational resources to those configurations that show a more promising behavior. For this purpose two different criteria have been used in order to select the configurations. The first one is based on the improvements that each configuration is able to achieve along the executions. The second one tries to detect synergies among the configurations, i.e., detect which configurations obtain better solutions when they are cooperating. Computational results obtained for two different real-world instances of the FAP demonstrate the validity of the proposed model. The new designed schemes have made possible to improve the previously known best frequency plans for a real-world network.     

Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem

Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.     

Unified encoding for hyper-heuristics with application to bioinformatics

This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.     

Surrogate constraint normalization for the set covering problem

The set covering problem (SCP) is central in a wide variety of practical applications for which finding good feasible solutions quickly (often in real-time) is crucial. Surrogate constraint normalization is a classical technique used to derive appropriate weights for surrogate constraint relaxations in mathematical programming. This framework remains the core of the most effective constructive heuristics for the solution of the SCP chiefly represented by the widely-used Chvátal method. This paper introduces a number of normalization rules and demonstrates their superiority to the classical Chvátal rule, especially when solving large scale and real-world instances. Directions for new advances on the creation of more elaborate normalization rules for surrogate heuristics are also provided.     

Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.