Capacitated Multiple Item Ordering with Incremental Quantity Discounts

This paper presents a heuristic algorithm for determining order quantities for multiple items given incremental quantity discounts and a single resourse constraint. The heuristic is based on Lagrangian relaxation. The performance of the heuristic is compared, for small problems, with a procedure that generates optimal solutions. Results from computational experiments are given that demonstrate the quality and computational efficiency of the heuristic algorithm.     

A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem

Dynamic programming (DP) algorithms for the traveling salesman problem (TSP) can easily incorporate time dependent travel times, time windows, and precedence relationships which present difficulties for algorithms based on linear or nonlinear programming formulations and for many TSP heuristics. However, exact DP algorithms for the TSP have exponential storage and computational time requirements and can solve only very small problems. We present a restricted DP heuristic (a generalization of the nearest neighbor heuristic) that can include all the above considerations but solves much larger problems. The heuristic cannot guarantee optimality because only a userspecified specified number of partial tours is retained at each stage. In this paper, the heuristic is implemented for the time dependent traveling salesman problem and is tested on a personal computer on randomly generated problems. The quality of the solution improves, on average, as more computational time is permitted.     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

An artificial bee colony algorithm for the capacitated vehicle routing problem

This paper introduces an artificial bee colony heuristic for solving the capacitated vehicle routing problem. The artificial bee colony heuristic is a swarm-based heuristic, which mimics the foraging behavior of a honey bee swarm. An enhanced version of the artificial bee colony heuristic is also proposed to improve the solution quality of the original version. The performance of the enhanced heuristic is evaluated on two sets of standard benchmark instances, and compared with the original artificial bee colony heuristic. The computational results show that the enhanced heuristic outperforms the original one, and can produce good solutions when compared with the existing heuristics. These results seem to indicate that the enhanced heuristic is an alternative to solve the capacitated vehicle routing problem.     

An efficient tabu search procedure for the p-Median Problem

In this paper we present a new solution heuristic for the p-Median Problem. The algorithm is based on tabu search principles, and uses short term and long term memory, as well as strategic oscillation and random tabu list sizes. Our proposed procedure is compared with two other move heuristics: a well-known interchange heuristic and a recent hybrid heuristic. In computational tests on networks ranging in size up to 500 nodes the new heuristic is found to be superior with respect to the quality of solutions produced.     

Reducing mean flow time in permutation flow shop

This paper deals with the traditional permutation flow shop scheduling problem with the objective of minimizing mean flowtime, therefore reducing in-process inventory. A new heuristic method is proposed for the scheduling problem solution. The proposed heuristic is compared with the best one considered in the literature. Experimental results show that the new heuristic provides better solutions regarding both the solution quality and computational effort.     

An Iterative Construction Heuristic for the Ore Selection Problem

The ore selection problem involves choosing a processing option for a number of mining blocks that maximises the expected payoff for a given level of financial risk. An innovative neighbourhood search heuristic is proposed for the ore selection problem. This iterative construction heuristic employs a stochastic demolition and reconstruction strategy. Computational experiments with this heuristic for two ore selection problem instances, one involving 2,500 blocks and the other involving 78,000 blocks, are given. These problem instances are made publicly available for use by future workers. Our computational experiments indicate that the proposed heuristic produces better quality solutions faster than a relay hybrid (constructive-simulated annealing) heuristic.     

A Tabu Search Heuristic Procedure for Solving the Transportation Problem with Exclusionary Side Constraints

A new heuristic procedure for the transportation problem with exclusionary side constraints is developed and implemented. Tabu search, a meta-heuristic method, is used to guide the search to follow a path selectively to prevent from being trapped at local optimal solutions in order to find a global optimal or near global optimal solution. The simplex method on a graph is employed to lead the search from one solution to an adjacent solution in order to take advantage of the underlying network structure of the problem. In the procedure, net changes in cost and in infeasibility are used to measure the attractiveness of a move, and strategic oscillation is used to implement the intensification and diversification functions. A computational experiment was conducted to test the performance of the heuristic procedure and substantial computational results are reported. These results show that the new heuristic procedure finds very good quality solutions and outperforms an existing heuristic procedure in terms of both solution quality and CPU time.     

A Genetic Algorithm for the Multidimensional Knapsack Problem

In this paper we present a heuristic based upon genetic algorithms for the multidimensional knapsack problem. A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach. Computational results show that the genetic algorithm heuristic is capable of obtaining high-quality solutions for problems of various characteristics, whilst requiring only a modest amount of computational effort. Computational results also show that the genetic algorithm heuristic gives superior quality solutions to a number of other heuristics.     

An Almost Optimal Heuristic for Preemptive C max Scheduling of Dependent Tasks on Parallel Identical Machines

We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.     

Bard-type Methods for the Linear Complementarity problem with symmetric positive Definite Matrices

In this paper, the authors develop two heuristic Block Bard-typemethods for solving linear complementarity problems with P-matrices.Two implementations of these algorithms for sparse symmetricP (positive definite) matrices without special structure aredescribed. A computational study of these methods is also presented,and shows that the heuristic methods are quite efficient forthe solution of large-scale linear complementarity problemswith such matrices.     

A high quality solution constructive heuristic for flow shop sequencing

This paper addresses the flow shop sequencing problem. Following an investigation of the problem characteristics, a property of this scheduling problem is presented, and is used for the development of a new constructive heuristic with the objective of minimizing the total time to complete the schedule (makespan). The new method, denoted by N&M, is compared with the best constructive heuristic reported in the literature, named NEH. Results from computational experience have shown that for problems having up to 10 machines and 100 jobs, the new heuristic outperforms, on average, the NEH heuristic. There is no significant difference regarding computation effort for both NEH and N&M heuristics.     

A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer.     

A New Heuristic Method for the Permutation Flow Shop Scheduling Problem

A new heuristic method for the permutation flow shop scheduling problem is presented and compared with two other heuristics named NEH and SPIRIT. The new heuristic method is based on a property of the scheduling problem that provides an upper bound on the idle time of the last machine between any two adjacent jobs regardless of their position in the sequence of jobs. The results from computational experience have shown that the new heuristic outperforms, in solution quality, all others for problems having up to 50 jobs and 30 machines.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem

In this paper we propose a hybrid memory adaptive heuristic for solving the Capacitated Minimum Spanning Tree (CMST) problem. We augment the problem formulation with additional non-redundant constraints via use of adaptive memory, to improve upon the performance of an elementary heuristic (the Esau-Williams heuristic). Our methodology is tested against many of the previously reported heuristics for the CMST. We conclude that our generalized procedure performs on par with the best of these approaches in terms of solution quality, while expending a very modest amount of computational effort.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

A heuristic algorithm for the multidimensional zero-one knapsack problem

Computational and theoretical aspects of a new heuristic for the multidimensional zero-one knapsack problem are studied. Its computational efficiency is compared with two other well-known heuristics.