Evolving ant colony system for large-sized integrated process planning and scheduling problem considering sequence-dependent setup times

Abstract

This paper proposes a new ant colony optimization (ACO) algorithm suitable for integrated process planning and scheduling (IPPS) that optimizes both process planning and scheduling simultaneously. The IPPS covered in this study, when compared to the conventional IPPS, is more flexible and complicated because sequence-dependent setups and tool-related capacity constraints are additionally considered. Traditional ACOs have limitations in improving the solution quality and computation time for IPPS. The high flexibility and complexity of IPPS requires a large size of repository for pheromone trails and it causes the long computation time for updating them, excessive evaporation of pheromones, and unbalancing between pheromones and desirability. In the proposed ACO, each ant agent improves their own incumbent solution or finds a new solution using the pheromone trails that is composed of the experience information of the colony. Therefore, the proposed ACO conducts individual and cooperative evolving at the same time. Furthermore, we propose a simplified updating rule for pheromone trails and standardization of the transition probability to increase efficiency of the algorithm. Experimental results show that the proposed ACO is superior to recently proposed meta-heuristics for benchmark problems of different sizes in terms of both solution quality and computation time.

1 Introduction

Process planning and scheduling are two key activities in manufacturing planning. Process planning or computer aided process planning (CAPP) is the activity of determining the appropriate process, tool, sequence, and processing conditions to transform raw materials into a designed shape. CAPP plays a central role in building computer integrated manufacturing (CIM) systems by connecting computer aided design (CAD) and computer aided manufacturing (CAM) (Reddy 1999; Tan and Khoshnevis 2000). Scheduling is an activity that determines the starting times and the completion times of the operations to be processed. Optimization of these two activities has traditionally been carried out independently and sequentially, that is, the scheduling is conducted with the predetermined process plan. Shao et al. (2009), however, argued that the sequential approach involves four vulnerabilities. First, the optimal plan can be often infeasible according to the status of the shop floor at the time of execution. Second, even though the plan is optimized by reflecting the real-time status, it also may become infeasible due to the time delay between planning and execution. Third, the optimal schedule based on the optimal process plan can lead to shortages of certain resources and bottlenecks in certain machines. Fourth, optimization for a single-objective may be inappropriate for multi-objective practical manufacturing.

To overcome those shortcomings, integrated process planning and scheduling (IPPS) that optimizes the two distinct activities simultaneously has been considered. It is known that IPPS can improve facility efficiency, mean flow time, work-in-process, machine utilization, and robustness of the shop floor (Rachamadugu and Stecke 1994; Shao et al. 2009). Over the past two decades, research on IPPS has grown. In previous studies, various flexibilities and constraints were covered to reflect an actual manufacturing environment. Flexibilities include process flexibility for alternative process routings, sequence flexibility for alternative operation orders, machine and tool flexibility for alternative facilities, and TAD flexibility for alternative tool access directions (TADs) (Kim et al. 2007; Petrović et al. 2016; Dou et al. 2018). As constraints, precedence relations between operations are essential. Capacity constraints such as tool capacity and tool magazine capacity and sequence-dependent setups have been rarely dealt with in a few studies (Kim et al. 2007; Srinivas et al. 2012).

Although various flexibilities and constraints have been handled in IPPS, no study has covered all of the flexibilities and constraints, i.e., each individual study has only considered some of them by adopting impractical assumptions. A typical example is setups. Setups include handling tools, setting the jigs and fixtures, loading and unloading workpieces, and inspecting the material. There are two types of setups: sequence-independent setups and sequence-dependent setups. If the setups of the current operation are dependent on the preceding operations, they are sequence-dependent; otherwise, they are sequence-independent. Most existing studies assume sequence-independent setups and merge the constant setup times into the processing time. However, in flexible manufacturing system (FMS), where IPPS is primarily applied, the sequence-dependent setups make up a majority of setups, because multi-purpose machines are the main facilities (Eren 2010). In this case, separate consideration of the sequence-dependent setup times can draw a better schedule (Srinivas et al. 2012).

Both process planning and scheduling belong to the NP-hard class, and therefore so does IPPS. This implies IPPS has a high complexity and huge solution space. Hence, most researchers have preferred meta-heuristics as an optimization approach for IPPS, which include genetic algorithm (GA), ant colony optimization (ACO), and particle swam optimization (PSO). Among them, ACO is an optimization method that utilizes the stigmergic behavior of multi-agents represented by an ant colony. For each iteration, all ant agents seek a route, i.e., a solution for the problem, and the information of the best route in the colony is accumulated in the pheromone trails. It is combined with the preferred node selection rule, so called heuristic desirability, and is used by an ant agent to search for a new route. This procedure is a kind of collective intelligence. ACO has been successfully applied to the optimization of NP-Hard problems, such as the traveling salesman problem (TSP), scheduling, routing, and digital image processing (Chandra and Baskaran 2012). ACO, however, is often vulnerable to very complicated problems like IPPS. As IPPS considers various flexibilities, the number of nodes and edges are large, and subsequently the repository size of the pheromone trails is large. To maintain and update the pheromone trails, a considerable amount of computation is required for deposition and evaporation procedures. Moreover, as the information belonging to the best route is only a small fraction of the information in all the pheromone trails, the amount of evaporated pheromone is larger than the amount of deposited pheromone. As the iteration is progressed, the influence of the pheromone trails weakens, and the influence of the heuristic desirability increases relatively. Therefore, the stigmergic property of ACO does not operate properly.

The goal of this study is to develop an efficient ACO for IPPS considering almost all the flexibilities and constraints previously dealt with. Covered flexibilities include process, sequence, machine, tool, and TAD flexibility. Considered constraints include precedence relationship, tool capacity, tool magazine capacity, and sequence-dependent setup times. Transportation time, which is essential for the distributed manufacturing, is also considered. This comprehensive IPPS problem has not been considered yet within the IPPS field. This IPPS is much more complex than the existing one, so the solution space is larger, implementation is hard, and computation time is longer. We overcome the obstacles by proposing an evolving-based ACO, which we call the evolving ant colony system (EACS). The main procedure of EACS is similar to that of conventional ACO. However, as with conventional ACOs, not every ant agent is replaced on every iteration. In EACS, some ant agents improve their solution route using the proposed greedy heuristics and the rest search for a new route according to the route construction rule using pheromone trail and desirability. For the next generation, some of superior ant agents are replaced by the current ant agents with low performance. The routes of the iteration best solution in the colony and the general best solution are accumulated in the pheromone repository at every iteration in different amounts. Through these individual and cooperative evolving procedures, high quality solutions can be efficiently found for the comprehensive IPPS.

This paper is organized as follows. Section 2 defines the comprehensive IPPS problem we are dealing with, shows how to calculate sequence-dependent setup times, and describes a conventional ant colony system (ACS) for IPPS. Section 3 intensively investigates previous studies focusing on sequence-dependent setups and ACO in IPPS. Section 4 details the procedures of EACS proposed in this study. Section 5 summarizes the benchmark problems and the experimental environment to verify the performance of EACS. In Sect. 6, we analyze the influence of sequence-dependent setup times and verify the superiority of EACS by comparing its performance with that of recently developed meta-heuristics. Finally, Sect. 7 states the conclusions of this study and suggests directions for future research.

2 Background knowledge for IPPS and ACO

Notations

$j$ :

index of job, $j \in \left\{{1,2,3, \ldots,n^{JOB}} \right\}$, $n^{JOB}$ is the total number of jobs

$o$ :

index of operation of the job $j$, $o \in \left\{{1,2,3, \ldots,n_{j}^{OP}} \right\}$, $n_{j}^{OP}$ is the total number of operations of the job $j$

$m$ :

index of machine, $m \in \left\{{1,2,3, \ldots,n^{M}} \right\}$, $n^{M}$ is the total number of machines

$t$ :

index of tool, $t \in \left\{{1,2,3, \ldots,n^{T}} \right\}$, $n^{T}$ is the total number of tool types

$k$ :

index of TAD, $k \in \left\{{-\,x, x, -\,y, y, -\,z, z} \right\}$, $-\,x, x, -\,y, y, -\,z, z$ are directions of tool access

$O_{j,o}$ :

the operation $o$ of the job $j$ not yet assigned $m$, $t$, and $k$

$O_{j,o}^{m,t,k}$ :

the $O_{j,o}$ assigned $m$, $t$, and $k$

$CA$ :

a set of ant agents

$\Phi$ :

a set of pheromone trails

$c$ :

the current node (operation) where the ant agent is staying or the most recently assigned operation, $c = u\,{\text{or}}\,v$

$A$ :

a set of nodes where the ant agent can move from $c$

$d$ :

the destination node, $d \in A$

$u$ :

the most recently assigned operation with the same job index with $d$

$v$ :

the most recently assigned operation in the same machine with $d$

$sct\left(d \right)$ :

the setup change time of the $d$

$tct\left(d \right)$ :

the tool change time of the $d$

$pt\left(d \right)$ :

the processing time of the $d$

$ult\left(c \right)$ :

