Keywords

1 Introduction

Scheduling problems have been extensively studied in the literature. This fact is due to at least two aspects. The first one is the practical interest, since there are various applications on this class of problems in industry field, as for example, textile [11], electronics [15] and iron [21]. The other aspect that interests the study of this kind of problem is the theoretical interest, once most of the scheduling problems belong to the class of \(\mathcal NP \)-hard problems [3].

Although the problem of scheduling jobs involves various objectives, in most of the researches in this field only one objective is considered. When more than one is considered, usually it is defined only one objective represented by the linear combination of involved objectives, thus, the problem is treated normally in a single-objective approach.

This work discusses the scheduling problem in single machines, in which the setup time of the machine depends on the scheduling and family of the jobs. The grouping of the jobs in the family occurs, for example, in the iron field. In [4], the author shows a process of manufacturing iron products (corner, rebar, bar, etc.) in the lamination sector, in which jobs are grouped in families in accordance with the similarity of the products. In this case, the products from same family are those which differ between themselves by the thickness. On those circumstances the setup time is so short and unimportant when compared to the processing time of jobs that is usual to consider it equivalent to zero. The advantage of making this grouping, thus, is that the jobs which belong to the same family, when processed sequentially, do not need setup time.

The problem in hand takes two objectives into account: makespan and total weighted tardiness minimization. It means that instead of looking for a solution which satisfies one or other objective separately, the main goal is to obtain a set of non-dominated solutions, this way each solution that belongs to this set is not worse than any other, considering both objectives simultaneously.

Noticing the computational complexity of the scheduling problems, the most used methods to solve them are metaheuristics. Reviews in literature show that methods inspired by the process of natural evolution, such as Non-dominated Sorting Genetic Algorithm II— NSGA-II [7] and Strength Pareto Approach— SPEA2 [25] are among the most used when multi-objective optimization is concerned. On the other hand, recently it were discovered reports of successful applications of multi-objective methods based on local search, such as Multi-objective Variable Neighborhood Search—MOVNS [9] and Pareto Iterated Local Search—PILS [10], as shown in the works of [1, 18] and [20]. In this last, for example, it is observed a superiority of PILS over SPEA2.

Due to the good performance of the algorithms in similar problems, in this work the multi-objective algorithms MOVNS and PILS are tested to solve the scheduling problem at hand. The MOVNS algorithms of [1] and [20] were adapted to solve the problem, giving birth to the MOVNS_Ottoni and MOVNS_Arroyo variants, respectively. Furthermore, a new perturbation procedure is proposed for PILS, giving birth to the PILS1 variant. Computational experiments showed that the last algorithm outperforms the other tested algorithms.

The rest of this work is organized as follows. In Sect. 2 the problem characteristics are described. Section 3 presents the proposed multi-objective algorithms, and in Sect. 4 the used test instances are described as well as the metrics used to assess and compare the developed algorithms. Also in Sect. 4, the results of the accomplished experiments are presented and analyzed. Section 5 concludes the work.

2 Problem Description

The problem in focus can be defined as follows: there is a set \(J = \{1, 2, 3, \ldots , n\}\) with \(n\) jobs that have to be scheduled in a single machine at the starting point zero. Each job \(j \in J\) has a processing time \(p_{j}\), a due date \(d_{j}\) and a weight for tardiness \(\beta _{j}\). The jobs are grouped in families \(f\) according to their characteristics and each family \(i\) has \(n_i\) jobs. A setup time \(s_{ik}\) is required between the execution of two consecutive jobs of different families \(i\) and \(k\) and, if they are from the same family, no setup time is necessary. Given a sequence \(\pi \), for each job \(j\) a tardiness \(T_{j}\) is associated. Since \(C_j\) is the completion time of the job \(j\), its tardiness is calculated by Eq. (1):

$$\begin{aligned} T_{j} = \text{ max }\{C_{j} - d_{j}, 0\} \end{aligned}$$
(1)

