Search

The paper deals with human-computer interaction in which the cooperation leads to solve a difficult issue of discrete optimization. Considered jobs scheduling problem in a robotic cell consisting of two machines and a robotic operator. Only one of two machines can work at a time and there are setup times between successive operations on a machine. The goal is to determine a schedule — permutation of jobs — and an assignment of jobs to machines, which minimize the minimal cycle time. We show that although there is exponential number of assignments of jobs to machines, it is possible to determine optimal assignment in the polynomial time. Next, we propose higher level metaheuristics — tabu search and evolutionary algorithm.

Steel slabs are intermediates in the production of sheets, plates or coils in the steel industry. In this paper we consider cold charge slabs which are stored in stacks on a slab yard for a couple of hours, days or weeks until they are assigned to a rolling schedule and retrieved. When a slab is not positioned on top of a stack, retrieval requires the movement, also called shuffling, of all slabs above. We introduce a new model formulation, suitable neighbourhood and perturbation operators and discuss strategies for optimizing slab yard assignments with respect to shuffles and travel distance in picking.

Production Fine Planning is often performed directly using all information and assuming that it is fixed. In practice, however, this information changes regularly and the plan has to be adapted. This often means a complete rescheduling of all operations. We present a new approach to this problem by optimizing priority rules that can sort the available next actions. These priority rules often yield similar results even though they do not resemble each other. By using genetic programming to build these priority rules, a distributed system to compute the simulations and a solution archive with a cache of hundreds of thousands of priority rules, new insights into priority rule-based optimization are gained. This archive does not only speed up calculation by avoiding re-simulation of the same rule but can provide a pseudo Pareto front of shorter sub-optimal solutions that facilitate interpretation of the more complex rules and their evolution during the optimization process.

The vehicle routing problem is a class of problems that frequently occurs in the field of transportation logistics. In this work, we tackle very-large scale problem instances with time windows. Among other techniques, metaheuristics are frequently used to solve large-scale instances close to optimality. We present an island-model genetic algorithm variant and apply several techniques such as offspring selection and adaptive constraint relaxation. To validate our approach, we perform test runs on benchmark instances with 1000 customers and compare the results to the currently best-known solutions.

Since the 1960s researcher have developed various storage assignment strategies for different warehouse scenarios. Much of this research has been devoted to re-warehousing, which involves extensive re-arrangements akin to filling a warehouse from scratch. However, due to seasonal fluctuations in demand or product mix, operations managers need to periodically review item placement in practise and re-organize the warehouse to keep it operating efficiently. In this paper we demonstrate for a sample warehouse how applying a small number of cleanup tasks (=healing) every day will lead to a good total warehouse assignment over the course of many months and show that the results are competitive to re-warehousing.

Solutions to the Quadratic Assignment Problem (QAP) can be compared with each other in several ways. In this work a new distance metric for measuring the distance respectively similarity between two solutions will be introduced. Such a metric is useful in measuring the performance of heuristic optimization algorithms and generally in the analysis of the QAP's fitness landscape. The new metric is described, compared to the most commonly used metric and evaluated on a number of problem instances. The correlation between the fitness distance and the solution distance can be improved in several problem instances providing a different and more interesting picture on algorithm performance.

In urban areas freight transport imposes many social and environmental issues. Solid waste collection accounts for a considerable amount of freight transportation in municipal areas. We propose a simulation-based approach to evaluate different scenarios where electric trucks replace conventional trucks for the collection of municipal glass-waste. Under special consideration of the characteristics of electric trucks, the simulation of real-time fill level information is used and coupled with an optimization component to evolve adapted waste collection strategies. We illustrate our approach on two test-scenarios based on real-world data. We use the simulation model to evaluate several scenarios in terms of costs and environmental impact and the optimization environment to generate collection strategies that minimize those performance figures while maintaining a given service quality.

Formal fitness landscape analysis enables us to study basins of attraction with great detail. This seemingly simple concept shows more variability and influence on heuristic algorithms than might be expected. We have taken a new perspective and a closer look at the properties of basins of attraction using two-dimensional visualizations to arrive at a conceptually simple but heuristically challenging test function that exhibits “misleading” basins of attraction.

This paper exemplarily points out how essential genetic information evolves during the runs of certain selected GA-variants. The discussed algorithmic enhancements to a standard genetic algorithm certify the survival of essential genetic information by supporting the survival of relevant alleles rather than the survival of above average chromosomes. This is achieved by defining the survival probability of a new child chromosome depending on the child's fitness in comparison to the fitness values of its own parents. The described kind of analysis assumes the knowledge of the unique global optimal solution and is therefore restricted to rather theoretical considerations The main aim of this paper is to explain the most important properties of the discussed algorithm variants in a rather intuitive way. Aspects for meaningful and practically more relevant generalizations as well as more sophisticated experimental analyses are indicated.

This work treats the topic of solving dynamic pickup and delivery problems, also known as dial-a-ride problems. A simulation model is introduced that describes how an agent is able to satisfy the transportation requests. The agent behavior is given in form of a complex dispatching rule, which is optimized by metaheuristic approaches. For this purpose, a fitness function is described which is used to evaluate the quality of a solution. The rule to be optimized is a weighted sum of several primitive dispatching rules where each describes a small part of the information available in the system at a given time. Given a good configuration of the weights, we will show that the agents are able to serve the transportation requests. The optimization of the weights was conducted with the generic, open, and extensible optimization framework HeuristicLab. Index Terms—simulation, pickup and delivery, dispatching, optimization

In this paper the author presents three approaches to parallel tabu search, applied to several instances of the capacitated vehicle routing problem with time windows (CVRPTW). Attention in this work was given to keep the parallel implementations simple. The parallel algorithms are of two kinds: two of them are parallel with respect to functional decomposition and one approach is a collaborative multisearch TS. The implementation builds upon a framework called distributed meta-heuristics or DEME for short. Tests were performed on an SGI Origin 3800 supercomputer at the Johannes Kepler University of Linz, Austria.