the unload time of the $c$

$trt\left(c \right)$ :

the transportation time of the $c$

$ect\left(d \right)$ :

the expected completion time of the $d$

$\tau \left({c,d} \right)$ :

the pheromone trail on the edge $\left({c,d} \right)$, $\tau \left({c,d} \right) \in\Phi$

$\eta \left(d \right)$ :

the desirability of the $d$

$c_{t}, c_{m}, \gamma_{t}, \gamma_{m}$ :

adjusting parameters for calculating penalty.

2.1 IPPS representation

There are three types of representations used to describe IPPS: mathematical programming (Li et al. 2010; Nourali et al. 2012; Shen and Yao 2015), disjunctive graph (Leung et al. 2010), and network representation (Kim et al. 2007; Petrović et al. 2016). Among them, network representation is the most preferred in IPPS studies. It is easy to understand intuitively and has the advantage of representing various flexibilities in a graph. It, however, is lacking in describing the mechanism of ACO because it has only conjunctive edges. Thus, we use a combination of the network representation and the disjunctive graph.

An IPPS can be expressed as a graph as shown in Fig. 1a, i.e., $IPPS = \left({O,C \cup D} \right)$, where $O$ refers to the set of nodes, and $C$ and $D$ denote the sets of conjunctive and disjunctive edges, respectively. A node represents an operation to be executed at a machine, and an edge represents the relationship between operations. For example, Fig. 1a shows a network representation of an IPPS consisting of two jobs (or parts).

Fig. 1

Simple IPPS example composed of two jobs

Nodes $O$ consists of a starting node SN, an ending node EN, and several intermediate nodes. A solution of an IPPS is a sequence of the intermediate nodes from SN to EN. Every intermediate node $O_{j,o}^{m,t,k}$ has attributes of job and operation indices ($j,o$), machine, tool, and TAD indices ($m,t,k$) and operation times ($sct,tct,pt,ult,trt$). An operation $O_{j,o}$ can be performed in the same way by alternative machines (machine flexibility) with alternative types of tools (tool flexibility) under alternative TADs (TAD flexibility). The operation times ($sct,tct,pt,ult$) depend on the combination of ($m,t,tad$).

There are two types of edges: conjunctive (solid line with an arrowhead) and disjunctive (dashed line without an arrowhead) edges. Two distinct nodes are connected by a conjunctive edge if there is a precedence relationship between them; otherwise, they are connected by a disjunctive edge. As disjunctive edges are non-directional, various sequences of operations can be constructed as a solution route (sequence flexibility). Every diverging conjunctive sub-route is in an OR or AND relation. The relationship ends at the rejoining node. The OR relation is marked by “OR” at the bottom of the first node, otherwise, it implies an AND relation. The OR relation implies that there are alternative processing routes for processing the same feature (process flexibility). If several sub-routes are in an OR relation, only one of them must be selected and processed. Otherwise (AND relation), all of them must be processed. SN, EN, and all nodes belonging to the unselected sub-routes by the OR relations, are dummy nodes (gray-colored) that are not actually performed. All other nodes (white-colored) should be performed.

IPPS is generally defined under the following assumptions: (1) jobs to be produced are determined prior to optimization, that is, no job is inserted or removed until completion of the predetermined jobs; (2) all machines are ready to work at the starting time of the schedule, i.e., available starting times of all machines are zero; (3) all raw materials are always available; (4) no interruption is allowable during an operation; (5) assigned machine, tool, and TAD do not change during an operation; (6) there is no breakdown on machines or tools; (7) the number of slots in the tool magazine of a machine is fixed; and (8) the number of each type of tool is fixed.

Network representation is easy to understand IPPS, but rigorous description of problems and constraints is impossible. To overcome this, we have presented a mathematical programming model for IPPS in Appendix 1. The proposed IPPS cannot maintain linearity due to sequence-dependent setup times and transportation times of the next subsection, so it is mixed integer nonlinear programming (MINLP).

2.2 Setup and transportation times

Setups are non-value added activities that prepare related workers, machines, tools, and drawings to facilitate the operation (Allahverdi 2015). Setups can be classified as follows: sequence-dependent and sequence-independent. If a setup is sequence-dependent, the setup times or costs depends on the machines, tools, and TADs of the preceding operation and the current operation. If a setup is sequence-independent, the setup times or costs are considered as constants. According to the literature surveys by Allahverdi et al. (2008) and Allahverdi (2015), in about 90% of scheduling studies, setups were ignored or were assumed to be sequence-independent. Moreover, they argued that this situation paradoxically means that separate consideration of sequence-dependent setups can lead to further improvement of solution quality in scheduling.

In most IPPS studies, the setups have also been assumed as sequence-independent and have been ignored in optimization. However, in IPPS, consideration of sequence-dependent setups is important, as such setups are common in FMS (Eren 2010) which is a major application of IPPS. Three types of sequence-dependent setup times have been considered in IPPS (Azab et al. 2009): (1) the setup change time for positioning a workpiece on a machine; (2) the tool change time for changing tool; and (3) the unloading time for removing a workpiece from a machine.

Transportation time is the time taken to move a machined workpiece to another machine for subsequent operation. The amount of the time is determined by the attributes of the workpiece such as weight and volume, the ability of the transport such as speed and capacity, and the distance between the machines. In IPPS, transportation time has also been frequently ignored. However, if the times are large enough or a distributed manufacturing environment is considered, those are not negligible.

In this study, setup times and transportation times are determined through the following procedure. Let $d$ be the current operation to be processed, $u$ be the last operation assigned that belongs to the same job as $d$, and $v$ be the last operation performed on the machine where $d$ should be performed. Suppose that the amounts of setup change time, tool change time, and unloading time are determined by only the type of machine, i.e., $SCT\left(m \right)$, $TCT\left(m \right)$, and $ULT\left(m \right)$, respectively. In fact, those sequence-dependent setup times are functions of ($m,t,tad$) of $d$, $u$, and $v$. However, we adopt the simplified functions in this study because the complicated functions only change the amounts of times. From an optimization approach point of view, it is not significant. The actual sequence-dependent setup times can easily be obtained at the shop floor during execution. In addition, let the amount of transportation time depend on only the distance between two machines and its size as $TRT\left({m_{1},m_{2}} \right)$.

Under these assumptions, setup times and transportation times are calculated by Eqs. (1)–(4), where ‘$\wedge$’ and ‘$\vee$’ are logical operators representing ‘and’ and ‘or’, respectively.

