An effective operations permutation-based discrete harmony search approach for the flexible job shop scheduling problem with makespan criterion

Abstract

The Flexible Job Shop Scheduling Problem (FJSSP) represents a challenging applicative problem for metaheuristic algorithms because it imposes the development of innovative domain-dependent search operators that have to deal both with its combined discrete and permutation nature. Emerging as an effective approach for the resolution of a broad spectrum of hard optimization problems, some few discrete declinations of the Harmony Search (HS) algorithm have been recently proposed for tackling the FJSSP. Recent advances include an investigation of an innovative and promising permutation-based proposal. Accordingly, this paper proposes an Effective Operations Permutation-based Discrete Harmony Search (EOP-DHS) approach for FJSSP with Makespan criterion. The approach adopts an integrated two-part “affectation-sequencing” representation of the solution harmony and a dedicated improvisation operator particularly adapted to the integer-valued and operations permutation-based used coding scheme. Besides, a Modified Intelligent Mutation (MIM) operator is integrated to the adopted framework in order to enhance its overall search ability. Mainly, by balancing maximum machine workload during the overall search process, MIM operator allows essentially maintaining and enhancing the reciprocal equilibrium of diversification and intensification abilities of the proposed EOP-DHS algorithm. Conducted numerical experimentations on 188 benchmarking instances validate the proposal comparatively to a representative set of previously deployed metaheuristic approaches to FJSSP with Makespan criterion. Furthermore, main contribution of the paper is extended with an experimental procedure proving the effectiveness of the adopted permutation-based HS scheme for the resolution of combinatorial optimization problems. Hard benchmarking instances of the classical Job Shop Scheduling Problem (JSSP) are thus considered for exemplification.

1 Introduction

Scheduling problems arise in many management and engineering fields and are generally identified as belonging to the class of hard combinatorial optimization problems. One of those, the Job Shop Scheduling Problem (JSSP) describes a representative machine-scheduling problem where a set of independent jobs, each one constituted by an ordered set of operations, has to be executed on dedicated specialized machines while optimizing a predefined performance criterion. Mainly, the problem consists of finding the proper sequence of operations execution on machines considering imposed affectations. Formulated by Brucker and Schlie [1] as a generalization of JSSP, the Flexible Job Shop Scheduling Problem (FJSSP) relaxes affectation constraints described by JSSP and allows to operations to be executed by a machine chosen from a predefined set of allowable machines. Therefore, the resolution of the FJSSP implies both determination of a proper sequence of execution of operations on machines and a proper affectation of machines to operations. In accordance with its inherent complexity, FJSSP is classified as a harder generalization of the classical JSSP that is fundamentally known as NP-hard combinatorial optimization problem [2, 3].

Indeed, by integrating both sequencing and affectation problems, FJSSP is characterized by strong practical implications and an admitted academic relevance that is due to the fact that it incarnates a fair representation of the general domain of combinatorial optimization. Thus, developing effective resolution processes for FJSSP will allow the resolution of broad kinds of existing real-world combinatorial optimization problems. These facts motivated the utilization of a number of approaches for its resolution, ranging from exact mathematical, to approximation methods and computational intelligence tools. In [4] an exact mathematical and a heuristic approaches are considered for the resolution of FJSSP. Presented experimental and comparative results clearly indicate the ineffectiveness of the proposed mathematical approach for the resolution of medium size instances of the problem that consist of more than four jobs and five machines. Actually, due to their scalability issue, general deterministic methods are commonly admitted to be (being) unsuccessful for the resolution of large scale and realistic scheduling problems in an acceptable time and are generally considered for a small problem and academic studies.

Metaheuristic optimization methods and in line with their ability to efficiently cope with the strong combinatorial nature of hard optimization problems stay the most reexamined class of approximation approaches for the resolution of a wild spectrum of hard manufacturing scheduling problems. Historically, trajectory based methods such as Tabu Search (TS) algorithm initiated the application of metaheuristic framework to FJSSP and are contentiously investigated [5,6,7,8,9]. Evolutionary technics also maintain a permanent position in FJSSP literature with a number of effective and superior achievements [10,11,12,13,14,15,16]. Besides, different recent metaheuristic approach proposals for tackling the complexity of FJSSP exemplify perfectly its academic relevance. Such proposals include Biogeography-based optimization [17], Variable Neighborhood Search [18], Artificial Immune Algorithms [19], Estimation of distribution algorithms [20], artificial bee colony algorithms [21], Particle Swarm Approaches [22, 23], and Hybrid of Artificial Immune/Simulated Annealing approach [24]. Further readings concerning the development of the FJSSP and a consolidated survey of various techniques that have been employed since 1990 for problem resolution are proposed in [25]. Moreover, it is important to note at this stage that despite the fact of being a generalization of JSSP, FJSSP motivated a dedicated branch of research literature, generally unsuitable for the JSSP and where common JSSP instances are omitted from the computational experiments. Actually, the two problems are generally tackled independently with few exceptions such as in [26]. Regarding the basic JSSP, a recent review paper of the application of Artificial Intelligence (AI) technics to the problem [27] shows that as for FJSSP, a significant spectrum of metaheuristic approaches is constantly proposed for JSSP. Example of recently published proposals include novel declinations of Evolutionary Algorithms [28], multi-population ones [29, 30], Biogeography-based Algorithm [31], and Parallel Bat Algorithm [32].

Proposed by Geem [33], the Harmony Search (HS) metaheuristic algorithm, emerged in just more than one decade of research, as an effective approach for the resolution of a broad kind of hard optimization problems, including construction, engineering, robotics, telecommunications, health, and energy [34]. The HS algorithm simulates the improvisation process of music players and was originally conceptualized using the musical process of searching for a perfect state of harmony. Indeed, HS is a population-based algorithm that maintains and improves a population of solutions, the Harmonies Memory (HM). It uses a replacement policy and an improvisation operator that produces at each iteration a new harmony (solution vector) merging the information of different solutions stored in HM. Generally, the newly generated Harmony replaces the bad harmony in HM if it is better. Particularly, HS improvisation operator generates the New Harmony by using a recombination mechanism that acts independently on each component of the solution vector and considers all the solutions stored in HM. As reported in [34] and [35] this distinctive characteristic of the HS algorithm from other population-based metaheuristic approaches is one of its important innovative operational procedures. Furthermore, it is stressed in [34] that by playing a major role in achieving a good trade-off between diversification and intensification, the improvisation operator constitutes another remarkable strength of the HS algorithm. Also, numerical comparisons in [36, 37] demonstrated that evolution in the HS algorithm was faster than the canonical Genetic Algorithm (GA). These particular features in addition to its simplicity and ease of implementation motivated the deployment of HS algorithm for the resolution of a continuously increasing number of hard optimization problems leading to a number of improvements and adaptation mechanisms. In fact, recent literature (See [35, 38]) reports different improvements of HS algorithm that covered different aspects related to algorithms’ parameters adaptation, improvisation mechanisms and integration within the HS process of other metaheuristic search components such as the genetic mutation operator [39, 40].

