TORSCHE Scheduling
Toolbox for Matlab

Imagine that you are a man, who repairs watches. Your boss gave you a list of repairs, which have to be done tomorrow. Our goal is to decide, how to organize the work to meet all desired finish times if possible.

List of repairs:

Batteries will be delivered to you at 9:00, seal ring at 11:00 and the hand for watch number 2 at 10:00.

Time of repairs:

Let’s look at the list more closely and try to extract and store the information we need to organize the work (see Table 11.1, “Information we need to organize the work”). We consider working day starts at 8:00.

Solution of the case study is shown in five steps:

Figure 11.1. Result of case study as Gantt chart

Transportation of goods by two conveyor belts is a simple example of using List Scheduling in practice. Construction material must be carried out from place to place with minimal time effort. Transported articles represent five kinds of construction material and two conveyor belts as processors are available. Table 11.2, “Material transport processing time.” shows the assignment of this problem.

Solution of the case study is shown in five steps:

Figure 11.2. Result of case study as Gantt chart

This example is slightly more difficult and demonstrates some of advanced possibilities of the toolbox. It solves a problem of chair manufacturing by two workers (cabinetmakers). Their goal is to make four legs, seat and backrest of the chair and assembly all of these parts with minimal time effort. Material, which is needed to create backrest, will be available after 20 time units of start and assemblage is divided out into two stages. Figure 11.3, “Graph representation of Chair manufacturing” shows the mentioned problem by graph representation.

Figure 11.3. Graph representation of Chair manufacturing

Solution of the case study is shown in six steps:

Figure 11.4. Result of case study as Gantt chart

As an illustration, an example application of RLS (Recursive Least Squares) filter for active noise cancellation is shown in Figure 11.5, “An application of Recursive Least Squares filter for active noise cancellation.” [RLS03]. The filter uses HSLA [HSLA02], a library of logarithmic arithmetic floating point modules. The logarithmic arithmetic is an alternative approach to floating-point arithmetic. A real number is represented as the fixed point value of logarithm to base 2 of its absolute value. An additional bit indicates the sign. Multiplication, division and square root are implemented as fixed-point addition, subtraction and right shift. Therefore, they are executed very fast on a few gates. On the contrary addition and subtraction require more complicated evaluation using look-up table with second order interpolation. Addition and subtraction require more hardware elements on the target chip, hence only one pipelined addition/subtraction unit is usually available for a given application. On the other hand the number of multiplication, division and square roots units can be nearly by arbitrary.

Figure 11.5. An application of Recursive Least Squares filter for active noise cancellation.

RLS filter algorithm is a set of equations (see the inner loop in Figure Figure 11.6, “The RLS filter algorithm.”) solved in an inner and an outer loop. The outer loop is repeated for each input data sample each 1/44100 seconds. The inner loop iteratively processes the sample up to the N-th iteration (N is the filter order). The quality of filtering increases with increasing number of filter iterations. N iterations of the inner loop need to be finished before the end of the sampling period when output data sample is generated and new input data sample starts to be processed.

The time optimal synthesis of RLS filter design on a HW architecture with HSLA can be formulated as cyclic scheduling on one dedicated processor (add unit) [Sucha04]. The tasks are constrained by precedence relations corresponding to the algorithm data dependencies. The optimization criterion is related to the minimization of the cyclic scheduling period w (like in an RLS filter application the execution of the maximum number of the inner loop periods w within a given sampling period increases the filter quality).

for (k=1;k<HL;k=k+1)
   E(k)  = E(k-1) - Gfold(k) * Pold(k-1)
   f(k)  = Gold(k-1) * E(k-1)
   P(k)  = Pold(k-1) - Gbold(k) * E(k-1)
   b(k)  = G(k-1) * P(k-1)
   A(k)  = A(k-1) - Kold(k) * P(k-1)
   Gf(k) = Gfold(k) + bnold(k) * E(k)
   F(k)  = L * Fold(k) + f(k) * E(k-1) + T
   B(k)  = L * Bold(k) + b(k) * P(k-1) + T
   fn(k) = f(k) / F(k)
   bn(k) = b(k) / B(k)
   Gb(k) = Gbold(k) + fn(k) * P(k)
   K(k)  = Kold(k) + bn(k) * A(k)
   G(k)  = G(k-1) - bn(k) * b(k)
end

Figure 11.6, “The RLS filter algorithm.” shows the inner loop of RLS algorithm. Data dependencies of this problem can be modeled by graph rls_hsla in Figure 11.7, “Graph G modeling the scheduling problem on one add unit of HSLA.”, where nodes represent particular operations of the RLS filter algorithm on add unit, i.e. a task on the dedicated processor. First user parameter on node represents processing time of task (time to `feed' the add unit ). The second one is a number of dedicated processor (unit). User parameters on edges are lengths and heights, explained in Section Cyclic scheduling (General).

Figure 11.7. Graph G modeling the scheduling problem on one add unit of HSLA.

Solution of this scheduling problem is shown in following steps:

Figure 11.8. Resulting schedule of RLS filter.