Mathematical modeling and two metaheuristic algorithms for integrated process planning and group scheduling with sequence-dependent setup time

Abstract

The advancement of technology enables manufacturing companies to employ multifunction machines to increase the flexibility of a system in producing miscellaneous products in a short time. In this situation, goods can be usually produced through different process plans, and considering process planning and scheduling in an integrated framework would be essential. Furthermore, group processing is regarded to overcome the difficulty of long setup times and consequently increase the productivity of a manufacturing system. This paper deals with the integrated process planning and group scheduling problem with sequence-dependent setup time between each group of jobs. Two mixed-integer linear programming models with different approaches are presented. Moreover, two metaheuristic algorithms are proposed to solve the problems heuristically. The experiments show the high performance of the combination-based mathematical model for small-size problems as well as the proposed metaheuristic algorithms for medium-size and large-size instances.

1 Introduction

In today’s highly competitive business environment, producing not only high quality with minimum cost but also customized products in a short time is very important. In such a competitive market, manufacturing companies must be capable of responding to instantaneous changes rapidly. To achieve this goal, high flexibility is required in the manufacturing system. As two essential functions, process planning and scheduling have significant impacts on the flexibility and thus the efficiency of the manufacturing system. Process planning determines the selection and sequence of production operations based on product design specification as well as the required manufacturing resources, including machines, tools and tool-approach direction (TAD). In general, a process plan identifies how a product can be manufactured according to engineering design. On the other hand, scheduling allocates limited manufacturing resources to the operation in the process plans over time, subject to the precedence relations in the process plan.

These two functions are traditionally performed sequentially. Scheduling plans were generated after process plans had been determined. The disadvantages of this method were reported in the IPPS-related research (Li et al. 2010a, b). For example, in the separate process planning manufacturing systems, it is assumed that the resources have infinite capacity and are always available too. Therefore, process planners consider the most desirable resources for each job. It may cause unbalanced loads of resources and create an unexpected bottleneck. Besides, because of unpredictable shop floor disturbances such as machine breakdown, order cancellation, rush order, adding of a new machine, and the machine maintenance, and especially, the delay between the process planning and scheduling phases, the predefined optimal process plans generated in the process planning phase may even be infeasible. Some surveys show that up to 30% of process plans have to be modified due to the changing shop floor condition (Li et al. 2010d). By integrating process planning and scheduling, the load of the resources is balanced, and flow-time, work-in-process inventory, cycle time, and thus production costs are reduced (Lee and Kim 2001).

Three kinds of flexibility can be considered in the integrated process planning and scheduling (IPPS) context: operation flexibility (OF), sequencing flexibility (SF), and processing flexibility (PF). OF refers to the possibility of performing an operation on different machines and is also called routing flexibility. SF implies the availability of various permutations of manufacturing operations as long as they satisfy the precedence constraints to create a specific feature of a job, and PF means the possibility of producing the same manufacturing feature with an alternative set of operations. By taking all these flexibilities into account, although more reliable and stable plans are generated, but makes the IPPS problem much more complicated.

Furthermore, based on the concept of group technology (GT), jobs are organized into different groups according to their similarity in design, shape, material, processing operations, or other characteristics. This approach results in a reduction of setup time, throughput time, work-in-process inventory, simplification of material, and good flows and thus increases the productivity and efficiency of a manufacturing system (Lu and Logendran 2013). Production scheduling based on group technology is called “group scheduling” (Ham et al. 1985). In group scheduling (with a GT assumption), all jobs of a group are processed consecutively without interruption by jobs of a different group. Two levels of sequencing can be observed in a group scheduling problem. At the first level, a sequence of jobs within each group has to be determined, which is called a job sequence. At the second level, a group sequence is identified. These two levels should be considered simultaneously while solving group scheduling problems because of their strong interactions.

Since jobs in the same group are similar, the setup time required to change from one job to another can be ignored or included in processing times. However, a major setup time would be needed to switch from one group to another, which can be sequence-dependent or sequence-independent. The required setup for a machine is sequence-dependent if it depends on both the current and the group previously processed on that machine.

Sequence-dependent group scheduling (SDGS) is widely studied under various circumstances and objective functions in the flow shop environment. However, to the best of our knowledge, the benefits of group scheduling in other shop floors have not been considered yet, while it can be observed in a lot of production systems, especially where high technology multifunction machines are available. These machines process parts in a short time, but setup times for changing between functions are considerably high. For instance, in a compressor’s filter manufacturing company, three kinds of filters are produced: air/oil separator, air filter, and oil filter. To produce each kind of filter, some operations and machines are needed, which are usually common in one or even all two other types. The filters in each category are processed together, aiming to achieve setup time reduction, whereas their process routes are different. In this case, the rolling machine is needed for all three kinds of filters, but its setup requirement is different, and it depends on which type of filters are processed previously. Furthermore, each of the aforementioned products can be manufactured in more than one way, and for some operations such as cutting and spot welding, alternative machines with different processing and setup times are available. Thus, in order to take the characteristics of this real-world instance into account, a novel process planning and group scheduling problem arises.

In this paper, the integrated process planning and group scheduling problem with sequence-dependent setup time (IPPGS-SDST) has been investigated. This problem can be considered as a flexible job shop scheduling problem (FJSP) with multiple routings and sequence-dependent setup time group processing. From another point of view, the IPPGS-SDST problem can be regarded as a sequence-dependent group scheduling in a flexible job shop environment with multiple process plans. Jobs are assigned to different groups. Jobs can be processed through various process plans, while a process plan can be selected for all jobs in the same group, and some or all operations can be performed by alternative machines. All jobs of a group are subsequently processed without being interrupted by a job from a different group, and each group requires a sequence-dependent setup time on each machine. The characteristics of both flow shop and job shop environments can be found in this problem. Within each group, all jobs must be performed in the specified order, but each group of jobs as a whole has its own route. So, it contains a flow shop problem at the job sequencing level and also a job shop problem at the group sequencing level.

Since a two-machine group scheduling problem with sequence-dependent setup time is NP-hard in the strong (Gupta and Darrow 1986; Kleinau 1993), so the IPPGS problem will be a strongly NP-hard problem which is more difficult to achieve optimal solutions by traditional accurate solution methods with reasonable time and effort. However, in order to study the nature of the problem and recognize its characteristics, two mathematical formulations are presented in this paper. One is based on the traditional point of view, and the other is network graph-based which is more applicable and efficient. Moreover, two metaheuristic algorithms are applied to find a good enough solution in an acceptable time: (1) a genetic algorithm (GA) with a new two-section representation, and (2) a hybrid water cycle algorithm (WCA) which utilize both WCA and GA operators. The main contributions of this paper can be summarized as follows:

• (1) Inspired by modern manufacturing systems where the mass production of customized products is accomplished by multifunction machines, the IPPGS-SDST problem is considered for the first time.

• (2) The problem is modeled mathematically in two different approaches to figure out more the characteristics of the problem.

• (3) Due to group processing, the algorithms proposed in the IPPS literature cannot be applied for the considered problem. Furthermore, the group scheduling approaches are only applicable in a flow shop environment. Therefore, one of the most successful algorithms for the IPPS problem has been developed. Moreover, WCA as a novel approach is applied with an efficient discrete strategy to solve the IPPGS problem.

• (4) In all solution methods of the IPPS problems, a list of process plans should be prepared as a prerequisite for running the algorithm. This time-consuming phase is eliminated using the second mathematical model approach in both presented algorithms.

The remainder of the paper is organized as follows: in Sect. 2, we review some relevant literature on the integration of process planning and scheduling as well as group scheduling separately. Representation and definition of the IPPGS problem with sequence-dependent setup time is presented in Sect. 3. Section 4 introduces the proposed MILP models and presents a comparison of the models according to the most critical complexity indices. The proposed genetic and hybrid water cycle algorithm are elaborated in Sect. 5. In Sect. 6, the managerial insight of the proposed problem is explained by an example to clarify the importance of the subject. Section 7 evaluates the proposed solution methods using generated benchmark problems. The last section is the conclusion and further research suggestions.

2 Literature review

Group scheduling, firstly presented by Hitomi and Ham (1976), has been discussed by many researchers for a long time. In addition, both sequence-dependent and sequence-independent setup times between processing groups have been considered. The first mixed-integer linear programming model for SDGS problems was investigated by Salmasi et al. (2010) with the minimization of total completion time as the criterion. Along with proposing some metaheuristic algorithms based on tabu search and ant colony optimization, they applied the mathematical model to develop a lower bounding method based on a branch-and-price algorithm. By modifying this model, Naderi and Salmasi (2012) presented two better MILP models for the permutation flow shop sequence-dependent group scheduling (FSDGS) problem. Their model was modified by Behjat and Salmasi (2017) to support the no-wait assumption. Shahvari et al. (2012) proposed a model for the flexible flow shop sequence-dependent group scheduling problem with the minimization of makespan as the criterion using the concept of slots. Their considered problem was formulated by Keshavarz and Salmasi (2013) with sequence-based variables where jobs can skip some stages. They showed that their model is much smaller than the model proposed by Shahvari et al. in terms of the number of constraints, binary variables, and continuous variables. A bi-criteria formulation of FSDGS for minimizing the weighted sum of the total weighted completion time and the total weighted tardiness was considered by Lu and Logendran (2013). A comprehensive review can be found in Neufeld et al. (2016). Nevertheless, the majority of group scheduling research has been discussed in a flow shop or flow line shop floor environment. As a result, group processing of parts has not been studied in the IPPS problem yet. In the following paragraphs, a comprehensive literature review of IPPS has been presented.

The basic idea of process planning and scheduling was first introduced by Chryssolouris et al. (1984). The first heuristic algorithm for the IPPS problem was also proposed in Khoshnevis and Chen (1991) based on opportunistic planning and used a time window to enhance its performance. The IPPS problem has widely been considered by many researchers over the past three decades. Numerous approaches have been proposed, including mathematical programming methods, meta-heuristic algorithms, and multi-agent systems for different single and multiple objectives (Jin et al. 2015). Since the single-objective case of the problem is studied in this paper, most of the related works with multi-objective functions have not been considered here.

Brandimarte and Calderini (1995) developed a bi-level hierarchical model for the IPPS problem. In the first level, a set of process plans was optimized, considering cost and load balancing as objectives. Then in the second one, for each process plan, Tabu search was used to generate the optimized scheduling plan while the makespan was taken into account. The first mixed integer programming model was presented in Kim and Egbelu (1999) for the IPPS problem with a makespan objective. They developed a MILP model for JSP in which each job has multiple process plans or operation routing. However, it is only applicable for small-size problems. Tan and Khoshnevis (2004) proposed a polynomial mixed integer programming model (PMIPM) for the IPPS problem. However, each feature consists of only one operation in their model, and sequence and process flexibility have not been considered. Kim et al. (2003) utilized a symbiotic evolutionary algorithm (SEA) with random symbiotic partner selection, which outperformed the two traditional approaches, i.e., the hierarchical approach (Brandimarte and Calderini 1995) and the co-evolutionary cooperative algorithm (Potter et al. 1994). A new approach based on the multi-agent system was developed by Wang and Shen (2003) in a distributed manufacturing environment. Notable instances of multi-agent approach in IPPS were reported in Wong et al. (2006a, b). They proposed an agent-based negotiation approach in Wong et al. (2006a) and then presented an online hybrid agent-based negotiation (oHAN) system in Wong et al. (2006b) by extending their approach with the supervisor agent and rescheduling function.

A simulated annealing-based optimization approach was utilized by Li and McMahon (2007) to facilitate the optimization of integrated process planning and scheduling. Their proposed algorithm was compared with GA and PSO considering various objective functions like makespan, job tardiness, balanced machine utilization. A multi-agent system (MAS) using data mining with a hybrid TS-SA algorithm was presented in Shukla et al. (2007). Li et al. (2008) proposed a game theory-based cooperation applying Pareto, Nash, and Stackelberg theory and GA, SA, and PSO as optimization algorithms. Some applications of PSO for IPPS can be found in Guo et al. (2009a, b). Chan et al. (2009) used a hybrid of GA, SA, and fuzzy logic controller (FLC), outperforming GA, SA, TS, and hybrid TS and SA. A preliminary implementation of an ant colony-based optimization algorithm on multi-agent systems was proposed in Leung et al. (2010). Li et al. (2010c) developed a hybrid algorithm (HA) based on an effective GA with an efficient local search scheme. Many subsequent scholars used the proposed HA to evaluate their solution methods as a comparison basis. Zhao et al. (2010) discussed the IPPS problem in holonic manufacturing systems, and the hybrid particle swarm optimization was presented to solve the utilization of all machines problem. Other noteworthy approaches developed for the IPPS problem are improved genetic algorithm (IGA) (Lihong and Shengping 2012), the imperialist competitive algorithm (ICA) (Lian et al. 2012a, b), active learning genetic algorithm (ALGA) (Li et al. 2012), and memetic algorithm (MA) (Jin et al. 2016b).

