Scheduling in Manufacturing Systems: The Ant Colony Approach

4.1. The comparison with polynomial algorithms

To show convergence of ACO algorithm towards optimum, one can compare their results with optimal results of already existing, precise, polynomial algorithms for certain exemplary problems of task scheduling. If a heuristic algorithm finds an optimal solution to polynomial problems, it is probable that solutions found for NP-complete problems will also be optimal or at least approximated to optimal. Heuristic algorithm described herein was tested with known polynomial algorithms and all of them achieved optimal solutions for those problems. The comparisons utilized such polynomial algorithms as:

• Coffman – Graham Algorithm,
• Hu Algorithm,
• Baer Algorithm,

Comparisons of ACO solutions with selected precise polynomial algorithms will be presented as an example.

Coffman and Graham algorithm

Scheduling of tasks which constitute a discretionary graph with singular performance times on two identical processors in order to minimize C _max. Calculation complexity of the algorithm is O(n ² ).

Test problem no 1:

• 2 identical processors (a), 3 identical processors (b).
• 15 tasks with singular performance times.
• Graph with tasks:

Figure 5.
Graph of tasks used for the comparison of ACO algorithm with Coffman and Graham algorithm (test problem no 1).

• Optimal scheduling for two processors obtained as a result of Coffman and Graham algorithm use (1a).

Figure 6.
Optimal scheduling for two processors - Coffman and Graham algorithm (1a).

• Optimal scheduling for two processors obtained as a result of ACO algorithm use (1a).

Figure 7.
Optimal scheduling for two processors - ACO algorithm (1a).

• Scheduling for three processors obtained as a result of Coffman and Graham algorithm use (1b).

Figure 8.
Problem scheduling for 3 processors - Coffman and Graham algorithm use (1b).

• Scheduling for three processors obtained as a result of ACO algorithm use (1b).

Figure 9.
Optimal problem scheduling for 3 processors – ACO algorithm (1b).

For two processors (1a) ACO algorithm identical to Coffman and Graham algorithm obtained optimal scheduling. It was the same in the case of three processors (1b) – both algorithms obtained the same scheduling. Coffman and Graham algorithm is optimal only for two identical processors. For task graph under research it also found optimal scheduling for 3 identical processors.

Another test problem is shown by the non-optimality of Coffman and Graham algorithm for processor number greater than 2.

Test problem no 2:

• 2 identical processors (a), 3 identical processors (b)
• 12 tasks with singular performance times.
• Graph of tasks:

Figure 10.
Graph of tasks used for the comparison of ACO algorithm with Coffman and Graham algorithm (test problem no 2).

• Optimal scheduling for two processors obtained as a result of Coffman and Graham algorithm use (2a).

Figure 11.
Optimal scheduling for 2 processors - Coffman and Graham algorithm (2a).

• Optimal scheduling for two processors obtained as a result of ACO algorithm use (2a).

Figure 12.
Optimal scheduling for 2 processors - ACO algorithm (2a).

• Non-optimal scheduling for three processors obtained as a result of Coffman and Graham algorithm use (2b).

Figure 13.

Non-optimal scheduling for 3 processors – Coffman and Graham algorithm (2b).

• Optimal scheduling for three processors obtained as a result of ACO algorithm use (2b).

Figure 14.
Optimal scheduling for 3 processors - ACO algorithm (2b).

For the problem of two processors (2a) both algorithms obtained optimal scheduling. In the case of three processors (2b) the Coffman and Graham algorithm did not find optimal scheduling, whereas the ACO algorithm did find it without any difficulty.

In another test example both algorithms were compared for the problem of task scheduling on two identical processors with singular and different performance times.

Test problem no 3:

• 2 identical processors.
• 5 tasks with singular performance times (a), 5 tasks with different performance times (b)
• Graph of tasks:

Figure 15.
Graph of tasks used for the comparison of ACO algorithm with Coffman and Graham algorithm (test problem no 3)

• Optimal scheduling for singular task performance times obtained as a result of Coffman and Graham algorithm use (3a).

Figure 16.
Optimal problem scheduling for singular task performance times – Coffman and Graham algorithm (3a)

• Optimal scheduling for singular task performance times obtained as a result of ACO algorithm use (3a).

Figure 17.

Optimal problem scheduling for singular task performance times – ACO algorithm (3a)

• Non-optimal scheduling for irregular task performance times obtained as a result of Coffman and Graham algorithm use (3b).

Figure 18.

Non-optimal problem scheduling for irregular task performance times – Coffman and Graham algorithm (2b)

• Optimal scheduling for irregular task performance times obtained as a result of ACO algorithm use (3b):

Figure 19.

Optimal problem scheduling for irregular task performance times – ACO algorithm (3b)

Both compared algorithms obtain optimal scheduling for the problem with regular (singular) task performance times (3a). For different task performance times (3b) the Coffman and Graham algorithm does not obtain optimal scheduling, whereas the ACO algorithm does obtain.

Hu algorithm

Scheduling of tasks with singular performance times which create a digraph of anti-tree type on identical processors in order to minimize C _max . Algorithm complexity is O(n).

Figure 20.
Graph of tasks used for the comparison of ACO and Hu algorithms.

Test problem no 1:

• 3 identical processors,
• 11 tasks with singular performance times,
• Graph of tasks (anti-tree):

• Optimal scheduling for problem 1 obtained as a result of Hu algorithm use:

Figure 21.
Optimal scheduling for problem 1 solved with Hu algorithm.

• Optimal scheduling for problem 1 obtained as a result of ACO algorithm use.

Figure 22.
Optimal scheduling for problem 1 solved with ACO algorithm.

Test problem no 2:

• 3 identical processors,
• 12 tasks with singular performance times,
• Graph of tasks (anti-tree):

Figure 23.

Graph of tasks used for the comparison of ACO and Hu algorithms (test problem no 2)

• Optimal scheduling for problem 2 obtained as a result of Hu algorithm use.

Figure 24.
Optimal scheduling for problem 2 solved with Hu algorithm

• Optimal scheduling for problem 2 obtained as a result of ACO algorithm use.

Figure 25.
Optimal scheduling for problem 2 solved with ACO algorithm

Both problems solved with Hu algorithm were also solved easily by ACO algorithm. Scheduling obtained is optimal.

Baer algorithm

Scheduling of indivisible tasks, with singular performance times, which create a graph of anti-tree type on two uniform processors in order to minimize C_max.

Test problem:

• 2 uniform processors with speed coefficients b₁ = 2, b₂ =1.
• 11 tasks with singular performance times.
• Graph of tasks (anti-tree):

Figure 26.
Graph of tasks used for the comparison of ACO and Baer algorithms.

• Optimal scheduling for the problem solved with Baer algorithm, obtained as a result of ACO algorithm use.

Figure 27.
Optimal scheduling for the problem solved with Baer algorithm, obtained as a result of ACO algorithm use

For the problem optimized with Baer algorithm, the ACO algorithm also obtains optimal solution.