# Multi-machine Scheduling with Setup Times

Wojciech Bożejko, Łukasz Kacprzak, Piotr Nadybski, Mieczysław Wodecki

► To cite this version:

Wojciech Bożejko, Łukasz Kacprzak, Piotr Nadybski, Mieczysław Wodecki. Multi-machine Scheduling with Setup Times. 15th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2016, Vilnius, Lithuania. pp.300-311, 10.1007/978-3-319-45378-1_27. hal-01637475

HAL Id: hal-01637475

https://inria.hal.science/hal-01637475

Submitted on 17 Nov 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Multi-machine scheduling with setup times

Wojciech Bożejko¹, Łukasz Kacprzak¹, Piotr Nadybski²,
and Mieczysław Wodecki³

¹ Department of Automatics, Mechatronics and Control Systems,
Faculty of Electronics, Wrocław University of Science and Technology,
Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland
{wojciech.bozejko,lukasz.kacprzak}@pwr.edu.pl

² Faculty of Technical and Economic Science
The Witelon State University of Applied Sciences in Legnica
Sejmowa 5a, 59-220 Legnica, Poland
nadybskip@pwsz.legnica.edu.pl

³ Institute of Computer Science, University of Wrocław
Joliot-Curie 15, 50-383 Wrocław, Poland
mieczyslaw.wodecki@uwr.edu.pl

**Abstract.** In this paper we are considering the problem of tasks scheduling executed simultaneously on multiple identical machines with a cost-criterion, which is the product of the tasks execution time and the number of used machines. Moreover, it is assumed that between the tasks performed sequentially there must be setup of the machines performed. Solution to the problem comes down to a generalization of a two-dimensional packing problem. The paper presents simulated annealing algorithm with different variants of packing strategy. The conducted computational experiments proved that designated solution differs little from some lower bounds for the constraints of the objective function.

# 1 Introduction

In the vast majority of the considered in the literature scheduling problems, it is assumed that a task is done on a single machine. However, in many real production processes, in particular - modern computational systems - a task execution requires the use of more than one machine (CPU), Bożejko et al. [5]. Then, we can talk about systems with parallel machines and multi-machine (multi-processor) tasks. We can meet such an approach also in cloud exploration [17]. In literature, such problems have been considered for a long time, for instance in the work of Drozdowski [8], [10] and in the monograph [9], Fleitelson [11], as well as in doctoral thesis of Kramer [13] where they mainly concern computer systems.

The first applications of multi-machine models of tasks scheduling refer not only to chemical industry (Bozoki and Richard [3]) but also to projects scheduling (Vizing [18]). The natural reference for this type of tasks are, examined from decades, multiprocessor computer systems (Błażewicz et al. [1]). In the vast majority of them the completion date of the execution of all tasks ($C_{max}$) was
maximized. Today, many computer centers offer performance of calculations and the cost of the service depends not only on the duration of the computations but also on the number of required processors. Therefore, there appears a need for the construction and testing of new, corresponding to the reality models and analysis of criterion functions taking into account the overall costs. We can en-couter similar issues in construction projects planning, where the simultaneous use of multiple resources is the basis for the organization of work.

The basic problem of multi-machine scheduling, $P|size_j|C_{max}$ (where P - is a symbol of multimachine, whereas $size_j$ — required number of machines) was studied mainly in reference to the approximate algorithms and the worst case scenario(Lin [15], Lloyd [16]). It has been proven that already in the case of two machines, the problem $P2|size_j|C_{max}$ is NP-hard. Błądek et al. [2] consider the problem with $C_{max}$ criterion assuming further that to certain tasks there must be assigned a fixed number of neighboring machines. In addition, it is assumed that the time of task scheduling undergoes learning or aging process, depending on the start of its execution.

In this paper we consider the problem of multi-machine scheduling, in which, between the tasks performed in sequence, there are additionally setups of machines introduced. In the case of construction processes, a setup is the time required for the movement of machines, equipment and employees. However, in computer systems, the setup time is related to the exchange (update) of the software transfer data/results, synchronization calculations, etc. Apart from the execution time of machine, the criteria, taking into account also other parameters (e.g. the number of used processors ) undoubtedly enable more accurate determination of the actual cost of operating of such a system.