As recent notable works, Zhang and Wong (2014) proposed an enhanced ant colony optimization (E-ACO) to solve the IPPS problem. The result of the algorithm was compared with the SEA, IGA, and two-stage ACO algorithm. An object-coding genetic algorithm (OCGA) was implemented for IPPS (Zhang and Wong 2015a). In OCGA, genetic representation was based on real objects, and operation sequences were directly used as chromosomes. The performance of the proposed algorithm was evaluated against CCGA, SEA, and IGA using benchmark problems proposed in Kim et al. (2003). It shows their algorithm can reach the lower bound for 14 of 24 problems and for the other 10 problems, and the best results are very close to their lower bounds. Jin et al. (2015) proposed an MILP model for the IPPS problem as well as a hybrid honey bee mating optimization (HBMO) and variable neighborhood search (VNS) to solve the IPPS problem. A new ant colony optimization algorithm was used for the IPPS problem by Liu et al. (2016). Their comparison results showed that the proposed algorithm had better performance for 9 of 10 Kim’s benchmark problems. Zhang and Wong (2016) presented a generic framework for implementing constructive meta-heuristics. ACO, as a widely-used constructive meta-heuristic, was illustrated as an example while an enhanced mapping rule was constructed. Petrović et al. (2016) considered IPPS with five flexibility types, i.e., machine, tool, tool access direction (TAD), process, and sequence flexibility, and used AND/OR network to describe the flexibilities. They applied the chaotic particle swarm optimization (cPSO) algorithm to solve this problem using ten different chaotic maps. Sobeyko and Mönch (2016) assumed that products could be manufactured with different bills of materials (BOM) and routes for the same product and considered the total weighted tardiness as the objective. They proposed variable neighborhood search and efficient heuristic based on local search to solve the problem.

In the domain of IPPS mathematical modeling, four MILP models for IPPS problems were also developed by Jin et al. (2016a). Unlike previous MILP models in the literature, which assume that all the process plans are generated in advance (Type-1), their proposed Type-2 models are suitable for network graph-based instances and are able to solve the instances expressed by an AND/OR graph while both the Manne’s and the Wagner’s modeling approaches are used. Other mathematical modeling approaches of IPPS problems can be found in Liu et al. (2016), Sobeyko and Mönch (2016), and Zhang et al. (2015). Regarding the high complexity of the IPPS problem, exact solution methods are rarely used. Barzanji et al. (2019) applied the Benders decomposition algorithm. They divided the IPPS problem into master-problem and sub-problem based on the decision variables. In their approach, process plan and operation-machine assignment variables are optimized in the master-problem while the sub-problem determines the scheduling variables. Since they assumed a set of process plans predetermined in advance for each job, their algorithm is not applicable to the IPPS problem in which multiple process plans are presented by network graphs.

The merits of separate consideration of setup times have been investigated widely in production scheduling problems, and some reviews have been conducted (Allahverdi 2015; Allahverdi et al. 1999, 2008). In the IPPS domain, however, most of the research has assumed setup times to be a part of processing times or can be ignored. A few papers were considered the IPPS problem with setup time issues. Imanipour (2006) presented nonlinear mixed-integer programming for the IPPS problem considering sequence-dependent setup times and proposed a hybrid of tabu search and a greedy neighborhood search to solve the problem. However, process flexibility was not considered in the model, and no comparison has been made between the results of the proposed algorithm and the mathematical model. Wan et al. (2011) applied an ant colony optimization algorithm constructed under a multi-agent system for the IPPS problem with inseparable and sequence-dependent setup time. However, the setup requirements added to IPPS problem tests to conduct the experiments are sequence-independent. In Nourali et al. (2012), a mixed-integer programming model for IPPS based on Manne’s approach in the flexible assembly job shop environment with sequence-dependent setup time was developed by modifying the model of Özgüven et al. (2010). Altarazi and Yasin (2015) presented a MIP mathematical model for the IPPS problem with sequence-dependent setup time. However, alternative machines for each operation were not considered. They employed the proposed model to solve a small-size example. Four types of setup time (part loading/unloading, fixture preparation, tool/TAD changing, and transportation) have been studied in the IPPS problem by Zhang and Wong (2015b) and compared with the situation that the setup times are ignored or absorbed into processing times. An enhanced ant colony optimization (E-ACO) has been applied to solve the problem. Their results have shown that when setup times are considered separately, more accurate optimal schedules will be generated in most cases. A recent setup and transportation time consideration in the IPPS problem has been done in Ha (2019). Although three types of setup time, i.e., setup change time, tool change time, and unloading time were taken into account, but they only depended on the type of machine.

As it was mentioned before, technology advancement makes the use of SDGS inevitable in any shop floors with the aim of increasing the productivity and efficiency of a manufacturing system. This is the specific gap discussed in this paper.

3 Problem definition

The IPPGS-SDST problem can be defined as $n$ jobs to be accomplished by $m$ machines. jobs are assigned to $g$ groups according to group technology so that group $s$ has ${n}_{s}$ jobs. Because of the technological similarity among the jobs of a group, a set of process plans ${T}_{s}$ or equivalently a set of operation combinations ${H}_{s}$ is available for all jobs in the same group. The goal is to assign a process plan to all jobs in each group, select a processing machine for each operation in the process plan and find the best sequence of processing the jobs as well as the groups in order to minimize the makespan.

The alternative process plans and precedence constraints are specified by disjunctive AND/OR graphs. There are three node types in an AND/OR graph: starting node, operation node, and ending node. The starting node and the ending node are dummy nodes and, respectively, indicate the start and the completion of the manufacturing process of a job (or group of jobs). Other nodes are operation nodes, which include the operation number, the available alternative machines, and corresponding processing times. An arrow between two nodes indicates the precedence relation between them: if node A is connected to node B, operation B should be processed after operation A directly or indirectly. If there is an OR mark on a node, it means that the operations on only one OR link path should be processed. For nodes without an OR label, all operations on link paths coming from that node should be performed (Jin et al. 2016a).

$l$th process plan of job $i$ contains a set of operations (${NO}_{i,l}$). Similarly, $h$th operation combination of job $i$ includes a set of operations (${NO}_{i,h}$). Each operation is to be processed by one of the alternative machines with known processing time. Each group requires a setup time on each machine, which depends on both the selected machine and the previously processed group (sequence-dependent setup time).

An IPPGS problem is shown in Fig. 1. It consists of five jobs categorized in two groups (${G}_{1}=\left\{{J}_{1}\text{, }{J}_{2}\right\}$ and ${G}_{2}=\left\{{J}_{3}\text{, }{J}_{4}, {J}_{5}\right\}$). Four multifunction machies are available (${M}_{1}, {M}_{2}, {M}_{3}, {M}_{4}$). The jobs in groups 1 and 2 can be processed according to graph A and graph B, respectively. According to the graphs, three process plans for group 1 and two process plans for group 2 can be recognized as follows:

Fig. 1

An IPPGS problem instance with two groups of jobs

$${T}_{1}=\left\{\begin{array}{c}{O}_{1}\to {O}_{2}\to {O}_{2}\\ {O}_{1}\to {O}_{3}\to {O}_{4}\\ {O}_{1}\to {O}_{4}\to {O}_{3}\end{array},\right.\quad {T}_{2}=\left\{\begin{array}{c}{O}_{1}\to {O}_{2}\to {O}_{3}\to {O}_{4}\\ {O}_{1}\to {O}_{3}\to {O}_{2}\to {O}_{4}\end{array}\right..$$

In other words, the jobs in group 1 can be performed through two operation combinations while the jobs in group 2 have only one operation combination as demonstrated below:

$${H}_{1}=\left\{{O}_{1},{O}_{2}\right\},\left\{{O}_{1},{O}_{3},{O}_{4}\right\},\quad {H}_{2}=\left\{{O}_{1},{O}_{2},{O}_{3},{O}_{4}\right\}.$$

It means the jobs in group 1 can be done by $\left\{{O}_{1},{O}_{2}\right\}$ or $\left\{{O}_{1},{O}_{3},{O}_{4}\right\}$ while all operations of graph B are needed to perform the jobs of group 2. Moreover, the following assumptions are taken into account:

• A machine can execute only one operation at a given time.

• Different operations from one job cannot be processed at the same time

• The group technology assumption is considered, i.e., the jobs in the same group must be processed in succession, and the process of the jobs belonging to a group cannot be interrupted by another job belonging to another group.

• If a machine can process more than one kind of operation (multifunction machines are available), the process of one kind of operation cannot be interrupted by another kind of operation even if both operation kinds are related to the same groups or jobs (the operational constraint)

• All setup and processing times are deterministic, known in advance.

• Group setup operations are anticipatory, i.e., they can be started before the arrival of the first job in the group when the processing machine is idle.

• All jobs and machines are independent and available at time zero.

• Jobs are non-preemptive.

• Once the operation of a job is finished, it will be immediately transferred to another machine (the transport time is negligible).

• Setup times between the jobs in the same group are negligible or included in the processing time.

4 Mathematical models

Due to the combination of two manufacturing functions and the aforementioned flexibility types existing in manufacturing systems, the IPPS problem belongs to the complex, difficult NP-hard problem (Petrović et al. 2016). Although mathematical model-based accurate algorithms cannot achieve an optimal solution in a reasonable computational time, but also mathematical modeling can point out the characteristics of the problem accurately and provide a basis for evaluating other algorithms.

Considering the noticeable mathematical programming models in the research area of IPPS and group scheduling, two mathematical models with different approaches are presented for the IPPGS problem in this section: (1) the process plan-based model, and (2) the combination-based model. In both models, we consider a dummy group ($s=0$) consisting of a dummy job ($i=0$) with one process plan or operation combination. The dummy job is assumed to have one operation on each machine with zero processing time. Dummy jobs are used to identify the required initial setup on each machine. When a group/job processes after the dummy group/job, it is the first group /job on the related machine.

4.1 The process plan-based model

To develop the process plan-based mathematical model for IPPGS problems, we suppose a list of possible process plans (${T}_{s}$) are available in advance for the jobs in each group. In order to define the aforementioned problem mathematically, the following notations, parameters, and decision variables are adopted:

$s, {s}^{{\prime}}$:

Groups

$i, {i}^{{\prime}}$:

Jobs

$j, {j}^{{\prime}}$:

Operations

$l, {l}^{{\prime}}$:

Process plans

$k$:

Machines

$G$:

The set of groups

$N$:

The set of jobs

$M$:

The set of machines

${G}_{s}$:

The set of jobs in group $s$

${T}_{s}$:

The set of process plans for all jobs in group $s$

${NO}_{i,l}$:

The set of operations of $l$ th process plan of job $i$

${O}_{i,j,l}$:

The $j$ th operation of job $i$ using the $l$ th process plan of the job

$M{O}_{k}$:

The set of operations can be processed on machine $k$

${R}_{i,j,l}$:

The set of available machines for ${O}_{i,j,l}$

${t}_{i,j,l,k}$:

The processing time of ${O}_{i,j,l}$ on machine $k$

$g=\left|G\right|$:

The number of groups

$n=\left|N\right|$:

The number of jobs

$m=\left|M\right|$:

The number of machines

${n}_{s}=\left|{G}_{s}\right|$:

The number of jobs in group $s\in \left\{1,2,\dots ,g\right\}$

${a}_{s,{s}^{{\prime}},k}$:

The setup time of the group ${s}^{{\prime}}$ if it is processed immediately after group $s$on machine $k$

$A$:

A very large positive number

Variables

${C}_{max}$: Makespan

${X}_{i,l}=\left\{\begin{array}{l}1,\text{ if the }l\text{th alternative process plan of job }i\text{ is selected}\\ 0, \, {\text{otherwise}}\end{array}\right.$

${Z}_{i,j,l,k}=\left\{\begin{array}{l}1,\quad {\text{if}} \, {{O}}_{{{i}},{{j}},{{l}}} \, {\text{is}} \, {\text{processed on machine}}\, {{k}} \\ 0,\quad {\text{otherwise}}\end{array}\right.$

${Y}_{i,{i}^{{\prime}},j,l}=\left\{\begin{array}{l}1,\quad \text{ if }{O}_{i,j,l}\text{ precedes the operation }{O}_{{i}^{{\prime}},j,l}\\ 0,\quad {\text{otherwise}}\end{array}\right.$

$\begin{aligned}& {U}_{s,{j,l,s}^{\prime},{j}^{\prime},{l}^{\prime},k}\\ & =\left\{\begin{array}{ll}1, &\quad \text{If the } {j}^{\prime}\text{th operation of a job in group } {s}^{\prime}\text{ using the }\\&\quad {l}^{\prime}\text{th process plan is processed immediately} \\ 0& \quad \text{after the } j\text{th operation of a job in group } s \text{ using the }\\&\quad l \text{th process plan on machine } k \\ 0, &\quad \text{otherwise}\end{array}\right.\end{aligned}$

${C}_{i,j}$: The completion time of the $j$ th operation of job $i$

${ST}_{s,j,k}$: The starting time of the $j$ th operation of the first job of group $s$ on machine $k$

${FT}_{s,j,k}$: The finishing time of the $j$ th operation of the last job of group $s$ on machine $k$

According to above definitions, the process plan-based model is formulated as follows:

$${\mathrm{Min }C}_{max}$$

(1)

s.t.

$$\sum_{l\in {T}_{s}}{X}_{i,l}=1, \quad \forall s\in G, i\in {G}_{s}$$

(2)

$${X}_{i,l}={X}_{{i}^{{\prime}},l},\quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{S}$$

(3)

$$\sum_{k\in {R}_{i,j,l}}{Z}_{i,j,l,k}+\left(1-{X}_{i,l}\right)=1, \quad \forall s\in G, i\in {G}_{s}, l\in {T}_{s}, j\in {NO}_{i,l}$$

(4)

$${Z}_{i,j,l,k}={Z}_{{i}^{{\prime}},j,l,k}\quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{S}, j\in {NO}_{i,l},k\in {R}_{i,j,l}$$

(5)

$${C}_{i,j}\ge {C}_{i,j-1}+\sum_{k\in {R}_{i,j,l}}{t}_{i,j,l,k} {Z}_{i,j,l,k},\quad \forall s\in G, i\in {G}_{s}, l\in {T}_{s}, j\in {NO}_{i,l}, j>1$$

(6)

$$\begin{aligned}{C}_{{i}^{{\prime}},j}& \ge {C}_{i,j}+{t}_{{i}^{{\prime}},j,l,k}-A\left(3-{Y}_{i,{i}^{{\prime}},j,l}-{Z}_{i,j,l,k}-{Z}_{{i}^{{\prime}},j,l,k}\right),\\ & \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{s}, j\in {NO}_{i,l}, k\in {R}_{i,j,l}\end{aligned}$$

(7)

$$\begin{aligned}{C}_{i,j}&\ge {C}_{{i}^{{\prime}},j}+{t}_{i,j,l,k}-A\left(2+{Y}_{i,{i}^{{\prime}},j,l}-{Z}_{i,j,l,k}-{Z}_{{i}^{{\prime}},j,l,k}\right), \\ & \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{s}, j\in {NO}_{i,l}, k\in {R}_{i,j,l}\end{aligned}$$

(8)

$${Y}_{i,{i}^{{\prime}},j,l}\le {X}_{i,l},\quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{s}, j\in {NO}_{i,l}$$

(9)

$${Y}_{i,{i}^{{\prime}},j,l}\le {X}_{{i}^{{\prime}},l},\quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, l\in {T}_{s}, j\in {NO}_{i,l}$$

(10)

$${C}_{i,j}\ge {ST}_{s,j,k}+{t}_{i,j,l,k}-A\left(1-{Z}_{i,j,l,k}\right), \forall s\in G, i\in {G}_{s}, l\in {T}_{s}, j \in {NO}_{i,l}, k\in {R}_{i,j,l}$$

(11)

$${FT}_{s,j,k}\ge {C}_{i,j}-A\left(1-{Z}_{i,j,l,k}\right),\quad \forall s\in G, i\in {G}_{s}, l\in {T}_{s}, j\in {NO}_{i,l}, k\in {R}_{i,j,l}$$

(12)

$$\begin{aligned}{ST}_{{s}^{{\prime}},{j}^{{\prime}},k}& \ge {FT}_{s,j,k}+{a}_{s,{s}^{{\prime}},k}-A\left(1-{U}_{s,{j,l,s}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}},k}\right), \\ & \quad \forall s,{s}^{{\prime}}\in G\text{, }{s}^{{\prime}}\ne 0\text{, }i\in {G}_{s}, {i}^{{\prime}}\in {G}_{{s}^{{\prime}}}, l\in {T}_{s},{ l}^{{\prime}}\in {T}_{{s}^{{\prime}}}, \\ &\quad j\in {NO}_{i,l}, {j}^{{\prime}}\in {NO}_{{i}^{{\prime}},{l}^{{\prime}}}\text{, }k\in {R}_{i,j,l}\cap {R}_{{i}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}}}\end{aligned}$$

(13)

$$\begin{aligned}&\sum_{s\in G}\sum_{i\in {G}_{s}}\sum_{l\in {T}_{s}}\sum_{\begin{subarray}{c} j \in {NO}_{i,l}\\ {O}_{i,j,l}\in M{O}_{k}\end{subarray}}\left(\frac{{U}_{s,{j,l,s}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}},k}}{{n}_{s}}\right)={Z}_{{i}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}},k},\\ & \quad \forall {s}^{{\prime}}\in G, {s}^{{\prime}}\ne 0, {i}^{{\prime}}\in {G}_{{s}^{{\prime}}},{ l}^{{\prime}}\in {T}_{{s}^{{\prime}}}, {j}^{{\prime}}\in {NO}_{{i}^{{\prime}},{l}^{{\prime}}}\text{, }k\in {R}_{{i}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}}}\end{aligned}$$