$$sct\left(d \right) = \left\{{\begin{array}{*{20}l} {SCT\left({m_{d}} \right),} \hfill & { if\, \left({m_{u} \ne m_{d}} \right) \vee \left({ j_{v} \ne j_{d}} \right) \vee \left({\left({m_{u} = m_{d}} \right) \wedge \left({j_{v} = j_{d}} \right) \wedge \left({tad_{v} \ne tad_{d}} \right)} \right)} \hfill \\ {0,} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(1)

$$tct\left(d \right) = \left\{{\begin{array}{*{20}l} {TCT\left({t_{d}} \right),} \hfill & {if\, t_{v} \ne t_{d}} \hfill \\ {0,} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(2)

$$ult\left(u \right) = \left\{{\begin{array}{*{20}l} {ULT\left({m_{u}} \right),} \hfill & { if\, m_{u} \ne m_{d}} \hfill \\ {0,} \hfill & {o.w.} \hfill \\ \end{array}} \right.,\quad ult\left(v \right) = \left\{{\begin{array}{*{20}l} {ULT\left({m_{v}} \right),} \hfill & {if\, j_{v} \ne j_{d}} \hfill \\ {0,} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(3)

$$trt\left(u \right) = \left\{{\begin{array}{*{20}l} {TRT\left({m_{u},m_{d}} \right),} \hfill & { if\, m_{u} \ne m_{d}} \hfill \\ {0,} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(4)

Setup change time $sct\left(d \right)$ occurs when the machines of two consecutive operations in a job differ or the jobs or TAD of two consecutive operations in a machine differ. Tool change time $tct\left(d \right)$ occurs when the types of tools of two consecutive operations in a machine differ. Unloading time $ult\left(u \right)$ occurs when the machines of two consecutive operations in a job differ and $ult\left(v \right)$ occurs when the jobs of two consecutive operations in a machine differ. Transportation time $trt\left(u \right)$ occurs when the machines of two consecutive operations in the same job change.

2.3 Conventional ant colony system for IPPS

ACO introduced by Dorigo and Gambardella (1997) is a population-based algorithm that accumulates information about excellent routes searched by a group of ant agents (an ant colony) and reuses the experience for searching new routes. ACO has been evolved into a variety of variants. Those includes the ant system (AS), the ant colony system (ACS), the ${\mathcal{MAX}}$−${\mathcal{MIN}}$ ant system (MMAS), and the rank-based version of the ant system (Stützle and Dorigo 1999). This section describes the mechanism of ACO for IPPS based on ACS, the most popular ACO.

Figure 2 shows the typical procedure of conventional ACS used to minimize the makespan for IPPS, where $s = \left\{{O_{j,o}^{m,t,k}} \right\}$ is a sequence of operations (solution); $f\left(s \right)$ is the objective function; and $\tau_{0}$ is an initial pheromone level. At the start of the algorithm, all the pheromone trails are initialized with $\tau_{0}$. For every iteration, each ant agent in the colony finds a solution route from SN to EN using the route construction rule described below. During the route search, whenever an ant agent determines the next visiting node, the pheromone trails $\Phi$ for the edge is locally updated to increase the diversification. If a solution route is constructed, the general best solution is updated depending on the objective value. Once all ant agents complete their route searches, the pheromone trails $\Phi$ for the general best solution are updated to increase intensification. These processes are repeated until the termination condition is reached. Then, the general best solution becomes the final solution and the algorithm is stopped.

Fig. 2

Main procedure of typical ACS for IPPS

In the ACS procedure, design factors are a route construction rule and pheromone updating rules. They differ between AS, ACS, and MMSS. The route construction rule is a selection rule for an ant agent to select the next visiting node among the candidates. Suppose that $c$ is a current node (operation), $d$ is a candidate node, and $A$ is a set of candidate nodes that satisfy precedence constraints from ${\text{c}}$. Let $\tau \left({c,d} \right) \in\Phi$ denote a magnitude of pheromone deposited on the edge $\left({c,d} \right)$, and $\eta \left({c,d} \right)$ denote a magnitude of heuristic desirability for the edge. The destination node $d^{*}$ is selected by Eq. (5). If a generated random number $rand\left(\cdot \right)$ is less than the parameter $p_{ns} \left({0 \le p_{ns} \le 1} \right)$, then $\mathop {\arg \max}\nolimits_{d \in A} \left\{{\tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}} \right\}$ becomes $d^{*}$, where $\alpha$ and $\beta$ are design parameters for adjusting the contribution of $\tau$ and $\eta$, respectively. Otherwise $d^{*}$ is selected by roulette wheel selection (${\text{roulette}}_{{{\text{wheel}}\left\{\cdot \right\}}}$) with the state transition probability $\frac{{\tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}}}{{\mathop \sum \nolimits_{d \in A} \tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}}}$. A large value of $p_{ns}$ enhances intensification and a small value enhances diversification.

$$d^{*} = \left\{{\begin{array}{*{20}l} {\mathop {\arg \max}\limits_{d \in A} \left\{{\tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}} \right\}, } \hfill & {if\,rand\left(\cdot \right) < p_{ns}} \hfill \\ {\mathop {{\text{roulette}}_{\text{wheel}}}\limits_{d \in A} \left\{{\frac{{\tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}}}{{\mathop \sum \nolimits_{d \in A} \tau \left({c,d} \right)^{\alpha} \eta \left({c,d} \right)^{\beta}}}} \right\},} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(5)

The heuristic desirability $\eta \left({c,d} \right)$ is an indicator of the degree of preference of the ant agent to the destination node. If the objective is to minimize makespan, the inverse of the processing time of Eq. (6) is generally applied, where $Q_{\eta}$ is an operating parameter of the ACS.

$$\eta \left(d \right) = \frac{{Q_{\eta}}}{pt\left(d \right)}$$

(6)

The pheromone updating rule determines how to manage pheromones in pheromone trails. There are two updating rules in ACS: the global update and local update rules. The global update is performed on the general best solution of the $i$th iteration $s_{i}^{gb}$ as shown in Eq. (7), where $\tau_{i} \left({c,d} \right)$ denotes the amount of pheromone on the edge $\left({c,d} \right)$ at the $i$th iteration. First, the increment in the pheromone, $\Delta\tau_{i}^{gb}$, is calculated by $Q_{\tau} /C_{MAX} \left({s_{i}^{gb}} \right)$, where $Q_{\tau}$ is a design parameter for adjusting the amount of pheromone deposition and $C_{MAX} \left({s_{i}^{gb}} \right)$ denotes the makespan of the solution $s_{i}^{gb}$. Second, the amount of pheromone of all edges in $C \cup D$ is reduced by $1 - \rho_{gu}$ times, where $\rho_{gu}$($0 < \rho_{gu} < 1$) is the evaporation rate. Finally, for only edges belonging to $s_{i}^{gb}$, $\Delta\tau_{i}^{gb}$ is added.

$$\tau_{i} \left({c,d} \right) = \left\{{\begin{array}{*{20}l} {\left({1 - \rho_{gu}} \right)\tau_{i - 1} \left({c,d} \right) +\varDelta\tau_{i}^{gb},} \hfill & {if\, \left({c,d} \right) \in s_{i}^{gb}} \hfill \\ {\left({1 - \rho_{gu}} \right)\tau_{i - 1} \left({c,d} \right),} \hfill & {if\, \left({c,d} \right) \notin s_{i}^{gb} \, and\, \left({c,d} \right) \in C \cup D} \hfill \\ \end{array}} \right.$$

(7)

The local update adjusts pheromone as shown in Eq. (8). It is controlled by the evaporation rate $\rho_{lu} \left({0 < \rho_{lu} < 1} \right)$ for the local update. The local update increases diversification by reducing the pheromone of the visited edges, while the global update increases intensification.

$$\tau_{i} \left({c,d} \right) = \left({1 - \rho_{lu}} \right)\tau_{i} \left({c,d} \right)$$

(8)

Let us explain the above ACS procedure in detail using the network representation in Fig. 1a and the Gantt chart in Fig. 1b. Suppose that an ant agent is trying to find a solution route from SN to EN. Due to precedence constraints, the ant agent at SN can only move to nodes {A, F, G}. Assume that the ant agent selects node A according to the route construction rule in Eq. (5). Node A, $O_{1,1}^{1,2, + z}$, must be machined by machine M1 with tool 1 in the + z direction. Since M1 is currently empty and the operation does not have any preceding operations, a setup change time, a tool change time, and a processing time is scheduled to M1 as shown in Fig. 1b. Now, as node A is already scheduled, it is dropped from the candidate set. In Fig. 1a, node A is connected to nodes B and D by conjunctive edges and to nodes F and G by disjunctive edges. Note that Fig. 1a only shows the edges associated with the route search of the ant agent among all disjunctive edges for the sake of simplicity. Hence, nodes B, D, F, and G become candidates for the next visiting nodes and those are merged into the current candidate set {F, G}. Finally, the candidate set becomes {F, G, B, D}.

Assume that the ant agent selects node D from {F, G, B, D} as the next node according to the route construction rule. Node D is in an OR relationship with route B–C, so nodes B and C are deactivated as dummy nodes. Node D, $O_{1,4}^{1,3, - z}$, must be processed on the same machine as the previous operation $O_{1,1}^{1,2, + z}$, but the TAD and tool are changed. Therefore, the workpiece does not need to be unloaded after $O_{1,1}^{1,2, + z}$ is completed, but the operation can only start after exhausting the setup change time and tool change time. After scheduling of node D, it is dropped from the candidates and new candidate nodes are searched by precedence relations. As a result, the candidate set becomes {F, G, E} by insertion of node E. Assume that the ant agent has finally arrived at node E. Node E, $O_{1,5}^{2,2, + y}$, must be machined by M2. The operation can start when the workpiece of job1 arrives at M2 after completion of $O_{1,4}^{1,3, - z}$ in M1. In this case, the setup change time schedule of $O_{1,5}^{2,2, + y}$ overlaps with the transportation time schedule of the workpiece of job2 (shaded area). However, it does not affect to the starting time of $O_{1,5}^{2,2, + y}$ because M2 is empty. Finally, the ant agent arrives at EN. Then, the final solution route (red lines) is determined as A–D–G–H–F–E and the makespan of the solution is determined as the latest completion time of all operations.

3 Literature review

3.1 Setup consideration on IPPS

Although numerous studies have been conducted for IPPS over the past two decades, few have explored the consideration of setups. Moon et al. (2002) proposed a GA for IPPS with sequence-dependent setup times and transportation times on a multi-plant supply chain environment. However, they did not handle the setup change time, tool change time, and unloading time separately. Li and McMahon (2007) proposed a simulated annealing approach to optimize makespan, utilization, tardiness, and cost for multi-objective IPPS, in which the sequence-dependent setup change time and tool change time are considered. Guo et al. (2009) proposed a PSO to re-plan multi-objective IPPS for occurrence of machine breakdown and new order arrival, in which a united sequence-dependent setup time is considered. Wan et al. (2011) proposed an ACO for IPPS. They argued that the sequence-dependent setup times should be handled separately to obtain an efficient schedule because the setup times cannot be ignored if two immediately preceding jobs are sequence-dependent. They considered the tool change time, loading (setup change) time, and unloading time separately. Furthermore, they verified that separate consideration of the sequence-dependent setup times can improve the makespan using an example proposed by Li et al. (2002) and Li and McMahon (2007). However, their research lacks mathematical descriptions of applying the sequence-dependent setup times and extensive experiments for various problems. Nourali et al. (2012) proposed a mixed integer linear programming model for IPPS considering a unified sequence-dependent setup time. Srinivas et al. (2012) proposed an approach combining ACO and PSO to minimize total manufacturing cost for IPPS, in which a sequence-dependent tool change cost and a setup change cost is considered. Recently, three hybrid PSOs (Petrović et al. 2016; Miljković and Petrović 2017; Dou et al. 2018) were proposed to minimize total manufacturing cost and total weighted production time for IPPS with sequence-dependent setups, in which a tool change time/cost, setup change time/cost, and transportation time/cost are dealt with. However, unloading time/cost is not considered. PSO combined with chaos theory (Petrović et al. 2016), PSO combined with GA (Miljković and Petrović 2017), and discrete PSO combined with GA (Dou et al. 2018) are proposed to overcome premature convergence of PSO.

All the above studies deal with sequence-dependent setup times and/or transportation time in IPPS. However, most of them do not handle various sequence-dependent setup times separately. In addition, most of the studies ignore some of the various sequence-dependent setup times, do not provide clear mathematical descriptions, or lack experiments. In this study, we have considered all existing sequence-dependent setup times and transportation time separately.

3.2 Ant colony optimization for IPPS

ACO focused studies in IPPS are as follows. Leung et al. (2010) proposed ACS with an elite strategy, but did not consider TAD flexibility, setups, and tool capacity. Srinivas et al. (2012) argued that the two planning activities conflict with objectives; process planning is meant to satisfy technological requirements and scheduling is meant to optimize timing aspects. As an approach to solve the conflict, they proposed a sequential hybrid algorithm in which ACO finds an optimal process planning and PSO finds an optimal schedule under the optimal process plan. However, they did not provide sufficient experimental results except only a few selected small-sized examples. Wang et al. (2014) proposed an improved AS for IPPS. To overcome the weakness of ACO of the local convergence, they proposed a method to reduce extraordinary accumulation of pheromones and a local pheromone updating rule that allows repeated accumulation of pheromones to avoid stagnation. Zhang and Wong (2014) proposed an ACO approach to retain two distinct pheromone trails on nodes and edges, respectively. To improve the performance of their approach, they also adopted the elitist strategy, the $\mathcal{MAX}$−$\mathcal{MIN}$ strategy, and the desirability function as the inverse of the increment of make span. Liu et al. (2016) introduced a mathematical programming model for IPPS and proposed a typical ACO to solve the problem. Zhang and Wong (2016) proposed a constructive meta-heuristic based on ACO for IPPS. To improve the solution quality, during operation selection, they adopted the earliest finishing time rule and time-window based mapping to reduce idling time. However, all three studies (Liu and MacCarthy 1997; Zhang and Wong 2014, 2016) did not consider TAD flexibility, sequence-dependent setups, and tool capacity constraints.

Most existing IPPS studies applying ACO as a main solver have omitted to consider sequence-dependent setups, TAD flexibility, and tool capacity constraints. The tool capacity constraints were discussed only by Kim et al. (2007). They, however, applied an asymmetric multileveled symbiotic evolutionary algorithm rather than ACO as an optimization algorithm, and ignored sequence-dependent setups and TAD flexibility. Srinivas et al. (2012) considered TAD flexibility and sequence-dependent setups, but they also ignored tool capacity constraints and provided experimental results for only a small-sized problem example. We believe that typical ACOs are limited in their ability to cover the various flexibilities and high complexity that IPPS has, and as an alternative to this, we suggest the evolving ant colony system in Sect. 4.2.

4 Proposed evolving ant colony system (EACS)

4.1 Issues of the conventional ant colony system

The stigmergic property of ACO is useful for improving solution quality, but it also causes a local convergence and/or a stagnation (Wang et al. 2014). Zhang and Wong (2013, 2014) pointed out three drawbacks in applying typical ACO to IPPS: (1) high likelihood of local convergence owing to a greedy strategy based on the shortest processing time when selecting the next node, (2) frequent reset of the algorithm and premature convergence due to excessive evaporation of pheromone trails, and (3) inefficient improvement of solution quality by adopting the makespan that is indistinct in value as an objective function. We fully agree with their claims; in particular, the evaporation issue is the most serious for IPPS.

Due to various flexibilities of IPPS, an operation can have many alternative operations depending on the machine, tool, or TAD to be processed. Since each alternative operation generates a distinct schedule, it is regarded as an independent operation in IPPS. Thus, as IPPS allows more flexibility, the number of nodes and edges increases sharply, and consequently, the size of the pheromone repository increases. For example, suppose that there are 20 jobs (parts) to be processed in total, each job consists of 20 operations, and the number of alternatives for machine, tool, and TAD for each operation is 3, 3, and 3, respectively. Then, the total number of independent operations is 10,800 (= 20 × 20 × 3 × 3 × 3); therefore, the total number of edges or the size of pheromone repository becomes 10,800 × 10,799. When the pheromone trails are updated globally, the evaporation process should be performed at every edge. The update requires a large calculation, which slows down the algorithm. However, the deposit process is performed only on the edges belonging to the general best solution at every iteration. It is only quite a small fraction of the total number of edges in pheromone trails. If the evaporation rate is not large enough, it implies that the total amount of deposited pheromone is smaller than the total amount of evaporated pheromone in the trails. As the iteration runs, the total amount of pheromone in trails decreases, and the pheromone trails become disabled. If the evaporation rate is set too large to avoid the disability, the relatively large pheromone on some edges causes a premature convergence. The magnitude of the effect depends on the number of edges in IPPS and the objective values of intermediate solutions. It implies that ACO is too sensitive to problems. Zhang and Wong (2013, 2014) attempted to solve these drawbacks of ACO for IPPS by various add-ons and a complicated procedure. We will tackle these using a simpler approach.

4.2 Overall procedure of EACS

In IPPS, all alternatives of an operation should be handled as independent nodes. Nevertheless, only a node among the alternative nodes is selected in a final solution route. In other words, almost all nodes in the IPPS network are redundant. Compared to the TSP where all nodes (cities) are included in the route, this situation leads to ineffective maintenance of pheromone trails. To overcome it, Zhang and Wong (2014) managed the pheromone trails for only operation $O_{j,o}$ and the alternative machines of the operation were determined by the dispatching rule during ACO execution. Since this approach does not generate redundant nodes, the size of pheromone trails can be kept constant number regardless of the number of alternative machines. This approach, however, does not retain all information for the best solution completely because the pheromone trails only accumulate experience for $O_{j,o}$ other than $O_{j,o}^{m,t,k}$. To compensate for the lack of information, they operated two distinct pheromone trails: edge-based trails for determining a sequence of operations and node-based trails for determining the resources $\left({m,t,k} \right)$ of an operation. However, the performance of their approach is doubtful because the effect of the resources on the schedule of an operation highly depends on the sequence of operations.

We, therefore, suggest an approach that accumulates the experience of sequences in the pheromone trails while the experience for resources stores in each ant agent. This approach not only allows efficient management of pheromone trails by disregarding redundant nodes, but also improves the solution quality by utilizing the experience for resources. In addition, it has the advantage of saving computation time by recycling the resource information included in the excellent solution routes. We will call the proposed approach the evolving ant colony system (EACS). A typical ACS, for each iteration, regenerates a certain number of ant agents, searches for new solution routes, stores information of the general best solution in the pheromone trails, and then destroys the ant agents. On the other hand, the proposed EACS conserves some ant agents that provide excellent solution for every iteration as shown in Fig. 3, where $s = \left\{{O_{j,o}^{m,t,k}} \right\}$ is a sequence of operations (solution); $f\left(s \right)$ is the objective function; $\tau_{0}$ is an initial value of a pheromone tail; $n_{iter}$ is the number of iteration, and $n_{CA}$ is the size of $CA$. Then, it improves the current solutions or searches for new solutions as shown in Fig. 4. Finally, it replaces a number of ant agents according to their performance and stores information of the iteration best and the general best solution in the pheromone trails.

Fig. 3

Pseudo-code for the main procedure of EACS

Fig. 4

Pseudo-code for the solution construction procedure of EACS

4.3 Route construction rule of EACS

The route construction rule of EACS is similar to that of ACS but differs from the heuristic desirability function and standardization of pheromone and desirability. Zhang and Wong (2014) demonstrated that applying the earliest completion time rule rather than the typical shortest processing time rule to the desirability function was more superior for improving the solution quality. After performing the preliminary experiments, we also reached the same conclusion.

EACS applies the desirability function $\eta \left(d \right)$ of Eq. (9) that is the difference of the expected completion time $ect\left(d \right)$ from the maximum among the candidates, i.e., $\mathop {\max}\nolimits_{d \in A} \left\{{ect\left(d \right)} \right\}$. In the equation, one is applied to avoid zero division error. The $ect\left(d \right)$ can be calculated using Eqs. (1)–(4) and (10), where notation $u$ and $v$ are the same as described above. Transportation time should be applied with caution. If a workpiece on the move is out of machine, so it only affects the starting time of subsequent operations belonging to the same job, the first term of Eq. (10) represents the earliest starting time of $d$. Unlike ACS, EACS does not use correction parameters such as $Q_{\eta}$ in Eq. (6) in the desirability calculation because the magnitude of $\eta$ is adjusted by the standardization described below.

$$\eta \left({c,d} \right) = \mathop {\max}\limits_{d \in A} \left\{{ect\left(d \right)} \right\} - ect\left(d \right) + 1$$

(9)

$$ect\left(d \right) = \hbox{max} \left\{{ult\left(u \right) + trt\left(u \right),ult\left(v \right)} \right\} + sct\left(d \right) + tct\left(d \right) + pt\left(d \right)$$

(10)

For all candidate nodes $d \in A$, one of them is selected as the next node $d^{*}$ to move. The node selection procedure of EACS is the same as Eq. (5) of ACS as shown in Eq. (11). For a random number $rand\left(\cdot \right)$, if $rand\left(\cdot \right) \le p_{ns}$, the node with the maximum value of $\widetilde{{\tau \left({c,d} \right)}}^{\alpha} \widetilde{{\eta \left({c,d} \right)}}^{\beta}$ among $d \in A$ is selected as the next node to increase intensification; otherwise, a node is determined by the roulette wheel selection to increase the diversity.

$$d^{*} = \left\{{\begin{array}{*{20}l} {\mathop {\arg \max}\limits_{{\hat{d} \in A}} \left\{{\widetilde{{\tau \left({c,d} \right)}}^{\alpha} \widetilde{{\eta \left({c,d} \right)}}^{\beta}} \right\},} \hfill & {if\,rand\left(\cdot \right) \le p_{ns}} \hfill \\ {\mathop {{\text{roulette}}_{\text{wheel}}}\limits_{{\hat{d} \in A}} \left\{{\frac{{\widetilde{{\tau \left({c,d} \right)}}^{\alpha} \widetilde{{\eta \left({c,d} \right)}}^{\beta} }}{{\mathop \sum \nolimits_{{\hat{d} \in A}} \widetilde{{\tau \left({c,d} \right)}}^{\alpha} \widetilde{{\eta \left({c,d} \right)}}^{\beta}}}} \right\},} \hfill & {o.w.} \hfill \\ \end{array}} \right.$$

(11)

The difference between this approach and ACS is that $\tau \left({c,d} \right)$ and $\eta \left({c,d} \right)$ are not used directly but are standardized as $\widetilde{{\tau \left({c,d} \right)}} = \frac{{\tau \left({c,d} \right)}}{{\mathop \sum \nolimits_{d \in A} \tau \left({c,d} \right)}}$ and $\widetilde{{\eta \left({c,d} \right)}} = \frac{{\eta \left({c,d} \right)}}{{\mathop \sum \nolimits_{d \in A} \eta \left({c,d} \right)}}$, respectively. In fact, $\tau \left({c,d} \right)$ and $\eta \left({c,d} \right)$ depend on the solution route until node $c$, the order of $c$ in the route, the processing times and setup times of operations, and the assigned machines, tools, and TADs of $c$, $d$, $u$, and $v$. Conventional ACS compensates for the variation by using the adjusting parameters $Q_{\tau}$ and $Q_{\eta}$. However, the effect is questionable because there are no absolute criteria for the magnitudes of $\tau \left({c,d} \right)$ and $\eta \left({c,d} \right)$. The unstable magnitudes of $\left({c,d} \right)$ and $\eta \left({c,d} \right)$ may also make it difficult to determine the parameters $\alpha$ and $\beta$, which are the degrees of contribution of the pheromone trails and desirability, respectively. If the magnitudes of $\tau \left({c,d} \right)$ and $\eta \left({c,d} \right)$ vary from IPPS to IPPS and from iteration to iteration, then determining the appropriate $\alpha$ and $\beta$ becomes another optimization problem. Our proposed standardization approach can maintain $\widetilde{{\tau \left({c,d} \right)}}$ and $\widetilde{{\eta \left({c,d} \right)}}$ within [0,1], so it is a good way to overcome this issue.

4.4 Solution improving heuristics

Through preliminary tests, we found that the following three factors reduce the performance of ACO for IPPS; (1) premature convergence due to lack of diversification, (2) slow improvement of solution quality due to various flexibilities, and (3) infeasibility of solutions due to capacity constraints in large sized problems. To overcome those, we introduce three greedy heuristics: OC, MTTC, and TUNING. The detailed procedures are expressed as pseudo code in Figs. 5, 6 and 7, respectively, where $n_{s}$ is the size of solution $s$; $O_{i}$ is the $i$th operation of solution $s$; $O_{{j,o_{u}}}^{{m_{u},t_{u},k_{u}}}$ is the operation that precede $O_{j,o}^{m,t,k}$ immediately in the job $j$; and $O_{{j_{v},o_{v}}}^{{m,t_{v},k_{v}}}$ is the operation that precede $O_{j,o}^{m,t,k}$ immediately on the machine $m$.

Fig. 5

Pseudo-code for the order change heuristic of EACS

Fig. 6

Pseudo-code for the machine, tool, and TAD change heuristic of EACS

Fig. 7

Pseudo-code for the machine, tool, and TAD tuning heuristic of EACS

In ACO, ant agents tend to follow the most popular solution route due to pheromone trails. OC increases the diversity of the solution route by artificially altering the sequence while maintaining precedence relations between operations. MTTC is a heuristic that randomly selects some operations, and then changes the machine, tool, and TAD of minimal processing time among alternatives. It is effective in improving the solution quality by allowing ant agents to retain excellent combinations of resources. TUNING coincides resources of successor to ones of predecessor. This procedure not only increases the feasibility of the solution by increasing reuse of resources, but also reduces sequence-dependent setup times.

4.5 Pheromone update rule of EACS

As discussed in Sect. 4.1, the biggest issue in applying ACO to IPPS is excessive evaporation of pheromone and the computation time required for pheromone update. To overcome it, we propose a simple approach that increases the pheromone by a constant without allowing evaporation. As the proposed updating rule only increases a fixed amount of pheromone, it may cause performance degradation of the algorithm due to unbalance in the magnitudes of $\tau \left({c,d} \right)$ and $\eta \left({c,d} \right)$ when applying the route construction rule. However, the standardization approach avoids such an imbalance.

The pheromone updating function of EACS is presented in Eq. (12), where the constant parameter $\Delta\tau$ is a constant incremental amount of the pheromone. The local update ($\Delta\tau_{local}$) and global update ($\Delta\tau_{global}$) are the same except for the amount of $\Delta\tau$. This simple updating function saves much computational effort because it updates only a few edges belonging to one solution route, rather than entire pheromone trails.

$$\tau_{i} \left({c,d} \right) = { \hbox{max} }\left\{{\tau_{max}, \tau_{i - 1} \left({c,d} \right) +\Delta\tau} \right\},\quad if \left({c,d} \right) \in s.$$

(12)

4.6 Objective function

It is reasonable to use the reciprocal of makespan $C_{MAX} \left(s \right)$ as an objective function if the objective of IPPS is to minimize makespan. However, the IPPS under consideration in this study has several constraints such as magazine capacity and tool capacity, so it is appropriate to add penalties for infeasible solution as in Kim et al. (2007). Equation (13) represents the penalty imposed on the objective function.

$$f\left(s \right) = \frac{100,000}{{C_{max} \left(s \right) + c_{t} \mathop \sum \nolimits_{\forall t} NST\left(t \right)^{{\gamma_{t}}} + c_{m} \mathop \sum \nolimits_{\forall m} NSS\left(m \right)^{{\gamma_{m}}}}}$$

(13)

Here, $C_{max} \left(s \right)$ represents the makespan for a solution route $s$, $NST\left(t \right)$ denotes the number of shortage of tools for the tool $t$, i.e., $NST\left(t \right) = \hbox{max} \left\{{n_{t}^{TOOL} - C_{t}^{TOOL},0} \right\}$, where $n_{t}^{TOOL}$ is the number of the tool $t$ used and $C_{t}^{TOOL}$ is the capacity of the tool $t$, and $NSS\left(m \right)$ is the number of shortage of slots in the tool magazine of the machine $m$, i.e., $NSS\left(m \right) = \hbox{max} \left\{{n_{m}^{SLOT} - C_{m}^{SLOT},0} \right\}$, where $n_{m}^{SLOT}$ is the number of slots to equip tools on the machine $m$ and $C_{m}^{slot}$ is the capacity of tool slots on the machine $m$. $c_{t}$, $c_{m}$, $\gamma_{t}$ and $\gamma_{m}$ are the adjusting parameters that determine the influence of the penalty on the objective function.

5 Experiment environment

5.1 Benchmark problem sets

There is no exact existing benchmark problem for the IPPS considered in this study, so we constructed 31 benchmark problems by modifying those of Kim et al. (2007), who used an IPPS that is most similar to our IPPS. Table 1 summarizes the identification of each problem, the list of jobs involved, and the total number of operations involved in the problem. The problem set is divided into small-sized problems (P1–P12), medium-sized problems (P13–P20), large-sized problems (P21–P28) and very-large-sized problems (P29–P31) depending on the number of jobs involved. For a detailed network representation, see Kim et al. (2007).

Table 1 Basic information on benchmark problems

Table 2 summarizes the information related to each job, machine, and tool. The job column provides information on the number of operations (#O) and the number of OR relations (#OR) included in each job. The machine column summarizes the capacity of slots on each machine. The tool column lists the capacity of each tool and the number of required slots for the tool $t$, i.e., $r_{t}^{SLOT}$. The sequence-dependent setup times $SCT\left(m \right)$, $ULT\left(m \right)$, and $TCT\left(t \right)$ and transportation time $TRT\left({m_{1},m_{2}} \right)$ used in the experiments are also summarized in Table 3.

Table 2 Information related to each job, machine, and tool

Table 3 Information on setup times and transportation time

5.2 Meta-heuristics and experiment environment for comparative study

We compare the performance of the proposed EACS with the three different meta-heuristics proposed for IPPS: the modified PSO (mPSO) by Miljković and Petrović (2017), the feasible sequence oriented discrete PSO (FSDPSO) by Dou et al. (2018), and enhanced ACO (E-ACO) by Zhang and Wong (2014). Since all three meta-heuristics have been proposed recently and the operating mechanisms are different, we believe that reasonable comparisons are possible. Among those, the most recently proposed FSDPSO was developed to overcome the difficulty of applying conventional continuous PSOs such as mPSO to discrete combinatorial problems such as IPPS. FSDPSO supports to discrete problems by updating particles using crossover and mutation operators of GA while maintaining the basic mechanism of PSO which improves particle swarm by correlation of current solution, iteration best solution and global best solution. Since the IPPSs applied by the methods are not the same as the IPPS we considered, we have slightly modified those to handle our problem. The algorithms of EACSNS and EACS are the same. The difference is that EACSNS treats all setup times as sequence-independent, so $sct\left(\cdot \right)$, $tct\left(\cdot \right)$, and $ult\left(\cdot \right)$ are always applied. Transportation time is applied to all algorithms in common.

Table 4 summarizes the parameters applied to the methods and EACS. Operational parameters of the comparative methods are assigned as the recommended values in each paper (Zhang and Wong 2014; Miljković and Petrović 2017; Dou et al. 2018), where $n_{iter}$ is the number of iterations; $n_{CA}$ is the size of colony or swarm; $n_{repeat}$ is the number of repetitions of the experiments; $W_{min}$ and $W_{min}$ are the initial and the final values of weighting parameters, respectively; $C_{1}$ and $C_{2}$ are self-recognition and social component acceleration coefficients, respectively; $p_{crossover}$, $p_{mutation}$, and $p_{shift}$ are selection probabilities for GA operations adopted at mPSO; $\omega$ is an inertia weight for velocity control, $p_{m}$ is fragment mutation probability; $k_{1}$ is scale factor for adjusting $p_{m}$; $k_{2}$ is the basic value of $p_{m}$; $Q$ and $D$ are scale factors for pheromone calculation; $C$ is a scale factor for heuristic desirability calculation; $\tau_{min}$ and $\tau_{max}$ are the lower and the upper bound of pheromone level, respectively; $\tau_{0}$ is an initial value of pheromone level; $\alpha$ and $\beta$ are respective weights of pheromone trail and heuristic desirability, respectively; $\rho_{gu}$ and $\rho_{lu}$ are evaporation rates for the global update and the local update, respectively; and $p_{ns}$ is node selection probability. The determination of parameters for EACS will be dealt with in detail in the next subsection. All algorithms were implemented using the Julia language Version 1.0 and the experiments were performed on an Intel^® Core™ i7-6700 CPU @3.40 GHz with 16.0 GB.

Table 4 Values of the parameters used in the meta-heuristics for comparative study

6 Experimental results

6.1 Parameter determination

A full factorial experiment was performed to determine the optimal operating parameters of EACS. We applied $3^{3}$ factorial design with 27 treatments with 3 levels for $p_{tune}$, $p_{mttc}$, and $p_{ns}$, respectively. Other parameters were determined by preliminary tests. Observations were made on makespan $C_{max}$ and computation time $t_{comp}$ for P1, P13, P21, P29, and P31, which are representative problems of each size level. Table 5 summarizes the results of this experiment. The value of each cell represents an average value of $C_{max}$ or $t_{comp}$ by repeating 20 times. In the $\overline{{C_{max}}}$ column, the sum of $\overline{{C_{max}}}$s of all problems (sum) and the performance rank (rank) based on it are added separately.

Table 5 $\overline{{C_{max}}}$ and $\overline{{t_{comp}}}$ according to $p_{tune}$, $p_{mttc}$, and $p_{ns}$ for the selected IPPS benchmark problems

Table 6 shows the results of an analysis of variance (ANOVA) to test whether the parameters and their interactions affect the sum of $\overline{{C_{max}}}$ s. All three parameters were statistically significant at the 0.05 significance level, but the interactions of them were not significant. The right-hand side of Table 7 is the ANOVA table after pooling the non-significant interactions. The boxplot for each factor is shown in Fig. 8a–c to determine the optimal level of the parameters. EACS shows similar performance at 0.7 and 0.8 of $p_{tune}$. We assigned 0.8 to $p_{tune}$ to improve calculation time. $p_{mttc}$ was determined to be 0.1 which shows the most stable solution quality. $p_{ns}$ was determined to be 0.8 which shows the best solution quality. This combination of the parameters is consistent with the result of the rank in Table 5. Although the summary is not presented, ANOVA for the $\overline{{t_{comp}}}$ was also performed. All parameters and several interactions were statistically significant. However, as Fig. 8d shows, the computation time decreases sharply as $p_{tune}$ increases. This is because the route improvement using the procedure TUNNING is much faster than the search of the new route using the route construction rule. However, the larger the $p_{tune}$, the worse the solution quality, so $p_{tune}$ is determined as the arbitrated value.

Table 6 ANOVA tables for the sum of $\overline{{C_{max}}}$s

Table 7 Makespan improvement caused by considering the sequence-dependent setup times for the benchmark problems

Fig. 8

Boxplots for $\overline{{C_{max}}}$ and $\overline{{t_{comp}}}$ according to $p_{tune}$, $p_{mttc}$, and $p_{ns}$

6.2 Effect of sequence-dependent setups

To confirm the assertion of Wan et al. (2011) that the optimal schedule can be improved by considering sequence-independent setups independently, an experiment was conducted on the benchmark problems. The experimental environment was the same as Table 4. Figures 9 and 10 show the best solution of EACSNS and EACS for P21 in a Gantt chart. In the figure, the y-axis represents machine identification and the x-axis is time. Each box represents schedules of an operation, where blue boxes are tool change times, red boxes are setup change times, yellow boxes are unloading times, and gray boxes are transportation time. The color of the texted boxes represents the job identification and the text in the box denotes $\left({j,o,m,t,k} \right)$ of the operation. The thick lined black rounded boxes in Fig. 6 show the examples for which the schedule was improved by applying the sequence-dependent setup times, in other words, the sequence-dependent setup times can be reduced by EACS.

Fig. 9

Gantt chart of a solution of EACSNS for P21

Fig. 10

Gantt chart of a solution of EACS for P21

The experimental results for $\overline{{C_{max}}}$ and $\overline{{t_{comp}}}$ are summarized in Table 7. EACS improves $\overline{{C_{max}}}$ up to 22% over EACSNS. The degree of improvement depends on the problem settings and the algorithm such as the magnitude of the setup times, the performance of the algorithm, the size of the ant colony, and the number of iterations. Nevertheless, the improvement of the makespan is clear and it positively affects to manufacturing cost.

6.3 Performance comparison for other meta-heuristics

The final series of experiments were conducted to compare the performance with existing meta-heuristics for IPPS. Four algorithms were used for the comparative study. mPSO (Miljković and Petrović 2017) and FSDPSO (Dou et al. 2018) are based on PSO and E-ACO (Zhang and Wong 2014) and EACS are based on ACO. The experiment was performed in the same way as the parameter setting in Table 4. As an exception, we increased the swarm size $n_{K}$ of FSDPSO to 60 for a fair comparison, because its computation time per iteration is very short compared to other meta-heuristics. The experimental results are summarized in Table 8. In Table 8, makespan and computation time are averaged for fifty repetitions, such as $\overline{{C_{max}}}$ and $\overline{{t_{comp}}}$, respectively. $C_{max}^{*}$ is the best makespan and $r_{inf}$ indicates the percentage of infeasible solutions among 50 repetitions. The last two columns compare $C_{max}^{*}$ and $\overline{{C_{max}}}$ of the current best algorithm FSDPSO versus EACS.

Table 8 Performance comparison for various types of meta-heuristics for IPPS

According to Table 8, with regards to solution quality, EACS presented the smallest $C_{max}^{*}$ and $\overline{{C_{max}}}$ for all problems except P4. This is easily confirmed by the boxplot in Fig. 11. Compared with the mPSO and E-ACO, EACS provides better solutions for all benchmark problems with less computation times. Even EACS is superior to the current best algorithm FSDPSO in solution quality. The decreases in $C_{max}^{*}$ and $\overline{{C_{max}}}$ of EACS compared with those of FSDPSO are 22% and 21%, respectively, and the increases in computation time is negligible. In fact, if we adjust $p_{tune}$ of EACS to 0.9, we can reduce $\overline{{t_{comp}}}$ by about 40% while slightly increasing $\overline{{C_{max}}}$ as shown in Table 5. Moreover, all solutions of the EACS and FSDPSO were feasible, but mPSO and E-ACO frequently derived infeasible solutions for large-sized problems. The effectiveness of OC, MTTC, and TUNING, which are three greedy heuristics proposed in Sect. 4.4, are summarized separately in Appendix 2.

Fig. 11

Boxplots of $C_{max}$ obtained by various methods for the selected IPPS problems

Table 9 summarizes the results of hypothesis tests using a single-sided two sample t test for the experiment. Although the makespans of E-ACO for P31 did not satisfy the normality, the test was performed because the difference is so clear in the boxplot of Fig. 8. Some of test pairs do not satisfy the equality of variances, so all the tests were performed assuming unequal variances. As a result of the hypothesis test at a significance level 0.05, the solution quality of EACS was superior to that of all existing meta-heuristics even including EACSNS.

Table 9 Hypothesis test for $\mu_{{C_{max}}}$ at a significance level of 0.05(**)

7 Discussion and conclusion

The contributions of this study can be summarized in two ways. The first is that the flexibilities, constraints, and setups considered in the IPPS to date have been aggregated into a comprehensive IPPS problem. By doing so, the IPPS is closer to the real manufacturing environment. Secondly, we proposed a new ACO approach to solve the more complicated IPPS. Existing ACOs have limitations when they are applied to large-sized problems. The newly proposed EACS can reduce the computational effort required to maintain the pheromone trails. Furthermore, it can improve the performance of the ACO by enhancing the capability of each ant agent. Nevertheless, there are some issues that need to be discussed.

First, although EACS improves the efficiency of ACO, it continues to require a large amount of computational effort. Various flexibilities considered in IPPS generate many alternative operations. Every ant agent in ACO should determine the next visiting node among those alternatives on every node in all iterations, which results in a large computation time. If the sequence-dependent setups are considered, it is even worse. We expect that development of a greedy heuristic such as Lin–Kernighan in the symmetric traveling salesman problem will help this obstacle. Second, a new design of pheromone trails is necessary. The key factors for determining the schedule in IPPS are job, operation, and machine. Thus, the pheromone trails should have three-dimensional structures that can handle these three factors simultaneously. However, both the existing ACO and our EACS run with two-dimensional pheromone trails based on job and operation. This is only because the repository size of the pheromone trails due to many alternatives. Parallel computing or distributed repository might be a solution for this problem.

Appendices

Appendix 1: Mathematical programming model of IPPS

The mathematical programming model for IPPS has been developed by Li et al. (2010) and Nourali et al. (2012). Nourali et al. (2012) proposed a mixed integer linear programming for assembly jobshop considering sequence-dependent setup times. However, the assembly jobshop problem is different from IPPS, but it does not consider loading and unloading, tool change, TAD change, and transportation time. On the other hand, Li et al. (2010) deals with IPPS but does not consider sequence-dependent setup times. Therefore, we present a new mixed integer nonlinear programming model for the proposed IPPS through the improvement of these two MILPs.

Sets and indices

$j$:

job identification (ID) ($j \in J$)

$o$:

operation ID of job $j$ ($o \in O_{j}$)

$m$:

machine ID ($m \in M$)

$t$:

tool ID ($t \in T$)

$k$:

TAD ID ($k \in K$)

$p_{j}$:

process route ID of job $j$ ($p_{j} \in P_{j}$)

$J$:

set of jobs; $J = \left\{{1,2,3, \ldots,n^{JOB}} \right\}$, $n^{JOB}$ is the total number of jobs

$O_{j}$:

set of operations of job $j$ ($O_{j} \subseteq O$); $O_{j} = \left\{{1,2,3, \ldots,n_{j}^{OP}} \right\}$, $n_{j}^{OP}$ is the total number of operations of the job $j$

$M$:

set of machines; $M = \left\{{1,2,3, \ldots,n^{M}} \right\}$, $n^{M}$ is the total number of machines

$T$:

set of tools; $T = \left\{{1,2,3, \ldots,n^{T}} \right\}$, $n^{T}$ is the total number of tool types

$K$:

set of TADs; $K = \left\{{-\,x, x, -\,y, y, -\,z, z} \right\}$, $- x, x, - y, y, - z, z$ are directions of tool access

$P_{j}$:

set of alternative process routes of job $j$

$O_{{jp_{j}}}$:

ordered set of operation IDs in the process route $p_{j}$ of job $j$ ($O_{j} = \mathop {\bigcup}\nolimits_{{p_{j} \in P_{j}}} O_{{jp_{j}}} \forall j \in J$)

$O_{j,o}$:

the operation $o$ of job $j$

$O_{j,o}^{m,t,k}$:

the $O_{j,o}$ that is assigned the machine $m$, the tool $t$, and the TAD $k$

$O_{{jp_{j} i}}$:

the $i$th operation ID of $O_{{jp_{j}}}$; $O_{{jp_{j} f}}$ is the first and $O_{{jp_{j} l}}$ is the last element of $O_{{jp_{j}}}$

$O_{{jp_{j} imtk}}$:

operation $O_{{jp_{j} i}}$ that is assigned machine $m$, tool $t$, and TAD $k$

$M_{{jp_{j} i}}$:

set of alternative machines for the operation $O_{{jp_{j} i}}$, $M_{{jp_{j} i}} \subseteq M$

$T_{{jp_{j} im}}$:

set of alternative tools for the operation $O_{{jp_{j} i}}$ at the machine $m$; $T_{{jp_{j} im}} \subseteq T$

$K_{{jp_{j} im}}$:

set of alternative TADs for the operation $O_{{jp_{j} i}}$ at the machine $m$; $K_{{jp_{j} im}} \subseteq K.$

Parameters

$R_{{jp_{j} ii^{\prime}}}$:

1, if the operation $O_{{jp_{j} i}}$ must precede the operation $O_{{jp_{j} i^{\prime}}}$; 0, otherwise

$C_{m}^{SLOT}$:

the number (capacity) of tool slots of the machine $m$

$C_{t}^{TOOL}$:

the available number (capacity) of the tool $t$

$r_{t}^{SLOT}$:

the number of required slots for the tool $t$

$L$:

a very large number.

Decision variables

$X_{{jp_{j} imtk}}$:

1, if machine $m$, tool $t$, and TAD $k$ are selected for the $O_{{jp_{j} i}}$; 0, otherwise

$Z_{{jp_{j}}}$:

1, if process route $p_{j}$ of job $j$ is selected; 0, otherwise

${\text{Y}}_{{jp_{j} ij^{\prime} p_{{j^{\prime}}} i^{\prime} m}}$:

1, if operation $O_{{jp_{j} i}}$ precedes operation $O_{{j^{\prime} p_{{j^{\prime}}} i^{\prime}}}$ immediately on machine $m$; 0, otherwise

$U_{mt}$:

1, if tool $t$ is installed on machine $m$; 0, otherwise

$st_{{jp_{j} imtk}}$:

starting time of $O_{{jp_{j} imtk}}$

$ct_{{jp_{j} imtk}}$:

earliest completion time of $O_{{jp_{j} imtk}}$

$sct_{{jp_{j} imtk}}$:

setup change time of $O_{{jp_{j} imtk}}$

$tct_{{jp_{j} imtk}}$:

tool change time of $O_{{jp_{j} imtk}}$

$pt_{{jp_{j} imtk}}$:

processing time of $O_{{jp_{j} imtk}}$

$ult_{{jp_{j} imtk}}$:

unload time of $O_{{jp_{j} imtk}}$

$trt_{{jp_{j} imtk}}$:

transportation time to the successive operation of $O_{{jp_{j} imtk}}$

C_max:

makespan.

MINLP for IPPS

$${\text{Minimize}}\quad C_{max}$$

(14)

subject to

$$\mathop \sum \limits_{{p_{j} \in P_{j}}} Z_{{jp_{j}}} = 1 \quad \forall j \in J$$

(15)

$$\mathop \sum \limits_{{m \in M_{{jp_{j} i}}}} \mathop \sum \limits_{{t \in T_{{jp_{j} im}}}} \mathop \sum \limits_{{ k \in K_{{jp_{j} im}}}} X_{{jp_{j} imtk}} = Z_{{jp_{j}}} \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}$$

(16)

$$st_{{jp_{j} imtk}} + ct_{{jp_{j} imtk}} \le L\left({X_{{jp_{j} imtk}}} \right)\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(17)

$$\begin{aligned} & st_{{jp_{j} imtk}} + sct_{{jp_{j} imtk}} + tct_{{jp_{j} imtk}} + pt_{{jp_{j} imtk}} + ult_{{jp_{j} imtk}} - L\left({1 - X_{{jp_{j} imtk}}} \right) \le ct_{{jp_{j} imtk}} \\ & \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}} \\ \end{aligned}$$

(18)

$$\begin{aligned} & ct_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} mt^{\prime} k^{\prime}}} - L\left({{\text{Y}}_{{jp_{j} ij^{\prime} p_{{j^{\prime}}} i^{\prime} m}}} \right) \le st_{{jp_{j} imtk}} \\ & \quad \forall j,j^{\prime} \in J, \forall p_{j} \in P_{j}, \forall p_{{j^{\prime}}} \in P_{{j^{\prime}}} \forall i \in O_{{jp_{j}}},\forall i^{\prime} \in O_{{j^{\prime} p_{{j^{\prime}}}}}, \\ & \quad \forall m \in M_{{jp_{j} i}} \cap M_{{j^{\prime} p_{{j^{\prime}}}}},\forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}},\forall t^{\prime} \in T_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} m}}, \forall k^{\prime} \in K_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} m}} \\ \end{aligned}$$