## 2 Problem definition

The considered in the work problem of multi-machine tasks scheduling can be formulated as follows.

**Problem:** there is a set of tasks $\mathcal{J} = \{1,2,...,n\}$, given, which should be executed on identical machines (i.e. characterized with the same functional properties and equal capacities) from the set $\mathcal{M} = \{1,2,...,m\}$. Task $i \in \mathcal{J}$ requires at the same time execution of $size_i$ machines in $p_i > 0$ time units. Machines $l, k \in \mathcal{M}$ ($l \neq k$) are called *neighbouring*, if $k = l+1$ ($l = 1, 2, ..., m-1$) lub $k = l - 1$ ($l = 2, 3, ..., m$). By $s_{i,j}$ we denote the time of machine setup after the completion of task $i$ and before starting the task $j$ ($i, j \in \mathcal{J}$), where both tasks are performed on the same machine. At the same time the following restrictions must be met:

a) any machine, at any moment, cannot exercise more than one task,

b) the task execution cannot be interrupted,

c) each task is performed on the required number of neighboring machines,

d) between the tasks executed sequentially there must be setup of the machine performed.
We assume further that the number of machines is $m \ge \max\{size_i : i \in \mathcal{J}\}$.

The considered in the work problem (in short denoted by MPP) boils down to determining, for each task, a subset of machines and the starting moments of its execution (for each machine) satisfying the constraints (a)-(d), to optimize the adopted criterion. The first solution can be represented by a pair of $\Theta = (Q, S)$ is such that:

- $\mathbf{Q} = [Q_1, Q_2, ..., Q_n]$, where $Q_i (Q_i \subseteq \mathcal{M}, |Q_i| = size_i, )$ is a set of machines (assignment) on which the task $i \in \mathcal{J}$,

- $\mathcal{S} = [S_{1,1}, ..., S_{1,m}, S_{2,1}, ..., S_{2,m}, ..., S_{n,1}, ..., S_{n,m}]$, will be executed, where the element $S_{i,j}$ is the starting moment of task $i$ execution on machine $j$ (if $j \notin Q_i$, then we assume $S_{i,j} = -\infty$).

By $\Omega$ let us denote the set of all solutions to MPP problem.
For any solution $\Theta \in \Omega$

$$C_{\max}(\Theta) = \max\{S_{i,j} + p_i : i \in \mathcal{J}, j \in \mathcal{M}\}$$

is the moment of all task completion, and

$$M_{\max} = \max\{j : j \in Q_i, i \in \mathcal{J}\}$$

the maximum number of machine from all allocated to tasks execution. Let

$$F(\Theta) = C_{\max}(\Theta) \cdot M_{\max}(\Theta). \qquad (1)$$

We consider the problem of scheduling of Textbf MPP tasks consisting in determination of solution $\Theta^* \in \Omega$ such that

$$F(\Theta^*) = \min\{F(\Theta) : \Theta \in \Omega\}.$$

**Example.** There is a set of multi-machine tasks given $\mathcal{J} = \{1, 2, 3, 4, 5, 6\}$ to be executed on $m = 4$ machines from the set $\mathcal{M} = \{1, 2, 3, 4\}$. The parameters of the individual tasks are shown in Table 1 (it is assumed that the setup times equal 0).

<table><caption>Table 1: Tasks parameters.</caption><tr><td>task (j)</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr><tr><td>p<sub>j</sub></td><td>1</td><td>2</td><td>1</td><td>3</td><td>3</td><td>1</td></tr><tr><td>size<sub>j</sub></td><td>4</td><td>3</td><td>1</td><td>2</td><td>2</td><td>1</td></tr></table>

Figure 1 shows a Gantt diagram to certain solution $\Theta = (\mathbf{Q}, \mathcal{S})$, where $\mathbf{Q} = [Q_1, Q_2, Q_3, Q_4, Q_5, Q_6]$ and
$Q_1 = \{1, 2, 3, 4\}$, $Q_2 = \{2, 3, 4\}$, $Q_3 = \{1\}$, $Q_4 = \{3, 4\}$, $Q_5 = \{1, 2\}$, $Q_6 = \{1\}$. The beginning times of execution of tasks $S = (0, 0, 0, 0, -\infty, 1, 1, 1, 1, -\infty, -\infty, -\infty, -\infty, 3, 3, 3, 3, -\infty, -\infty, 2, -\infty, -\infty, -\infty)$. For this solution