Accordingly, different declinations of HS algorithm have been recently proposed for the resolution of various manufacturing scheduling problems. The existing contributions can be broadly classified into two principal categories: “continuous-discrete domain mapping-based approaches” and “discreet domain approaches”. Developments of the first class of approaches are motivated by the difficulty to adapt the continuous domain operators of HS algorithm to manufacturing scheduling problems, particularly those where the solution vector is coded using a discrete permutation-based form such as for JSSP and FJSSP. Indeed, approaches falling within that category use the canonical continuous-domain HS algorithm and a dedicated mapping scheme for the generation and the evaluation of the solution in the permutation-based native domain of the scheduling problem. Different recently published contributions for tackling various classes of flow shop scheduling problems [41,42,43] and parallel machine one [44] belong to that category. Other works falling into the second category of applicative methodologies of HS algorithm to scheduling problems propose a fundamental adaptation of HS operators to the targeted permutation-based representation domain. In [45] and [46], different discrete HS strategies and job permutation-based improvisations operators are respectively proposed for the no-wait flow shop scheduling problem with total flow time criterion and the single-machine earliness/tardiness problem.

Lately, few but important contributions have been reported concerning the application of HS algorithm to FJSSP. Indeed, when solved using metaheuristic approaches, a FJSSP solution is naturally coded using a two-vectors representation that express both affectation of machines to operations and the sequencing of operations on machines (operations permutation). Thus, FJSSP can be considered as a challenging applicative problem for the HS algorithm because it imposes the development of innovative domain-dependent HS operators that have to deal both with its discrete and permutation nature in one effective and efficient research process. Yuan et al. [47] tackled the problem using a HS-based hybrid optimization scheme that make use of the continuous domain HS algorithm augmented with a variable neighborhood local search approach exploiting the concept of critical path. Gao et al. [48] investigated a discreet HS approach for the multi-objective FJSSP (MOFJSSP) with weighted linear combination of two minimization criteria: Makespan and mean of earliness and tardiness. Mainly, the approach uses a GA crossover operator for the improvisation of the operations permutation part of the coding scheme. As well, Gao et al. [49] proposes a discrete HS approach for the FJSSP with fuzzy processing time that makes uses of an operations permutation-based improvisation operator that work only on two harmonies at a time. In [50], the authors presented a study on the application of different metaheuristic approaches for the resolution of the MOFJSSP investigating as well a discrete operation permutation-based HS (OP-DHS) proposal. Mainly, introduced improvisation operator deals clearly with the discrete and permutation nature of FJSSP and exploits a large amount of solutions in HM. In succinct experiments compared to a Genetic and TS algorithm, OP-DHS approach depicted a promising search behavior for the resolution of MOFJSSP with weighted linear combination of three minimization criteria, including Makespan.

From the above presented recent literature concerning the application of HS algorithm to the FJSSP, it is worth noting that conceptually, with the exception of OP-DHS algorithm, none of the other approaches proposes an adaptation of HS algorithm and operators to FJSSP, considering both its discrete and permutation-based nature. Mainly, the hybrid HS-based resolution process presented in [47] is formulated in the continuous domain. Although they use a discrete improvisation operator to deal with the affectation part of the solution vector, approaches presented in [48] and [49] did not propose a conceptually suitable permutation-based improvisation operator that, with respect to the canonical formulation of the HS algorithm, exploits a large number of the solutions stored in HM. It is thus noticeable that OP-DHS approach proposed in [50] constitutes a fundamental development regarding the application of HS algorithm to the FJSSP considering that it proposes a strong adaptation of the canonical continuous domain HS algorithm to the discrete and permutation-based nature of the problem. However, considering limitations of the reported experimental procedure and results, it is clear that further investigations and improvements of the basic OP-DHS approach are important to give a fair insight and a rigorous assessment of HS algorithm performances in its permutation-based form for the resolution of FJSSP using usual criterion and comparative procedures. This fact constitutes the main motivation of the present research work. Moreover, this investigation is also motivated both by the representativeness of the FJSSP in combinatorial optimization area and the recently reported “infancy” of research works concerning the application of HS algorithm to discrete and scheduling problems [35, 46]. Mainly, academic and practical implications of presently reported extended investigation of the HS algorithm in its combined discrete and permutation declination are expected to go beyond the context of FJSSP.

In accordance with the above presented research context and motivations, this paper presents as a main contribution an Effective Operations Permutation-based Discrete Harmony Search (EOP-DHS) approach for the resolution of FJSSP with Makespan criterion. The proposed EOP-DHS algorithm largely adopts the discrete and permutation-based research process of the basic OP-DHS [50] and improves its search ability by exploiting a Modified declination of the Intelligent Mutation operator (MIM) previously introduced in [14]. Integrated to the basic OP-DHS scheme MIM is probabilistically applied on each newly improvised harmony to balance maximum machines workload (sum of processing times of the most loaded machine); this is done by re-affecting a flexible operation belonging to a machine with maximum workload to another allowable machine. Thus, MIM is mainly expected to have both explorative and exploitative role in the research process. Actually as a mutation operator, MIM conceptually plays an explorative role. By balancing machines maximum workload it also acts as an exploitative operator because of, as noted in [51], Makespan and maximum workload are often positively correlated. Mainly, MIM operator essentially allows maintaining and enhancing the reciprocal balance of explorative and exploitative power of the developed effective HS framework for the resolution of FJSSP.