(19)

$$\begin{aligned} & ct_{{jp_{j} imtk}} - L\left({1 - {\text{Y}}_{{jp_{j} ij^{\prime} p_{{j^{\prime}}} i^{\prime} m}}} \right) \le st_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} mt^{\prime} k^{\prime}}} \\ & \quad \forall j,j^{\prime} \in J, \forall p_{j} \in P_{j}, \forall p_{{j^{\prime}}} \in P_{{j^{\prime}}} \forall i \in O_{{jp_{j}}},\forall i^{\prime} \in O_{{j^{\prime}p_{{j^{\prime}}}}}, \\ & \quad \forall m \in M_{{jp_{j} i}} \cap M_{{j^{\prime} p_{{j^{\prime}}}}},\forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}},\forall t^{\prime} \in T_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} m}}, \forall k^{\prime} \in K_{{j^{\prime} p_{{j^{\prime}}} i^{\prime} m}} \\ \end{aligned}$$

(20)

$$\begin{aligned} & \mathop \sum \limits_{{m \in M_{{jp_{j} \left({i - 1} \right)}}}} \mathop \sum \limits_{{t \in T_{{jp_{j} \left({i - 1} \right)m}}}} \mathop \sum \limits_{{ k \in K_{{jp_{j} \left({i - 1} \right)m}}}} \left({ct_{{jp_{j} \left({i - 1} \right)mtk}} + trt_{{jp_{j} \left({i - 1} \right)mtk}}} \right) \le \mathop \sum \limits_{{m^{\prime} \in M_{{jp_{j} i}}}} \mathop \sum \limits_{{t^{\prime} \in T_{{jp_{j} im}}}} \mathop \sum \limits_{{ k^{\prime} \in K_{{jp_{j} im}}}} st_{{jp_{j} im^{\prime} t^{\prime} k^{\prime}}} \\ & \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}} - \left\{{O_{{jp_{j} f}}} \right\} \\ \end{aligned}$$

