Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

<Emphasis Type="Italic">T</Emphasis>-optimal designs for discrimination between rational and polynomial models

This paper considers the problem of the analytical construction of experimental designs optimal with respect to the popular T-optimality criterion proposed by A.C. Atkinson and V.V. Fedorov in 1975 for discrimination between the simplest rational and polynomial regression models. It is shown how the classical results from approximation theory can be used to derive explicit formulas describing the behavior of support points and weights of T-optimal designs for different fixed parameter values. An applied discrimination problem for rational and polynomial regression models is considered as an example. For this models the numerical construction of experimental designs optimal with respect to robust analogues of T-criterion is also briefly discussed.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

A Cutting Planes Algorithm for the <Emphasis Type="Italic">m</Emphasis>-Salesmen Problem

The existence of reliable and flexible FORTRAN programs for integer linear programming has recently enabled the development of very efficient algorithms for the travelling salesman problem. The main characteristic of these algorithms is the relaxation of most of the constraints of the problem during its solution. The same approach can be used for the solution of the m-salesmen problem in which m salesmen starting from the same city must visit only once n cities at minimum cost. The number of salesmen can be fixed in advance or allowed to vary, upper and lower bounds set on the number of salesmen and even fixed costs associated with the salesmen. The results obtained so far are very encouraging. Problems of up to 100 cities have been solved optimally for the m-travelling salesmen case and other more complex problems are currently under study.     

Robust optimization for routing problems on trees

The prize-collecting travelling salesman problem (pc-tsp) is a known variant of the classical travelling salesman problem. In the pc-tsp, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow {\mathbb {R}}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow {\mathbb {R}}_+\) and the goal is to find a closed tour K such that \(r\in V(K)\) and such that the cost \(\ell (K)+\pi (V{\setminus } V(K))\), which is the sum of the weights of the edges in the tour and the cost of the vertices not spanned by K, is minimized. In this paper, we study the pc-tsp from a viewpoint of robust optimization. In our setting, an operator must find a closed tour in a (known) edge-weighted tree \(T=(V,E)\) starting and ending in the depot r while some of the edges may be blocked by “avalanches” defining the scenario \(\xi \). The cost \(f(K,\xi )\) of a tour K in scenario \(\xi \) is the cost resulting from “shortcutting” K, i.e. from restricting K to the nodes which are reachable from r in scenario \(\xi \), i.e. in the graph \(T {\setminus } \xi =(V,E{\setminus }\xi )\). In the absolute robust version of the problem one searches for a tour which minimizes the worst-case cost over all scenarios, while in the deviation robust counterpart, the regret, that is, the deviation from an optimum solution for a particular scenario, is sought to be minimized. We show that both versions of the problem can be solved in polynomial time on trees.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

Heuristic for the Asymmetric Travelling Salesman Problem

The paper describes a heuristic algorithm for the asymmetric travelling salesman problem. The procedure is a generalization of Webb's Simple Loss 1 Method and is of the sequential type, i.e. in each step one link of the tour is fixed. The method proved to produce "high quality" near optimal solutions in a computing time, which only grows proportional to n^1.82.     

Total flowtime and makespan for a no-wait <Emphasis Type="Italic">m</Emphasis>-machine flowshop with set-up times separated

This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic.     

Counting rises and levels in <Emphasis Type="Italic">r</Emphasis>-color compositions

An r-color composition of a positive integer n is a sequence of positive integers, called parts, summing to n in which each part of size r is assigned one of r possible colors. In this paper, we address the problem of counting the r-color compositions having a prescribed number of rises. Formulas for the relevant generating functions are computed which count the compositions in question according to a certain statistic. Furthermore, we find explicit formulas for the total number of rises within all of the r-color compositions of n having a fixed number of parts. A similar treatment is given for the problem of counting the number of levels and a further generalization in terms of rises of a particular type is discussed.     

Solutions to the Constrained Flowshop Sequencing Problem

If the flowshop sequencing problem is constrained so that job profiles are maintained independently of other work on the shop, then a range of new problem solutions are possible. Using geometrical relationships between the cumulative process times, a slope matching method has been devised which generally provides better results than Palmer's method and Gupta's algorithm. Secondly, it has been possible to reformulate the flowshop sequencing problem in terms of the travelling salesman problem. This has enabled the performance of the slope matching, Palmer and Gupta methods to be compared against a non-heuristic solution. Finally, provided that expressing a job in terms of the slopes of the cumulative start and end times is satisfactory, this enables in n-job, M-machine flowshop to be converted into an equivalent n-job 2 machine flowshop to which the use of Johnson's method will provide optimal sequences.     