$$M_{\max}(\Theta) = 4, C_{\max}(\Theta) = 6,$$

therefore the value of the goal function is $F(\Theta) = 24$.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Gantt diagram for solution $\Theta$.</figcaption></figure>

The work [14] proved that the problem of multi-machine task scheduling (without setup times) is NP-hard. Some lower and upper bound estimation of the criterion (1) were presented in work [10]. To solve the considered in the work MPP problem there was a simulated annealing algorithm presented. The starting moments of tasks execution $S$, at a fixed order, will be designated with the use of the algorithm solving two-dimensional packing problem (already one-dimensional problem of packing is strongly NP-hard, Garey et all. [12]).

## 3 Packing problem

Two-dimensional bin packing problem consists in such arrangement of rectangles, that the field occupied by them had minimum surface area. In the considered variant the rectangles, which contact the sides (hights) should be moved from one other to some extent. To put the matter more formally, it can be described as follows:

**Problem:** there is a set of rectangles $\mathcal{R} = \{r_1, r_2, ..., r_n\}$ given. The sizes of the rectangle $r_k \in \mathcal{R}$ are defined by a pair of numbers $t_k = (l_k, w_k)$, where $l_k$ denotes the height, whereas $w_k$ - width of the rectangle. By $d_{i,j}$ we denote the distance by which the rectangle $r_i$ must be moved from $r_j$, when they are placed right next to one another.
The considered problem is to find the G shape of a minimal surface area, within which it is possible to place all rectangles, i.e. minimization of the product,

$$ \Phi(G) = L \cdot W, \qquad (2) $$

where L is the height and W - the width of G. shape. In short, the considered in the paper packing problem will be denoted by **BBP**.

With each rectangle located within the G shape there is identified the position, in which it was enclosed, represented by the coordinates in a Cartesian coordinate system. The rectangles should be placed inside the G shape in such a way so as not to overlap one other, whereas their edges, representing respectively their length and width, were located parallely to the edges representing the length and width of G. shape. The interval in the horizontal plane, between any two rectangles $r_i, r_j \in \mathcal{R}$ cannot be less than the value $d_{r_i, r_j}$. The example illustrating the above-described definitions and indications is given in Fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2: G shape with enclosed rectangles</figcaption></figure>

It is easy to observe the following relationship:

**Corollary 1** *The problem of multi-machine task scheduling MPP is equivalent to the problem of two-dimensional bin packing BBP.*

## 3.1 Simulated annealing algorithm

The solution is represented in the form of a permutation (sequence) of rectangles

$$ \alpha = [r_1, r_2, \dots, r_n]. $$
On its basis, using the **packing strategy** (the decoding solution), there is the value of the solution determined, i.e. the surface area of the $G(\alpha)$ shape in which rectangles are placed. Permutation $\Lambda$ determines the order of rectangles in which they will be executed by the packing procedure. Let $\Omega$ be the set of all permutations of elements of $\mathcal{R}$, i.e. the set of feasible solutions. The simulated annealing algorithm (SA) will be used to search through this set.

The key elements of the algorithm are: initial temperature, probability function, with which the solutions worse than the current one, are accepted and cooling scheme (decreasing of the value) of the temperature.

In each step of the algorithm there are some elements the solutions space $\Lambda$ - neighborhood of the current solution considered. It is a set of elements, generated by small modifications of the considered solution. In the case where the current solution is worse than the one drawn from the neighborhood, it is replaced by it. With some probability, it is also possible to replace the current solution with the worse solution. This strategy is used not only to prevent stagnation but also to direct the trajectory of explorations in new areas of the solution space. The selection of temperature, cooling scheme and the probability function has influence on the frequency of accepting solutions worse than the current solutions, thus not only on the ability of the algorithm to leave local minima but also on the stability of the search itself.

Let $\alpha \in \Omega$ be any starting solution. By $\mathcal{N}(\alpha)$ we denote the neighborhood, whereas by $t$ the control parameter (temperature).

