Any solution generated in the meta-heuristic 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.

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.

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. (12) S + ∑ i ∈ I t i q i ∑ i ∈ I q i , ∀ I ∈ { 1 , 2 , … , v } , 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 S 1 and S 2 setup types, respectively.

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 ⩽ Inventory holding time of sequence A, B.

So, (13) ( T − S − ∑ i ∈ B t i q i ) ( ∑ i ∈ B q i ) + ( T − S − ∑ i ∈ B t i q i − S − ∑ i ∈ A t i q i ) ( ∑ i ∈ A q i ) ⩽ ( T − S − ∑ i ∈ A t i q i ) ( ∑ i ∈ A q i ) + ( T − S − ∑ i ∈ A t i q i − S − ∑ i ∈ B t i q i ) ( ∑ i ∈ B q i ) , which implies, (14) S + ∑ i ∈ B t i q i ∑ i ∈ B q i ⩾ S + ∑ i ∈ A t i q i ∑ i ∈ A q i .

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. (15) s 2 q j + t j , ∀ j ∈ { 2 , … , w − 1 } in each set . 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 ⩽ Inventory holding time of sequence j, i.

Then, (16) ( T − ( s 2 + t j q j ) ) q j + ( T − ( s 2 + t i q i ) − ( s 2 + t j q j ) ) q i ⩽ ( T − ( s 2 + t i q i ) ) q i + ( T − ( s 2 + t j q j ) − ( s 2 + t i q i ) ) q j , which implies, (17) s 2 q j + t j ⩾ s 2 q i + t i .

The above-mentioned theorem and rules are used to generate a good initial solution for the meta-heuristic 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.

As the initial solution obtained by Algorithm 1 will be used in some meta-heuristic approaches which are presented in the following sections, three neighbourhood search operators are introduced in this sub-section. These operators are designed in a way to respect the previously mentioned theorem and rules.

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 meta-heuristic 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 ( f ( neighbour ) − f ( current ) current temperature ) ⩾ 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.

Another hybridization of the TS is done by help of Variable Neighbourhood Search (VNS) algorithm. The structure of this hybrid algorithm (TS-VNS) is the same as the structure of TS-SA algorithm. The only difference is that instead of the SA algorithm, a VNS algorithm is used. The VNS is of single solution based meta-heuristics which starts with an initial (current) solution and uses a set of some different neighbourhood search operators to explore neighbour solutions. Focusing on the initial (current) solution, first search operator is applied for a number of iterations. The best obtained neighbour solution is saved as the current solution and the algorithm is repeated in the same way for other neighbourhood search operators. At the end, current solution is introduced as the best obtained solution of the VNS.

Pseudo code of this hybrid algorithm is shown by Fig. 6, where the parameters used in the algorithm are noted in Table 3.

In this study, the hybrid meta-heuristic algorithms are proposed in order to improve the performance of the classical algorithms TS, VNS, and SA. Therefore, the proposed TS-VNS and TS-SA have the following advantages comparing to the classical algorithms: •

The classical TS has a simple neighbourhood search structure. The proposed TS-SA applies the SA as a local search mechanism in order to improve the search structure of TS.

To study the performance of the proposed algorithms, some benchmark problems are needed. The study of Niroomand and Vizvari (2015) contains just one benchmark (obtained from the case of the study) which is a large-sized benchmark containing 15 colours and 10 sizes. In this study, that benchmark is considered as the largest benchmark and for generating some other benchmarks, its sizes are decreased. Notably, the values of data (explained in Section 2) in the generated benchmarks remain unchanged, just the size of matrices and vectors which contain data are decreased by removing extra rows and columns. These benchmarks are detailed in Table 4.

Any meta-heuristic algorithm consists of some parameters which should be fixed in advance. As most of algorithms behave randomly, the values given for their parameters may affect the quality of obtained solutions. Generally larger values for parameters result in larger CPU running time and maybe better result. This relation cannot be true always. Therefore, parameters of meta-heuristic algorithms should be tuned before performing final experiments. The tuning procedure can be done to optimize one or more responses obtained from running an algorithm for a benchmark. In most of studies, the tuning procedure is done to study the effect of parameters’ levels for obtaining solutions with better objective function. As a more complete study on the behaviour of parameters, except quality of solutions, CPU running time also can be considered as another response, meaning that a multi-response study can be done to tune the parameters of a meta-heuristic algorithm.

To tune the parameters of the proposed algorithms of this study, two responses of objective function value (quality) and CPU running time are considered to be optimized. To optimize the parameters’ levels according to these two responses, a method based on regression analysis is done. The method previously was introduced by Pasandideh et al. (2015). The steps of this method are explained here:

Step 1: Select an algorithm to tune its parameters. Select a proper interval for each parameter of the selected algorithm.

Step 2: Select a proper benchmark and randomly generate a proper number of test problems for that benchmark. Notably, the values of parameters in each test problem are uniformly generated within the intervals specified in Step 1.

Step 3: Run each test problem by the selected algorithm and obtain the values of required responses.

Step 4: Linearly normalize the values of parameters and responses of each test problem. Find quadratic regression function of each response separately. For example, a quadratic regression function for a response (say R i ) dependent on three parameters of an algorithm (say P 1 , P 2 , P 3 ) is as follows: (18) E ( R i ) = β 0 + β 1 P 1 + β 2 P 2 + β 3 P 3 + β 11 P 1 2 + β 22 P 2 2 + β 33 P 3 2 + β 12 P 1 P 2 + β 13 P 1 P 3 + β 23 P 2 P 3 , where β i , β i i and β i j are the linear, quadratic and interaction coefficients, respectively.

Step 5: Find the weighted sum of all E ( R i ) as follows: (19) E ( R ) = ∑ i = 1 N w i ( E ( R i ) ) , where w i is the importance weight of response i, N is the number of responses and ∑ i = 1 N w i = 1.

Step 6: Solve the following non-linear mathematical model to obtain the most effective levels of the parameters. (20) max E ( R ) (21) subject to All interval of the parameters To apply the above-mentioned steps to the proposed algorithms of this study, the proper interval of each parameter is selected (see Table 5). The benchmark number 4 is selected to tune the parameters. 50 test problems were generated uniformly considering the specified intervals of the parameters. To overcome the randomness of the algorithms, each test problem was run for five times. The average response values (objective function value and CPU time) of the 5 runs of each test problem is considered in regression analysis. Finally, the best obtained levels of the parameters are shown by Table 5.

Notably, when performing Step 6 of the tuning procedure, the w i values are assumed to be equal to 0.5. Although, in meta-heuristic algorithms, higher values of parameters may result in better solution, this is correct for the cases when the only response is objective function value. In the case of this study, as CPU time is also considered as a response, therefore, some parameters may not get their highest level as best level.

The best level obtained for each parameter is applied to perform the final experiments on the benchmarks.

The best level of the parameters reported in Table 5 is applied in the proposed algorithms to perform the final experiments on all the benchmarks of Table 4. To compare the results of the proposed algorithms with the methods of literature, the SA and VNS algorithms of Niroomand and Vizvari (2015) are simulated and applied. Notably, these algorithms are used with the best levels of their parameters reported in Table 5, except for the parameter Q (as these methods do not have such parameter). All the four algorithms for each benchmark are allowed to run for 1000 v w milliseconds. To obtain more reliable results, each benchmark with each algorithm is run for 10 times. For more comparison, the proposed formulation (1)–(11) is coded by the GAMS and the benchmarks of Table 4 are solved by the CPLEX solver of the GAMS as an exact method. This solver uses Branch and Bound method as a solution approach. For this aim, the running time of 3 hours (10800 seconds) is considered for all benchmarks. The results obtained by the meta-heuristic algorithms and the exact method of GAMS are shown by Table 6.

The results of Table 6 are normalized to be plotted for graphical illustrations. The graphs of normalized results for minimum, average and maximum values of Table 6 are shown by Figs. 7–9. As can be seen from the table and figures, in most of the benchmarks the TS-SA performs better than the other algorithms in the case of minimum, average, and maximum obtained solutions. There is just one exception that in the second benchmark (B2) the minimum obtained value for the VNS is better than the others. For the case of exact solution method, as mentioned above, 10800 seconds of running time is allowed to the GAMS for each of the benchmarks. The values of 5626.30 and 32362.48 obtained for the benchmarks B1 and B2 are not optimal and the optimality gap of 100% still remains for each of them after 10800 seconds of running time. For the benchmarks B3, B4, and B5, after 10800 seconds the GAMS is unable to introduce any feasible solution. This fact shows the complexity of the problem. Concludingly, the proposed meta-heuristics perform better than the exact solution method of the GAMS. Also, the stability of the solutions obtained over 10 runs of each algorithm for all the benchmarks can be studied. For this aim, the difference of maximum and minimum values of each algorithm for each benchmark is calculated and plotted in Fig. 10. In this case, the TS-SA and TS-VNS algorithms perform better than the SA and VNS algorithms.