In order to assess its effectiveness and efficiency, the proposed EOP-DHS algorithm is experimented using an extensive set of benchmarking problems and compared to a wild spectrum metaheuristic approaches recently deployed for the resolution of FJSSP including existing declinations of HS algorithm. Comparative algorithms have been chosen to have as fair as possible representation of the general domain of metaheuristic approach appliance to FJSSP with makespan, which is too large to be considered entirely. Thus, different classes of algorithms with different sophistication level but proved effectiveness for most of them have been selected for comparative purpose (GA, TS, Biogeography-Based Optimization (BBO), Mimetic Algorithm (MA), Artificial Bee Colony (ABC), Parallel Variable Neighborhood Search (PVNS), Artificial Immune Algorithm (AIA), Particle Swarm-Optimization, and Hybrid of Artificial Immune and simulated annealing (HAISA).

Furthermore, in order to rigorously assess the effectiveness of the contribution, the integrated MIM operator is investigated, and the EOP-DHS algorithm is experimentally validated in comparison with its mutation-free declination, which is precisely the mono-objective version of the original OP-DHS algorithm with Makespan criterion. Wilcoxon non-parametric statistical procedure is used to support the conclusions drawn.

The paper presents a complementary experimental contribution by investigating the effectiveness of the adopted permutation-based HS scheme for the resolution of classical JSSP. The basic OP-DHS algorithm (without the integration of operations affectation search mechanisms) is experimented for the resolution of different hard benchmarking instances of classical JSSP. A main motivation of such investigation is to enrich existing knowledge by providing a consistent evaluation of the adopted operation permutation-based HS scheme for the resolution of hard permutation-based scheduling problems. This is achieved by alleviating the possible experimental bias that can be introduced by simultaneously considering both of affectation and sequencing related HS components, as have been done for FJSSP. Considering the simplicity of the experimented HS framework, the experimental comparative investigation does not consider existing superior and generally sophisticated metaheuristic approach existing in the literature for the classical JSSP but just a restraint sample of algorithms representing different classes of sophistication and effectiveness.

The reminder of this paper is organized as follows: in the Section 2 we formulate FJSSP. The canonical HS algorithm is presented in Section 3. Section 4 details the proposed effective operations permutation-based discrete harmony search framework. Section 5 reports and discusses the results of the experimental studies. Finally, Section 6 concludes this paper with some perspectives for future works.

2 FJSS problem formulation

The FJSS problem is defined as follow: given a set of n independent jobs J = {J ₁, J ₂,…, J _n}to be processed on a set of m machines M = { M ₁,M ₂ ,…, M _m }. Each job J _i consists of a sequence of n _i ordered operations { O _i1,O _i2 ,…, $O_{in_{i}}$}. Each operation O _{i j} (i = 1,2,…,n; j = 1,2,…,n _i ) has to be processed, with no interruption, by one machine out of a set of allowable machines for the operation $M_{ij} \subseteq M$. The processing time of an operation O _{i j} on machine M _k ∈ M _{i j} is p _{i j k} . Each machine can only handle at most one operation at a time.

A solution to the problem consists in assigning both a machine and a starting time t _{i j} to each operation to minimize the makespan C$_{\max }$, which is the maximum of completion time of jobs.

$$ C_{max}=\text{Max}_{\,1\leq\, i <\,n} \ C_{i} $$

(1)

Where, C _i is the completion time of the last operation of job J _i .

From the given problem definition, we note that the JSS Problem is a particular case of the FJSS Problem where the set of allowable machines for each operation contains exactly one machine (i.e. | M _{i j} | = 1 ∀i = 1,2,…,n; ∀j = 1,2,…, n _i ).

3 The harmony search algorithm

The conceptual inception of the HS technic is the analogy between the intelligent exploration of harmonies space process depicted during jazz band musical improvisations, and intelligent explorative search in meta-heuristic optimization technic [33]. Thus, the HS algorithm is a population-based evolutionary algorithm that mimics the improvisation process of music players. Accordingly, when a group of musicians seek to find musically pleasing melodies, they iteratively explores the harmonies search space by a creative process that is made up of three different stages: (i) playing any pitch from memory, (ii) modifying a pitch which exists in the memory, or (iii) improvising any pitch from the possible pitch range. The New Harmony is then integrated or not in musician’s memories according to its audio-aesthetic significance.

According to the optimization point of view, a decision solution vector is represented by a harmony, and a population of solution vectors is represented by a harmonies memory. At each algorithm iteration a new harmony is generated (improvised) with the value of each decision variable composing the solution vector obtained using one of the following three options: (i) assigning a value from the memory, (ii) modifying an existing value in the memory, or (iii) assigning a possible random value. The generated harmony is then assessed for insertion in the harmonies memory using a predefined replacement policy based on its objective value.

This analogy give rise to a simple iterative optimization approach that consists of five steps:

• Step 1: Initializing the optimization problem and algorithm parameters

• Step 2: Initialize the Harmonies Memory (HM)

• Step 3: Improvising a new harmony from the HM

• Step 4: Updating the HM

• Step 5: Repeat Step 3 and 4 until the termination criterion is met.

The continuous and basic form of the algorithm is succinctly presented in the following subsections.

3.1 Initializing the optimization problem and algorithm parameters

The continuous optimization problem is defined as follows:

$$ minimizeF\left( x \right), $$

(2)

Subject to $x_{i \ }\mathrm {\in \ }\mathrm {X}_{\mathrm {i}}\mathrm {= \ }\left \{ x_{i}\left (1 \right ), \ \mathellipsis , \ x_{i}\left (k \right ), \ \mathellipsis ., \ x_{i}\left (k_{i} \right ) \right \}$

Where F(x) is the objective function, and $x=\thinspace \thinspace \left \{ x_{1},\mathellipsis .,\thinspace x_{N} \right \}$ is the optimal solution that has to be found by the harmony search algorithm. The set of candidate values for the variables are $x_{i\thinspace }\thinspace \in \thinspace \thinspace X_{i}=\thinspace \{x_{i}\left (1 \right ),\thinspace \mathellipsis ,$ $\thinspace x_{i}\left (k \right ),\thinspace \mathellipsis .,\thinspace x_{i}\left (k_{i} \right )$ .

The algorithm initialization phase considers the following parameters:

• Harmony memory size (HMS), (i.e. number of solution vectors in the harmonies memory)

• Harmony memory consideration rate (HMCR), where HMCR$\mathrm {\thinspace \in \thinspace \thinspace }\left [ \mathrm {0,\thinspace 1} \right ]$

• Pitch adjusting rate (PAR), where PAR$\mathrm {\in \thinspace \thinspace }\left [ \mathrm {0,\thinspace 1} \right ]$

• Number of improvisations (NI) that is the stopping criterion.

3.2 Harmony memory representation and initialization

A matrix of solution vectors, extended with a column of calculated objective value for each corresponding harmony represents the Harmony Memory (HM). During initialization, the matrix is filled with randomly generated solution vectors. Accordingly, each solution value is randomly selected within the range of its set of allowable values. The solutions are evaluated and based on their objective function values, they are sorted with a^worst and a^Best the worst and best harmony vector respectively.

$$ \text{HM}=\left[ \left. {\begin{array}{cccc} \mathrm{x}_{\mathrm{1}}^{\mathrm{1}} & \mathrm{x}_{\mathrm{2}}^{\mathrm{1}} & \mathrm{{\cdots} } & \mathrm{x}_{\mathrm{N}}^{\mathrm{1}}\\ \mathrm{x}_{\mathrm{1}}^{\mathrm{2}} & \mathrm{x}_{\mathrm{2}}^{\mathrm{2}} & \mathrm{{\cdots} } & \mathrm{x}_{\mathrm{N}}^{\mathrm{2}}\\ \mathrm{{\vdots} } & \mathrm{{\vdots} } & \mathrm{{\cdots} } & \mathrm{{\vdots} }\\ \mathrm{x}_{\mathrm{1}}^{\text{HMS}} & \mathrm{x}_{\mathrm{2}}^{\text{HMS}} & \mathrm{{\cdots} } & \mathrm{x}_{\mathrm{N}}^{\text{HMS}}\\ \end{array} } \right|{\begin{array}{c} \mathrm{f(}\mathrm{x}^{\mathrm{1}}\mathrm{)}\\ \mathrm{f(}\mathrm{x}^{\mathrm{2}}\mathrm{)}\\ \mathrm{{\vdots} }\\ \mathrm{f(}\mathrm{x}^{\text{HMS}}\mathrm{)}\\ \end{array} } \right] $$

(3)

3.3 Improvising a new harmony from the HM

Harmony improvisation process embeds recombination operators of the approach. It principally associates at each iteration different intensification and explorative components for the generation of a new harmony. It is mainly expected to exploit a wide region of the search space during recombination, which is a noticeable particularity compared to other population-based evolutionary algorithms. Improvisation makes use of three recombination operators for the generation of a new harmony $\mathrm {x=}\left \{ \mathrm {x}_{\mathrm {1}}^{\prime },\mathrm {x}_{\mathrm {2}}^{\prime },\mathrm {x}_{\mathrm {3}}^{\prime },\mathellipsis ., \mathrm {x}_{\mathrm {N}}^{\prime } \right \}$: memory consideration, pitch adjustment, and randomization.

Applied with a certain probability determined by HMCR$\in \left [ \mathrm {0, 1} \right ]$, harmony consideration forces the new values $\mathrm {x}_{\mathrm {i}}^{\prime }$ to be randomly inherited from corresponding values stored in HM:$\left \{ \mathrm {x}_{\mathrm {i}}^{\mathrm {1}}, \mathrm {x}_{\mathrm {i}}^{\mathrm {2}},.. \mathellipsis ., \mathrm {x}_{\text {HMS}}^{\prime } \right \}$. Otherwise, using a randomization component with an implicit probability of (1 – HMCR), value of $\mathrm {x}_{\mathrm {i}}^{\prime }$ is chosen according to its admissible range X_i. The following equation summarizes memory consideration and random consideration steps:

$$ \mathrm{x_{i}}^{\prime}\leftarrow \left\{ {\begin{array}{l} \mathrm{x_{i}}^{\prime} \in \left\{ \mathrm{x_{i}}^{\mathrm{1}},\mathrm{x_{i}}^{\mathrm{2}},..\mathellipsis ., \mathrm{x_{HMS}}^{\prime} \right\} \,\,\, \mathrm{ w.p.HMCR } \\ \mathrm{x_{i}}^{\prime} \in \mathrm{X_{i}} \qquad\qquad\qquad \mathrm{ w.p. \, (1-HMCR)} \\ \end{array}} \right. $$

(4)

Using a probability determined by the PAR parameter, pitch adjustment component examines every value chosen by harmony consideration to determine whether it should be adjusted or not. Adjusting decision for $\mathrm {x}_{\mathrm {i}}^{\prime }$ is given by (5), where bw is an arbitrary distance bandwidth that determines the nature and amount of change that can occur in ${\mathrm {x}}_{\mathrm {i}}^{\prime }$ It depends mainly on the considered optimization problem. The function rand() generates a random number ∈ [0, 1].

$$ \mathrm{x}_{\mathrm{i}}^{\prime}\mathrm{ \leftarrow }\left\{ {\begin{array}{lr} {\mathrm{x}}_{\mathrm{i}}^{\prime}=\mathrm{x}_{\mathrm{i}}^{\prime}\pm \mathrm{rand().bw} & \mathrm{w.p. PAR } \\ {\mathrm{x}}_{\mathrm{i}}^{\prime}=\mathrm{x}_{\mathrm{i}}^{\prime} & \mathrm{w.p.\ \ }\left( \mathrm{1-PAR} \right) \end{array}} \right. $$

(5)

3.4 Updating the HM

Harmonies Memory updating mechanism is based on a replacement policy that can take different forms. The replacement policy mainly characterize the admissibility or not of the new improvised solution (New Harmony) in the Harmonies Memory and, if considered, which solution from the HM will be replaced. According to its common and basic form, the HM is updated if the new generated harmony vector is better than the worst harmony in the HM. In this case a^new will replace a^worst and become a new member of the HM. If a^new is worst than a^worst it is not considered. The following equation summarizes HM updating step:

$$ \mathrm{a^{worst}}\leftarrow \left\{ {\begin{array}{lll} \mathrm{a^{new}} &\quad \mathrm{if:} &\,\,\, \mathrm{f}\left( \mathrm{a^{new}} \right)< \quad f\left( \mathrm{a^{worst}} \right) \\ \mathrm{a^{worst}} &\quad \mathrm{if:} & \,\,\, \mathrm{f}\left( \mathrm{a^{worst}} \right)\le \quad \mathrm{f}\left( \mathrm{a^{new}} \right) \end{array}} \right. $$

(6)

3.5 Stopping criterion

If the predefined termination criterion is met - for example the number of improvisations -, return the best harmony vector a ^best. Otherwise, go to step (3).

4 An effective operations permutation-based discrete HS algorithm for the FJSSP

In this section, the improved discrete permutation-based form of the canonical HS algorithm introduced in Section 3 is presented for the resolution of FJSSP with Makespan minimization objective. Mainly, for completeness this section highlights important conceptual and algorithmic features of the basic OP-DHS approach adopted in this work. Furthermore, this section details the integrated MIM operator. At the end of this section, the overall algorithm flow of the proposed EOP-DHS approach is presented.

4.1 Harmony coding and decoding

As reported by Wu and Wu [16] and Zhang et al. [15] different coding approaches have been used in FJSSP literature. In this work, the adopted representation from [15] codes the FJSSP solution vector by means of two parts that express independent assignment of machines to operations and the processing sequence of operations on machines. Accordingly, a Harmony representation for FJSSP is composed of two vectors: a Machine Selection Vector (MSV) and an Operation Sequence Vector (OSV). Table 1 depicts an example of a FJSSP instance. Numerical values indicate the execution time of each operation on the corresponding allowable machines. N/A means that the machine is Not Allowable for the corresponding operation. Figure 1 illustrates a harmony MS/OS vectors representation of a feasible solution for FJSSP of Table 1.

Table 1 Example of a FJSSP instance

Fig. 1

MS/OS coding of a Harmony

Integer-valued MSV indexed by p, expresses the assignment of each operation to a machine selected from the set of allowable machines for the corresponding operation. Its number of elements is equal to the total number of operations of all jobs (T _{o p} ) and each element MSV _p indicates a column index (a machine choice) in the matrix of alternative allowable machines/processing-time for the operation O_ij corresponding to P. As an example and as depicted in Fig. 1, the operation O_2,2 is assigned to machine 2 which correspond to the column index 1 in the matrix of alternative allowable machines for that operation. The second row in the matrix corresponds to the execution times of the operation O _2,2 for each of the possible machines.

The Operations Sequence Vector $\left (\text {OSV} \right )$ indexed by (s) expresses the processing sequence of all the operations in the system. With a length also equal to the total number of operations (T _{o p} ), it uses an “Operations Permutation-based representation” that defines all operations of a job with the same integer value and then interprets them according to the sequence of their appearance. Therefore, the index i of the job J _i appears n _i times in the vector, with n _i the number of operations of the job J _i . As an example, the OS part of the solution vector illustrated in Fig. 1 expresses the following sequence of operations execution: (O _2,1 → O _1,1 → O _3,1 → O _1,2 → O _2,2 → O _3,2 → O _2,3 → O _3,3 → O _1,3 → O _3,4).

The evaluation procedure is based on a decoding process that transforms Harmony solution vectors to a feasible schedule. In this study, a priority-based and machine’s idle-time occupation decoding scheme such as described in [12, 13, 15] is used. It assists in a construction process that iteratively inserts each operation of OSV in its corresponding selected machine according to its priority, which is determined by its order of appearance. The corresponding machine and processing time are identified using the MSV, and the operation is inserted at the first allowable idle-time interval respecting precedence constraints, or at the end of the machine. The algorithm presented in Fig. 2 depicts the adopted decoding procedure and an example of a construction of a schedule structure (represented by a Gantt diagram) integrating machines idle-time occupation process is depicted in Fig. 3b. The considered Harmony is: [2 1 3 1 2 3 2 3 1 3]. During the construction process the operation O_3,2 is inserted at the allowable idle time interval in machine 2 before the operation O_2,2, generating a final Makespan of eight time unit. The utilization of a decoding process that does not integrate machines idle-time occupation strategy place the operation O_3,2 after the operation O_2,2 and generates a Makespan of 9 time unit (Fig. 3a).

Fig. 2

Harmony decoding procedure

Fig. 3

Example of a decoding procedure without (a) and with allowable machine idle time interval occupation strategy (b)

4.2 Harmonies memory initialization

Expected to enhance evolutionary algorithms resolution process efficiency, different population initialization strategies have been adopted in the FJSSP literature. Such as the strategies presented in [14, 15]. These approaches generally consider different local and global search heuristic mechanisms for minimizing or balancing machine’s workload during the generation of a new solution, introducing a number a supplementary algorithm parameters to be tuned. In this work, a simple random harmonies memory initialization approach is adopted such as to maintain the number of algorithm parameters as small as possible. Furthermore, this strategy allows the generation of an initial HM with high solutions diversity.

4.3 Harmony improvisation operator

According to HS optimization process, at each algorithm step a new harmony is improvised from HM using three recombination components: memory consideration, pitch adjustment, and random consideration. In this work, two dedicated discrete improvisation schemes fitting the two-part adopted FJSSP representation are adopted: Machine Selection and Operations Sequence vector Improvisation.

4.3.1 Machine selection vector improvisation

The integer coded machines selection vector presents no particular structural relationships between its components. Accordingly, the MSV improvisation scheme uses with slight modifications, related to the integer valued nature of the MSV, the basic operators presented in Section 3.3. Hence, applied with a certain probability determined by $\mathrm {HMCR\in }\left [ \mathrm {0,\thinspace 1} \right ]$, the harmony consideration operator force the new values of machine selection index for the operation O _{i, j} at the position $p\thinspace ({\text {MSV}}_{p}^{New})\thinspace$to be inherited from a randomly selected historical values stored in the HM. Otherwise and using a random consideration with an implicit probability of (1 −HMCR), the values of ${\text {MSV}}_{p}^{New}$ is randomly chosen according to its possible range of values. Every component chosen by harmony consideration is examined for adjustment in its possible range of values, which is the number of allocation possibilities for that operation.

Figure 4 depicts a succinct example of an MSV improvisation process for the problem described in Table 1. As it is shown, the new final MSV part of the harmony is iteratively generated from the Machine selection part of the HM. Indeed, each element is generated using one of the possible rules with a certain probability: Consideration, Consideration + adjustment, or Randomization. Value adjustment and randomization are expected in the range of the possible allocations for each operation that is also depicted in Fig. 4.

Fig. 4

Example of MSV Improvisation Process

4.3.2 Order sequence vector improvisation

As formerly presented in Section 4.1, the OSV uses an operations Permutation-based representation commonly adopted for metaheuristic approach to FJSSP. Therefore, ordinary HS improvisation operators are not suitable to this structurally constrained representation because of the possibility to generate unfeasible solutions. An operations permutation-based HS improvisation operator is adopted in this work in order to tackle this issue. This operator depicts two main conceptual features: It approaches the explorative behavior of the HS improvisation operator in its native formulation and avoids from the generation of an unfeasible OSV during recombination. Particularly, as for the basic HS algorithm, for the generation of one OSV, this operator exploits with some probability a large amount of the information contained within the HM and is expected to increase its exploitation ability with the increase of the number of jobs. The operator processes according to two consecutive conceptual stages (Procedure in Fig. 5):

Fig. 5

OSV Improvisation procedure

The first Stage concerns the generation of a matrix of N intermediates OSVs, each one corresponding to a specific Job. Accordingly, for each job from the vector of randomly sorted set of all jobs, the job-based consideration scheme, if used, copies all the operations of the considered job from a randomly selected OSV from the HM in their corresponding positions in the empty intermediate OSV. Next, if applied to the intermediate OSV the Operation-Based adjustment scheme adjusts randomly the position of a randomly selected operation in the vector. If consideration and adjustment are not of concerns, a random intermediate OSV is obtained by applying the Job-Based consideration scheme to a newly generated OSV. In the second stage, the final OSV is generated from the matrix of intermediates OSVs. Essentially, the components of the final OSV are filled considering the values of non-empties components of each column of the matrix of intermediates OSVs sequentially. The values of non-empties components of each column are considered according to their order of apparition from the first to the last line of the matrix.

In Fig. 6 the OSV improvisation process for the problem described in Table 1 is illustrated by an applicative example. Actually, the randomly generated J o b ^Rand vector in this example is $\left [ 2,1,\thinspace 3 \right ]$.

Fig. 6

Example of OSV Improvisation procedure

4.4 Modified intelligent mutation operator

Inspired by the Intelligent Mutation operator proposed in [14] and also used in [19], the Modified Intelligent Mutation (MIM) operator is applied with a certain rate to the newly improvised harmony. The operator mainly balances maximum machines workload by reassigning a random flexible operation from the machine with the maximum workload to another randomly chosen allowable machine. Main difference between the MIM and the original version of the operator is that it considers systematically the obtained solution as a current one. Actually, the original operator used in [14] evaluates the fitness of the generated solution and consider it only if it minimize Makespan comparatively to the altered individual.

MIM operator processes according to three steps summarized in Fig. 7. Its utilization implies the introduction of a new algorithm parameter that is the Modified Intelligent Mutation Rate (MIMR).

Fig. 7

Conceptual steps of the modified intelligent mutation operator

4.5 Framework of the proposed EOP-DHS algorithm

As described in Fig. 8, the overall framework of the proposed EOP-DHS algorithm to FJSSP consists in six steps. Actually, the five steps canonical HS framework is extended with the application of MIM operator and modified according to the presented discrete and permutation form of the adopted operators. Besides, we note that despite the introduction of a new algorithm parameter that is MIMR, the overall number of HS algorithm parameters is maintained to five. This is because the presented approach does not use an adjustment bandwidth as for the canonical HS algorithm.

Fig. 8

Overall framework of the proposed EOP-DHS algorithm for the FJSSP

5 Experimental study

In order to assess the effectiveness of the proposed EOP-DHS algorithm this section provides an experimental evaluation of its performances and a comparative study with different stat of the art metaheuristic approaches to FJSSP, considering significant benchmarking instances of different dimensions. The comparative algorithms have been mainly chosen such as to give a wide exemplification of the spectrum of approaches previously investigated for the resolution of FJSSP, and they represent different levels of algorithmic complexity and effectiveness. Additionally, the proposed enhanced EOP-DHS approach integrating the MIM operator is experimentally compared to the basic OP-DHS algorithm (the mutation-free EOP-DHS) and the Wilcoxon non-parametric statistical test is used in order to characterize achieved improvement. Finally, the experimental examination is extended with supplementary results related to the performances of the adopted operations-permutation based HS framework for the resolution of the classical JSSP comparatively to a sample of metaheuristic algorithms previously deployed for the resolution of the classical JSSP.

5.1 EOP-DHS approach performances and comparative results

The first experimentation round in this subsection concerns the assessment of the performances of the proposed EOP-DHS approach comparatively to several previously published state of the art metaheuristic proposals to FJSSP. Thus, the ten BRdata test instances of Brandimarte [5] are first considered and in order to enhance approach efficiency, algorithm parameters are set empirically as follow: MCR = 0.97, PAR = 0.01, MIMR = 0.5 and NI = 500 000. HMS parameter is adopted as a free dimensioning parameter and is determined empirically for each instance of the problem. Besides, the algorithm is coded in Java language and run on an I7 PC with 3.30 GHz and 8 GB of RAM memory. Regarding the stochastic nature of the proposed metaheuristic approach, 30 runs are realized for the resolution of each problem instance.

Table 2 compares the EOP-DHS algorithm to six algorithms previously investigated on BRdata; ABC algorithm of Wang et al. [21], PVNS algorithm (PVNS) of Yazdani et al. [18], MA of Kobti [26], GA of Pezzella et al. [14], the hybrid Tabu Search with Public Critical Block-based neighborhood structure (TSPCB) of Li et al. [9], and BBO of Rahmati et al. [17]. The first three columns report respectively the name of the instance, the corresponding number of jobs and machines and the best-known solution obtained so far for that instance (BKS). The following columns report best-reported solutions sets for the different algorithms and both the reported computational results of the ABC algorithm and the obtained computational results for the proposed EOP-DHS. For the ABC and the EOP-DHS algorithms, the results involve four metrics for each problem: the best-obtained Makespan (BCm), the average Makespan (AvCm), the standard deviation of the Makespan (SDV), and the average computational time in seconds (AvT(s)). Besides, to characterize their global relative performances, the number of best solution obtained (#BCm) and Mean Relative Deviation metric (MRD) are reported for each algorithm. An algorithm MRD from the BKS set is defined as follows:

$$MRD\thinspace \left( \% \right)= \frac{1}{p} \sum\nolimits_{i=1}^{p} {Rdv}_{i} $$

With ${Rdv}_{i}\thinspace \left (\% \right )=\thinspace \frac {1}{C_{i}}\thinspace \left (C_{i}-\thinspace C_{i}^{bks} \right )\thinspace \times 100$

Table 2 Results of the proposed EOP-DHS and comparison with different metaheuristic approaches on BRdata

Where R d v _i , represents the relative deviation for the considered instance i, p denotes the number of tested instances, C _i denotes the Makespan of the considered instance, and $C_{i}^{bks}$ denotes the best-known Makespan so far for the instance i.

Table 2 results indicate that the proposed EOP-DHS algorithm to FJSSP depicts a superior behavior comparatively to a wild spectrum of metaheuristic approaches previously investigated for the FJSSP. Actually, the algorithm dominates the six algorithms in term of MRD from the best-known solution set, where it achieves a minimum MRD of 1.09%. Concerning the #BCm indicator, both the proposed EOP-DHS and the ABC approaches achieved the best result among the seven approaches with eight best solutions obtained out of the 10 test problems. It is noticeable that ABC algorithm depicts an interesting competitive behavior compared to the proposed EOP-DHS both in term of solution quality and robustness to initial conditions (appreciated using AvCm and SDV metrics). Because of the difference in computing environments, it can be simply appreciated that both two approaches depict a comparable and acceptable computational efficiency. Hence, considering the nature of the two approaches and the fact that EOP-DHS algorithm is not equipped with any sophisticated initialization scheme or critical path-based local search technique as with ABC approach, one can easily support the contextual dominance of EOP-DHS algorithm to ABC. In the other side, the appreciated superiority of the proposed EOP-DHS approach to the overall set of considered algorithms, amongst them different highly competitive algorithms such as PVNS, MA, and GA, confirm that the EOP-DHS algorithm is effective and robust for the resolution of the FJSSP on the well-known BRdata set.

The second experimentation round concerns a comparative investigation of performances of the proposed EOP-DHS to FJSSP on Fdata benchmarking set [4]. Thus, EOP-DHS results concerning the ten medium size Fdata problems are considered comparatively to the results obtained by three effective and competitive metaheuristic proposals from the literature: Artificial Immune Algorithm (AIA) of Bagheri et al. [19], Hybrid of Artificial Immune and Simulated Annealing approach (AISA) of Roshanaei et al. [24], and Particle Swarm-based approach of Teekeng et al. [23] (EPSO). Table 3 reports for each algorithm and problem instance the best-found solution and relative deviation from the BKS. Besides, the table reports previously introduced performance metrics for each algorithm (MRD, #BCm). Algorithm parameters are set empirically as follow: MCR = 0.97, PAR = 0.01, MIMR = 0.5, NI = 500 000 and HMS = 100.

Table 3 Results of EOP-DHS and comparison with existing FJSSP metaheuristic approaches on Fdata

It can be noticed in Table 3 that the search ability of the proposed EOP-DHS approach is also confirmed using a different dataset and comparatively to different effective and sophisticated metaheuristic approaches to the FJSSP. Indeed, the EOP-DHS algorithm obtained the best performances among the four algorithms with nine BKSs out of the ten considered problems and a superior MRD of 0.025%.

The third and final experimentation round of this subsection concerns the comparison of the proposed EOP-DHS approach to existing declinations of HS algorithm to the FJSSP on BRdata: the basic Operations permutation-based discrete HS (OP-DHS) approach of Gaham et al. [50], the Discrete HS (DHS) algorithm of Gao et al. [48], and the Hybrid HS (HHS) algorithm of Yuan et al. [47]. Indeed, in Table 4 the first and second columns indicate the name for each test instance and its corresponding BKS. The following columns report best solutions obtained by the three algorithms and the corresponding relative deviation from the BKS for each problem. MRD and #BCm metrics are also included for each algorithm.

Table 4 Results of EOP-DHS and comparison with existing HS-based FJSSP Metaheuristics proposals

Reported results show that the proposed EOP-DHS algorithm clearly outperforms existing discrete adaptations of the HS algorithm to the FJSSP both in term of MRD and #BCm. The EOP-DHS algorithm achieve also competitive performances compared to the hybrid critical path-based local search continuous domain HHS approach with a same #BCm and a difference in MRD that is inferior to 0.5%, what is in our sense an expected result considering the nature of the two algorithms. These succinctly presented results confirm that the EOP-DHS is of an outperforming searching ability comparing to stat of the art discrete harmony search approach to the FJSSP.

5.2 Performance analysis of the modified intelligent mutation operator

In order to assess the effectiveness of the contribution, particularly the effect of the integration of MIM operator into the research process, the EOP-DHS algorithm is experimentally validated in this subsection in comparison with its Mutation-Free declination (EOP-DHS _{M F} ) (that is essentially the basic OP-DHS algorithm to the mono-objective FJSSP with Makespan). Taking into account the motivation of the following experimentation that is self-contained and the fact that previous presented experimentations of the EOP-DHS algorithm have been carried out using the Harmony size as a free dimensioning parameter, an alternative and uniform experimental design is adopted in this part. Thus, the EOP-DHS _{M F} and the EOP-DHS algorithms are experimented using both BRdata and Fdata benchmarking sets and with the following parameters: HMS = 200, MCR = 0.97, PAR = 0.01, and NI = 300 000. The MIMR is naturally set to zero for the EOP-DHS _{M F} and to 0.5 for the EOP-DHS. Besides, 50 runs are realized by each algorithm for the resolution of each problem instance and Wilcoxon signed rank test is adopted to measure the statistical relevance of the results. The confidence level for all tests is set to 95% (corresponding to α = 0.05). The Wilcoxon signed rank test [52] is a non-parametrical statistical procedure generally used to perform pairwise performances comparison of evolutionary algorithms [53]. Particularly, the test aims at the detection of significant differences between two sample means, that is, the behavior of two algorithms over a certain number of runs. The Wilcoxon signed ranks test have been for example used in several studies concerning the application of metaheuristic approach for the resolution of manufacturing scheduling problems [54, 55].

Table 5, presents obtained results. The first column reports the name of each instance. Its corresponding Best and average Makespan value obtained over 50 runs for both the EOP-DHS _{M F} and the EOP-DHS algorithms are reported in the following four columns. Sixth column reports the sum of ranks for the problems in which the EOP-DHS algorithm outperformed the EOP-DHS _{M F} (R +). The sum of ranks for the opposite (R -) and the numbers of ties cases (Ties) among the 50 runs are respectively reported in the seventh and the eighth columns. The last column reports the corresponding p-value that indicates the statistical relevance of obtained results. The attached signs “ + ” or “ −” indicate that the proposed EOP-DHS algorithm performs significantly better or worse than EOP-DHS _{M F} algorithm. The sign “ = ” denotes that there is no significant difference between the two declinations. Additional indicators; numbers of “ = ”, “ −” and “ + ” cases over the twenty benchmarking instances are also reported in the table.

Table 5 Results of the OP-DHS and comparison with the EOP-DHS on BRdata and Fdata

It can be observed from corresponding columns in Table 5 that EOP-DHS algorithm shows better performances compared to its mutation-free version considering average Makespan value among the 50 runs. This clearly indicates that by acting on maximum machines workload the integration of MIM operator improves the search ability of the adopted HS framework for the resolution of FJSSP. This conclusion is confirmed by the conducted statistical test. Actually, statistical results indicate that EOP-DHS algorithm performs significantly better than the EOP-DHS _{M F} algorithm on 13 out the 20 considered instances. Besides, it is important to note that the number of “ −” indicating that the EOP-DHS _{M F} algorithm performs significantly better than EOP-DHS algorithm is equal to zero.

5.3 EOP-DHS approach performances discussion and extended experimental investigation

Globally considered, presented results indicate that the proposed EOP-DHS algorithm is a simple and highly competitive algorithm for the resolution of FJSSP on well-known BRdata and Fdata problem instances. Actually, the approach at least competes effectively or outperforms the entire considered comparative set of recently deployed metaheuristic approaches for the FJSSP. In order to permit a fair consideration of this result, it is important to relativize the conceptual and algorithmic simplicity of the proposed EOP-DHS algorithm to the sophistication of most of the considered stat of the art comparative approaches. Indeed, these approaches often incorporate in addition to a specific initialization scheme, domain-specific local search components, sophisticated critical path-based neighborhood search, or the two mechanisms in the same time. This fact is clearly susceptible to introduce a significant implementation complexity of these approaches. Besides, the utilization of dedicated heuristic initialization procedures generally introduces a number of additional algorithm parameters that have to be tuned, which is a complex task in the context of non-deterministic optimization.

According to our appreciation, the effective search behavior of the proposed EOP-DHS algorithm is clearly in line with its developed operational procedures that maintain a correct balance between its explorative and exploitative capabilities overall the search process: first, the EOP-DHS algorithm exploits a solutions decoding scheme that generates an active schedule at each evaluation step. Secondly, the EOP-DHS algorithm does not use any specific initialization scheme, what foster a high diversity of the generated initial population and avoid from a guided convergence of the algorithm to a specific region of the search space. Besides, this strategy allows a free-parameters HM initialization scheme that avoids from any inconsistent behavior of the search process due to a poor choice of these parameters. Thirdly, by using an improvisation operator that probabilistically exploits at each iteration a large number of the solutions stored in the HM, the algorithm guaranties, as it have been noted in [34, 35], an appropriate balance between exploration and exploitation ability of the search space. Finally, exploitation and exploration abilities of the EOP-DHS approach are enhanced by the use of MIM operator that exploits the correlation that often exist between maximum machines workload and Makespan criteria. Actually, as indicated in [51], maximum machines workload and Makespan are generally linearly correlated what implies a minimization of the Makespan when reducing maximum machines workload. The MIM operator exploits this fact and acts probabilistically as an intensification operator. Besides by altering the solution generated by the improvisation operator, MIM operator behaves probabilistically also as an explorative search component.

Comparatively to the EOP-DHS approach, different metaheuristic algorithms have been investigated in this work. Considering BRdata benchmarking set as a basis for the following analysis (Table 2), the population-based BBO algorithm presented in [17] showed relatively poor performances comparatively to the overall set of considered approaches. According to our appreciation, this fact is probably due, among others, to the adopted population initialization approach. Actually, in BBO algorithm the affectation part of the solutions are initialized using dedicated rules that mostly foster the generation of solutions with minimum global workload (total sum of processing times for all machines), where it is showed in [51] that for FJSSP, global workload and Makespan are generally inversely correlated. On the other side, TSPCB approach [9] uses a sophisticated initial solution generation scheme based on different rules particularly articulated around machines workloads balancing and minimization. Besides, an efficient neighborhoods structure for machine assignment is used. However, the approach fails to obtain effective solutions for Mk04, MK06, and Mk10 problems and showed a lack of exploration ability, what is generally a difficult task within the context of trajectory-based metaheuristic approaches, particularly for hard and computationally expensive problems (such as MK04, MK06, MK07. MK09, Mk10). We note also that the TSPCB approach does not exploit any active schedule-based solutions decoding scheme. Moreover, GA of Pizzella [14] exploits a sophisticated initial population generation scheme based on global workload balancing and an Intelligent Mutation Operator (IMO) that acts probabilistically on each solution to balance maximum workload. GA showed relatively good search ability for the considered dataset but fail in getting high quality solutions for MK06, MK09, and MK10 problems, which is probably due to a lack of exploration ability of the algorithm. Possible reasons for that, lies in the fact that IMO is used only as an intensification operator and obtained solution are considered only if they improve solutions Makespan. Besides, as for TSPCB algorithm, we also note that the GA do not exploit any active schedule-based solutions decoding scheme.

Above presented analysis of the performances of various metaheuristic approaches previously applied to the FJSSP considered mainly approaches with a relatively simples search procedures. For comparative purpose, different other highly sophisticated resolution processes have been considered. Actually, MA [26], PVNS [18], and ABC approach [21] achieved globally high quality results for BRdata benchmarking instances and obtained an MRD (mean relative deviation from the best known solution set in Table 5) that is inferior to 2%. This appreciated superior search ability is certainly due to various facts related to operational procedures embedded within these approaches and proves that they clearly achieved a proper balance between exploitation and exploration abilities of the search space. However, some search components are of particular interest; in ABC approach a continuous updating mechanism of the population is proposed to enrich the searching behavior and avoid the premature convergence of the algorithm. MA uses a novel Priority-based fitness function (PBFF) during selection. Accordingly, when ties occur between individuals, a priority scheme is considered to direct the search process considering the lower maximum workload. Authors stressed that the solution which has lower maximum workload is more likely to be the direction to the optimal solution. Besides, a maximum workload-based strategy is also considered in PVNS within the adopted Neighborhood structures. Conceptually, proposed EOP-DHS approach for FJSSP adopts a great part of these search components in an effective and simple optimization process.

Finally, in order to provide a fair consideration of the performances of the proposed EOP-DHS algorithm for the resolution of the FJSSP, an extended experimental investigation have been endeavored on series of 168 benchmarking problems with actual complexity: The data set from Dauzére-Pérés and Paulli [56] (DPdata), the data set from Barnes and Chambers [57] (BCdata), and the data set from Hurink et al. [58] that contains three sets of benchmark problems: Hurink Edata, Hurink Rdata, and Hurink Vdata.

Table 6 reports computational performance of the proposed EOP-DHS algorithm comparatively to different metaheuristic approaches deployed for the resolution of the FJSSP and tested using the adopted extended benchmarking data sets: The recent and highly superior Hybrid genetic and tabu search Algorithms (HA) of Li and Gao [59], the hybrid Genetic Algorithm (hGA) of Al-Hinai et al. [60], and previously investigated Hybrid HS (HHS) algorithm of Yuan et al. [47], PVNS algorithm (PVNS) of Yazdani et al. [18], and the GA of Pezzella et al. [14]. Particularly, Table 6 reports for each approach and dataset the MRD from the best-known lower bound obtained over 50 runs and the Global Relative Deviation (GRD) computed for all datasets.

Table 6 Results of EOP-DHS on extended datasets and comparison with different metaheuristic proposals

Obtained results clearly confirm previously appreciated highly competitive behavior of the EOP-DHS algorithm for the resolution of FJSSP, extending the conclusions to realistically dimensioned and computationally expensive datasets. Indeed, the approach obtained a GRD from the best-known lower bound of just 6.67% that represent a significant performance comparatively to the superior HA, and show a clear superior search behavior comparatively to other approaches.

5.4 Classical JSSP experimental investigation

Final experimentation subsection, deals with the investigation of the adopted operations permutation-based HS framework initially proposed in [50] for the resolution of the classical JSSP with Makespan criterion. Thus, 27 problems of a generally affirmed intractability taken from the OR-Library [61] are considered: 2 problems from the Fisher and Thompson instances (ft10, ft20) and 25 problems from Lawrence instances (LcA16-LA40). Algorithm parameters are set empirically as follow: MCR = 0.97, PAR = 0.08, NI = 500 000 and HMS = 100.

Table 7 reports computational achievement of OP-DHS algorithm in term of best obtained Makespan (BCm), Average Makespan (AvCm) and average computational time (Av(T)) for 30 independent runs (last three columns). For each problem, the name, the dimension, and the BKS are reported in the first three columns. For performances comparison purpose, Table 5 reports also best obtained results for three metaheuristics approaches from the literature (columns 4, 5 and 6): The Bat Algorithm (BA) approach investigated in [32], the Hybrid Genetic Algorithm/Local Search algorithm (Hybrid) proposed in [62] and the New Island Model Genetic Algorithm (NIMGA) presented in [29]. In addition, Average Makespan and average computational time for the NIMGA approach are reported in columns 7 and 8.

Table 7 Results of EOP-DHS for the JSSP and comparison with different metaheuristic proposals

Table 7 results show that OP-DHS algorithm to the JSSP depicts either a superior or a highly competitive searching behavior comparatively to the investigated approaches. Indeed, achieving a BCm and an MRD respectively equal to 12 and 1.03%, OP-DHS algorithm clearly outperforms the BA that obtains respectively 0 and 1.57% for the considered measures. We note that the basic BA has been chosen as a comparative algorithm because, not using any complementary improvement operators, it is considered from the same algorithmic class of EOP-DHS approach. The results also show that OP-DHS algorithm outperform GA/TS approach that attains an MRD of 3,84% and a BCm equal to 5. The GA/TS approach represents an example of a sophisticated optimization method using a hybrid of a genetic algorithm and a Tabu Search. Besides, comparatively to the effective NIMGA, obtained average Makespan and computational time results of the EOP-DHS approach reflect a superior behavior both in term of robustness and efficiency for the resolution of JSSP. Indeed, EOP-DHS results are clearly superior to those of NIMGA for both average Makespan and computational time. It is important to mention that the parallel three populations-based NIMGA have been implemented in C + + and tested using a computing environment close to the one used for this study (a PC with 3.40 GHz Intel(R) Core(TM) i7-3770 CPU and 8.00GB).

Thus, considering obtained results and the admitted intractability of most of the investigated benchmarking instances, it can be affirmed that the OP-DHS approach depicts a highly competitive behavior both in term of effectiveness and efficiency for the resolution of the JSSP with Makespan criterion. That particular and complementary result confirms specially the effectiveness of the adopted HS framework and used improvisation scheme for the resolution of hard combinatorial scheduling problems.

6 Conclusion and future works

In this paper, an Effective Operations Permutation-based Discrete Harmony Search approach was proposed to solve the FJSSP with Makespan criterion. Proposed EOP-DHS approach adopts an integrated “affectation-sequencing” two-part representation of the solution harmony and a dedicated improvisation operator particularly adapted to the integer-valued and operations permutation-based used coding scheme. A complementary search operator, the Modified Intelligent Mutation (MIM) is integrated to the adopted framework in order to enhance its overall search ability by probabilistically balancing maximum machine workload during the overall search process. MIM operator allows essentially maintaining and enhancing the reciprocal equilibrium of diversification and intensification abilities of the proposed EOP-DHS algorithm. For performances assessment purpose, EOP-DHS approach has been experimented on a set of 188 test problems and compared with a representative spectrum of metaheuristic resolution approaches recently formulated for the FJSSP. Obtained and discussed results indicate that the proposed algorithm is effective for the resolution of the FJSSP. In addition, a complementary experimental procedure proving the effectiveness of the adopted permutation-based HS scheme for the resolution of hard combinatorial optimization problems exemplified by the JSSP has been carried on.

Enhancement of the approach considering its efficiency will be considered in future works. Furthermore, an extended examination of the adopted Permutation-based improvisation framework for the resolution of other hard combinatorial problems will be of a notable usefulness.