**Simulated annealing algorithm**

```
alpha_best ← alpha;
repeat
    repeat
        Randomly determine element $\beta$ from neighborhood $\mathcal{N}(\alpha)$;
        if $G(\beta) < G(\alpha)$ then $\alpha \leftarrow \beta$
        else
            if $\exp\{-(G(\beta) - G(\alpha))/t\} > \text{random}$ then $\alpha \leftarrow \beta$;
            if $G(\beta) < G(\alpha_{best})$ then
                $\alpha_{best} \leftarrow \beta$;
        until Change_control_parameter;
        Change control parameter $t$;
    until End_Condition.
```

Neighborhood $\mathcal{N}(\alpha)$ is generated by two types of random moves, namely - the swap and the twist type. Such neighborhoods are described in details in the works of Bożejko and Wodecki [4, 6, 7]. The temperature, in turn, is changed according to the geometric distribution, i.e. $t_{k+1} = t_k \cdot \lambda$ where $\lambda$ is such that $0, 8 \le \lambda < 1$.
## 3.2 Packing strategy

In the construction of rectangle packing procedures, i.e. in the process of determination of the shape (area) within which the rectangle is enclosed, there are different strategies applied. They differ from one another in the criteria for selecting the area (coordinates), in which the considered rectangle will be placed. In each of the used strategies we consider rectangles in the order they appear in the solution (permutation), at the same time trying to designate the space of the smallest possible surface area. A general description of the rectangle packing procedure is presented below.

Let $\alpha = [r_1, r_2, \dots, r_n]$ be a certain sequence (permutation) of rectangles. The rectangles are considered in the order they appear in $\alpha$. In i-th iteration of the procedure ($i = 1, 2, \dots, n$) we will enclose the rectangle $r_i$ to G shape (area), in which there are already enclosed rectangles $r_1, r_2, \dots, r_{i-1}$. The set $P_{i-1} = \{z_1, z_2, \dots, z_s\}$, where $z_i = (x_i, y_i)$ contains positions on which the considered rectangle is inserted (we assume that at the starting moment the area $G = \emptyset$ and $P_0 = \{(0,0)\}$). Next, rectangle $r_i$ is 'temporarily' placed into the G, area (shape) on each position from the set $P_{i-1}$. In this way, we generate a set of temporary areas $O = \{G_1, G_2, \dots, G_s\}$. Depending on the used packing strategy, we choose from O corresponding area (i.e. the coordinates of the point where we insert a rectangler $r_i$). If the area $G_l$, was chosen, then:

(i) rectangle $r_i$ is placed into the G shape on the position $z_l = (x_l, y_l)$,

(ii) the set of positions $P_i = P_{i-1} \setminus \{z_l\} \cup \{(x_l+d_{r_c,r_i} \cdot \delta, y_l), (x_l+d_{r_c,r_i} \cdot \delta, y_l+l_i)\}$, where $\delta \in \{0, 1\}$ and takes the value 1, if the placed rectangle $r_i$ was moved by size $d_{r_c,r_i}$, and position $z_l$ was created in the result of placing the rectangle $r_c$. Otherwise $\delta = 0$.

Next, we move to the next iteration. The procedure ends after placing all rectangles on their positions. When selecting position, in which the following rectangle is inserted, the following strategies were used:

1. *Minimum area* - the position, causing minimal enlargement of the area (2) is chosen, created as a result of the insertion of the considered rectangle,

2. *Area-sizes* - it is the development of the minimum area strategy. The value of the ratio is calculated, taking into account the surface area of the temporary (area) shape and the difference in the length of its sides. The purpose of application of this factor is to create areas having a uniform shape,

3. *Roulette* - the position is drawn in accordance with the principle of a roulette. The probability of drawing is proportional to the size of the temporary area,

4. *XYZ* - similarly as in the case of a roulette but the drawing is carried out according to the uniform distribution.

In the simulated annealing algorithm, each of the above-described packing strategy was implemented. For each designated by the algorithm solution $G$ there was *packing accuracy* calculated $T/\Phi(G)$, where $T$ is the sum of all the areas of rectangles (the lower bound of function $\Phi$).
## 4 Computational experiments