(14)

$$\begin{aligned}& \sum_{\begin{subarray}{c}{s}^{{\prime}}\in G\\ {s}^{{\prime}}\ne 0\end{subarray}}\sum_{{i}^{{\prime}}\in {G}_{{s}^{{\prime}}}}\sum_{{ l}^{{\prime}}\in {T}_{{s}^{{\prime}}}}\sum_{\begin{subarray}{c} {j}^{{\prime}} \in {NO}_{{i}^{{\prime}},{ l}^{{\prime}}}\\ {O}_{{i}^{{\prime}},{j}^{{\prime}},{ l}^{{\prime}}}\in {MO}_{k}\end{subarray}}\left(\frac{{U}_{s,{j,l,s}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}},k}}{{n}_{{s}^{{\prime}}}}\right)\le {Z}_{i,j,l,k},\\ & \quad \forall s\in G, i\in {G}_{s}\text{, }l\in {T}_{s}, j\in {NO}_{i,l}\text{, }k\in {R}_{i,j,l}\end{aligned}$$

(15)

$${C}_{max}\ge {C}_{i,j}, \quad \forall s\in G, i\in {G}_{s}, l\in {T}_{s}, j \in {NO}_{i,l}$$

(16)

$${C}_{i,j}, {ST}_{s,j,k}, {FT}_{s,j,k}\ge 0$$

(17)

$${X}_{i,l}, {Z}_{i,j,l,k}, {Y}_{i,{i}^{{\prime}},j,l}, {U}_{s,{j,l,s}^{{\prime}},{j}^{{\prime}},{l}^{{\prime}},k}\in \left\{0,1\right\}$$

(18)

The makespan minimization is expressed by Eq. (1) as the objective function. Constraint set (2) ensures that only one process plan is selected for each job. The same process plan should be chosen for all jobs in a group. Constraint set (3) is incorporated into the model in order to support this fact. Constraint set (4) is incorporated into the model to make sure that each operation of a selected process plan for a job is assigned to only one machine. Constraint set (5) implies the $j$th operation of all jobs in the same group must be processed on the same machine, consequently (group technology assumption). Since a job cannot be processed on two different machines at the same time, the completion time of an operation should be greater than the completion time of the previous operation plus its processing time. Constraint set (6) is incorporated into the model in order to support this fact. Constraint sets (7) and (8) are included in the model to schedule different operations on the same machine. Operation ${O}_{i,j,l}$ can precede operation ${O}_{{i}^{{\prime}},j,l}$ if process plan $l$ is selected for job $i$. In addition, operation ${O}_{{i}^{{\prime}},j,l}$ can be processed after operation ${O}_{i,j,l}$ if process plan $l$ is selected for job ${i}^{{\prime}}$. Constraint sets (9) and (10) express these statements, respectively. Constraint set (11) ensures that each job should start after starting times of the group it belongs to. Constraint set (12) ensures that the completion time of a group on each machine is greater than or equal to the completion time of its jobs on that machine. The start time of processing a job belonging to a specific group (say group ${s}^{{\prime}}$) on a machine (say machine $k$) is greater than the completion time of the immediately previous group (say group $s$) process on the machine plus the related sequence-dependent setup time (i.e., ${a}_{s,{s}^{{\prime}},k}$). Constraint set (13) is incorporated into the model for this reason. Constraint set (14) supports the statement that if group ${s}^{{\prime}}$ is processed on machine $k$, then only one group precedes immediately group ${s}^{{\prime}}$ or group ${s}^{{\prime}}$ is the first group on the machine. Constraint set (15) ensures that at most one group follows immediately group $s$ on machine $k$. Constraint set (16) is used to capture the value of the makespan. Constraint sets (17) and (18) define the decision variables.

4.2 The combination-based model

As mentioned above, Type-2 models for IPPS problems were developed by Jin et al. (2016a) based on the term “combination,” which defines as the different operation combinations that a job can perform through them. As they discussed, the main motive to develop Type-2 models is that it is sometimes so difficult to identify and generate all the process plans for a job according to its AND/OR graph.

As an example, more than 100 process plans can be identified for a job with the relatively simple AND/OR graph in Fig. 2. However, there is only one combination of operations for the job. Clearly, it is time-consuming and sometimes impossible to list all process plans of jobs with more complicated graphs. Based on this weakness, the combination-based model emerged.

Fig. 2

An AND/OR graph with numerous process plans

In this section, a mathematical model is presented by applying the combination concept and the results of the Jin et al. research using the Manne's approach. Notations, parameters, and decision variables of the model are as follows:

$s, {s}^{{\prime}}$:

Groups

$i, {i}^{{\prime}}$:

Jobs

$j, {j}^{{\prime}}$:

Operations

$h, {h}^{{\prime}}$:

Combinations

$k$:

Machines

$G$:

The set of groups

$N$:

The set of jobs

$M$:

The set of machines

${N}_{i}$:

The set of operations of job $i$

${G}_{s}$:

The set of jobs in group $s$

${H}_{s}$:

The set of operation combinations for all jobs in group $s$

${NO}_{i,h}$:

The set of operations of $h$ th combination of job $i$

${O}_{i,j}$:

The $j$ th operation of job $i$

${OH}_{h}$:

The set of operations (${O}_{i,j}$) including combination $h$

$M{O}_{k}$:

The set of operations (${O}_{i,j}$) can be processed on machine $k$

${R}_{i,j}$:

The set of available machines for ${O}_{i,j}$

Parameters

${t}_{i,j,k}$: the processing time of ${O}_{i,j,l}$ on machine $k$

$g=\left|G\right|$ : the number of groups

$n=\left|N\right|$ : the number of jobs

$m=\left|M\right|$ : the number of machines

${n}_{s}=\left|{G}_{s}\right|$ : the number of jobs in group $s\in \left\{1,2,\dots ,g\right\}$