Construction of D-Optimal Experimental Designs for Nonparametric Regression Models

Under study is the problem of a D-optimal experimental design for the problem of nonparametric kernel smoothing. Modification is proposed for the process of calculating the Fisher information matrix. D-optimal designs are constructed for one and several target points for the problems of nonparametric kernel smoothing using a uniform kernel, the Gauss and Epanechnikov kernels. Comparison is performed between Fedorov’s algorithm and direct optimization methods (such as the Nelder–Mead method and the method of differential evolution). The features of the application of the optimality criterion for the experimental design of the problems with several target points were specified for the cases of various kernels and bandwidths.     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.     

A “Branch-and-Bound” Algorithm for the Exact Solution of the Three-Machine Scheduling Problem

By combining Roy's graph-theoretical interpretation of the problem of job scheduling on machines and some general results of his theory with the “branch-and-bound” method recently applied by Little et al. to the travelling salesman problem an algorithm has been obtained for the exact solution of the scheduling problem in the case of three machines. The working of the algorithm has been illustrated by numerical examples and possibilities of further investigations have been indicated.     

Scheduling Parts in a Combined Production-transportation Work Cell

This paper is concerned with a combined production-transportation scheduling problem. The problem comprises a simple, two-machine, automated manufacturing cell, which either stands alone or is a subunit of a complete flexible manufacturing system. The cell consists of two machines in series with a dedicated part-handling device such as a crane or robotic arm for transferring parts from the first machine to the second. The loading of a new piece on the first machine and the ejection of a finished piece from the second machine are performed by dedicated automated mechanisms. The introduction of parts into the system is done n at a time, whereby the parts are reshuffled into a sequence that minimizes completion time. All processing and transfer times are considered deterministic—a reasonable assumption for a cell comprising a robotic transfer device and two CNC machining units. What complicates the problem is the assumption of a non-negligible time for the transfer device to return (empty) from the second machine to the first. The operation is a generalization of a two-machine flowshop problem, and is formulated as a specially structured, asymmetric travelling salesman problem. An approximate polynomial time 0(n log n) algorithm is proffered. The procedure incorporates a lower bound using the Gilmore–Gomory algorithm for the no-wait, two-machine flowshop problem.     

The Solution of Travelling Salesman Problems Based on Industrial Data

This paper partially replicates a comparison of travelling salesman heuristics carried out by Golden et al. more than a decade ago. It differs in two important ways, however. (1) We consider two heuristics—k-OPT and the space filling curve technique—which were developed after the original comparison. These new techniques appear to add little to the quality of solutions to the test problems utilized here. (2) Instead of test problems using geographical data, ours are based on programs for parts produced by a numerically controlled machine. Because of the different characteristics of these test problems we reach somewhat different conclusions concerning the efficacy of the different procedures.     

A new algorithm for minimizing makespan, <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript>, in blocking flow-shop problem through slowing down the operations

In this paper, a new algorithm with complexity O(nm²) is presented, which finds the optimal makespan, C_max, for a blocking flow-shop problem by slowing down the operations of a no-wait flow-shop problem, F _m ∣no-wait∣C_max, for a given sequence where restriction on the slowing down is committed. However, the problem with performance measure makespan, C_max, in a non-cyclic environment, is a special case of cyclic problem with cycle time, C _t , as its performance measure. This new algorithm is much faster than the previously developed algorithms for cyclical scheduling problems.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

Packing circles in the smallest circle: an adaptive hybrid algorithm

The circular packing problem (CPP) consists of packing n circles C _i of known radii r _i , i∈N={1,?…,?n}, into the smallest containing circle ?. The objective is to determine the coordinates (x _i ,?y _i ) of the centre of C _i , i∈N, as well as the radius r and centre (x,?y) of ?. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

New heuristics for flow shop problem to minimize makespan

This paper investigates the flow shop problem with the objective to minimizemakespan. New algorithms are designed: one is off-line heuristic, Single JobFirst, for problemF _m ∥C _max ;and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problemF _m |r _i |C _max and its on-line version. It is proved that the two heuristics are asymptoticallyoptimal when the size of the problem is large enough. In addition, theasymptotical optimality of First-Come, First-Served manner is obtained as abyproduct of the asymptotical analysis of DSJF heuristic. At the end of thepaper, a new lower bound with performance guarantee is provided for problemF _m ∥C _max , andcomputational experiments show the effectiveness of these heuristicalgorithms.