The computations were performed on a computer equipped with a 6-core Intel Core i7 X980 CPU (3.33GHz) and Linux operating system Ubuntu 12.04.5 LTS. For the purposes of computational experiments there were test data of varying degrees of heterogeneity randomly generated. The number of possible types of rectangles is 3(107), 5(101), 8(143), 10(134), 12(142), 15(129), 20(161). The total number of rectangles is given in brackets. The following values of the SA algorithm parameters were adopted: initial temperature $t_0 = 125$, rate of temperature change $\lambda = 0,98$, while the temperature change occurs every 100 iterations (return to the initial value every 500 iterations) and a maximum number of iterations is 5000. The results of the carried out study are presented in tables (2-5). Each row of the table contains the results obtained for one installation of test data: the number of types of rectangles (*Types*), the accuracy of the designated solution (*Accuracy*), the surface area of the shape (area) including the considered rectangles (*Shape area*), lengths of the shorter and the longer side of the surface area (*Shorter*, *Longer side*), the ratio of the longer side to the shorter side(*Ratio*) and the calculations time in seconds (*Time*). By far the best results for all instances of the problem were obtained by applying the strategy of minimum area (Table 2) in the packing procedure. For each example there was the shortest time of calculations observed. The parameter values *Ratio* were much greater than the value received after the application of other packing strategies (longer side was from 12.23 to 60.00 times larger than the shorter side). This strategy shows a clear preference of the surface area of the specified space. Using the Area-sizes ratio strategy (table 3) the results were only a little

<table><caption>Table 2: Minimum area strategy.</caption><thead><tr><td>Types</td><td>Accuracy</td><td>Shape area</td><td>Shorter side</td><td>Longer side</td><td>Ratio</td><td>Time</td></tr></thead><tbody><tr><td>3</td><td>0,920</td><td>489176</td><td>94</td><td>5204</td><td>55,36</td><td>56</td></tr><tr><td>5</td><td>0,873</td><td>677100</td><td>150</td><td>4514</td><td>30,09</td><td>37</td></tr><tr><td>8</td><td>0,850</td><td>766140</td><td>113</td><td>6780</td><td>60,00</td><td>117</td></tr><tr><td>10</td><td>0,860</td><td>641200</td><td>229</td><td>2800</td><td>12,23</td><td>162</td></tr><tr><td>12</td><td>0,842</td><td>689475</td><td>145</td><td>4755</td><td>32,79</td><td>171</td></tr><tr><td>15</td><td>0,874</td><td>699470</td><td>226</td><td>3095</td><td>13,69</td><td>102</td></tr><tr><td>20</td><td>0,841</td><td>892080</td><td>216</td><td>4130</td><td>19,12</td><td>160</td></tr></tbody></table>

worse than those listed in the table 2. With the use of this strategy the smallest value of the *Ratio* coefficient for the number of types 3, 8, 10, 12, 15 and 20 were obtained. For the two types 3 and 5, the values were the same as in the strategy Roulette strategy. The value of the *Ratio* parameter close to 1.00 means that shape of the designated area is close to the square.

The next two tables 4 and 5 include the results obtained after application of non-deterministic packing strategy in SW algorithm. The values of the solutions
<table><caption>Table 3: Area-sizes ratio strategy.</caption><thead><tr><td>Types</td><td>Accuracy</td><td>Shape area</td><td>Shorter side</td><td>Longer side</td><td>Ratio</td><td>Time</td></tr></thead><tbody><tr><td>3</td><td>0,861</td><td>522440</td><td>706</td><td>740</td><td>1,05</td><td>141</td></tr><tr><td>5</td><td>0,851</td><td>694540</td><td>820</td><td>847</td><td>1,03</td><td>115</td></tr><tr><td>8</td><td>0,832</td><td>782310</td><td>879</td><td>890</td><td>1,01</td><td>278</td></tr><tr><td>10</td><td>0,803</td><td>686412</td><td>828</td><td>829</td><td>1,00</td><td>217</td></tr><tr><td>12</td><td>0,816</td><td>711490</td><td>842</td><td>845</td><td>1,00</td><td>254</td></tr><tr><td>15</td><td>0,819</td><td>746496</td><td>864</td><td>864</td><td>1,00</td><td>190</td></tr><tr><td>20</td><td>0,804</td><td>933131</td><td>961</td><td>971</td><td>1,01</td><td>376</td></tr></tbody></table>

