Download (PDF)

Many real-world optimization problems are assignment problems whereby resources are assigned a set of tasks to perform. In such problems, the objective function can be productivity, speed, robustness, etc, or a combination thereof. The optimization can be further subjected to hard or soft constraints. If the resources are human beings, there are un-verbalized and/or un-formulated and/or subjective criteria and constraints such as implicit knowledge and preferences specific to each of the participants that are not taken into account in the objective function. For example, in a factory scheduling application where workers are assigned jobs to minimize production time under such constraints as changeover times or machine compatibility, some workers may have special knowledge about the factory or may prefer to work on certain machines they like or know better; such factors are not taken into account in the objective function but may be crucial to worker efficiency, worker satisfaction and overall productivity.
In another example, mailmen are assigned tours; management’s objective function is to minimize the amount of time it takes to deliver mail to increase speed of service; constraints include load balancing (each mailman should have approximately the same distance and the same load to carry) or the maximum weight a mailman can carry; certain mailmen may subjectively prefer certain tours because they know the terrain well or because the tours end close to where they live, or for other reasons unknown to the optimizer; there is also implicit knowledge a mailman has about certain tours, such as when building caretakers are present.
An evolutionary technique originally developed to generate “interesting” images and pieces of art can be used to perform task allocation by integrating subjective criteria and subjective knowledge into the search process.