Scheduling in Manufacturing Systems: The Ant Colony Approach

4.2.1. NP- complete problem no 1:

Scheduling nonpreemptive, independent tasks on identical processors for C _max minimization.

Numberof tasks	Numberof processors	CmaxNeuralAlgorithm	CmaxACOAlgorithm
5	3	4	4
10	3	9	8
10	6	4	4
20	3	15	16
20	6	9	8
20	8	7	6

Table 1. Scheduling nonpreemptive, independent tasks on identical processors.

For all problems under research algorithms found similar solutions. Only neural algorithm did worse – for the problem of scheduling 10 tasks on 3 identical processors, 20 tasks on 6 processors and 20 tasks on 8 processors as well ACO algorithm for the problem of scheduling 20 tasks on 3 identical processors.

4.2.2. NP-complete problem no 2:

List scheduling with various methods of priority allocation

Because in general case the problem of scheduling dependent, nonpreemptable tasks is highly NP-complete, in some applications one can use polynomial approximate algorithms. Such algorithms are list algorithms.

In the chapter five types of list scheduling rules were compared: HLFET (Highest Levels First with Estimated Times), HLFNET (Highest Levels First with No Estimated Times), RANDOM, SCFET (Smallest Co-levels First with Estimated Times), SCFNET (Smallest Co-levels First with No Estimated Times).

The number of cases, in which the solution differs less than 5% from optimal solution, is accepted as an evaluation criterion for the priority allocation rule. If for 90% of examined examples the sub-optimal solution fit in the above range, the rule would be described as "almost optimal". This requirement is met only by HLFET rule, which gives results varying from optimum by 4,4% on average.

Example:

• 2 identical processors.
• 12 tasks with different performance times: (Z_0,1), (Z_1,1), (Z_2,7), (Z_3,3), (Z_4,1), (Z_5,1), (Z_6,3), (Z_7,2), (Z_8,2), (Z_9,1), (Z_10,3), (Z_11,1).
• Graph of tasks:

Figure 28.
The graph of tasks used for the comparison of ACO and list algorithms

Scheduling obtained as a result of ACO algorithm operation.

Figure 29.
Scheduling obtained with ACO algorithm.

The length of obtained scheduling is compliant with the scheduling which was obtained by means of the best list scheduling available for this case and which is HLFET ("almost optimal").

4.2.3. Comparison with PDF/HIS algorithm

For research purposes a set of graphs was utilized from the website below: http://www.kasahara.elec.waseda.ac.jp/schedule/index.html. Task graphs made available therein were divided into groups because of the number of tasks. Minimum scheduling length was calculated by means of PDF/HIS algorithm (Parallelized Depth First/ Implicit Heuristic Search) for every tasks graph. STG graphs are vectored, a-cyclic tasks graphs. Different task performance times, discretionary sequence constraints as well as random number of processors cause STG tasks scheduling problems to be NP-complete problems. Out of all solved problems heuristic algorithms under research did not find an optimal solution (assuming this is the solution obtained with PDF/IHS algorithm) only for three of them. However, results obtained are satisfactory, because the deviation from optimum varies from 0,36% to 4,63% (table Tab 2).

STG	Num-ber oftasks	Number of processors	PDF/IHS	Ant colony			Neural
			Cmax	Cmax	Number of iterations	Diffe- rence [%]	Cmax	Number of itera-tons	Diffe- rence [%]
rand0008	50	2	281	281	117	0	281	80	0
rand0038	50	4	114	114	1401	0	114	818	0
rand0107	50	8	155	155	389	0	155	411	0
rand0174	50	16	131	131	180	0	131	190	0
rand0017	100	2	569	569	171	0	569	92	0
rand0066	100	4	253	253	4736	0	257	3644	1,58
rand0106	100	8	205	205	861	0	205	927	0
rand0174	100	16	162	162	265	0	162	216	0
rand0020	300	2	827	846	5130	2,30	830	4840	0,36
rand0095	300	8	382	394	5787	3,14	384	5253	0,52
rand0136	300	16	324	339	2620	4,63	324	3067	0

Table 2. Comparison with PDF/IHS algorithm – the influence of tasks number

Algorithms were investigated by scheduling tasks represented with the same graph (50 STG tasks) on a different number of processors.

Numberof tasks	Numberof processors	PDF/IHS	Ant colony		Neural
		Cmax	Cmax	Number of iterations	Cmax	Number of iterations
50	2	228	228	132	228	92
50	4	114	114	1401	114	925
50	8	57	61	4318	58	4442
50	16	48	48	58	48	33

Table 3.

Minimization of C_max of dependent tasks (STG rand0008.stg)

Numberof tasks	Numberof processors	PDF/IHS	Ant colony		Neural
		Cmax	Cmax	Number of iterations	Cmax	Number of iterations
50	2	267	267	388	267	412
50	4	155	157	4487	160	3339
50	8	155	154	89	155	112
50	16	155	155	10	155	8

Table 4. Minimization of C_max of dependent tasks (STG rand0107.stg)

In all researched problems algorithms under comparison found optimal solution. The only difference can be observed in the number of iterations needed to find an optimal solution. ACO algorithm needed less iterations than neural one to find the solution.