obtained with the use of the Roulette strategy (tab 4) were significantly worse than ones obtained with the use of Minimum area or area-size ratio strategy. Also, the time of computations was longer. For the two types 3 and 5 there were the biggest values of the Ratio parameter obtained.

<table><caption>Table 4: Roulette strategy.</caption><thead><tr><td>Types</td><td>Accuracy</td><td>Shape area</td><td>Shortest side</td><td>Longer side</td><td>Ratio</td><td>Time</td></tr></thead><tbody><tr><td>3</td><td>0,220</td><td>2042350</td><td>1396</td><td>1463</td><td>1,05</td><td>142</td></tr><tr><td>5</td><td>0,303</td><td>1947150</td><td>1379</td><td>1412</td><td>1,02</td><td>121</td></tr><tr><td>8</td><td>0,183</td><td>3565740</td><td>1774</td><td>2010</td><td>1,13</td><td>317</td></tr><tr><td>10</td><td>0,256</td><td>2151000</td><td>1434</td><td>1500</td><td>1,05</td><td>268</td></tr><tr><td>12</td><td>0,193</td><td>3009260</td><td>1704</td><td>1766</td><td>1,04</td><td>315</td></tr><tr><td>15</td><td>0,201</td><td>3043580</td><td>1689</td><td>1802</td><td>1,07</td><td>238</td></tr><tr><td>20</td><td>0,148</td><td>5069220</td><td>2075</td><td>2443</td><td>1,18</td><td>444</td></tr></tbody></table>

While applying the strategy XYP (the results - Table 5) there were the worst solutions, for the six types, obtained. This concerned both the computation time and the accuracy. Generally, deterministic strategies proved to be much better than probabilistic ones. If we take into account only the surface area, it is better to use the Minimum area strategy. On the other hand, when we are looking for an area of shape similar to a square, then it is better to use the Area-sizes strategy. For the determination of costs of multiprocessor tasks, the choice of packing strategy, depends on the relationship between the time of CPU utilization (computations time) and the number of processors used.

**Simulated Annealing and Genetic Algorithm comparison** The canonical version of the Genetic algorithm was adopted. The algorithm has been configured as follows. For crossover, the PMX method was used, the Mutation was based on random chromosome fields exchange. The stopping condition was the maximum iteration number – 5000.
<table><caption>Table 5: XYP strategy.</caption><thead><tr><th>Types</th><th>Accuracy</th><th>Shape area</th><th>Shorter side</th><th>Longer side</th><th>Ratio</th><th>Time</th></tr></thead><tbody><tr><td>3</td><td>0.134</td><td>3352340</td><td>1713</td><td>1957</td><td>1.14</td><td>180</td></tr><tr><td>5</td><td>0.244</td><td>2423280</td><td>1366</td><td>1774</td><td>1.30</td><td>154</td></tr><tr><td>8</td><td>0.157</td><td>4158810</td><td>1622</td><td>2564</td><td>1.58</td><td>423</td></tr><tr><td>10</td><td>0.182</td><td>3035430</td><td>1305</td><td>2326</td><td>1.78</td><td>354</td></tr><tr><td>12</td><td>0.167</td><td>3476110</td><td>1547</td><td>2247</td><td>1.45</td><td>417</td></tr><tr><td>15</td><td>0.168</td><td>3632800</td><td>1353</td><td>2685</td><td>1.98</td><td>315</td></tr><tr><td>20</td><td>0.151</td><td>4966610</td><td>1793</td><td>2770</td><td>1.54</td><td>604</td></tr></tbody></table>

