An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem

This article proposes an iterative rounding search-based algorithm for approximately solving the disjunctively constrained knapsack problem. The problem can be viewed as a variant of the well-known knapsack problem with some sets of incompatible items. The algorithm considers two key features: a rounding strategy applied to the fractional variables of a linear relaxation and a neighbouring strategy used for improving the quality of the solutions at hand. Both strategies are iterated into a process based on adding a series of (i) valid cardinality constraints and (ii) lower bounds used for bounding the objective function. The proposed algorithm is analysed computationally on a set of benchmark instances of the literature. The proposed algorithm outperforms the Cplex solver and the results obtained improve on most existing solutions.     

Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem

This article addresses a Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem, an NP-hard combinatorial optimization problem. The problem is solved by using a cooperative approach that uses a local search for exploring a series of neighbourhoods induced from the Lagrangian relaxation. Each neighbourhood is submitted to an optimization process using two alternative strategies: reducing and moving strategies. The reducing strategy serves to reduce the current search space whereas the moving strategy explores the new search space. The performance of the proposed approach is evaluated on benchmark instances taken from the literature. Its obtained results are compared with those reached by some recent methods available in the literature. New solutions have been obtained for almost 80% of the instances tested.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

Variable neighbourhood search for dual-resource constrained flexible job shop scheduling

Dual-resource constrained flexible job shop scheduling problem (FJSP) is considered and an effective variable neighbourhood search (VNS) is presented, in which the solution to the problem is indicated as a quadruple string of the ordered operations and their resources. Two neighbourhood search procedures are sequentially executed to produce new solutions for two sub-problems of the problem, respectively. The search of VNS is restarted from a slightly perturbed version of the current solution of VNS when the determined number of iterations is reached. VNS is tested on some instances and compared with methods from literature. Computational results show the significant advantage of VNS on the problem.     

An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem

This article presents an efficient heuristic placement algorithm, namely, a bidirectional heuristic placement, for solving the two-dimensional rectangular knapsack packing problem. The heuristic demonstrates ways to maximize space utilization by fitting the appropriate rectangle from both sides of the wall of the current residual space layer by layer. The iterative local search along with a shift strategy is developed and applied to the heuristic to balance the exploitation and exploration tasks in the solution space without the tuning of any parameters. The experimental results on many scales of packing problems show that this approach can produce high-quality solutions for most of the benchmark datasets, especially for large-scale problems, within a reasonable duration of computational time.     

Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem

The single-machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. This problem has been proved to be NP hard and thus provides a challenging area for metaheuristics, especially the variable neighbourhood search algorithm. In this article, a multiple variable neighbourhood search (m-VNS) algorithm with multiple neighbourhood structures is proposed to solve the problem. Special mechanisms named matching and strengthening operations are employed in the algorithm, which has an auto-revising local search procedure to explore the solution space beyond local optimality. Two aspects, searching direction and searching depth, are considered, and neighbourhood structures are systematically exchanged. Experimental results show that the proposed m-VNS algorithm outperforms all the compared algorithms in solving the SMTWT problem.     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems

In this paper we address the multi-depot open vehicle routing problem (MDOVRP), a complex and difficult problem arising in several real-life applications. In the MDOVRP vehicles start from several depots and do not need to return to the depot at the end of their routes. We propose a hybrid adaptive large neighbourhood search algorithm to solve the MDOVRP coupled with improvement procedures yielding a hybrid metaheuristic. The performance of the proposed metaheuristic is assessed on various benchmark instances proposed for this problem and its special cases, containing up to 48 customers (single-depot version) and up to six depots and 288 customers. The computational results indicate that the proposed algorithm is very competitive compared with the state-of-the-art methods and improves 15 best-known solutions for multi-depot instances and one best-known solution for a single-depot instance. A detailed sensitivity analysis highlights which components of the metaheuristic contribute most to the solution quality.     

Investigating Ahuja–Orlin’s large neighbourhood search approach for examination timetabling

Since the 1960s, automated approaches to examination timetabling have been explored and a wide variety of approaches have been investigated and developed. In this paper we build upon a recently presented, sequential solution improvement technique which searches efficiently over a very large set of “adjacent” (neighbourhood) solutions. This solution search methodology, originally developed by Ahuja and Orlin, has been applied successfully in the past to a number of difficult combinatorial optimisation problems. It is based on an improvement graph representation of solution adjacency and identifies improvement moves by finding cycle exchange operations using a modified shortest path label-correcting algorithm. We have drawn upon Ahuja–Orlin’s basic methodology to develop an effective automated exam timetabling technique. We have evaluated our approach against the latest methodologies in the literature on standard benchmark problems. We demonstrate that our approach produces some of the best known results on these problems.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