The objectives of the problem in focus are to minimize the makespan \(f_1(\pi )\) and the total weighted tardiness \(f_2(\pi )\), simultaneously. The values of \(f_1(\pi )\) and \(f_2(\pi )\) are calculated by Eqs. (2) and (3):

$$\begin{aligned} f_1(\pi ) = \mathop {\text{ max }}\limits _{1 \leqslant j \leqslant n} \{C_{j}\} \end{aligned}$$
(2)
$$\begin{aligned} f_2(\pi ) = \mathop {\sum }\limits _{1 \leqslant j \leqslant n}\beta _{j}T_{j} \end{aligned}$$
(3)

3 Methodology

A solution is represented by a sequence \(\pi = \{\pi _1,\pi _2,\ldots ,\pi _k, \ldots , \pi _n\}\) in which \(\pi _k\) indicates the \(k\)th job to be done.

The proposed algorithms begin with a set of non-dominated solutions generated by four different heuristics based on the following dispatching rules [22]: Earliest Due Date (EDD) rule, generating a scheduling of jobs in a non-decreasing order of their due dates; Shortest Processing Time (SPT) rule, generating a scheduling of jobs in a non-decreasing order of their processing time; Longest Processing Time (LPT) rule, generating a scheduling of jobs in a non-increasing order of their processing time; Minimum Slack Time (MST) rule, generating a scheduling of jobs in a non-decreasing order of the difference between the due date and processing time.

In order to explore the solution space of the problem, insertion and exchange movements are applied changing the scheduling of the jobs, as follows.

Given a sequence \(\pi = \{\pi _1,\pi _2,\ldots ,\pi _n\}\), the insertion move of a job \(\pi _x\) consists in moving this job to a position \(y\) (\(y\ne x\) e \(y\ne x-1\)). The group of insertion movements in a sequence \(\pi \) defines the neighborhood \(N^I(\pi )\) which is composed by (n − 1)2 solutions.

Given a sequence \(\pi = \{\pi _1,\pi _2,\dots ,\pi _n\}\), the exchanging move between two jobs \(\pi _x\) and \(\pi _y\) consists in moving the job \(\pi _x\) to the position \(y\) and the job \(\pi _y\) to the position \(x\). The group of exchanging movements in a sequence \(\pi \) defines the neighborhood \(N^T(\pi )\), formed by \({\frac{n \times (n-1)}{2}}\) solutions.

3.1 Algorithms Based on MOVNS

The Multi-objective Variable Neighborhood Search (MOVNS) is an optimization multi-objective algorithm proposed in [9] and the metaheuristic Variable Neighborhood Search—VNS [19].

Variants of MOVNS Algorithm In literature there are two variants of the MOVNS algorithm. The first one, named as MOVNS_Ottoni, was proposed by [20] and consists in adding an intensification procedure to the original MOVNS. The second variant of MOVNS, named MOVNS_Arroyo, was proposed by [1] and consists in adding another different intensification.

3.2 Algorithms Based on PILS

Pareto Iterated Local Search—PILSis an optimization multi-objective algorithm proposed by [10], with a structure based on the meta-heuristic Iterated Local Search—ILS [17]. PILS basic pseudo-code is presented in Algorithm 1.

figure a

In Algorithm 1, initially it is obtained a set of non-dominated solutions (\(ND\)) (line 1), using four different heuristics described previously. After this, one of the solutions of the set \(ND\) is selected randomly (line 2). In each iteration of the external loop (lines 3–27) all neighbors of the current solution are explored (lines 5–17). If a neighbor solution dominates the current solution, then this neighbor solution becomes the new current solution, the neighborhoods are randomly reordered and the procedure returns to the first neighborhood of the new generated order. This procedure is repeated while there are non-visited solutions in set \(ND\). After all solutions of set \(ND\) are visited—when the algorithm is in an local optimum concerning the explored neighborhood—is a solution is randomly selected from set \(ND\) (line 23) and a perturbation is applied (line 24), as described as follows. After this, all neighborhood of the current solution is explored (lines 5–17). In the case that all neighbors of the solution generated through the perturbation are dominated by any solution of set \(ND\), then the perturbation procedure is repeated. The most external loop (lines 3–27) is repeated while the stopping criterion is not met.

