Scheduling in Manufacturing Systems: The Ant Colony Approach
Read this section. It makes the case that production systems are similar to ant colonies because ants continue to learn from one another and find ways to become more efficient at their task at hand. As you read, pay special attention to some of the scheduling problems.
6. Conclusions
Conducted research shows that presented algorithms for task scheduling obtain good solutions - irrespectively of investigated problem complexity. These solutions are considered optimal or sub-optimal whose deviation from optimum does not exceed 5%. Heuristic algorithms proposed for task scheduling problems, especially ACO, should be a good tool for supporting planning process.
One should indicate a possible and significant impact of anomalies in task scheduling on the quality of the obtained results. The following examples show a possibility of appearing such anomalies. Take an example of this digraph of tasks:
- 112345671234567max
- Diminishing of performance time for all the tasks ti' = ti – 1 and the scheduling is longer than optimum scheduling (independently from choice list!):
For different problem instances, particular algorithms may achieve different successes; others may achieve worse results at different numbers of tasks. The best option is to obtain results of different algorithms and of different runs.
The goal of this scheduling is to find an optimum solution satisfying the requirements and constraints enforced by the given specification of the tasks and resources as well as criteria.
As for the optimality criteria for the manufacturing system for better control, we shall assume its minimum cost, maximum operating speed, and minimum power consumption.
We will apply multi-criteria optimization in sense of Pareto. The solution is optimized in sense of Pareto if it is not possible to find a better solution, regarding at least one criterion without deterioration in accordance to other criteria. The solution dominates other ones if all its features are better. Pareto ranking of the solution is the number of solutions in a pool which do not dominate it. The process of synthesis will produce a certain number of non-dominated solutions. Although non-dominated solutions do not guarantee that they are an optimal Pareto set of solutions; nevertheless, in case of a set of suboptimal solutions, they constitute one form of higher order optimal set in sense of Pareto and they give, by the way, access to the problem shape of Pareto optimal set of solutions.
Let's assume that we want to optimize a solution of two contradictory requirements: the cost and power consumption Fig. 36.
While using a traditional way with one optimization function, it is necessary to contain two optimal criteria in one value. To do that, it is advisable to select properly the scales for the criteria; if the scales are selected wrongly, the obtained solution will not be optimal. The chart in the illustration shows where, using linearly weighed sum of costs, we will receive the solution which may be optimizes in terms of costs.
Figure 36.
Set of optimal solutions in sense of
Pareto.
Cost optimization, power, and time consumption in the problem of scheduling is, undoubtedly, the problem where the potential number of solutions in sense of Pareto is enormous.
Future research: others of instances of scheduling problems, and additional criteria, especially in sense of Pareto and for dependable systems, are still open and this issue is now studied.