A multiobjective hybrid ant colony optimization approach applied to the assignment and scheduling problem

摘要

The assignment and scheduling problem is inherently multiobjective. It generally involves multiple conflicting objectives and large and highly complex search spaces. The problem allows the determination of an efficient allocation of a set of limited and shared resources to perform tasks, and an efficient arrangement scheme of a set of tasks over time, while fulfilling spatiotemporal constraints. The main objective is to minimize the project makespan as well as the total cost. Finding a good approximation set is the result of trade-offs between diversity of solutions and convergence toward the Pareto-optimal front. It is difficult to achieve such a balance with NP-hard problems. In this respect, and in order to efficiently explore the search space, a hybrid bidirectional ant-based approach is proposed in this paper, which is an improvement of a bi-colony ant-based approach. Its main characteristic is that it combines a solution construction developed for a more complicated problem with a Pareto-guided local search engine.