(21)

$$\begin{aligned} & \mathop \sum \limits_{{m \in M_{{jp_{j} i}}}} \mathop \sum \limits_{{t \in T_{{jp_{j} im}}}} \mathop \sum \limits_{{ k \in K_{{jp_{j} im}}}} \left({ct_{{jp_{j} imtk}} + trt_{{jp_{j} imtk}}} \right) - L\left({1 - R_{{jp_{j} ii^{\prime}}}} \right) \le \mathop \sum \limits_{{m^{\prime} \in M_{{jp_{j} i^{\prime}}}}} \mathop \sum \limits_{{t^{\prime} \in T_{{jp_{j} i^{\prime} m}}}} \mathop \sum \limits_{{ k^{\prime} \in K_{{jp_{j} i^{\prime} m}}}} st_{{jp_{j} i^{\prime} m^{\prime} t^{\prime} k^{\prime}}}, \\ & \quad \forall i < i^{\prime},j \in J, \forall p_{j} \in P_{j}, \forall i,i^{\prime} \in O_{{jp_{j}}} \\ \end{aligned}$$

(22)

$$ult_{{jp_{j} lmtk}} \ge ULT\left(m \right)\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall m \in M_{{jp_{j} l}}, \forall t \in T_{{jp_{j} lm}}, \forall k \in K_{{jp_{j} lm}}$$