<table><caption>Table 6: Simulated Annealing and Genetic algorithms comparison</caption><thead><tr><th rowspan="2"></th><th colspan="3">Simulated Annealing</th><th colspan="3">Genetic Algorithm</th></tr><tr><th>Accuracy</th><th>Ratio</th><th>Time</th><th>Accuracy</th><th>Ratio</th><th>Time</th></tr></thead><tbody><tr><td>Area</td><td>0.920</td><td>55,36</td><td>55,7</td><td>0.920</td><td>55,36</td><td>15</td></tr><tr><td>Area-sizes</td><td>0.861</td><td>1,05</td><td>140,9</td><td>0.894</td><td>1,05</td><td>16</td></tr><tr><td>Roullette</td><td>0.220</td><td>1,05</td><td>141,7</td><td>0.256</td><td>1,16</td><td>149</td></tr><tr><td>XYP</td><td>0.134</td><td>1,14</td><td>180,0</td><td>0.323</td><td>1,86</td><td>34</td></tr><tr><td>Area</td><td>0.873</td><td>30,09</td><td>36,5</td><td>0.872</td><td>58,11</td><td>21</td></tr><tr><td>Area-sizes</td><td>0.851</td><td>1,03</td><td>114,8</td><td>0.892</td><td>1,00</td><td>23</td></tr><tr><td>Roullette</td><td>0.303</td><td>1,02</td><td>121,1</td><td>0.346</td><td>1,22</td><td>130</td></tr><tr><td>XYP</td><td>0.244</td><td>1,30</td><td>154,3</td><td>0.462</td><td>1,24</td><td>37</td></tr><tr><td>Area</td><td>0.850</td><td>60,00</td><td>117,4</td><td>0.898</td><td>15,31</td><td>30</td></tr><tr><td>Area-sizes</td><td>0.832</td><td>1,01</td><td>278,1</td><td>0.866</td><td>1,00</td><td>63</td></tr><tr><td>Roullette</td><td>0.183</td><td>1,13</td><td>317,4</td><td>0.236</td><td>1,44</td><td>345</td></tr><tr><td>XYP</td><td>0.157</td><td>1,58</td><td>423,3</td><td>0.313</td><td>1,78</td><td>88</td></tr><tr><td>Area</td><td>0.860</td><td>12,23</td><td>161,8</td><td>0.887</td><td>11,61</td><td>44</td></tr><tr><td>Area-sizes</td><td>0.803</td><td>1,00</td><td>217,1</td><td>0.845</td><td>1,00</td><td>44</td></tr><tr><td>Roullette</td><td>0.256</td><td>1,05</td><td>268,3</td><td>0.305</td><td>1,04</td><td>322</td></tr><tr><td>XYP</td><td>0.182</td><td>1,78</td><td>354,2</td><td>0.418</td><td>1,22</td><td>69</td></tr><tr><td>Area</td><td>0.842</td><td>32,79</td><td>170,9</td><td>0.903</td><td>20,30</td><td>54</td></tr><tr><td>Area-sizes</td><td>0.816</td><td>1,00</td><td>254,4</td><td>0.852</td><td>1,00</td><td>52</td></tr><tr><td>Roullette</td><td>0.193</td><td>1,04</td><td>315,2</td><td>0.261</td><td>1,04</td><td>340</td></tr><tr><td>XYP</td><td>0.167</td><td>1,45</td><td>416,8</td><td>0.356</td><td>1,24</td><td>89</td></tr><tr><td>Area</td><td>0.874</td><td>13,69</td><td>101,6</td><td>0.903</td><td>13,79</td><td>36</td></tr><tr><td>Area-sizes</td><td>0.819</td><td>1,00</td><td>190,3</td><td>0.851</td><td>1,01</td><td>44</td></tr><tr><td>Roullette</td><td>0.201</td><td>1,07</td><td>238,3</td><td>0.306</td><td>1,03</td><td>280</td></tr><tr><td>XYP</td><td>0.168</td><td>1,98</td><td>315,0</td><td>0.390</td><td>1,33</td><td>60</td></tr><tr><td>Area</td><td>0.841</td><td>19,12</td><td>160,1</td><td>0.853</td><td>9,58</td><td>54</td></tr><tr><td>Area-sizes</td><td>0.804</td><td>1,01</td><td>376,1</td><td>0.835</td><td>1,01</td><td>91</td></tr><tr><td>Roullette</td><td>0.148</td><td>1,18</td><td>443,5</td><td>0.218</td><td>1,07</td><td>489</td></tr><tr><td>XYP</td><td>0.151</td><td>1,54</td><td>603,8</td><td>0.266</td><td>1,64</td><td>132</td></tr></tbody></table>
There are Accuracy, Ratio and Time results, for all strategies combined with Simulated Annealing and Genetic Algorithm compared in Table 6. The results are organized in four-row data structures, for all test data instances (3, 5, 8, 10 12, 15 and 20 types). Each row presents results for particular strategy and data set. The usage of Genetic algorithm in most cases improved the Accuracy results, especially for XYP strategy. Thirteen times the Ratio had greater value when Simulated Annealing algorithm was used, six times the result was equal. This means that structures built with Genetic Algorithm had the shape close to square more often. The computation time was shorter in all cases for Area, Area-sized and XYP strategy combined with Genetic Algorithm. Roulette packing strategy had shorter execution time with Simulated Annealing than with Genetic Algorithm.