$\begin{aligned}{V}_{i,j,{j}^{{\prime}}}=\left\{\begin{array}{*{20}l}1, & \quad \text{if the } {O}_{i,j}\text{ is an immediate predecessor of }{O}_{i,{j}^{{\prime}}}\\ & \quad \text{according to the network graph of job }i\\ 0, & \quad {\text{otherwise}}\end{array}\right.\end{aligned}$

${Q}_{i,j,{j}^{{\prime}}}=\left\{\begin{array}{*{20}l}10, & \quad \text{ if the }{O}_{i,j}\text{ should be processed before }{O}_{i,{j}^{{\prime}}}\\ & \quad\text{ directly or indirectly according to the network graph of job }i \\ 0, & \quad {\text{otherwise}}\end{array}\right.$

${a}_{s,{s}^{{\prime}},k}$: the setup time of the group ${s}^{{\prime}}$ if it is processed immediately after group $s$ on machine $k$

$A$: a very large positive number

Variables

${C}_{max}$: Makespan

${X}_{i,h}=\left\{\begin{array}{*{20}l}1,&\quad {\text{if}} \, {\text{the}} \, {{h}} \, {\text{th}} \, {\text{alternative combination of}}\\&\quad {\text{operations is selected to accomplish job}} \, {{i}} \\ 0,&\quad {\text{otherwise}}\end{array}\right.$

${Z}_{i,j,h,k}=\left\{\begin{array}{*{20}l}1,&\quad \text{ if the }h\text{ th combination is selected for job } i\text{ and }{O}_{i,j}\\&\quad\text{ is processed on machine }k\\ 0,&\quad {\text{otherwise}}\end{array}\right.$

${Y}_{i,j,{j}^{{\prime}}}=\left\{\begin{array}{ll}1,& {\text{if}} \, {{O}}_{{{i}},{{j}}} \, {\text{precedes}} \, {\text{the}} \, {\text{operation}} \, {{O}}_{{{i}},{{j}}^{{\prime}}} \\ 0,& {\text{otherwise}}\end{array}\right.$

${U}_{i,{i}^{{\prime}},j}=\left\{\begin{array}{ll}1,& \text{ if }{O}_{i,j}\text{ precedes the operation }{O}_{{i}^{{\prime}},j}, i,{i}^{{\prime}}\in {G}_{s}\\ 0,& {\text{otherwise}}\end{array}\right.$

$\begin{aligned}& {W}_{s,{j,s}^{{\prime}},{j}^{{\prime}},k} \\ &\quad=\left\{\begin{array}{*{20}l}10,& \quad \text{If the }{j}^{{\prime}} \text{th operation of a job in group }{s}^{{\prime}}\text{ is processed immediately}\\ &\quad \text{after the } j\text{th operation of a job in group } s\text{ on machine }k \\ 0,&\quad {\text{otherwise}}\end{array}\right.\end{aligned}$

${C}_{i,j}$: the completion time of the $j$ th operation of job $i$

${ST}_{s,j,k}$: the starting time of the $j$ th operation of the first job of group $s$ on machine $k$

${FT}_{s,j,k}$: the finishing time of the $j$ th operation of the last job of group $s$ on machine $k$

With regard to above definitions, the combination-based model of the IPPGS is formulated as follows:

$${\mathrm{Min }C}_{max}$$

(19)

s.t.

$$\sum_{h\in {H}_{s}}{X}_{i,h}=1, \quad \forall s\in G, i\in {G}_{s}$$

(20)

$${X}_{i,h}={X}_{{i}^{{\prime}},h}, \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, h\in {H}_{s}$$

(21)

$$\sum_{k\in {R}_{i,j}}{Z}_{i,j,h,k}+\left(1-{X}_{i,h}\right)=1, \quad \forall s\in G, i\in {G}_{s}, h\in {H}_{s}, j\in {NO}_{i,h}$$

(22)

$${Z}_{i,j,h,k}={Z}_{{i}^{{\prime}},j,h,k} \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}\text{, }h\in {H}_{s}, j\in {NO}_{i,h}\text{, }k\in {R}_{i,j}$$

(23)

$$\begin{aligned}{C}_{i,{j}^{{\prime}}}& \ge {C}_{i,j}+\sum_{k\in {R}_{i,{j}^{{\prime}}}}{t}_{i,{j}^{{\prime}},k} {Z}_{i,{j}^{{\prime}},h,k}-A\left(1-{X}_{i,h}\right),\\ & \quad \forall s\in G, i\in {G}_{s}, h\in {H}_{s}, j,{j}^{{\prime}}\in {NO}_{i,h}, j\ne {j}^{{\prime}}, {V}_{i,j,{j}^{{\prime}}}=1\end{aligned}$$

(24)

$$\begin{aligned}&{Y}_{i,j,{j}^{{\prime}}}+{Y}_{i,{j}^{{\prime}},j}=1,\\ & \quad \forall s\in G-\left\{0\right\}.i\in {G}_{s}, h\in {H}_{s}, j,{j}^{{\prime}}\in {NO}_{i,h}, j<{j}^{{\prime}}, {Q}_{i,j,{j}^{{\prime}}}+{Q}_{i,{j}^{{\prime}},j}=0,\end{aligned}$$

(25)

$${Y}_{i,j,{j}^{{\prime}}}={Y}_{{i}^{{\prime}},j,{j}^{{\prime}}}\quad \forall s\in G-\left\{0\right\}.i.{i}^{{\prime}}\in {G}_{s}\text{, }i<{i}^{{\prime}}. h\in {H}_{s}, j,{j}^{{\prime}}\in {NO}_{i,h}, j\ne {j}^{{\prime}}, {Q}_{i,j,{j}^{{\prime}}}+{Q}_{i,{j}^{{\prime}},j}=0$$

(26)

$$\begin{aligned}{C}_{i,{j}^{{\prime}}}& \ge {C}_{i,j}+\sum_{k\in {R}_{i,{j}^{{\prime}}}}{t}_{i,{j}^{{\prime}},k} {Z}_{i,{j}^{{\prime}},h,k}-A\left(1-{Y}_{i,j,{j}^{{\prime}}}\right)\\ & \quad \forall s\in G-\left\{0\right\}.i\in {G}_{s}, h\in {H}_{s}, j,{j}^{{\prime}}\in {NO}_{i,h}, j\ne {j}^{{\prime}}, {Q}_{i,j,{j}^{{\prime}}}+{Q}_{i,{j}^{{\prime}},j}=0\end{aligned}$$

(27)

$$\begin{aligned}{C}_{{i}^{{\prime}},j}& \ge {C}_{i,j}+{t}_{{i}^{{\prime}},j,k}-A\left(3-{U}_{i,{i}^{{\prime}},j}-{Z}_{i,j,h,k}-{Z}_{{i}^{{\prime}},j,h,k}\right),\\ & \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, h\in {H}_{s}, j\in {NO}_{i,h}, k\in {R}_{i,j}\end{aligned}$$

(28)

$$\begin{aligned}& {C}_{i,j}\ge {C}_{{i}^{{\prime}},j}+{t}_{i,j,k}-A\left(2+{U}_{i,{i}^{{\prime}},j}-{Z}_{i,j,h,k}-{Z}_{{i}^{{\prime}},j,h,k}\right),\\ & \quad \forall s\in G, i,{i}^{{\prime}}\in {G}_{s}, i<{i}^{{\prime}}, h\in {H}_{s}, j\in {NO}_{i,h}, k\in {R}_{i,j}\end{aligned}$$

(29)

$${C}_{i,j}\ge {ST}_{s,j,k}+{t}_{i,j,k}-A\left(1-{Z}_{i,j,h,k}\right),\quad \forall s\in G, i\in {G}_{s}, h\in {H}_{s}, j\in {NO}_{i,h}, k\in {R}_{i,j}$$

(30)

$${FT}_{s,j,k}\ge {C}_{i,j}-A\left(1-{Z}_{i,j,h,k}\right),\quad \forall s\in G, i\in {G}_{s}, h\in {H}_{s}, j\in {NO}_{i,h}, k\in {R}_{i,j}$$

(31)

$$\begin{aligned}{ST}_{{s}^{{\prime}},{j}^{{\prime}},k}& \ge {F}_{s,j,k}+{a}_{s,{s}^{{\prime}},k}-A\left(1-{W}_{s,{j,s}^{{\prime}},{j}^{{\prime}},k}\right),\\ & \quad \forall s,{s}^{{\prime}}\in G\text{, }{s}^{{\prime}}\ne 0\text{, }i\in {G}_{s}, {i}^{{\prime}}\in {G}_{{s}^{{\prime}}}, h\in {H}_{s},{ h}^{{\prime}}\in {H}_{{s}^{{\prime}}},\\&\quad j\in {NO}_{i,h}, {j}^{{\prime}}\in {NO}_{{i}^{{\prime}},{h}^{{\prime}}}\text{, }k\in {R}_{i,j}\cap {R}_{{i}^{{\prime}},{j}^{{\prime}}}\end{aligned}$$

(32)

$$\begin{aligned}&\sum_{s\in G}\sum_{i\in {G}_{s}}\sum_{\begin{subarray}{c} j\in {N}_{i}\\ {O}_{i,j}\in {MO}_{k}\end{subarray}}\left(\frac{{W}_{s,{j,s}^{{\prime}},{j}^{{\prime}},k}}{{n}_{s}}\right)=\sum_{\begin{subarray}{c}{h}^{{\prime}}\in {H}_{{s}^{{\prime}}}\\ {O}_{{i}^{{\prime}},{j}^{{\prime}}}\in {OH}_{{h}^{{\prime}}}\end{subarray}}{Z}_{{i}^{{\prime}},{j}^{{\prime}},{h}^{{\prime}},k},\\ & \quad \forall {s}^{{\prime}}\in G, {s}^{{\prime}}\ne 0, {i}^{{\prime}}\in {G}_{{s}^{{\prime}}}, {j}^{{\prime}}\in {N}_{{i}^{{\prime}}}\text{, }k\in {R}_{{i}^{{\prime}},{j}^{{\prime}}}\end{aligned}$$

(33)

$$\begin{aligned}&\sum_{\begin{subarray}{c}{s}^{{\prime}}\in G\\ {s}^{{\prime}}\ne 0\end{subarray}}\sum_{{i}^{{\prime}}\in {G}_{{s}^{{\prime}}}}\sum_{\begin{subarray}{c}{j}^{{\prime}}\in {N}_{{i}^{{\prime}}}\\ {O}_{{i}^{{\prime}},{j}^{{\prime}}}\in {MO}_{k}\end{subarray}}\left(\frac{{W}_{s,{j,s}^{{\prime}},{j}^{{\prime}},k}}{{n}_{{s}^{{\prime}}}}\right)\le \sum_{\begin{subarray}{c}h\in {H}_{s}\\ {O}_{i,j}\in {OH}_{h}\end{subarray}}{Z}_{i,j,h,k},\\ & \quad \forall s\in G, i\in {G}_{s}, j\in {N}_{i}\text{, }k\in {R}_{i,j}\end{aligned}$$

(34)

$${C}_{max}\ge {C}_{i,j},\quad \forall s\in G, i\in {G}_{s}, h\in {H}_{s}, j \in {NO}_{i,h}$$

(35)

$${C}_{i,j}, {ST}_{s,j,k}, {FT}_{s,j,k}\ge 0$$

(36)

$${X}_{i,l}, {Z}_{i,j,h,k}, {Y}_{i,j,{j}^{{\prime}}}, {U}_{i,{i}^{{\prime}},j}. {W}_{s,{j,s}^{{\prime}},{j}^{{\prime}},k}\in \left\{0,1\right\}$$

(37)

The makespan minimization is expressed by Eq. (19) as an objective function. Constraint set (20) ensures that only one combination is selected for each job. The same combination of operations should be chosen for all jobs in a group. Constraint set (21) is incorporated into the model in order to support this fact. Constraint set (22) is incorporated into the model to make sure that each operation is assigned to only one machine. Constraint set (23) implies the $j$ th operation of all jobs in the same group must be processed on the same machine, consequently (group technology assumption). Constraint set (24) is incorporated into the model to compute the completion time of two operations of a job that have immediate precedence in the related network graph. Constraint sets (25–27) determine the sequence of the operations that have no explicit precedence relationship with each other in the network. Among them, constraint set (27) ensures that all jobs in the same group should select the same process plan and hence should traverse the same route. Constraint sets (28) and (29) are incorporated into the model to schedule different operations on the same machine. Constraint set (30) ensures that each job should start after starting times of the group it belongs to. Constraint set (31) ensures that the completion time of a group on each machine is greater than or equal to the completion time of its jobs on that machine. The start time of processing a job belonging to a specific group (say group ${s}^{{\prime}}$) on a machine (say machine $k$) is greater than the completion time of the immediately previous group (say group $s$) process on the machine plus the related sequence-dependent setup time (i.e., ${a}_{s,{s}^{{\prime}},k}$). Constraint set (32) is incorporated into the model for this reason. Constraint set (33) supports the statement that if group ${s}^{{\prime}}$ is processed on machine $k$, then only one group precedes immediately group ${s}^{{\prime}}$ or group ${s}^{{\prime}}$ is the first group on the machine. Constraint set (34) ensures that at most one group follows immediately group $s$ on machine $k$. Constraint set (35) is used to capture the value of the makespan. Constraint sets (36) and (37) define the decision variables.

4.3 Comparison of the models

In this section, two proposed models are compared with each other according to the number of constraints (NC), the number of binary variables (NBV), and the number of continuous variables (NCV). As mentioned in the previous section, in many cases, only the graph of jobs confirms the superiority of the combination-based model, especially when some jobs have high sequence flexibility. In this situation, it is tedious to prepare a full list of process plans as a prerequisite for the process plan-based model. Hence, to compare the models, six low sequence flexibility graphs—taken from Zhang and Wong (2014), Zhang and Wong (2016), and Zhang and Wong (2015a) and presented in Fig. 3—are applied to generate five IPPGS problems with five machines. These problems are provided in different sizes, i.e., the different number of groups, jobs, and consequently, the total numbers of operations (TNO). Each problem has a total $n$ jobs in $g$ groups which ${n}_{1}$ jobs are in the first group with process plans depicted in AND/OR graph 1 (${G}_{1}$), ${n}_{2}$ jobs are in the second group with process plans depicted in AND/OR graph 2 (${G}_{2}$), and ${n}_{g}$ jobs are in the $g$ th group with process plans depicted in AND/OR graph $g$ (${G}_{g}$).

Fig. 3

AND/OR graphs used for comparison of the models

Table 1 provides the NC of the models for different problem sizes The combination-based model consists of less NC than the process plan-based one in all sizes. Table 2 includes the same problems to compare the NBV of the proposed models. The combination-based model has significantly less the NBV than the other model. In most sizes, the NBV of the process plan-based model is more than twice the NBV of the combination-based model. Finally, Table 3 compares the model based on the NCV. The process plan-based model formulates the problem with fewer continuous variables. However, the difference between the two models according to the NCV is less than 7%.

Table 1 Number of constraints (NC) comparison of the models

Table 2 Number of binary variables (NBV) comparison of the models

Table 3 Number of continuous variables (NCV) comparison of the models

The comparison of the two models shows considerable superiority in the NC and the NBV and, on the other hand, low inferiority in the NCV of the combination-based model. Since the type of both models above is mixed-integer linear programming, the NCV has a less substantial effect on the model performance. As a result, the combination-based model is more efficient. So, it is used to provide the basis for evaluating the following proposed solution algorithms. However, in the problem instances where all jobs have low sequence flexibility, the process plan-based model can be more efficient because the limited process plans are simply recognizable, and also, it is not required to build ${V}_{i,j,{j}^{{\prime}}}$ and ${Q}_{i,j,{j}^{{\prime}}}$ matrixes.

5 Solution methods

As mentioned in Sect. 1, the high level of complexity and huge solution space of the IPPGS problem makes the use of metaheuristic algorithms inevitable because it is almost impossible to achieve an optimal solution by accurate algorithms in reasonable times. In this section, two efficient metaheuristic algorithms are developed. The first one is a genetic algorithm with a new two-section and object-coding representation, and the other one is a hybrid of the relatively novel water cycle algorithm and genetic algorithm. As it is mentioned, in all optimization approaches of the IPPS domain, a list of process plans should be prepared at first, which is a tedious and time-consuming initial phase of these solution methods, mainly when the problem includes at least one graph with a high level of sequence flexibility. To settle these difficulties, the same approach in mathematical modeling, that is, the combination-based approach, is used for both metaheuristic optimization algorithms, too.

5.1 Genetic algorithm

Genetic algorithms were extensively applied with various characteristics in the IPPS domain. In some early studies, the basic procedure of the algorithm was used (Morad and Zalzala 1999). A few researchers combined it with other optimization methods to construct a hybrid algorithm for IPPS problem (Amin-Naseri and Afshari 2012; Li et al. 2019a, b; Uslu et al. 2018), while in many cases, an improved version of GA was applied (Li et al. 2012; Lihong and Shengping 2012; Luo et al. 2017; Mohapatra et al. 2015; Shao et al. 2009; Zhang et al. 2014). Also, since chromosome representation is the most important factor in the performance of a GA, some researchers focus on presenting efficient representation (Lee and Ha 2019).

In this section, a classical genetic algorithm using an object-coding representation presented by Zhang and Wong (2015a) is adopted with some modifications for the IPPGS problem. The most applicable procedures of GA, where each iteration consists mainly of the population generation, selection of parents, genetic operations, and population evaluation and truncation, were adopted to solve the problem.

5.1.1 Genetic representations

In order to gather all information included in AND/OR graphs of the IPPGS problem in an encoded chromosome and use it during the optimization process, a two-section representation is applied. Section 1 (numerical section) is a numerical representation that shows the operation combination used by each group, respectively, while Sect. 2 (object section) is based on real objects and indicates the sequence of operations based on the precedence relationship between them. The first section has $g$ (number of groups) genes, but the number of genes for the second section depends on the information provided in the first section.${O}_{i,j}^{k}$ in each gene of the chromosome represents $j$ th operation of job $i$ which performs on machine $k$ from its set of alternative machines.

A chromosome is presented in Fig. 4 representing a problem instance with five jobs in two groups. Jobs 1 and 2 are in group 1, and jobs 3, 4, and 5 are in group 2. Two groups can be processed on five machines, according to respectively graph 1 and graph 2 illustrated in Fig. 3a and b. Due to group processing, the same achine should be selected for the same operations of all jobs in a group.

Fig. 4

A chromosome for the IPPGS problem instance

In the above chromosome, the jobs in group 1 use their operations in combination 2 (${O}_{1}, {O}_{4}, {O}_{5})$, and the jobs in group 2 are planning to perform through their operations in only one available combination (${O}_{1}, {{O}_{2}, {O}_{3}, O}_{4}\text{, }{O}_{5}$). The object-coding section of the chromosome indicates the order of operation to enter the corresponding schedule. It should be noted that all the same operations of the jobs in the same group must be processed consecutively according to group technology assumption.

5.1.2 Initial population, individual evaluation, and selection of parents

With regard to the encoding scheme, the initial population, including ${N}_{pop}$ individuals are generated randomly, while precedence constraints are satisfied. On the other hand, the same machine is selected for the same operations of all jobs in a group. For example, in Fig. 4, machine 2 is assigned to all operations ${O}_{3,1}, {O}_{4,1}$, and ${O}_{5,1}$. Individual evaluation is based on the optimization criteria, which is to minimize the makespan in this paper. The popular tournament selection method is adopted in this algorithm to select a pair of parent individuals.

5.1.3 Genetic operators

Due to three kinds of flexibilities, i.e., process flexibility, sequence flexibility, and operation flexibility, and on the other hand, two levels of sequencing, i.e., job sequencing and group sequencing, GA operators should be capable of exploring and exploiting the entire search space according to all flexibilities and sequencing levels. In this proposed GA, the group processing version of the Precedence Preserving Order-based Crossover (POX) and three mutation operators, that is, shifting genes’ loci, shifting processing machines, and shifting operation combinations, are implemented.

5.1.3.1 Crossover

Crossover, which was applied on both the numerical and object sections of two individuals, focuses on all different flexibilities and sequencing levels in the IPPGS problem to construct new neighborhood space toward different dimensions for the GA. Crossover is executed with the probability of ${P}_{c}$ for each population member; in other words, it is applied by the GA with the number of $\frac{{P}_{c}\text{.}{N}_{pop}}{2}$ times in each iteration, and hence, ${n}_{c}={P}_{c}\text{.}{N}_{pop}$ offspring are reproduced. The Precedence Preserving Order-based Crossover (POX) (Luo et al. 2017; Zhang et al. 2005; Zhang and Wong 2015a) with group consideration is applied. In this recombination, operations of the same job between two individuals are exchanged in the situation precedence relationships are satisfied. The approach of the crossover operator is illustrated by an example in Fig. 5. ${P}_{1}$ and ${P}_{2}$ are selected from the population as parent chromosomes, and ${C}_{1}$ and ${C}_{2}$ are initially two empty indivisuals. A group is selected, and all jobs within it are put in JobSet 1. Other remaining jobs are gathered in JobSet 2. Then, for the object section, the operations of jobs in JobSet 1 of ${P}_{1}$ and ${P}_{2}$ are copied to the corresponding positions in ${C}_{1}$ and ${C}_{2}$. Afterwards, the vacancies in ${C}_{1}$ and ${C}_{2}$ are filled by the operations of jobs in JobSet 2 of ${P}_{2}$ and ${P}_{1}$ respectively with the same orders from left to right. Finally, remaining vacancies are omitted from new offspring. For the numerical section, the related positions of the selected group in ${C}_{1}$ and ${C}_{2}$ are filled by the corresponding numbers in ${P}_{1}$ and ${P}_{2}$, and for other groups, contrariwise, they are filled by the corresponding numbers in ${P}_{2}$ and ${P}_{1}$ respectively.

Fig. 5

Illustration of the crossover operator

5.1.3.2 Shifting genes' loci

The mutation of shifting genes' loci is used to alter operation sequences in the object section of an individual while the numerical section remains unchanged. To prevent the violation of precedence relationship between operations of the same job, a precedence preserving version of shifting genes' loci is exerted with the probability of ${P}_{m}$, and therefore ${n}_{m}={P}_{m}\text{.}{N}_{pop}$ individuals are reproduced in each iteration as follows:

Step 1: select an individual, say, ${I}_{1}$.

Step 2: make a copy of ${I}_{1}$ and obtain ${I}_{2}$.

Step 3: select two loci on ${I}_{2}$ randomly (${L}_{1}$ and ${L}_{2}$).

Step 4: if the related operations on ${L}_{1}$ and ${L}_{2}$ belong to the same job, eliminate ${L}_{1}$ and ${L}_{2}$, and go to Step 3; otherwise, go to Step 5.

Step 5: assume the operations on ${L}_{1}$ and ${L}_{2}$ belong to Job 1 and Job 2, respectively. Eliminate the operation on ${L}_{1}$, and shift all operations of Job 2 backward one by one to keep their orders until the operation on ${L}_{2}$ is shifted, and the gene on ${L}_{2}$ is empty.

Step 6: shift forward the operation of Job 1 one by one from left to right to keep their orders until all genes are filled. Other operations do not move.

Figure 6 illustrates precedence preserving shifting genes' loci. Numbers on the arcs show the shifting orders of operations.

Fig. 6

Illustration of precedence preserving shifting genes' loci

5.1.3.3 Shifting processing machines

In this mutation, which affects only the object section of an individual, the same operations of the jobs in the same group can change their processing machine simultaneously with the probability of ${P}_{k}$. It is performed on one of the offspring obtained from the crossover. Figure 7 explains how this mutation works on ${C}_{1}$. In this case, the processing machine of the second operations of the jobs in group 2 is changed from machine 3 to machine 2.

Fig. 7

Shifting processing machines

5.1.3.4 Shifting operation combinations

While shifting genes’ loci and shifting processing machines focus on respectively sequence and operation flexibilities, the main mutation idea in shifting operation combinations is based on the process flexibility and the number of OR link paths. It is applied to the other offspring which is not mutated with shifting processing machines, here ${C}_{2}$. In this mutation, another operation combination is selected for a group which has more than one operation combination – or have at least one OR node in its graph- with the probability of ${P}_{h}$ (usually ${P}_{h}<$ 0.1), and the related number in the numerical section is changed. This alteration completely affects the object section, and operations in one OR link path are substituted by the operations in a different OR link path but the same OR nodes. Omitted operations are replaced with new ones in the same order. If new operations are less than omitted one, empty genes should be eliminated; otherwise, if new operations are more than omitted ones, the genes with the related order should be multiplied to create enough genes for further operations. The mutation of shifting operation combinations helps GA to avoid getting trapped in a suboptimal solution or premature convergence.

An overview of this mutation is given in Fig. 8, where operation combination 2 with OR link path $\left\{{O}_{1},{O}_{4},{O}_{5}\right\}$ replace operation combination 1 with OR link path $\left\{{O}_{1},{O}_{2}, {O}_{3},{O}_{5}\right\}$ for all jobs in group 1. Hence, two empty genes are eliminated. When assigning processing machines to newly added operations, the same machine should be chosen for the same operations of all jobs in a group.

Fig. 8

Shifting operation combinations

5.1.4 Population evolution and truncation

As explained before, in each iteration of the proposed GA, the crossover operator produces ${n}_{c}$ individuals which $\frac{{n}_{c}}{2}$ of them are used in the mutation of shifting processing machines, and remaining $\frac{{n}_{c}}{2}$ offspring are mutated through shifting operation combinations. Shifting processing machines may not produce new individuals if the selected operations do not have an alternative machine. Shifting operation combinations will not produce new individuals if the chosen group has only one operation combination. On the other hand, shifting genes’ loci reproduces ${n}_{m}$ new individuals in each iteration. In total, at most $2{n}_{c}+{n}_{m}$ individuals are added to initial ${N}_{pop}$ individuals. Therefore, the worst individuals are eliminated at the end of each iteration to reduce the population size to ${N}_{pop}$. The general procedure of the proposed GA is as follows:

5.2 Hybrid water cycle algorithm (HWCA)

The WCA introduced by Eskandar et al. (2012) is a population-based metaheuristic algorithm. It is inspired by the hydrologic cycle process in nature and how rivers and streams flow downhill toward the sea. Despite the capabilities of the WCA to explore and exploit the search space of complex problems, the WCA was utilized in only two studies. Nayak et al. (2018) used WCA for the multiprocessor scheduling problem and compared it to GA. Their results showed that WCA outperforms GA. An improved discrete WCA (DWCA) was employed in Gao et al. (2017) for solving remanufacturing rescheduling problem.

Using the water from the rain, streams are created. The population of streams, as individuals, forms an initial population. After that, a number of ${N}_{sr}$ good individuals in terms of the objective function are considered the sea and rivers, and the best individual among them is chosen as the sea. Hence, ${N}_{sr}$ is the summation of the number of rivers plus one (sea). All other individuals are considered streams which flow to rivers and sea. In a $N$-dimension problem (i.e., a problem with $N$ design variables), a stream is defined as follows:

$$\mathrm{A\, stream }=\left[{x}_{1},{x}_{2}, {x}_{3}, \dots , {x}_{N}\right],$$

(38)

Consequently, a sorted population with ${N}_{pop}$ streams are given as follows (Sadollah et al. 2015b):

$$\text{Population of streams}=\left[\begin{array}{c}\begin{array}{c}{Stream}_{1}\\ {Stream}_{2}\\ {Stream}_{3}\end{array}\\ \vdots \\ {Stream}_{{N}_{pop}}\end{array}\right]=\left[\begin{array}{ccc}\begin{array}{ccc}\begin{array}{c}{x}_{1}^{1}\\ {x}_{1}^{2}\\ \begin{array}{c}\vdots \\ {x}_{1}^{{N}_{pop}}\end{array}\end{array}& \begin{array}{c}{x}_{2}^{1}\\ {x}_{2}^{2}\\ \begin{array}{c}\vdots \\ {x}_{2}^{{N}_{pop}}\end{array}\end{array}& \begin{array}{c}{x}_{3}^{1}\\ {x}_{3}^{2}\\ \begin{array}{c}\vdots \\ {x}_{3}^{{N}_{pop}}\end{array}\end{array}\end{array}& \begin{array}{c}\cdots \\ \cdots \\ \begin{array}{c}\vdots \\ \cdots \end{array}\end{array}& \begin{array}{c}{x}_{N}^{1}\\ {x}_{N}^{2}\\ \begin{array}{c}\vdots \\ {x}_{N}^{{N}_{pop}}\end{array}\end{array}\end{array}\right]$$

(39)

which can be given as a sorted population of streams based on the optimization criterion as follows:

$$Sorted\, population\, of \,streams =\left[\begin{array}{c}\begin{array}{c}Sea\\ {River}_{1}\\ \begin{array}{c}{River}_{2}\\ {River}_{3}\\ \vdots \end{array}\end{array}\\ \begin{array}{c}{Stream}_{{N}_{sr}+1}\\ {Stream}_{{N}_{sr}+2}\\ \begin{array}{c}{Stream}_{{N}_{sr}+3}\\ \vdots \end{array}\end{array}\\ {Stream}_{{N}_{pop}}\end{array}\right]$$

(40)

The number of streams which flow directly or indirectly to the rivers or sea is ${N}_{Streams}$, and is calculated using Eq. (41) as follows:

$${N}_{Streams}={N}_{pop}-{N}_{sr}$$

(41)

The sea and each river absorb a number of streams according to their flow magnitude. In fact, some of ${N}_{Streams}$ streams flow to the sea, and others flow to rivers. The number of streams which flow to the sea and each river is calculated using Eqs. (42) and (43) as follows (Eskandar et al. 2012):

$${C}_{n}={Cost}_{n}-{Cost}_{{N}_{sr}+1}$$

(42)

$${NS}_{n}=round\left\{\left|\frac{{C}_{n}}{{\sum }_{n=1}^{{N}_{sr}}{C}_{n}}\right|\times {N}_{Streams}\right\}, \quad n=1,2,\dots ,{N}_{sr}$$

(43)

where ${NS}_{1}$ is the designated streams for the sea, ${NS}_{2}$ is the designated streams for the best river, ${NS}_{3}$ is the designated streams for the second-best river, and so on. So, ${NS}_{{N}_{sr}}$ is the number of streams flow to the worst river. Using the above equations, streams tend to move toward the sea and rivers based on their quality in the term of the fitness function. In this way, the sea as the best individual possesses more streams. Each stream is controlled by one of the rivers or sea. Therefore, the sum of designated streams (${\sum }_{n=1}^{{N}_{sr}}{NS}_{n}$) should be equal to the total numbers of streams (${N}_{Streams}$). However, ${\sum }_{n=1}^{{N}_{sr}}{NS}_{n}$ may not be equal to ${N}_{Streams}$ after the designation of streams. In this situation, some modifications on ${NS}_{n}$ are needed (Sadollah et al. 2015b).

Hence, as the exploitation phase in the WCA, streams move toward their related river or sea, and rivers also move toward the sea. The new positions for streams and rivers have been proposed as follows:

$${\overrightarrow{X}}_{Stream}\left(t+1\right)={\overrightarrow{X}}_{Stream}\left(t\right)+rand\times C\times \left({\overrightarrow{X}}_{River}\left(t\right)-{\overrightarrow{X}}_{Stream}\left(t\right)\right),$$

(44)

$${\overrightarrow{X}}_{Stream}\left(t+1\right)={\overrightarrow{X}}_{Stream}\left(t\right)+rand\times C\times \left({\overrightarrow{X}}_{Sea}\left(t\right)-{\overrightarrow{X}}_{Stream}\left(t\right)\right),$$

(45)

$${\overrightarrow{X}}_{River}\left(t+1\right)={\overrightarrow{X}}_{River}\left(t\right)+rand\times C\times \left({\overrightarrow{X}}_{Sea}\left(t\right)-{\overrightarrow{X}}_{River}\left(t\right)\right),$$

(46)

where $1<C<2$ and rand is a uniformly distributed random number between 0 and 1. When the solution provided by a stream is better than its joining river, then the positions of river and stream are exchanged. Similarly, the exchange of the positions can happen for rivers and sea, and sea and streams as well.

Moreover, for the exploration phase, evaporation and raining processes are defined in Sadollah et al. (2015b) to enhance the capability of the algorithm to escape from local optima. Considering the mathematical perspective, if norm distances among rivers, streams, and sea are smaller than a predefined value (${d}_{max}$), new streams are generated flowing into the rivers and sea. The following criteria are used as evaporation conditions:

$$\Vert {\overrightarrow{X}}_{Sea}-{\overrightarrow{X}}_{River}^{i}\Vert <{d}_{max}\, \mathrm{or} \,rand<0.1 \quad i=1,2,\dots ,{N}_{sr}-1,$$

(47)

$$\Vert {\overrightarrow{X}}_{Sea}-{\overrightarrow{X}}_{Stream}^{i}\Vert <{d}_{max}\quad i=1,2,\dots ,{NS}_{1},$$

(48)

where ${d}_{max}$ is a small number close to zero, which controls the search intensity near the sea. The value of ${d}_{max}$ decreases in each iteration as follows:

$${d}_{max}\left(t+1\right)={d}_{max}\left(t\right)-\frac{{d}_{max}\left(t\right)}{max\text{\_}iteration}$$

(49)

More details about the original idea of the WCA, as well as a comparison to some other population-based algorithms, can be found in Eskandar et al. (2012), Sadollah et al. (2015a), Sadollah et al. (2015b), and Jafar et al. (2018). The steps of WCA are summarized as follows:

Step 1. Set the main parameters of the WCA (${N}_{pop},{N}_{sr},{d}_{max},\mathrm{max}\_iteration$).

Step 2. Generate an initial population of streams randomly using Eq. (38) and Eq. (39).

Step 3. Calculate the cost of all streams in the population.

Step 4. Choose a number of ${N}_{sr}$ from the best individuals as the sea and rivers. The individual, which has the best fitness value, is considered the sea.

Step 5. Determine the flow magnitude for rivers and sea using Eqs. (42) and  (43). If ${\sum }_{n=1}^{{N}_{sr}}{NS}_{n}={N}_{Streams}$ go to Step 7; otherwise, Step 6.

Step 6. Perform ${NS}_{n}$ modification procedure until ${\sum }_{n=1}^{{N}_{sr}}{NS}_{n}={N}_{Streams}$ and then go to Step 7.

Step 7. Streams flow to its joining river, according to Eq. (44). If the solution provided by a stream is better than its joining river, then exchange the positions of river and stream and go to Step 8; otherwise, go to Step 9.

Step 8. If the solution provided by a new river is better than the sea, then exchange the positions of a new river and sea.

Step 9. Streams move towards the sea based on Eq. (45). If the solution provided by a stream is better than the sea, then exchange their positions.

Step 10.Rivers flow to the sea using Eq. (46). If the solution provided by a river is better than the sea, then exchange their positions.

Step 11. Check evaporation conditions for rivers and the sea using Eq. (47). If it is satisfied, the raining process will take place, and the river is replaced by a new randomly generated stream.

Step 12. Check evaporation conditions for streams and the sea using Eq. (48). If it is satisfied, the raining process will take place, and the stream is replaced by a new randomly generated one.

Step 13. Reduce the value of ${d}_{max}$ using Eq. (49).

Step 14. If the stop criterion is satisfied, output the sea as the best solution; otherwise, return to Step 7 and repeat.

5.2.1 Encoding and decoding scheme

The WCA is a continuous algorithm in essence. Therefore, in order to apply the WCA for discrete search space (like the IPPGS problem), a discrete strategy should be provided. Due to all kinds of flexibility and two levels of job and group sequencing in the IPPGS problem, a discrete strategy is needed to cover all search space as much as possible. In this paper, $\left(3m+2\right)$ random number matrixes ($m$ is the number of machines) with elements distributed uniformly between $\left(0,1\right)$ are used as follows:

Random number matrix	Size
$X$	$g\times {h}_{max}$
${Z}_{k} \forall k=1,2,\dots ,m$	$g\times {J}_{max}$
${J}_{k} \forall k=1,2,\dots ,m$	$1\times n*{J}_{max}$
${S}_{k} \forall k=1,2,\dots ,m$	$1\times g$
$K$	$1\times m$

where $g$: the number of groups, $n$: the number of jobs, $m$: the number of machines, ${h}_{max}$: the maximum number of combinations, ${J}_{max}$: the maximum number of operations.

The set of above matrixes represents a stream as an individual, and therefore it is equivalent to a solution of the problem. Matrix $X$ is used to identify the operation combination of each job. Based on the group, including the job, the operation combinations of the group according to its AND/OR graph, and the maximum random number of the related row in this matrix, an operation combination is selected for each job. For the problem illustrated in Sect. 5.1.1, five jobs are categorized in two groups with at most two operation combinations. So, matrix $X$ can be as follows:

$$X=\left[\begin{array}{cc}0\text{.}0835& 0\text{.}6260\\ 0\text{.}3215& 0\text{.}5901\end{array}\right]$$

Jobs 1 and 2 in the first group, perform through their second operation combination (${O}_{1},{ O}_{4}\text{, }{O}_{5}$), while jobs 3,4, and 5 in the second group used their only one available combination (${O}_{1}, {{O}_{2}, {O}_{3}, O}_{4}\text{, }{O}_{5}$).

Matrixes ${Z}_{k}$ identify the selected machine for each operation. The processing machine is selected based on the group, including the job, the selected operation combination of the group according to matrix $X$, the available operations in the related combination, the available processing machines for each operation, and, finally, the maximum of associated random numbers. As an example of the considered problem instance, there are five matrixes ${Z}_{1}, {Z}_{2},\dots , {Z}_{5}$ as follows:

$$\begin{aligned}&{Z}_{1}=\left[\begin{array}{ccc}0\text{.}7829& 0\text{.}0427& \begin{array}{ccc}0\text{.}6730& 0\text{.}7669& 0\text{.}1932\end{array}\\ 0\text{.}6938& 0\text{.}3782& \begin{array}{ccc}0\text{.}4775& 0\text{.}6671& 0\text{.}2959\end{array}\end{array}\right]\\& {Z}_{2}=\left[\begin{array}{ccc}0\text{.}3119& 0\text{.}6289& \begin{array}{ccc}0\text{.}9976& 0\text{.}9274& 0\text{.}1248\end{array}\\ 0\text{.}1790& 0\text{.}1015& \begin{array}{ccc}0\text{.}8116& 0\text{.}9175& 0\text{.}5306\end{array}\end{array}\right]\end{aligned}$$

$${Z}_{3}=\left[\begin{array}{ccc}0\text{.}8352& 0\text{.}6195& \begin{array}{ccc}0\text{.}9727& 0\text{.}3569& 0\text{.}5906\end{array}\\ 0\text{.}3225& 0\text{.}3606& \begin{array}{ccc}0\text{.}3278& 0\text{.}6627& 0\text{.}6604\end{array}\end{array}\right]\quad {Z}_{4}=\left[\begin{array}{ccc}0\text{.}7150& 0\text{.}1386& \begin{array}{ccc}0\text{.}8770& 0\text{.}1892& 0\text{.}8112\end{array}\\ 0\text{.}8562& 0\text{.}5882& \begin{array}{ccc}0\text{.}3531& 0\text{.}9345& 0\text{.}0193\end{array}\end{array}\right]$$

$${Z}_{5}=\left[\begin{array}{ccc}0\text{.}4035& 0\text{.}3480& \begin{array}{ccc}0\text{.}0474& 0\text{.}8936& 0\text{.}7218\end{array}\\ 0\text{.}1220& 0\text{.}1217& \begin{array}{ccc}0\text{.}3424& 0\text{.}0548& 0\text{.}8778\end{array}\end{array}\right]$$

Regarding matrix $X$, Jobs 1 and 2 in the first group, should be done through their second operation combination, i.e.,${O}_{1},{ O}_{4},$ and ${O}_{5}$. The first operation (${O}_{1}$) can be processed on ${M}_{1}$, ${M}_{3}$, and ${M}_{4}$. In order to select the processing machine, the elements in the first row and the second column of ${Z}_{1}$, ${Z}_{3}$, and ${Z}_{4}$ are considered (0.0427, 0.6195, 0.1386), and the corresponding machine with the maximum random number is selected (${M}_{3}$). The random vectors $K$, ${S}_{k}$, and ${J}_{k}$ are used to determine the sequence of the operations in the real schedule. The object-coding vectors ${K}^{{\prime}}$ and ${S}_{k}^{{\prime}}$ are constructed based on sorted arrays of random number vectors $K$ and ${S}_{k}$ in ascending order, respectively. Vector ${K}^{{\prime}}$ indicates the order of machines, while vectors ${S}_{k}^{{\prime}}$ determine the sequence of groups on machine $k$.

Vectors ${J}_{k}$ need some modification to use as an ordered list of operations for entering to the schedule. This modification procedure will be applied to random vectors ${J}_{k}$ through six steps as follows:

• (1) Determine the ascending order of ${J}_{k}$ members to generate the corresponding object-coding vector (${J}_{k}^{1}$).

• (2) Remove omitted operations based on the information obtained from ${Z}_{1}, {Z}_{2},\dots , {Z}_{m}$, and $X$ (${J}_{k}^{2}$).

• (3) Categorize operations in ${J}_{k}^{2}$ based on the corresponding vector ${S}_{k}^{{\prime}}$ (${J}_{k}^{3}$).

• (4) Apply Repair Schedule_1 on all smallest sections of ${J}_{k}^{3}$ (${{J}^{{\prime}}}_{k,q}^{3}, q=1,2,\dots ,g\times m$) to reorder the operations according to precedence relationship (${J}_{k}^{4}$).

• (5) Apply Repair Schedule_2 on all smallest sections of ${J}_{k}^{4}$ (${{J}^{{\prime}}}_{k,q}^{4}, q=1,2,\dots ,g\times m$) to ensure that all the same operations of the jobs in the same group are processed consecutively according to group technology assumption (${J}_{k}^{5}$).

• (6) Order operations in ${J}_{k}^{5}$ based on their processing machine and ${K}^{{\prime}}$ (${J}_{f}$).

The general procedures of Repair Schedule_1 and Repair Schedule_2 are presented below:

Repair Schedule_1

Repair Schedule_2

To clarify how to obtain ${K}^{{\prime}}$ and ${S}_{k}^{{\prime}}$, and covert ${J}_{k}$ to ${J}_{f}$ through six steps as well as Repair Schedule_1 and Repair Schedule_2, the problem instance illustrated in Sect. 5.1.1 is used regarding matrixes $X$ and ${Z}_{k}$ given above. Due to space limitations, some matrixes are transposed.

$${S}_{1}=\left[\begin{array}{cc}0\text{.}8608& 0\text{.}0856\end{array}\right] \to {S}_{1}^{{\prime}}=\left[\begin{array}{cc}{S}^{2}& {S}^{1}\end{array}\right]$$

$${S}_{2}=\left[\begin{array}{cc}0\text{.}4665& 0\text{.}0674\end{array}\right] \to {S}_{2}^{{\prime}}=\left[\begin{array}{cc}{S}^{2}& {S}^{1}\end{array}\right]$$

$${S}_{3}=\left[\begin{array}{cc}0\text{.}4981& 0\text{.}8884\end{array}\right] \to {S}_{3}^{{\prime}}=\left[\begin{array}{cc}{S}^{1}& {S}^{2}\end{array}\right]$$

$${S}_{4}=\left[\begin{array}{cc}0\text{.}4874& 0\text{.}2332\end{array}\right] \to {S}_{4}^{{\prime}}=\left[\begin{array}{cc}{S}^{2}& {S}^{1}\end{array}\right]$$

$${S}_{5}=\left[\begin{array}{cc}0\text{.}2295& 0\text{.}8616\end{array}\right] \to {S}_{5}^{{\prime}}=\left[\begin{array}{cc}{S}^{1}& {S}^{2}\end{array}\right]$$

$$K=\left[\begin{array}{ccc}0\text{.}6580& 0\text{.}8896& \begin{array}{ccc}0\text{.}1096& 0\text{.}4378& 0\text{.}2802\end{array}\end{array}\right] \to {K}^{{\prime}}=\left[\begin{array}{ccc}{M}_{3}& {M}_{5}& \begin{array}{ccc}{M}_{4}& {M}_{1}& {M}_{2}\end{array}\end{array}\right]$$

$${J}_{1}^{T}=\left[\begin{array}{c}0.2469\\ 0.0954\\ 0.6480\\ 0.6505\\ 0.8354\\ 0.3215\\ 0.0496\\ 0.7485\\ 0.4486\\ 0.8992\\ 0.7061\\ 0.3429\\ 0.7231\\ 0.0240\\ 0.1709\\ 0.4431\\ 0.2690\\ 0.9594\\ 0.2687\\ 0.4169\\ 0.4723\\ 0.4081\\ 0.9254\\ 0.9596\\ 0.0149\end{array}\right] {J}_{2}^{T}=\left[\begin{array}{c}0.0089\\ 0.3526\\ 0.4334\\ 0.8574\\ 0.8357\\ 0.8065\\ 0.2832\\ 0.5678\\ 0.8160\\ 0.8999\\ 0.8314\\ 0.6382\\ 0.2788\\ 0.4911\\ 0.3993\\ 0.4333\\ 0.5597\\ 0.7753\\ 0.9867\\ 0.3801\\ 0.3334\\ 0.4620\\ 0.7390\\ 0.6463\\ 0.1567\end{array}\right] {J}_{3}^{T}=\left[\begin{array}{c}0.8149\\ 0.5934\\ 0.1398\\ 0.0844\\ 0.0499\\ 0.6014\\ 0.6535\\ 0.2990\\ 0.0983\\ 0.5241\\ 0.0348\\ 0.3430\\ 0.5824\\ 0.2783\\ 0.6976\\ 0.1752\\ 0.9448\\ 0.6077\\ 0.7722\\ 0.2133\\ 0.9758\\ 0.8263\\ 0.5674\\ 0.3796\\ 0.4716\end{array}\right] {J}_{4}^{T}=\left[\begin{array}{c}0.1405\\ 0.5852\\ 0.7519\\ 0.9721\\ 0.5459\\ 0.7896\\ 0.4897\\ 0.2561\\ 0.8596\\ 0.1202\\ 0.7578\\ 0.2165\\ 0.4210\\ 0.3398\\ 0.2037\\ 0.1932\\ 0.7145\\ 0.9480\\ 0.4754\\ 0.3829\\ 0.5554\\ 0.9912\\ 0.9688\\ 0.4766\\ 0.5430\end{array}\right] {J}_{5}^{T}=\left[\begin{array}{c}0.8799\\ 0.6677\\ 0.2418\\ 0.0315\\ 0.9432\\ 0.7992\\ 0.9729\\ 0.8866\\ 0.0276\\ 0.1778\\ 0.9571\\ 0.7862\\ 0.0921\\ 0.2873\\ 0.6663\\ 0.6164\\ 0.6792\\ 0.0596\\ 0.6809\\ 0.0297\\ 0.8463\\ 0.5239\\ 0.8245\\ 0.9119\\ 0.0597\end{array}\right]$$

$${\left({J}_{1}^{1}\right)}^{T}=\left[\begin{array}{c}{O}_{5,5}\\ {O}_{3,4}\\ {O}_{2,2}\\ {O}_{1,2}\\ {O}_{3,5}\\ {O}_{1,1}\\ {O}_{4,4}\\ {O}_{4,2}\\ {O}_{2,1}\\ {O}_{3,2}\\ {O}_{5,2}\\ {O}_{4,5}\\ {O}_{4,1}\\ {O}_{2,4}\\ {O}_{5,1}\\ {O}_{1,3}\\ {O}_{1,4}\\ {O}_{3,1}\\ {O}_{3,3}\\ {O}_{2,3}\\ {O}_{1,5}\\ {O}_{2,5}\\ {O}_{5,3}\\ {O}_{4,3}\\ {O}_{5,4}\end{array}\right] {\left({J}_{2}^{1}\right)}^{T}=\left[\begin{array}{c}{O}_{1,1}\\ {O}_{5,5}\\ {O}_{3,3}\\ {O}_{2,2}\\ {O}_{5,1}\\ {O}_{1,2}\\ {O}_{4,5}\\ {O}_{3,5}\\ {O}_{4,1}\\ {O}_{1,3}\\ {O}_{5,2}\\ {O}_{3,4}\\ {O}_{4,2}\\ {O}_{2,3}\\ {O}_{3,2}\\ {O}_{5,4}\\ {O}_{5,3}\\ {O}_{4,3}\\ {O}_{2,1}\\ {O}_{2,4}\\ {O}_{3,1}\\ {O}_{1,5}\\ {O}_{1,4}\\ {O}_{2,5}\\ {O}_{4,4}\end{array}\right] {\left({J}_{3}^{1}\right)}^{T}=\left[\begin{array}{c}{O}_{3,1}\\ {O}_{1,5}\\ {O}_{1,4}\\ {O}_{2,4}\\ {O}_{1,3}\\ {O}_{4,1}\\ {O}_{4,5}\\ {O}_{3,4}\\ {O}_{2,3}\\ {O}_{3,2}\\ {O}_{5,4}\\ {O}_{5,5}\\ {O}_{2,5}\\ {O}_{5,3}\\ {O}_{3,3}\\ {O}_{1,2}\\ {O}_{2,1}\\ {O}_{4,3}\\ {O}_{2,2}\\ {O}_{3,5}\\ {O}_{4,4}\\ {O}_{1,1}\\ {O}_{5,2}\\ {O}_{4,2}\\ {O}_{5,1}\end{array}\right] {\left({J}_{4}^{1}\right)}^{T}=\left[\begin{array}{c}{O}_{2,5}\\ {O}_{1,1}\\ {O}_{4,1}\\ {O}_{3,5}\\ {O}_{3,2}\\ {O}_{2,3}\\ {O}_{3,4}\\ {O}_{4,5}\\ {O}_{3,3}\\ {O}_{4,4}\\ {O}_{5,4}\\ {O}_{2,2}\\ {O}_{5,5}\\ {O}_{1,5}\\ {O}_{5,1}\\ {O}_{1,2}\\ {O}_{4,2}\\ {O}_{1,3}\\ {O}_{3,1}\\ {O}_{2,1}\\ {O}_{2,4}\\ {O}_{4,3}\\ {O}_{5,3}\\ {O}_{1,4}\\ {O}_{5,2}\end{array}\right] {\left({J}_{5}^{1}\right)}^{T}=\left[\begin{array}{c}{O}_{2,4}\\ {O}_{4,5}\\ {O}_{1,4}\\ {O}_{4,3}\\ {O}_{5,5}\\ {O}_{3,3}\\ {O}_{2,5}\\ {O}_{1,3}\\ {O}_{3,4}\\ {O}_{5,2}\\ {O}_{4,1}\\ {O}_{3,5}\\ {O}_{1,2}\\ {O}_{4,2}\\ {O}_{4,4}\\ {O}_{3,2}\\ {O}_{2,1}\\ {O}_{5,3}\\ {O}_{5,1}\\ {O}_{1,1}\\ {O}_{2,3}\\ {O}_{5,4}\\ {O}_{1,5}\\ {O}_{3,1}\\ {O}_{2,2}\end{array}\right]$$

$${J}_{1}^{2}=\left[\begin{array}{ccc}{O}_{4,1}& {O}_{2,4}& \begin{array}{ccc}{O}_{5,1}& {O}_{1,4}& {O}_{3,1}\end{array}\end{array}\right], \quad {J}_{2}^{2}=\left[\begin{array}{ccc}{O}_{3,3}& {O}_{5,3}& {O}_{4,3}\end{array}\right],$$

$${J}_{3}^{2}=\left[\begin{array}{ccc}{O}_{4,5}& {O}_{3,2}& \begin{array}{ccc}{O}_{5,5}& {O}_{2,1}& \begin{array}{ccc}{O}_{3,5}& {O}_{1,1}& \begin{array}{cc}{O}_{5,2}& {O}_{4,2}\end{array}\end{array}\end{array}\end{array}\right],$$

$${J}_{4}^{2}=\left[\begin{array}{ccc}{O}_{3,4}& {O}_{4,4}& {O}_{5,4}\end{array}\right],{J}_{5}^{2}=\left[\begin{array}{cc}{O}_{2,5}& {O}_{\text{1,}5}\end{array}\right]$$

$$\begin{aligned}&{J}_{1}^{3}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{1,1}^{3}\right]& \left[{{J}^{{\prime}}}_{1,2}^{3}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{4,1}& {O}_{5,1}& \begin{array}{ccc}{O}_{3,1}]& [{O}_{2,4}& {O}_{1,4}]\end{array}\end{array}\right],\\&{J}_{2}^{3}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{2,1}^{3}\right]& \left[{{J}^{{\prime}}}_{\text{2,}2}^{3}\right] \end{array}\right]=\left[ \begin{array}{ccc}{[O}_{3,3}& {O}_{5,3}& {O}_{4,3}] \left[\varnothing \right] \end{array}\right],\end{aligned}$$

$${J}_{3}^{3}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{3,1}^{3}\right]& \left[{{J}^{{\prime}}}_{3,2}^{3}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{2,1}& {O}_{1,1}]& \begin{array}{ccc}{[O}_{4,5}& {O}_{3,2}& \begin{array}{ccc}{O}_{5,5}& {O}_{3,5}& \begin{array}{cc}{O}_{5,2}& {O}_{4,2}] \end{array}\end{array}\end{array}\end{array}\right],$$