An adaptive transmission mechanism for parallel applications in wireless environments

Abstract

Parallel computing is a common technique for reducing execution time in distributed systems. An application is divided into several subtasks that can be executed simultaneously on a set of computers. Numerous parallel computing protocols and experiments have been measured on wired network environments, but little attention has been devoted to wireless networks. Wireless environments own characteristics that are unusual in wired networks, such as limited bandwidth, frequent disconnection, low power, and mobility. Due to the unique characteristics, the performance of parallel computing in wireless networks is degraded. This paper implements an adaptive transmission mechanism to cope with network contention and frequent disconnection. Experimental results show that the mechanism reduced total execution time effectively.     

A parallel genetic algorithm for dynamic cell formation in cellular manufacturing systems

Instead of using expensive multiprocessor supercomputers, parallel computing can be implemented on a cluster of inexpensive personal computers. Commercial accesses to high performance parallel computing are also available on the pay-per-use basis. However, literature on the use of parallel computing in production research is limited. In this paper, we present a dynamic cell formation problem in manufacturing systems solved by a parallel genetic algorithm approach. This method improves our previous work on the use of sequential genetic algorithm (GA). Six parallel GAs for the dynamic cell formation problem were developed and tested. The parallel GAs are all based on the island model using migration of individuals but are different in their connection topologies. The performance of the parallel GA approach was evaluated against a sequential GA as well as the off-shelf optimization software. The results are very encouraging. The considered dynamic manufacturing cell formation problem incorporates several design factors. They include dynamic cell configuration, alternative routings, sequence of operations, multiple units of identical machines, machine capacity, workload balancing, production cost and other practical constraints.     

Hybrid simulated annealing and reduced variable neighbourhood search for an aircraft scheduling and parking problem

Aircraft stands and runways at airports are critical airport resources for aircraft scheduling and parking. Making use of limited apron and runway resources to improve airport efficiency is becoming increasingly important. In this paper, we study a realistic Aircraft Scheduling and Parking Problem (ASPP) with the goal of simultaneously determining the takeoff and landing time of each aircraft with consideration for wake vortex effect constraints and parking positions in the limited parking apron at a target airport. The objective of the ASPP is to minimise the total service time for aircraft. We developed a mixed-integer linear programme formulation for the ASPP. A novel improved bottom-left/right strategy is applied to construct solutions and a Hybrid Simulated Annealing and Reduced Variable Neighborhood Search (HSARVNS) is proposed to identify near-optimal solutions. Numerical experiments on randomly generated ASPP instances and on a large set of benchmarks for a reduced version of the ASPP (i.e. the classical Two-Dimensional Strip-Packing Problem (2D-SPP)) demonstrate the effectiveness and efficiency of the proposed approach. For the ASPP, HSARVNS can find optimal solutions for small instances in a fraction of a second and can find high-quality solutions for instances with up to 250 aircraft within a reasonable timeframe. For the 2D-SPP, the HSARVNS can find optimal solutions for 32 of 38 tested benchmarks within 90 s on average.     

hp-version discontinuous Galerkin methods for hyperbolic conservation laws: A parallel adaptive strategy

This paper describes a parallel algorithm based on discontinuous hp-finite element approximations of linear, scalar, hyperbolic conservation laws. The paper focuses on the development of an effective parallel adaptive strategy for such problems. Numerical experiments suggest that these techniques are highly parallelizable and exponentially convergent, thereby yielding efficiency many times superior to conventional schemes for hyperbolic problems.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration

This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

Iterative mesh partitioning optimization for parallel nonlinear dynamic finite element analysis with direct substructuring

 This work presents a novel iterative approach for mesh partitioning optimization to promote the efficiency of parallel nonlinear dynamic finite element analysis with the direct substructure method, which involves static condensation of substructures' internal degrees of freedom. The proposed approach includes four major phases – initial partitioning, substructure workload prediction, element weights tuning, and partitioning results adjustment. The final three phases are performed iteratively until the workloads among the substructures are balanced reasonably. A substructure workload predictor that considers the sparsity and ordering of the substructure matrix is used in the proposed approach. Several numerical experiments conducted herein reveal that the proposed iterative mesh partitioning optimization often results in a superior workload balance among substructures and reduces the total elapsed time of the corresponding parallel nonlinear dynamic finite element analysis. Received 22 August 2001 / Accepted 20 January 2002