# 5 Conclusions

In the paper there was the problem of multi-machine tasks scheduling with setup times and minimizing the product of the number of machines used and the length of time of all tasks execution considered. Designation of a solution can be brought down to a two-dimensional rectangles packing problem with minimization of the surface area of the occupied area (shape). The simulated annealing algorithm using different packing strategies was presented in the work, i.e. placing rectangles within the proposed area. The conducted computational experiments showed that the designated surface area (to solve the tasks scheduling problem) are only slightly greater than the sum of surface areas of all the rectangles (i.e. the lower bound).

# References

1. Błażewicz J., Drabowski M., Węglarz J.: Scheduling multiprocessor tasks to minimize schedule length. IEEE Transactions on Computers Volume: C-35, Issue 5, 389-393 (1986)

2. Bładek I., Drozdowski M., Guinand F., Schepler X.: On contiguous and non-contiguous parallel task scheduling. Journal of Scheduling 18, 487-495 (2015)

3. Bozoki, G., Richard, J.-P.: A branch-and-bound algorithm for the continuous-process job-shop scheduling problem. AIIE Transactions 2/3, 246-252 (1970)

4. Bożejko W., Wodecki M.: On the theoretical properties of swap multimoves. Operations Research Letters 35/2, 227-231 (2006)

5. Bożejko W., Gniewkowski Ł., Wodecki M.: Solving timetabling problems on GPU. Lecture Notes in Artificial Intelligence No. 8468, 445-455 (2014)

6. Bożejko W., Wodecki M.: Solving Permutational Routing Problems by Population-Based Metaheuristics. Computers & Industrial Engineering 57, 269-276 (2009)

7. Bożejko W., Wodecki M.: Parallel genetic algorithm for the flow shop scheduling problem. Lecture Notes in Computer Science No. 3019, 566-571 (2004)

8. Drozdowski M.: Scheduling multiprocessor tasks an overview. European Journal of Operational Research 94, 215-230 (1996)
9. Drozdowski M.: Select problems of scheduling tasks in multiprocessor computer system. Poznań University of Technology Press, Series: Monographs, No. 321 (1997)

10. Drozdowski M.: Scheduling for parallel Processing. Computer Communications and Network, Springer (2009)

11. Feitelson D.G., Rudolph L., Schwiegelshohn U., Sevcik K.C., Wang P.: Theory and practice in parallel job scheduling. Lecture Notes in Computer Science No. 1291, 1–34 (1997)

12. Garey M.R., Johnson D.S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco (1979)

13. Kramer A.: Scheduling multiprocessor tasks on dedicated processors. PhD Thesis, Fachbereich Mathematik/Informatik, Univeristat Osnabruck (1995)

14. Lee C.Y., Cai X.: Scheduling one and two-processor tasks on two parallel processors. IIE Transactions 31(5), 445–455 (1999)

15. Lin J., Chen S.: Scheduling algorithm for nonpreemptive multiprocessor tasks. Computers and Mathematics with Applications 28/4, 85–92 (1994)

16. Lloyd E.: Concurrent task system. Operations Research 29/1, 189–201 (1981)

17. Smutnicki C., Pempera J., Rudy J., Żelazny D.: A new approach for multi-criteria scheduling. Computers & Industrial Engineering 90, 212–220 (2015)

18. Vizing, V.: About schedules observing deadlines, Kibernetika 1, 128–135 (1981)