$${J}_{4}^{3}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{\text{4,}1}^{3}\right]& \left[{{J}^{{\prime}}}_{\text{4,}2}^{3}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{3,4}& {O}_{4,4}& {O}_{5,4}] \left[\varnothing \right] \end{array}\right],{J}_{5}^{3}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{5,1}^{3}\right]& \left[{{J}^{{\prime}}}_{5,2}^{3}\right] \end{array}\right]\left[\begin{array}{cc}{ [O}_{2,5}& {O}_{\text{1,}5}\end{array}] \left[\varnothing \right]\right]$$

$$\begin{aligned}&{J}_{1}^{4}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{1,1}^{4}\right]& \left[{{J}^{{\prime}}}_{1,2}^{4}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{4,1}& {O}_{5,1}& \begin{array}{ccc}{O}_{3,1}]& [{O}_{2,4}& {O}_{1,4}]\end{array}\end{array}\right],\\&{J}_{2}^{4}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{2,1}^{4}\right]& \left[{{J}^{{\prime}}}_{\text{2,}2}^{4}\right] \end{array}\right]=\left[ \begin{array}{ccc}{[O}_{3,3}& {O}_{5,3}& {O}_{4,3}] \left[\varnothing \right] \end{array}\right],\end{aligned}$$

$${J}_{3}^{4}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{3,1}^{4}\right]& \left[{{J}^{{\prime}}}_{3,2}^{4}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{2,1}& {O}_{1,1}]& \begin{array}{ccc}{[O}_{3,2}& {O}_{3,5}& \begin{array}{ccc}{O}_{5,2}& {O}_{5,5}& \begin{array}{cc}{O}_{4,2}& {O}_{4,5}] \end{array}\end{array}\end{array}\end{array}\right],$$

