We present heuristics to handle practical travelling salesman problems with multiple time windows per node, where the optimization goal is minimal tour duration, which is the time spent outside the depot node. We propose a dynamic programming approach which combines state labels by encoding intervals to handle the larger state space needed for this objective function. Our implementation is able to solve many practical instances in real-time and is used for heuristic search of near-optimal solutions for hard instances. In addition, we outline a hybrid genetic algorithm we implemented to cope with hard or unknown instances. Experimental evaluation proves the efficiency and suitability for practical use of our algorithms and even leads to improved upper bounds for yet unsolved instances from the literature.

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objective is to minimize the makespan. Both formulations have different applications, for example, in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt et al. [1999]; for scheduling with nonavailability we provide the same lower bound. We use dual approximation, creation of a gap structure, and a PTAS for the multiple subset sum problem, combined with a postprocessing step to assign large jobs.

We study two closely related problems in non-preemptive scheduling of sequential jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. Both formulations have different applications, e.g. in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2 + ∊, respectively. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt, Steger & Weisser; for scheduling with non-availability we provide the same lower bound. In total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps.

Population-based search heuristics such as evolutionary algorithms or ant colony optimization have been widely used to tackle complex problems in combinatorial optimization. In many cases these problems involve the optimization of an objective function subject to a set of constraints which is very large. In this paper, we examine how population-based search heuristics can be sped up by making use of fast matrix multiplication algorithms. First, we point out that this approach is applicable to the wide class of problems which can be expressed as an Integer Linear Program (ILP). Later on, we investigate the speedup that can be gained by the proposed approach in our experimental studies for the multidimensional knapsack problem.

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 + ϵ and 8 + ϵ, as well as an algorithm with approximation ratio 7 + ϵ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z -axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ϵ and 5 + ϵ, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.