A solution is perturbed in order to explore other local optima. The original perturbation strategy of PILS, from [10], works in the following way: initially a solution \(\pi \) from the set \(ND\) is randomly selected. Then, a position \(j \le n-4\) and its four consecutively jobs of \(\pi \) are randomly chosen, i.e., positions \(j\), \(j+1\), \(j+2\) and \(j+3\). A perturbed solution \(s^{\prime \prime }\) is then generated by applying an exchanging move on the jobs in the positions \(j\) and \(j+3\), as well as the jobs in the positions \(j+1\) and \(j+2\). This way, the jobs before \(j\) and the jobs ahead of \(j+3\) are kept in their respective positions after the perturbation application.

In this work, the perturbation procedure of a solution (line 24 from Algorithm 1) has been modified when concerning the proposal of [10]. The perturbation is applied in levels, varying from 1 to \((n/2 - 1)\). In each level \(p\), \(p+1\) modifications are made on the solution. This way, on the lowest pertubation level two exchanges are applied while on the highest level \(n/2\) exchanges are made.

The level \(p\) of perturbation increases as the perturbation is not able to generate a non-dominated solution related to the set ND. The increasing is made by adding a unit of value to the current level of perturbation. When a non-dominated solution related to the set \(ND\) is found, the perturbation level returns to its lowest value, 1 in this case. If the perturbation level reaches its maximum value—(\(n/2 - 1\))—and it is still not possible to generate a non-dominated solution in relation to the set \(ND\), the perturbation level returns to its lowest value. The proposed procedure works as follows. A solution \(\pi \) from the set \(ND\) is randomly selected. Then it is chosen, also randomly, a subset of consecutive jobs of \(\pi \) on the positions \(j, j+1, \ldots , j+2p+1\). Then, exchanges are applied between the pairs of jobs \((j, \,j+2p+1), (j+1,\, j+2p),\ldots ,(j+p,\, j+p+1)\). This way, the procedure makes \(p+1\) exchanging moves on each call from the perturbation procedure. The PILS algorithm modified as such was named PILS1.

4 Computational Experiments

All algorithms were coded on C++ language and the tests were done in a Intel® Core™ 2 Quad 2.4 GHz with 6GB RAM.

The stopping criterion of each algorithm is a maximum CPU time proportional to the size of the instance. This criterion is common in literature and it has been established as \(1000 \times n\) ms, in which \(n\) is the number of jobs of the instance. For each instance 30 tests were performed, each one with a different random seed.

4.1 Instances

To assess the algorithms, instances were generated in a random way and with uniform distribution. As in [14], the number of jobs is a integer number \(n \in \{60, 80, 100\}\), the number of families \(f \in \{2, 3, 4, 5\}\) and the processing time is an integer number in the interval \([1, 99]\). The due date of the jobs was generated as in [2], being defined in the interval \((0, h \sum p_{j})\), with \(h \in \{0.5 ; 1.5 ; 2.5 ; 3.5\}\). Finally, the setup time between jobs families are integer numbers whose values belong to three classes of intervals: class S \([10, 20]\); class M \([51, 100]\) and class L \([101, 200]\).

The formation of such setup time intervals is a suggestion proposed in [13]. The class \(S\) setup time is relatively smaller than the average processing time. The class \(M\) setup time is close to the average processing time while the class \(L\) setup time is relatively bigger than the average processing time.

By combining the parameters of the number of jobs, number of families, number of intervals to the due dates and the number of classes of intervals to the setup time, an amount of 144 different instances were generated.Note that, for each \(n\), 48 instances were generated.

4.2 Performance Assessment Metrics