$${J}_{4}^{4}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{\text{4,}1}^{4}\right]& \left[{{J}^{{\prime}}}_{\text{4,}2}^{4}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{3,4}& {O}_{4,4}& {O}_{5,4}] \left[\varnothing \right] \end{array}\right],{J}_{5}^{4}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{5,1}^{4}\right]& \left[{{J}^{{\prime}}}_{5,2}^{4}\right] \end{array}\right]\left[\begin{array}{cc}{ [O}_{2,5}& {O}_{\text{1,}5}\end{array}] \left[\varnothing \right]\right]$$

$$\begin{aligned}&{J}_{1}^{5}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{1,1}^{5}\right]& \left[{{J}^{{\prime}}}_{1,2}^{5}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{4,1}& {O}_{5,1}& \begin{array}{ccc}{O}_{3,1}]& [{O}_{2,4}& {O}_{1,4}]\end{array}\end{array}\right],\\&{J}_{2}^{5}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{2,1}^{5}\right]& \left[{{J}^{{\prime}}}_{\text{2,}2}^{5}\right] \end{array}\right]=\left[ \begin{array}{ccc}{[O}_{3,3}& {O}_{5,3}& {O}_{4,3}] \left[\varnothing \right] \end{array}\right],\end{aligned}$$

$${J}_{3}^{5}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{3,1}^{5}\right]& \left[{{J}^{{\prime}}}_{3,2}^{5}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{2,1}& {O}_{1,1}]& \begin{array}{ccc}{[O}_{3,2}& {O}_{5,2}& \begin{array}{ccc}{O}_{4,2}& {O}_{3,5}& \begin{array}{cc}{O}_{5,5}& {O}_{4,5}] \end{array}\end{array}\end{array}\end{array}\right],$$