(23)

$$ct_{{jp_{j} lmtk}} \le C_{max} \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall m \in M_{{jp_{j} l}}, \forall t \in T_{{jp_{j} lm}}, \forall k \in K_{{jp_{j} lm}}$$

(24)

$$X_{{jp_{j} imtk}} \ge U_{mt} \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall m \in M_{{jp_{j} l}}, \forall t \in T_{{jp_{j} lm}}, \forall k \in K_{{jp_{j} lm}}$$

(25)

$$\mathop \sum \limits_{t \in T} r_{t}^{SLOT} \times U_{mt} \le C_{m}^{SLOT} \quad \forall m \in M$$

(26)

$$\mathop \sum \limits_{m \in M} U_{mt} \le C_{t}^{TOOL} \quad \forall t \in T$$

(27)

$$st_{{jp_{j} imtk}} \ge 0\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(28)

$$sct_{{jp_{j} imtk}} \ge 0\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(29)

$$tct_{{jp_{j} imtk}} \ge 0 \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(30)

$$pt_{{jp_{j} imtk}} \ge 0\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(31)

$$ult_{{jp_{j} imtk}} \ge 0 \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(32)

$$trt_{{jp_{j} imtk}} \ge 0\quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(33)

$$X_{{jp_{j} imtk}} \in \left\{{0,1} \right\} \quad \forall j \in J, \forall p_{j} \in P_{j}, \forall i \in O_{{jp_{j}}}, \forall m \in M_{{jp_{j} i}}, \forall t \in T_{{jp_{j} im}}, \forall k \in K_{{jp_{j} im}}$$

