In multi-agent collaborative search missions, task allocation is required to determine which agents will perform which tasks. We propose a new approach for decentralized task allocation based on a decentralized genetic algorithm (GA). The approach parallelizes a genetic algorithm across the team of agents, making efficient use of their computational resources. In the proposed approach, the agents continuously search for and share better solutions during task execution. We conducted simulation experiments to compare the decentralized GA approach and several existing approaches. Two objectives were considered: a min-sum objective (minimizing the total distance traveled by all agents) and a min-time objective (minimizing the time to visit all locations of interest). The results showed that the decentralized GA approach yielded task allocations that were better on the min-time objective than those created by existing approaches and solutions that were reasonable on the min-sum objective. The decentralized GA improved min-time performance by an average of 5.6% on the larger instances. The results indicate that decentralized evolutionary approaches have a strong potential for solving the decentralized task allocation problem.

In this paper, the expression "production systems" refers to flow shops, job shops, assembly systems, Kanban systems, and, in general, to any discrete event system which transforms raw material and/or components into products and/or components. Such a system is said to be cyclic if it provides the same sequence of products indefinitely. A schedule of a cyclic production system is defined as soon as the starting time of each operation on the related resource is known. It has been shown that, whatever the feasible schedule applied to the cyclic production system, it is always possible to fully utilize the bottleneck resource. In other words, it is always possible to maximize the throughput of such a system. As a consequence, we aim at finding the schedule which permits to maximize the throughput with a work in process as small as possible. We propose a heuristic approach based on Petri nets to find a near-optimal, if not optimal, solution. We also give a sufficient condition for a solution to be optimal.

This paper discusses the problem of minimizing the cost of sheet metal punching when nesting (batching) orders. Although the problem is NP-complete, the solution to a linear programming relaxation yields an efficient heuristic. This paper analyzes the heuristic's worst-case performance and discusses experimental results that demonstrate its ability to find good solutions across a range of cost parameters and problem sizes.

Robust discrete optimization is a technique for structuring uncertainty in the decision-making process. The objective is to find a robust solution that has the best worst-case performance over a set of possible scenarios. However, this is a difficult optimization problem. This paper proposes a two-space genetic algorithm as a general technique to solve minimax optimization problems. This algorithm maintains two populations. The first population represents solutions. The second population represents scenarios. An individual in one population is evaluated with respect to the individuals in the other population. The populations evolve simultaneously, and they converge to a robust solution and its worst-case scenario. Since minimax optimization problems occur in many areas, the algorithm will have a wide variety of applications. To illustrate its potential, we use the two-space genetic algorithm to solve a parallel machine scheduling problem with uncertain processing times. Experimental results show that the two-space genetic algorithm can find robust solutions.

In this paper, we study the one-machine scheduling problem of minimizing the total flowtime subject to the constraint that each job must finish before its deadline, where the jobs to be scheduled fall into different job classes and setups occur whenever the machine processes consecutive jobs from different classes. A new heuristic is proposed for the problem. We investigate the use of a genetic algorithm to improve solution quality by adjusting the inputs of the heuristic. We present experimental results that show that the use of such a search can be successful. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.