$${J}_{4}^{5}=\left[\begin{array}{cc}\left[{{J}^{{\prime}}}_{\text{4,}1}^{5}\right]& \left[{{J}^{{\prime}}}_{\text{4,}2}^{5}\right]\end{array}\right]=\left[\begin{array}{ccc}{ [O}_{3,4}& {O}_{4,4}& {O}_{5,4}] \left[\varnothing \right] \end{array}\right],{J}_{5}^{5}=\left[ \begin{array}{cc}\left[{{J}^{{\prime}}}_{5,1}^{5}\right]& \left[{{J}^{{\prime}}}_{5,2}^{5}\right] \end{array}\right]\left[\begin{array}{cc}{ [O}_{2,5}& {O}_{\text{1,}5}\end{array}] \left[\varnothing \right]\right]$$

$${J}_{f}=\left[\begin{array}{ccc}{ O}_{2,1}& {O}_{1,1}& \begin{array}{ccc}{O}_{3,2}& {O}_{5,2}& \begin{array}{ccc}{O}_{4,2}& {O}_{3,5}& \begin{array}{ccc}{O}_{5,5}& {O}_{4,5}& \begin{array}{ccc}{ O}_{2,5}& {O}_{\text{1,}5}& \begin{array}{ccc}{ O}_{3,4}& {O}_{4,4}& \begin{array}{ccc}{O}_{5,4}& { O}_{4,1}& \begin{array}{ccc}{O}_{5,1}& {O}_{3,1}& \begin{array}{ccc}{O}_{2,4}& {O}_{1,4}& \begin{array}{ccc}{O}_{3,3}& {O}_{5,3}& {O}_{4,3}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\right]$$