The comparison of two sets of non-dominated points, \(A\) and \(B\), obtained respectively through two optimization multi-objective algorithms is not a trivial task. Many performance assessment metrics have been proposed on literature [6, 8, 12, 23]. However, these metrics must be chosen in a proper way to make a fair comparison of algorithms.

In this work, five performance assessment metrics are used and they are called: cardinality [12], average distance [5], maximum distance [16], hypervolume [24] and epsilon [8]. In [8] it is shown that the hypervolume and epsilon metrics provide trustworthy measures, especially when two algorithms have similar performances.

The quality of a set of non-dominated points obtained by an algorithm, in a given instance, is assessed in relation to the set composed by all non-dominated points found during all experiments. This is called the set of reference points \(R\).

4.3 Results

The results presented on the following tables were obtained by the developed algorithms with different evaluation metrics. In the first column of these tables is indicated the group \(n\) of 48 instances (with number of jobs \(n\)). In the other columns the results of each algorithm are presented, with 30 algorithm executions. For each metric the average and best results are presented so as the average of the results in all instances.

Table 1 presents the average and best results obtained in 30 runs of the algorithms considering the cardinality metric. As can be seen from Table 1, PILS1 algorithm is able to generate a superior number of non-dominated solutions compared to the other algorithms. Besides this, the number of reference solutions generated by the PILS1 algorithm is, in average, at least seven times higher than the one generated by any other algorithm.

Table 1 Cardinality metric results
Full size table

Table 2 presents the average and best results in 30 runs of the algorithms considering the average distance metric.

Table 2 Average distance metric
Full size table

From Table 2 we can conclude that the set of non-dominated solutions produced by the algorithm PILS1 is closer to the reference set than the other algorithms.

Table 3 presents the results obtained by the implemented algorithms considering the maximum distance metric.

Table 3 Maximum distance metric
Full size table

As noticed in Table 3, the set of non-dominated solutions produced by the algorithm PILS1 is in a shorter distance from the reference set.

Table 4 presents the average and best results for the algorithms considering the hypervolume difference metric.

Table 4 Hypervolume difference metric
Full size table

On Table 4 it is verified that the formed area between the points from the PILS1 algorithm solution set and the points from the non-dominated set are the smallest ones in comparison to the other algorithms. It means that the PILS1 algorithm produces a better cover of the reference set \(R\).

Table 5 presents the average and best results obtained by the algorithms related to the epsilon metric.

Table 5 Epsilon metric
Full size table

From Table 5 it is noticed that the algorithm PILS1 is the one which produces the smallest values to the epsilon metric, indicating that the non-dominated solutions generated by this algorithm are closer to the reference set \(R\).

We also apply the non-parametrical Kruskal–Wallis test in order to verify the statistical superiority of the PILS1 algorithm. According to this test, there is statistical difference between the pairs of algorithms: MOVNS \(\times \) PILS1, MOVNS_Ottoni \(\times \) PILS1, MOVNS_Arroyo \(\times \) PILS1 and PILS \(\times \) PILS1.

5 Conclusions

This work dealt with the scheduling problem in single machine where the setup time of the jobs depends on the sequence and on the family, and there are two optimization criteria to be satisfied: makespan and total weight tardiness minimization.

To solve this problem, five multi-objective algorithms based on Pareto Iterated Local Search (PILS) and Multi-objective Variable Neighborhood Search (MOVNS) were implemented. Of these algorithms, three are based on the MOVNS; one of them is the original algorithm and the other two variants of this one found in the literature. And on the other two remaining algorithms, one is the original PILS and the second is a variant proposed in this work, named PILS1. This variant consists in changing the perturbation strategy of PILS.

The algorithms were compared considering Cardinality, Average Distance, Maximum Distance, Hypervolume Difference and Epsilon metrics. The computational results performed in generated instances for the problem were validated by statistical analysis, thus showing that the PILS1 variant is superior to every other algorithm considering the assessed metrics. This way, it is clear the contribution of the perturbation procedure proposed in this work.