In the study of Niroomand and Vizvari (
2015), three approaches are used to obtain an initial solution, e.g. (1) the cables with the same colour are grouped and the total processing time of each group is calculated. Then, the groups are arranged in descending order of the total processing time, (2) the cables are grouped according to the size, and the total processing time of each group is calculated. Then, the groups are arranged in descending order of the total processing time, (3) no grouping policy is applied, and the cables are arranged in descending order of their processing time. In that study it is proved that the first initial solution takes less total setup time which decreases the setup dependent labour cost which is a part of the objective function (
1). Of course, all the three initial solutions try to have less inventory holding cost (because of descending order of processing times). Finally, they applied two metaheuristic approaches, e.g. simulated annealing (SA) and variable neighbourhood search (VNS), using each of the obtained initial solutions separately. As a typical experimental result of their study, the initial solution (
1) results in a much better final solution than the others.
In this study, we develop some hybrid metaheuristics combining tabu search algorithm with SA and VNS separately. These hybrid approaches use the initial solution (
1) proposed by Niroomand and Vizvari (
2015) and try to improve it to obtain a better final solution than what was obtained by Niroomand and Vizvari (
2015). In the rest of this section, the initial solution and the proposed hybrid algorithms are explained.
4.1 EncodingDecoding Method and Initial Solution Generation
Any solution generated in the metaheuristic approaches of this study is represented as a vector of numbers. Each number shows a cable type. So, a vector illustrates a sequence of cables to be produced according to their order in the vector. For instance, a solution represented by vector (4, 2, 3, 1, 5) is shown by Fig.
1.
Fig. 1
A production schedule of the solution shown by vector (4, 2, 3, 1, 5).
In the solution represented by Fig.
1, the completion time of cable 5 is considered as the given due date of the cables (
T). So, automatically a required idle time (
${T_{0}}$) is applied here without needing to calculate it. Then, to calculate the objective function value of this solution, its inventory holding cost, processing cost, and setup cost, according to the concepts of the model (
1)–(
11), are calculated and summed up.
Now, to generate a good initial solution, a sequence of cables should be minimized from three points of view, e.g. total setup cost, total inventory holding cost, and total processing cost. As the processing times are constant values, so the total processing cost is always fixed and cannot be decreased. Therefore, in an initial solution we try to decrease the other cost types.
In order to generate an initial solution with lowest possible setup cost, the following theorem is introduced.
Theorem 1.
If in the vector of a solution, the cables with the same colour are produced consecutively in a way that the last cable of a colour has the same size with the first cable of the next colour, the solution has the minimum possible setup cost. In this case, the cables with the same colour are called a set of cables. An example of this type of solutions for 3
colours $(v=3)$ and 3
sizes $(w=3)$ is illustrated by Fig. 2.
Proof.
According to the data given in Section
2, in general case when there exist
n cables with
v colours and
w sizes, the number of
$S1$ setup type is
$v1$ and the number of
$S2$ setup type is equal to
$(vw1)(v1)$, while there is no
$S3$ setup type in this order of cables. Note that any change in the order of the cables in this type of solutions will increase the number of
$S1$ and
$S3$ setup types. As the relation
$\text{Setup cost}\hspace{2.5pt}(S2)<\text{Setup cost}\hspace{2.5pt}(S1)<\text{Setup cost}\hspace{2.5pt}(S3)$ exists, the theorem is proved. □
For any solution which follows the concepts of Theorem
1, it is possible to decrease its inventory holding cost by applying the following rules. These rules may help to generate a more efficient solution from inventory holding cost point of view.
Rule 1. If the cables are sequenced based on Theorem
1, the sets of cables (as defined in Theorem
1) are arranged in descending order of the below given value which is calculated for each set. This rule may cause less inventory holding time that results in less inventory holding cost.
where
S is total setup time of each set of cables which is the same for all sets and is calculated as
$S=w{s_{2}}+{s_{1}}$. Note that
${s_{1}}$ and
${s_{2}}$ are the setup times of
$S1$ and
$S2$ setup types, respectively.
Fig. 2
A schematic representation of the example of Theorem
1.
An evidence for this rule is mentioned here. Consider two sets A and B with an extra assumption that the inventory holding time of all units of cables of each set starts together immediately after processing all cables of that set. If an initial order of these sets is A and then B, supposing that the interchanged order of these sets results in less total inventory holding time, therefore,
Inventory holding time of sequence $B,A\leqslant $ Inventory holding time of sequence A, B.
Rule 2. In a solution satisfying Theorem
1 and Rule 1, in any set of cables (defined in Theorem
1) all cables, except for the first and the last cable of the set, are arranged in descending order of the below given value which is calculated for each of those cables. This rule also may result in less inventory holding time and, consequently, less inventory holding cost.
An evidence for this rule is mentioned here. Consider two cables
i and
j from any set of cables with initial sequence of
i and then
j. Suppose that the interchanged order of these sets results in less total inventory holding time, therefore,
Inventory holding time of sequence $i,j\leqslant $ Inventory holding time of sequence j, i.
The abovementioned theorem and rules are used to generate a good initial solution for the metaheuristic approaches that will be introduced in the rest of this section. The procedure of generating an initial solution is summarized in the pseudo code that is shown by Fig.
3.
4.2 Neighbourhood Search Operators
As the initial solution obtained by Algorithm 1 will be used in some metaheuristic approaches which are presented in the following sections, three neighbourhood search operators are introduced in this subsection. These operators are designed in a way to respect the previously mentioned theorem and rules.
Fig. 3
Pseudo code for generating an initial solution.
4.2.1 Neighbourhood Search Operator 1 (${\textit{SO}_{1}}$)
${\textit{SO}_{1}}$ is designed in a way to maintain all characteristics of an initial solution which is obtained by Algorithm 1. In a neighbour obtained by
${\textit{SO}_{1}}$, Theorem
1, Rule 1, and Rule 2 are respected. This operator is explained by the pseudo code of Fig.
4.
Fig. 4
Pseudo code of neighbourhood search operator 1 (${\textit{SO}_{1}}$).
${\textit{SO}_{1}}$ may give a neighbour solution with better objective function value than the initial solution. The generated neighbour solution has the same setup, scrap, and processing cost comparing to the initial solution but its inventory holding cost may be decreased as the sequence of cables is changed.
4.2.2 Neighbourhood Search Operator 2 (${\textit{SO}_{2}}$)
Applying
${\textit{SO}_{2}}$ on a set of cables with colour
i, two cables with different sizes from this colour set are selected randomly by generating two random numbers between 2 and
$w1$ (to respect Theorem
1, all sizes of the selected colour set can be selected, except for the first and last cable of the set) and are interchanged. In the neighbour solution generated by this operator, Theorem
1 and Rule 1 are respected while Rule 2 is not considered in the set of cables with colour
i.
4.2.3 Neighbourhood Search Operator 3 (${\textit{SO}_{3}}$)
Using ${\textit{SO}_{3}}$, a set of cables with colour i is selected. Two random numbers between 2 and $w1$ are generated. Then the sizes of cables which are associated to the generated random numbers in sets i and $i+1$ are interchanged separately. It seems that ${\textit{SO}_{2}}$ is done on two consecutive sets with the same random numbers.
4.3 Tabu Search Hybridized by Simulated Annealing (TSSA)
Tabu Search (TS) (see Lamghari and Dimitrakopoulos,
2012; Li and Gao,
2016) and Simulated Annealing (SA) (see Kirkpatrick
et al.,
1983; Niroomand
et al.,
2016) are two famous single solution based metaheuristic algorithms which have been widely applied to solve combinatorial optimization problems.
TS starts with a current solution (initial solution). This current solution is also marked as the best solution. Then TS uses some directions of searching space and finds some neighbour solutions. The best neighbour solution of the discovered neighbours can be used for three purposes, (1) it is saved as the best solution if it is better than the current best solution, (2) the best neighbour and also its neighbourhood direction is marked as a tabu solution and direction and saved in a tabu list, and (3) it is saved as the current solution. Then the algorithm is repeated for a number of iterations. In order to avoid repeating some previously considered current solutions, in each iteration the neighbour solutions obtained by tabu searching directions are not considered as a new current solution unless they are better than the best obtained solution. This condition is named aspiration criteria. Considering tabu list and aspiration criteria together is one of the advantages of TS which avoid cycling in searching procedure. When last iteration is done, the best solution is introduced as the best obtained solution of TS.
SA starts with an initial solution (called current solution and also best solution) in an initial state called initial temperature (current temperature). In the current temperature for a number of iterations, the current solution is tried to be improved by generating its neighbour solutions. Each generated neighbour solution could be used for the following purposes, (1) to be used instead of the best solution and the current solution if it has better objective function value than the best solution, (2) to be used instead of the current solution if it has better objective function value than just the current solution, and (3) to be used instead of the current solution if the condition $\exp (\frac{f(\mathrm{neighbour})f(\mathrm{current})}{\mathrm{current}\mathrm{temperature}})\geqslant r$ is held, where f is the objective function value and r is a fractional random number. Otherwise, the neighbour solution is ignored and the current and best solutions remain unchanged. Notably, after generating a neighbour solution the current and best solutions are updated (not necessarily) and the current solution is used for next neighbour generation. When the iterations of the current temperature are done, the current temperature is cooled down by a cooling ratio and the iterations are repeated in this current temperature. SA continues until the current temperature reaches a given final temperature. At the end, the best solution is introduced as the best obtained solution of SA.
In this study, TS is hybridized by SA. To combine these two algorithms and fit them to the problem of Section
3, in the first iteration of the TS the following is done:

• The initial solution obtained by Section
4.1 is used as current (initial) solution.

• Each colour of the cables in the initial solution is considered as a searching direction (except for the last one, because neighbourhood search operator 1 cannot be applied in this case).

• In each searching direction of the initial solution (current solution), an SA algorithm using neighbourhood search operator 1, is applied as a local search to obtain the best possible neighbour solution in each searching direction separately.

• The best obtained neighbour among all searching directions is saved instead of the current solution of the TS and this searching direction is added to the list of tabu directions.
The TSSA algorithm continues to the consequent iterations considering the current solution. Pseudo code of this hybrid algorithm is shown by Fig.
5, where the parameters used in the algorithm are noted in Table
2.