Vector ${J}_{f}$ indicates the sequence of operations in order to enter the schedule. To select an operation for scheduling based on ${J}_{f}$, precedence relationships of the operation should be considered. Operations are removed from ${J}_{f}$ one by one and are added to the schedule. If an operation cannot go into the schedule because of the precedence constraints, it should be transferred to the end of the vector ${J}_{f}$ to prevent an operation from processing between other different operations on a machine.

5.2.2 Hybrid WCA using mutation operators of GA

In order to increase exploration of the proposed WCA, the mutation operation of the GA is employed for ${K}^{{\prime}}$, ${J}_{k}^{2}$ and ${S}_{k}^{{\prime}}$ with the probability of ${P}_{m}$ for each individual. Shifting genes' loci and shifting processing machines, explained in Sect. 5.1.4, are applied respectively for ${J}_{k}^{2}$, while one of the three popular operators, swap, reversion, and insertion, are used randomly for ${K}^{{\prime}}$ and ${S}_{k}^{{\prime}}$. For ${J}_{k}^{2}$ (or ${S}_{k}^{{\prime}}$), one machine is selected randomly, and the related vector has been mutated. Shifting genes' loci changes operation sequences in one of the randomly chosen vectors ${J}_{k}^{2}$ and shifting processing machines alter the processing machine of the same operations of the jobs in the same group with the probability of ${P}_{k}$. Indeed, it moves the same operations of the jobs in the same group between different vectors of ${J}_{k}^{2}$ where the order of operations is preserved. The mutation operators are applied $nm$ times in each iteration. The following examples clarify how to use the aforementioned operators.

The mutation of ${K}^{{\prime}}$ (Insertion):

The mutation of ${S}_{3}^{{\prime}}$ (Swap): $\left[\begin{array}{cc}{S}^{1}& {S}^{2}\end{array}\right]\to \left[\begin{array}{cc}{S}^{2}& {S}^{1}\end{array}\right]$

Shifting genes' loci on ${J}_{3}^{2}$:

Shifting processing machines on the fifth operation of the jobs in the second group where ${M}_{4}$ is selected instead of ${M}_{3}$:

5.2.3 Movements of streams and rivers

The new position of the streams and rivers are determined by applying the Eqs. 44–46 on all the corresponding random matrixes as follows ($C=2$):

$${X}^{Stream\left(t+1\right)}={X}^{Stream\left(t\right)}+2\times rand\times \left({X}^{River\left(t\right)}-{X}^{Stream\left(t\right)}\right)$$

(50)

$${Z}_{k}^{Stream\left(t+1\right)}={Z}_{k}^{Stream\left(t+1\right)}+2\times rand\times \left({Z}_{k}^{River\left(t\right)}-{Z}_{k}^{Stream\left(t\right)}\right) \quad \forall k=1,2,\dots ,m$$

(51)

$${J}_{k}^{Stream\left(t+1\right)}={J}_{k}^{Stream\left(t+1\right)}+2\times rand\times \left({J}_{k}^{River\left(t\right)}-{J}_{k}^{Stream\left(t\right)}\right) \quad \forall k=1,2,\dots ,m$$

(52)

$${S}_{k}^{Stream\left(t+1\right)}={S}_{k}^{Stream\left(t+1\right)}+2\times rand\times \left({S}_{k}^{River\left(t\right)}-{S}_{k}^{Stream\left(t\right)}\right)\quad \forall k=1,2,\dots ,m$$

(53)

$${K}^{Stream\left(t+1\right)}={K}^{Stream\left(t\right)}+2\times rand\times \left({K}^{River\left(t\right)}-{K}^{Stream\left(t\right)}\right)$$

(54)

For the movement of streams and rivers to the sea, the same equations are utilized.

5.2.4 Evaporation condition

To check the evaporation condition, the summation of the 2-norm of all random matrixes related to an individual is used. The final condition for streams and the sea would be as follows:

$${\Vert {X}^{Sea}-{X}^{{Stream}_{i}}\Vert }_{2}+\sum_{k=1}^{m}{\Vert {Z}_{k}^{Sea}-{Z}_{k}^{{Stream}_{i}}\Vert }_{2}+\sum_{k=1}^{m}{\Vert {J}_{k}^{Sea}-{J}_{k}^{{Stream}_{i}}\Vert }_{2}+\sum_{k=1}^{m}{\Vert {S}_{k}^{Sea}-{S}_{k}^{{Stream}_{i}}\Vert }_{2}+{\Vert {K}^{Sea}-{K}^{{Stream}_{i}}\Vert }_{2}<{d}_{max} i=1,2,\dots , {NS}_{1}$$

(55)

The same condition can be applied for streams and rivers.

6 Managerial insights

As mentioned in Sect. 1, the IPPGS problem appears in manufacturing systems where setup times are significantly high relative to processing times. To clarify why considering group processing in IPPS problems is beneficial, a small-size IPPGS problem instance with low flexibility as delineated in Fig. 1, as well as sequence-dependent setup times reported in Table 4, is considered.

Table 4 Sequence-dependent setup times for the problem related to Fig. 1

The illustrated problem is solved using combination-based MILP with an optimum makespan of 69 in 0.73 s. As a second scenario, we ignore job grouping and therefore release the group technology constraint. Indeed, an IPPS problem, including five jobs with SDST, would be available, whereas the setup times between jobs 1 and 2 on the one hand and also between jobs 3, 4, and 5, on the other hand, are equal to zero. Other characteristics remain unchanged. Solving the newly generated problem, the optimum makespan is equal to 69 as achieved before, but with the CPU time of 128 s, i.e., more than 175 times larger than the IPPGS scenario. In other words, considering group processing reduces the solution time by more than 99%.

It should be noted that such a significant difference in the computational time exists just for a small and simple problem. The difference will increase drastically when a medium, large, or more complex problem is under consideration. As a result, job grouping in the IPPS environment enables achieving an optimum or a proper solution faster and handling larger and more complex problems.

7 Computational results

In this section, the performance of the proposed metaheuristic algorithms is evaluated. As mentioned in the previous sections, the IPPGS problem has not been studied before. Then there are no related benchmark problems in the literature. Therefore, 45 IPPGS problem instances are generated in different sizes and flexibility levels based on 18 Kim's benchmark jobs (Kim et al. 2003) with 15 machines to evaluate the performance of the algorithms. The problems are categorized into three sizes: small (with two groups of jobs), medium (with four groups of jobs), and large (with six groups of jobs). In addition, five levels of process flexibility (PF), sequence flexibility (SF), and operation flexibility (OF) are considered based on Kim's benchmark categorization, i.e., low, medium, high, low-medium, and medium–high. For example, L-LowSF is a large instance, including jobs with a low level of sequence flexibility, and M-MediumHighPF is a medium one, including jobs with both medium and high process flexibility. The measures introduced by Kim et al. (2003) are used to categorize three kinds of flexibility. The classification basis is shown in Table 5.

Table 5 Classification basis according to flexibility indices

Two to five jobs in each group have been taken into account. The selected AND/OR graph from Kim's Jobs, as well as the number of jobs in each group, are listed in Table 6. Also, Table 7 accounts for some general information for the benchmark problems, including the number of groups, the number of jobs, the maximum number of operations (NO), the maximum number of combinations (NC), and the total number of operations (TNO) of all jobs. The processing and setup times are randomly generated from uniform distributions between (1,20) and (20,50), respectively. The algorithms are implemented in Matlab 9.4 and run on an Intel Core i5-3470@3.20 GHz with 8 GB RAM PC. The parameters of both algorithms are set, as shown in Table 8.

Table 6 Specification of benchmark problems

Table 7 General information for benchmark problems

Table 8 The parameter setting of the proposed algorithms

In order to compare the performance of the proposed algorithms in the same situation, a limited CPU time set to $2\times$ the number of jobs $\times$ the number of machines is used as a stopping criterion for both metaheuristic algorithms under consideration. In this way, large problems have more time than medium and small ones, and similarly, medium problems in comparison with small ones. The experiment for each algorithm is repeated 10 times for every problem instance, and the best solution of each run is recorded. On the other hand, each benchmark problem is executed by the combination-based mathematical model using Cplex solver (version 12.8) within the GAMS (version 25.0.2) environment with a limitation of 2 h for Cplex execution time, and the best-found integer value of the objective function (BF) is reported for the exact method. It is evident that BF can be an optimum solution. Table 9 shows BF as well as the mean and the standard deviation of the solutions yielded by GA and HWCA for each problem instance.

Table 9 Comparison of makespan for the exact method and two proposed algorithms

Due to increased complexity, the exact method found the optimum solution for only 4 problems, whilst for 18 of 45 problems, it could not reach any feasible solution after 2 h. However, the best solution can be found by the exact method for 15 problems, including 14 small-size instances and one medium-size instance (problem 2). On the other hand, the best-found solution for all small-size instances except one (problem 28) can be achieved by the exact method. As a result, although the exact method is unable to reach the optimum solution in most cases, its output is better than or equal to two metaheuristic algorithms for 14 of 15 small-size problems. The metaheuristic algorithms have better performance for medium and large-size problems.

Figure 9 depicts the superiority of the solution methods for finding the best-found solution in terms of the size of the problems. As shown in Fig. 9, the best-found makespan is achieved by GA for 4 medium problems. However, HWCA is more capable of reaching a better solution for more complex and real-world problems. The best-found solution for all large problems and most medium problems (10 of 15) has been obtained by HWCA. Additionally, the flexibility is relatively low for five cases in which the best-found solution of the exact method or GA is better than HWCA.

Fig. 9

The superiority of the solution methods to achieve the best-found solution

The “improved rate” (IR rate), reported in Table 9, indicates the relative improved ratio of the HWCA result compared to the minimum result obtained by GA or the exact method. HWCA presents the best result where the improved rate is positive. It is shown the improvement for 17 of 18 medium and large-size problems with medium or high flexibility. For large-size problems, improved ratios are more than 5% when a flexibility factor is medium or high, and they are more than 9% when flexibility is high for all jobs. Figure 10 gives the Gantt chart of the last instance.

Fig. 10

The Gantt chart of the last instance

To examine the evolution trend of GA and HWCA, 6 problems 1, 2, 3, 7, 8, and 9 with different sizes and flexibility levels and also different search spaces are chosen. Figure 11 illustrates search capability within the limited computational time for the selected benchmark problems. As the figure shows, GA presents a better solution in the early stages of processing for all problems. In other words, GA tends to converge more quickly than HWCA. Combining genetic and WCA operators in HWCA increases more reproduced individuals and consequently more required computational time at each iteration. On the other hand, it causes a powerful and broad exploration in HWCA as a more qualified solution can be achieved when more time is available.

Fig. 11

Comparison of search capability within the limited computational time

8 Conclusions

In this research, two efficient MILP models for the integrated process planning and group scheduling (IPPGS) problem with sequence-dependent setup time (SDST) are proposed. The models were formulated based on different approaches called process plan-based and combination-based models. The combination-based mathematical model has superior performance compared to the other one. However, it can only be applied for small-size problems with a low level of flexibility. This mathematical model can be used in future research to provide high-quality lower bounds for the proposed problem. Also, two metaheuristic algorithms are proposed to provide an upper bound for the IPPGS problem. The first one is a genetic algorithm with a new two-section representation, including a numerical and an object-coding section. Genetic operators are customized to cope with the new genetic representation. The other optimization method is a hybrid water cycle algorithm (HWCA). The naturally continuous WCA was developed to accommodate the IPPGS problem using a discrete strategy. Moreover, in order to increase the exploration of the proposed WCA, the mutation operation of the GA is employed. Although the experimental results indicate that HWCA provides better outcomes than GA, but due to faster convergence in the early stages of the search, GA presents better results in a short time.

For future research, a lower bound can be provided for the proposed problem by applying the proposed combination-based model as well as the related techniques such as Lagrangian relaxation or branch-and-price. Furthermore, the IPPGS problem can be studied using total tardiness as an objective function. In addition, the proposed algorithms can be extended to cope with the IPPGS problem for other shop environments, such as assembly operations.