(34)

$$Z_{{jp_{j}}} \in \left\{{0,1} \right\} \quad \forall j \in J, \forall p_{j} \in P_{j}$$

(35)

$${\text{Y}}_{{jp_{j} ij^{\prime} p_{{j^{\prime}}} i^{\prime} m}} \in \left\{{0,1} \right\} \quad \forall j,j^{\prime} \in J, \forall p_{j} \in P_{j}, \forall p_{{j^{\prime}}} \in P_{{j^{\prime}}} \forall i \in O_{{jp_{j}}},\forall i^{\prime} \in O_{{j^{\prime} p_{{j^{\prime}}}}},\forall m \in M_{{jp_{j} i}} \cap M_{{j^{\prime} p_{{j^{\prime}}}}}$$

(36)

$$U_{mt} \in \left\{{0,1} \right\}\quad \forall m \in M, \forall t \in T$$

(37)

IPPS is a problem that minimizes makespan of the objective function (14). Constraints (15) allow only one process route to be selected in each job. Constraints (16) make sure that each operation of a selected process route selects only a combination of $\left({m,t,k} \right)$. Constraints (17) make time schedules of all dummy operations zero. Constraints (18) ensure that each operation is completed by consuming relevant sequence-dependent setup times and processing time. Constraints (19) and (20) ensure that two or more operations are not performed simultaneously on the same machine. Constraints (21) consider transportation time for workpiece movement in the same job. Constraints (22) ensure that all precedence relations between operations are satisfied. Constraints (23) ensure that the completed workpiece is unloaded at the last operation of each job. Constraints (24) determine makespan. Constraints (25) prevent duplicate installation of the same tool on a machine. Constraints (26) and (27) are constraints on machine’s slot capacity and tool capacity, respectively. Constraints (28)–(37) are the possible ranges of time schedules and decision variables.

Appendix 2: Validation of effectiveness of OC, MTTC, and TUNING

Additional experiments were performed to verify the effectiveness of the three greedy heuristics OC, MTTC, and TUNING proposed in Sect. 4.4. OC, MTTC, and TUNING were inserted into the procedures of mPSO, FSDPSO, and E-ACO. Then, the five representative problems P1, P13, P21, P29 and P31 were repeated 10 times for each algorithm. Table 10 summarizes the experimental results before and after applying the three greedy heuristics. Three greedy heuristics reduced $\overline{{C_{max}}}$ by 4.5% and 0.8% on average for mPSO and FSDPSO, respectively. On the other hand, for E-ACO, it resulted in a dramatic improvement by reducing $\overline{{C_{max}}}$ by 27.4% and $\overline{{t_{comp}}}$ by 75.4%. This phenomenon occurs because mPSO and FSDPSO contain procedures like OC, MTTC, and TUNING, but E-ACO does not. The results of this comparative study demonstrate that these three greedy heuristics are effective in improving the solution and reducing the computation time. Another notable point is that the performance of our proposed EACS is still better than others, although other meta-heuristics have been improved by OC, MTTC, and TUNING.

Table 10 Analysis of effectiveness of three greedy heuristics for various types of ACOs