Worst case analysis of Max-Regret,Greedy and other heuristics for Multidimensional Assignment and Traveling Salesman Problems

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman (Oper. Res. 39:150–161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s≥3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic (for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for the s-dimensional (s≥3) assignment problem.     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

On Markovian Multi-Class,Multi-Server Queueing

Multi-class multi-server queueing problems are a generalisation of the well-known M/M/k queue to arrival processes with clients of N types that require exponentially distributed service with different average service times. In this paper, we give a procedure to construct exact solutions of the stationary state equations using the special structure of these equations. Essential in this procedure is the reduction of a part of the problem to a backward second order difference equation with constant coefficients. It follows that the exact solution can be found by eigenmode decomposition. In general eigenmodes do not have a simple product structure as one might expect intuitively. Further, using the exact solution, all kinds of interesting performance measures can be computed and compared with heuristic approximations (insofar available in the literature). We provide some new approximations based on special multiplicative eigenmodes, including the dominant mode in the heavy traffic limit. We illustrate our methods with numerical results. It turns out that our approximation method is better for higher moments than some other approximations known in the literature. Moreover, we demonstrate that our theory is useful to applications where correlation between items plays a role, such as spare parts management.     

Encroaching lists as a measure of presortedness

Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such listsm provides a measure of presortedness with advantages over others in the literature. Experimental and analytic results are presented to cast light on the properties of encroaching lists. Also, we describe a new sorting algorithm,melsort, with complexityO(nlogm). Thus it is linear for well ordered sets and reduces to mergesort andO(nlogn) in the worst case.This work was partially supported by National Science Foundation Grant CCSR-8714565.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD process

We propose an analytically tractable approach for studying the transient behavior of multi-server queueing systems and feed-forward networks. We model the queueing primitives via polyhedral uncertainty sets inspired by the limit laws of probability. These uncertainty sets are characterized by variability parameters that control the degree of conservatism of the model. Assuming the inter-arrival and service times belong to such uncertainty sets, we obtain closed-form expressions for the worst case transient system time in multi-server queues and feed-forward networks with deterministic routing. These analytic formulas offer rich qualitative insights on the dependence of the system times as a function of the variability parameters and the fundamental quantities in the queueing system. To approximate the average behavior, we treat the variability parameters as random variables and infer their density by using ideas from queues in heavy traffic under reflected Brownian motion. We then average the worst case values obtained with respect to the variability parameters. Our averaging approach yields approximations that match the diffusion approximations for a single queue with light-tailed primitives and allows us to extend the framework to heavy-tailed feed-forward networks. Our methodology achieves significant computational tractability and provides accurate approximations for the expected system time relative to simulated values.     

Approximation results in parallel machnies stochastic scheduling

We consider scheduling a batch of jobs with stochastic processing times on parallel machines. We derive various new formulae for the expected flowtime and weighted flowtime under general scheduling rules. Smith's Rule, which orders job starts by decreasing ratio of weight to expected processing time provides a natural heuristic for this problem. We obtain a bound on the worst case difference between the expected weighted flow time under Smith's Rule and under an optimal policy. For a wide class of processing time distributions, this bound is of oderO(1) and does not increase with the number of jobs.This research was supported in part by NSF Grant ECS-8712798.     

A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times

This paper describes a generalized variable neighborhood search heuristic for the Capacitated Vehicle Routing Problem with Stochastic Service Times, in which the service times at vertices are stochastic. The heuristic is tested on randomly generated instances and compared with two other heuristics and with an alternative solution strategy. Computational results show the superiority and effectiveness of the proposed heuristic.     

Worst-case analysis for flow shop scheduling problems with an exponential learning effect

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with an exponential learning effect. By the exponential learning effect, we mean that the processing time of a job is defined by an exponent function of its position in a processing permutation. The objective is to minimize one of the four regular performance criteria, namely, the total completion time, the total weighted completion time, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single-machine scheduling problems. We also analyse the worst-case bound of our heuristic algorithms.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms.     

An average case analysis of the minimum spanning tree heuristic for the power assignment problem

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]^d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d.     

Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).     

Heuristics for unequal weight delivery problems with a fixed error guarantee

This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5−3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3−2/Q.     

Analysis of a shellsort algorithm

D. L. Shell published in 1959, [4], a fast algorithm for internal sorting. R. M. Frank and R. B. Lazarus pointed out in 1960, [3], a disadvantage in the original design of the algorithm and changes were proposed based on heuristic arguments. J. Boothroyd took care of Frank and Lazarus objections in an elegant algorithm published 1963, [1]. If we change Boothroyds algorithm slightly we get an algorithm which, in the general case with the arguments of Frank and Lazarus, is even worse than the original one. On the other hand this algorithm has the advantage that it is easy to analyse theoretically. To the author's knowledge such an analysis has not yet been given for any of the other Shellsort algorithms.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

A tabu-search heuristic for the flexible-resource flow shop scheduling problem

This paper presents a tabu-search heuristic for the flexible-resource flow shop scheduling (FRFS) problem [7]. The FRFS problem generalizes the classic flow shop scheduling problem by allowing job-operation processing times to depend on the amount of resource assigned to an operation; the objective is to determine simultaneously the job sequence, resource-allocation policy, and operation start times that optimize system performance. The tabu-search heuristic (TSH) employs a nested-search strategy based on a decomposition of the FRFS problem into these three components. We discuss computational experience with the THS procedure on more than 1600 test problems. The results show that TSH is effective in obtaining near-optimal solutions to the FRFS test problems. In particular, TSH generates optimal solutions for more than 70% of the test problems for which optimal solutions are known; overall, these solutions are within 0.3% of optimality on the average, and within 2.5% of optimality in the worst case.This research was supported in part by National Science Foundation grant SES90-22940.