# A Two-Level Metaheuristic for the Job-Shop Scheduling Problem with Multipurpose Machines

Authors: Pisut Pongchairerks
Journal: Complexity
 (2022)

---

## Abstract

This paper proposes a two-level metaheuristic consisting of lower- and upper-level algorithms for the job-shop scheduling problem with multipurpose machines. The lower-level algorithm is a local search algorithm used for finding an optimal solution. The upper-level algorithm is a population-based metaheuristic used to control the lower-level algorithm’s input parameters. With the upper-level algorithm, the lower-level algorithm can reach its best performance on every problem instance. Most changes of the proposed two-level metaheuristic from its original variants are in the lower-level algorithm. A main purpose of these changes is to increase diversity into solution neighborhood structures. One of the changes is that the neighbor operators of the proposed lower-level algorithm are developed to be more adjustable. Another change is that the roulette-wheel technique is applied for selecting a neighbor operator and for generating a perturbation operator. In addition, the proposed lower-level algorithm uses an adjustable delay-time limit to select an optional machine for each operation. The performance of the proposed two-level metaheuristic was evaluated on well-known benchmark instances. The evaluation’s results indicated that the proposed two-level metaheuristic performs well on most benchmark instances.


---

## Body

## 1. Introduction

The job-shop scheduling problem (JSP) is a well-known NP-hard optimization problem [1–3]. JSP involves scheduling jobs onto machines in order to minimize makespan, i.e., the schedule’s length. Each job consists of a number of operations, where each operation must be processed on a predetermined machine with a predetermined processing time. To complete each job, all of its operations must be processed in the sequence from the first to the last operations. JSP has many variants and related problems, such as [4–7]. One of the well-known variants of JSP is the job-shop scheduling problem with multipurpose machines (MPMJSP) [8–10]. MPMJSP is defined as a generalized variant of JSP. An only difference between them is that each operation in JSP has only one predetermined machine, while each operation in MPMJSP may have more than one optional machine. This difference makes MPMJSP be closer to the real-world applications in modern factories than JSP because, nowadays, most machines have been developed for multiple tasks.In this paper, the research’s objective is to develop a high-performing algorithm for MPMJSP. To do so, this paper proposes a two-level metaheuristic, based on the framework of [5, 11, 12], consisting of upper- and lower-level algorithms. The upper-level algorithm is a population-based metaheuristic that acts as a parameter controller for the lower-level algorithm. The upper-level algorithm’s population consists of the parameter-value combinations of the lower-level algorithm. In a parameter-value combination, each parameter’s value is iteratively changed by a sum of two changeable opposite-direction vectors. The directions of the first and the second vectors are toward and away from, respectively, the memorized best-found value. The lower-level algorithm is a local search algorithm searching for an optimal solution of the being-solved MPMJSP problem. Like other metaheuristics, the lower-level algorithm cannot perform its best on all instances with a single combination of input-parameter values. This drawback can be overcome when its input parameters are controlled by the upper-level algorithm.The proposed two-level metaheuristic is modified from its original variant [12], where the main differences are in their lower-level algorithms. Their lower-level algorithms both search for an optimal solution in hybrid neighborhood structures via their optional operators. Their optional neighbor operators are similarly modified from the traditional operators (i.e., swap, insert, and reverse) by limiting a distance between positions of two members selected in a solution-representing permutation. However, while the lower-level algorithm of [12] has only three levels of the distance limit, the distance limit in this paper is adjustable to any possible range. Another main difference is in their methods of generating their hybrid neighborhood structures. To generate each neighbor solution-representing permutation, the lower-level algorithm of [12] uses a given probability to select one of two neighbor operators. Instead, the proposed lower-level algorithm uses the roulette-wheel method [13] to select one from three neighbor operators. In this paper, the roulette-wheel method is also applied to select multiple optional operators for generating a perturbation operator. A purpose of using the roulette-wheel method is to diversify more on the hybridization of the neighborhood structure.As mentioned, each operation in MPMJSP has one or more optional machines. The lower-level algorithm proposed in this paper uses the delay-time limit (δ), as its input parameter, to make a criterion of selecting a machine for each operation. This use of δ is different from the uses of δ in the other researches, e.g., [10, 11, 14–17]. While the proposed lower-level algorithm uses δ to select a machine for each operation, the other researches use δ to select an operation into a timetable. A method of generating a schedule of the proposed lower-level algorithm is briefly presented as follows: First, an appearance order of all operations in a solution-representing permutation is used as a priority order for all operations. Then, every operation is assigned one-by-one into a schedule by the given priority order. When being assigned, each operation must be processed on the machine that satisfies δ, and it must be started as early as the machine can.The remainder of this paper is divided into five sections. Section2 describes MPMJSP and reviews the previous researches relevant to the proposed two-level metaheuristic. Section 3 describes the proposed two-level metaheuristic in detail. Section 4 shows experiment’s results of evaluating the proposed two-level metaheuristic’s performance. Section 5 then analyzes and discusses the experiment’s results. Finally, Section 6 concludes the research’s findings.


## 2. Preliminaries

In this section, the description of MPMJSP is given in Section2.1, and the review on the previous researches relevant to the proposed two-level metaheuristic is given in Section 2.2.


### 2.1. Description of MPMJSP

The job-shop scheduling problem with multipurpose machines (MPMJSP) is classified as a generalization of the job-shop scheduling problem (JSP). An only difference between JSP and MPMJSP is their numbers of optional machines of each operation. That is, while each operation in JSP has only one predetermined machine, each operation in MPMJSP has one or more optional machines. MPMJSP thus becomes JSP if each of its operations has only one optional machine. A similar variant of MPMJSP is the flexible job-shop scheduling problem (FJSP) [18, 19]. MPMJSP and FJSP both are the JSP’s variants where each operation may have more than one optional machine. However, the processing time of an operation in FJSP may change when changing its selected optional machine, while the processing time of each operation in MPMJSP is fixed for all of its optional machines. This means MPMJSP is a specific FJSP where, for each operation, all optional machines have the same processing time.Notation used to describe MPMJSP in this paper is defined below:(i)
Letn denote the number of all jobs in MPMJSP.(ii)
Letm denote the number of all machines in MPMJSP.(iii)
LetJi denote the i-th job in MPMJSP, where i = 1, 2, …, n.(iv)
LetMj denote the j-th machine in MPMJSP, where j = 1, 2, …, m.(v)
Letni denote the number of all operations of Ji.(vi)
LetOik denote the k-th operation of Ji, where k = 1, 2, …, ni.(vii)
Letτik denote the processing time of Oik.(viii)
Letmik denote the number of all optional machines of Oik, where i = 1, 2, …, n, and k = 1, 2, …, ni.(ix)
LetEikl ∈ all optional machines of Oik that appear in {M1, M2, …, Mm} and denote the l-th optional machine of Oik, where l = 1, 2, …, mik. In other words, Eikl is equivalent to the Mj that owns the l-th lowest value of j among all optional machines of Oik. For example, suppose O12 has three optional machines, i.e., M2, M4, and M5. Thus, E121 = M2, E122 = M4, and E123 = M5.MPMJSP comes withn given jobs (J1, J2, …, Jn) and m given machines (M1, M2, …, Mm). Each job Ji consists of a sequence of ni given operations (Oi1, Oi2, …, Oini) as a chain of precedence constraints. To complete each job Ji, Oi1 must be finished before Oi2 can start; Oi2 must be finished before Oi3 can start, and so on. Each Oik must be processed by one of Eik1, Eik2, …, Eikmik with the processing time of τik. Each machine cannot process more than one operation at a time, and it cannot be stopped during processing an operation. At the beginning (i.e., time 0), all jobs have already arrived, and all machines have not been occupied. An optimal schedule is a feasible schedule that minimizes makespan (i.e., the schedule’s length).MPMJSP was first introduced by Brucker and Schlie [8]. They also proposed a polynomial-time algorithm for MPMJSP with two jobs. MPMJSP with three jobs belongs to NP-hard problem even if the number of all machines is two [9]. Tabu-search algorithms were developed by [9] for solving three sets of MPMJSP benchmark instances, i.e., Edata, Rdata, and Vdata. Since then, these three instance sets have been commonly used for comparing results of different algorithms on MPMJSP. To date, many algorithms have been developed for solving MPMJSP and its closely related problems [10, 18–21].


### 2.2. Previous Relevant Researches

Iterated local search is traditionally defined as a single-solution-based metaheuristic that can search for a global optimal solution. During an exploration, it uses a neighbor operator repeatedly to find a local optimum and then uses a perturbation operator to escape the found local optimum. Note that a perturbation operator stands for an operator that generates a new initial solution by largely modifying a found local optimal solution [22]. Some untraditional iterated local search algorithms are enhanced in their performance by using multiple initial solutions [23, 24]. The iterated local search algorithms have been successful on many optimization problems, including MPMJSP and FJSP [25, 26].In iterated local search and related algorithms, there are three operators usually used as neighbor operators and perturbation operators. These three operators are the traditional swap, insert, and reverse operators [27]. To explain the mentioned operators, let u and v be two different integers randomly generated from 1 to D, where D represents the number of all members in a solution-representing permutation. The swap operator is to swap between the two members in the u-th and the v-th positions of the permutation. The insert operator is to remove a member from the u-th position of the permutation and then insert it back at the v-th position. The reverse operator is to reverse the sequence of all members from the u-th to the v-th positions of the permutation.A common drawback of most metaheuristics is that their performance is dependent on their parameter-value settings. To overcome such a drawback, many applications use upper-level algorithms to control parameters of their solution-searching algorithms [11, 12, 14, 15, 28–31]. Some of them, e.g., [5], require more than two levels of algorithms for very complicated problems; however, most of them require only two levels. For solving JSP, there are two two-level metaheuristics acting as adaptive iterated local search algorithms [11, 12]. In each of the two-level metaheuristics, the upper-level algorithm controls the lower-level algorithm’s input parameters, while the lower-level algorithm is a local search algorithm searching for an optimal job-shop schedule.UPLA and MUPLA are the upper-level algorithms in [11, 12], respectively; they both are population-based algorithms searching in real-number search spaces. In each of them, the population is a number of the parameter-value combinations of the lower-level algorithm. In a parameter-value combination, each parameter’s value is iteratively changed by a sum of two changeable opposite-direction vectors. The first vector’s and the second vector’s directions are toward and away from, respectively, the memorized best-found value. In only MUPLA, each parameter-value combination includes a different start operation-based permutation; thus, the two-level metaheuristic of [12] has a multistart property.LOLA, the lower-level algorithm in [11], is a local search algorithm exploring in a solution space of parameterized-active schedules (i.e., hybrid schedules [16]). Its input parameters (i.e., a delay-time limit, a scheduling direction, a perturbation operator, and a neighbor operator) are controlled by UPLA, its upper-level algorithm. Because the delay-time limit (δ) is one of the input parameters controlled, UPLA then can control the solution space’s size of parameterized-active schedules. Such a control of δ follows in the successes of the two-level PSOs of [14, 15]. Other techniques of controlling δ can also be found in literature. For example, the value of δ in [10] is dependent on the number of jobs and the number of machines, while the value of δ in [17] is dependent on the algorithm’s iteration index. In addition, the PSO in [32] controls the value of δ by using the concept of self-adaptive parameter control [28].LOSAP, the lower-level algorithm in [12], is a local search algorithm searching in a probabilistic-based hybrid neighborhood structure. By a given probability, LOSAP randomly uses one from two predetermined operators to generate a neighbor solution-representing permutation. In other words, based on the given probability, LOSAP can switch between the two given operators anytime during its exploration. While the search performance of LOLA [11] is mainly based on its special solution space, that of LOSAP is mainly based on its hybrid neighborhood structure. LOSAP has multiple optional operators for its perturbation and neighbor operators. These optional operators are modified from the traditional operators by limiting the distance of v from u. For generating v in LOSAP, there are three optional distance-limit levels: [u − 4, u + 4], [u − (D/5), u + (D/5)], and [1, D].


## 2.1. Description of MPMJSP

The job-shop scheduling problem with multipurpose machines (MPMJSP) is classified as a generalization of the job-shop scheduling problem (JSP). An only difference between JSP and MPMJSP is their numbers of optional machines of each operation. That is, while each operation in JSP has only one predetermined machine, each operation in MPMJSP has one or more optional machines. MPMJSP thus becomes JSP if each of its operations has only one optional machine. A similar variant of MPMJSP is the flexible job-shop scheduling problem (FJSP) [18, 19]. MPMJSP and FJSP both are the JSP’s variants where each operation may have more than one optional machine. However, the processing time of an operation in FJSP may change when changing its selected optional machine, while the processing time of each operation in MPMJSP is fixed for all of its optional machines. This means MPMJSP is a specific FJSP where, for each operation, all optional machines have the same processing time.Notation used to describe MPMJSP in this paper is defined below:(i)
Letn denote the number of all jobs in MPMJSP.(ii)
Letm denote the number of all machines in MPMJSP.(iii)
LetJi denote the i-th job in MPMJSP, where i = 1, 2, …, n.(iv)
LetMj denote the j-th machine in MPMJSP, where j = 1, 2, …, m.(v)
Letni denote the number of all operations of Ji.(vi)
LetOik denote the k-th operation of Ji, where k = 1, 2, …, ni.(vii)
Letτik denote the processing time of Oik.(viii)
Letmik denote the number of all optional machines of Oik, where i = 1, 2, …, n, and k = 1, 2, …, ni.(ix)
LetEikl ∈ all optional machines of Oik that appear in {M1, M2, …, Mm} and denote the l-th optional machine of Oik, where l = 1, 2, …, mik. In other words, Eikl is equivalent to the Mj that owns the l-th lowest value of j among all optional machines of Oik. For example, suppose O12 has three optional machines, i.e., M2, M4, and M5. Thus, E121 = M2, E122 = M4, and E123 = M5.MPMJSP comes withn given jobs (J1, J2, …, Jn) and m given machines (M1, M2, …, Mm). Each job Ji consists of a sequence of ni given operations (Oi1, Oi2, …, Oini) as a chain of precedence constraints. To complete each job Ji, Oi1 must be finished before Oi2 can start; Oi2 must be finished before Oi3 can start, and so on. Each Oik must be processed by one of Eik1, Eik2, …, Eikmik with the processing time of τik. Each machine cannot process more than one operation at a time, and it cannot be stopped during processing an operation. At the beginning (i.e., time 0), all jobs have already arrived, and all machines have not been occupied. An optimal schedule is a feasible schedule that minimizes makespan (i.e., the schedule’s length).MPMJSP was first introduced by Brucker and Schlie [8]. They also proposed a polynomial-time algorithm for MPMJSP with two jobs. MPMJSP with three jobs belongs to NP-hard problem even if the number of all machines is two [9]. Tabu-search algorithms were developed by [9] for solving three sets of MPMJSP benchmark instances, i.e., Edata, Rdata, and Vdata. Since then, these three instance sets have been commonly used for comparing results of different algorithms on MPMJSP. To date, many algorithms have been developed for solving MPMJSP and its closely related problems [10, 18–21].


## 2.2. Previous Relevant Researches

Iterated local search is traditionally defined as a single-solution-based metaheuristic that can search for a global optimal solution. During an exploration, it uses a neighbor operator repeatedly to find a local optimum and then uses a perturbation operator to escape the found local optimum. Note that a perturbation operator stands for an operator that generates a new initial solution by largely modifying a found local optimal solution [22]. Some untraditional iterated local search algorithms are enhanced in their performance by using multiple initial solutions [23, 24]. The iterated local search algorithms have been successful on many optimization problems, including MPMJSP and FJSP [25, 26].In iterated local search and related algorithms, there are three operators usually used as neighbor operators and perturbation operators. These three operators are the traditional swap, insert, and reverse operators [27]. To explain the mentioned operators, let u and v be two different integers randomly generated from 1 to D, where D represents the number of all members in a solution-representing permutation. The swap operator is to swap between the two members in the u-th and the v-th positions of the permutation. The insert operator is to remove a member from the u-th position of the permutation and then insert it back at the v-th position. The reverse operator is to reverse the sequence of all members from the u-th to the v-th positions of the permutation.A common drawback of most metaheuristics is that their performance is dependent on their parameter-value settings. To overcome such a drawback, many applications use upper-level algorithms to control parameters of their solution-searching algorithms [11, 12, 14, 15, 28–31]. Some of them, e.g., [5], require more than two levels of algorithms for very complicated problems; however, most of them require only two levels. For solving JSP, there are two two-level metaheuristics acting as adaptive iterated local search algorithms [11, 12]. In each of the two-level metaheuristics, the upper-level algorithm controls the lower-level algorithm’s input parameters, while the lower-level algorithm is a local search algorithm searching for an optimal job-shop schedule.UPLA and MUPLA are the upper-level algorithms in [11, 12], respectively; they both are population-based algorithms searching in real-number search spaces. In each of them, the population is a number of the parameter-value combinations of the lower-level algorithm. In a parameter-value combination, each parameter’s value is iteratively changed by a sum of two changeable opposite-direction vectors. The first vector’s and the second vector’s directions are toward and away from, respectively, the memorized best-found value. In only MUPLA, each parameter-value combination includes a different start operation-based permutation; thus, the two-level metaheuristic of [12] has a multistart property.LOLA, the lower-level algorithm in [11], is a local search algorithm exploring in a solution space of parameterized-active schedules (i.e., hybrid schedules [16]). Its input parameters (i.e., a delay-time limit, a scheduling direction, a perturbation operator, and a neighbor operator) are controlled by UPLA, its upper-level algorithm. Because the delay-time limit (δ) is one of the input parameters controlled, UPLA then can control the solution space’s size of parameterized-active schedules. Such a control of δ follows in the successes of the two-level PSOs of [14, 15]. Other techniques of controlling δ can also be found in literature. For example, the value of δ in [10] is dependent on the number of jobs and the number of machines, while the value of δ in [17] is dependent on the algorithm’s iteration index. In addition, the PSO in [32] controls the value of δ by using the concept of self-adaptive parameter control [28].LOSAP, the lower-level algorithm in [12], is a local search algorithm searching in a probabilistic-based hybrid neighborhood structure. By a given probability, LOSAP randomly uses one from two predetermined operators to generate a neighbor solution-representing permutation. In other words, based on the given probability, LOSAP can switch between the two given operators anytime during its exploration. While the search performance of LOLA [11] is mainly based on its special solution space, that of LOSAP is mainly based on its hybrid neighborhood structure. LOSAP has multiple optional operators for its perturbation and neighbor operators. These optional operators are modified from the traditional operators by limiting the distance of v from u. For generating v in LOSAP, there are three optional distance-limit levels: [u − 4, u + 4], [u − (D/5), u + (D/5)], and [1, D].


## 3. Proposed Two-Level Metaheuristic

For solving MPMJSP, this paper proposes the two-level metaheuristic consisting of the lower- and upper-level algorithms. In this section, MPM-LOLA and MPM-UPLA represent the lower-level algorithm and the upper-level algorithm, respectively. The description of MPM-LOLA is given in Section3.1, and the description of MPM-UPLA is given in Section 3.2.


### 3.1. MPM-LOLA

MPM-LOLA, as a variant of LOLA [11] and LOSAP [12], is a local search algorithm exploring in a hybrid neighborhood structure. Similar to LOLA and LOSAP, MPM-LOLA generates its neighborhood structure by using multiple optional operators. However, there are many changes of MPM-LOLA from its older variants. Although MPM-LOLA uses the delay-time limit (δ) like LOLA does, it uses δ in different way and purpose. While LOLA uses δ to select an operation, MPM-LOLA uses δ to select an optional machine for each operation. In the remaining other parts, MPM-LOLA is more similar to LOSAP than LOLA. The major changes of MPM-LOLA from LOSAP are summarized below:(i)
While the LOSAP’s solution-decoding method generates JSP’s solutions, the MPM-LOLA’s solution-decoding method generates MPMJSP’s solutions.(ii)
MPM-LOLA is similar to LOSAP in that its optional operators are modified from the traditional operators by limiting the distance ofv from u. However, while LOSAP has only three levels of distance limit, the distance limit of MPM-LOLA is adjustable to any possible range.(iii)
Unlike LOSAP, MPM-LOLA applies the roulette-wheel method to select a neighbor operator. It also applies the roulette-wheel method to select optional operators for generating a perturbation operator.For the purpose of clarification, the description of MPM-LOLA is divided into two parts: a description of its solution-decoding method and a description of its overall procedure. The solution-decoding method is described in Section3.1.1, and the overall procedure is described in Section 3.1.2.


#### 3.1.1. Solution-Decoding Method

MPM-LOLA decodes a solution-representing permutation into a schedule by using the delay-time limit (δ) and the tiebreak criterion (TB). Note that TB is used only if there is more than one optional machine that satisfies δ. In this paper, every solution-representing permutation is in a form of the operation-based permutation [33, 34]. An operation-based permutation is a permutation of numbers 1, 2, …, n where the number i (i = 1, 2, …, n) appears ni times. Remind that n and ni denote the number of all jobs and the number of all operations of the job Ji, respectively. In the permutation, the number i in its k-th appearance represents the operation Oik. Then, a schedule is constructed by scheduling all operations one-by-one in the order given by the permutation. Each operation must be processed by its optional machine that satisfies δ and TB, and it must be started as early as this machine can. It is noticed that the use of δ in this paper is different from those in the other researches, e.g., [10, 11, 14–16]. While MPM-LOLA uses δ to select an optional machine for each operation, the other researches use δ to select an operation into the timetable.As mentioned above,δ ∈ [0, 1) and TB ∈ {lowest, highest} are used to select an optional machine for each operation. If δ = 0, each operation must be processed on its optional machine that can start processing earliest. When the value of δ is assigned larger, the maximum delay-time allowed for each operation is then longer; consequently, it may increase the number of optional machines that satisfy δ for each operation. If there is more than one optional machine that satisfies δ, then TB is required as a tie breaker. If TB is selected to be lowest, the lowest-indexed optional machine that satisfies δ is selected; otherwise, the highest-indexed optional machine that satisfies δ is selected.Algorithm1 presents the solution-decoding method used by MPM-LOLA. The algorithm uses δ and TB, as its input parameters, to transform an operation-based permutation into an MPMJSP’s solution. Note that Algorithm 1 may return a different schedule from the same operation-based permutation if the values of δ and TB are changed. Notation used in Algorithm 1 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji (i = 1, 2, …, n).(ii)
LetП denote the sequence of operations transformed from the operation-based permutation.(iii)
Let Φ denote the schedule transformed fromП.(iv)
LetOi′k′ denote the k′-th operation of the job Ji′, and it represents the as-yet-unscheduled operation that is currently in its turn to be scheduled.(v)
Letmi′k′ denote the number of all optional machines of Oi′k′.(vi)
LetEi′k′l denote the l-th optional machine of Oi′k′, where l = 1, 2, …, mi′k′.(vii)
LetE denote the chosen machine for processing Oi′k′. This machine must be chosen from all Ei′k′l (l = 1, 2, …, mi′k′).(viii)
Letδ be a real number within [0, 1) and denote the delay-time limit.(ix)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine to process Oi′k′. It is used only if there is more than one optional machine that satisfies δ. If TB = lowest, let E be the machine with the lowest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ. If TB = highest, let E be the machine with the highest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ.(x)
Letτi′k′ denote the processing time of Oi′k′.(xi)
LetσM denote the minimum of the earliest available times of all optional machines of Oi′k′.(xii)
LetσJ denote the earliest possible start time of Oi′k′ in the job Ji′. This means σJ is equal to the finished time of Oi′k′– 1. If Oi′k′ has no immediate-preceding operation, then σJ is equal to 0.(xiii)
Letσ denote the earliest possible start time of Oi′k′. It is equal to the maximum between σM and σJ.Algorithm 1: Solution-decoding method.
Step 1. Receive a δ’s value, a TB’s value, and an operation-based permutation needed to be transformed from MPM-LOLA (Algorithm 2).Step 2. Transform the operation-based permutation taken from Step 1 into П by changing the number i in its k-th appearance into the operation Oik (i = 1, 2, …, n; k = 1, 2, …, ni). For example, the operation-based permutation (3, 2, 3, 1, 1, 2) is transformed into П = (O31, O21, O32, O11, O12, O22).Step 3. Transform П into Φ by using Steps 3.1 to 3.6.Step 3.1. Let Φ ⟵ an empty schedule, and let t ⟵ 1.Step 3.2. Let Oi′k′ ⟵ the leftmost as-yet-unscheduled operation in П.Step 3.3. Find σM, σJ, and σ of Oi′k′.Step 3.4. Let E ⟵ the machine, chosen from all Ei′k′l (l = 1, 2, …, mi′k′), that can start processing not-later-than σ + δτi′k′. If there is more than one machine that can be chosen as E, then choose one of them that has the lowest l if TB = lowest; otherwise, choose one of them that has the highest l.Step 3.5. Modify Φ by assigning E to process Oi′k′. In the schedule, let E start processing Oi′k′ as early as possible.Step 3.6. If t < D, then t ⟵ t + 1 and repeat from Step 3.2. Otherwise, go to Step 4.Step 4. Return Φ as the complete schedule to MPM-LOLA (Algorithm 2).


#### 3.1.2. Procedure of MPM-LOLA

MPM-LOLA generates its neighborhood structure based on multiple optional operators. These optional operators consist ofd-swap, d-insert, d-reverse, D-swap, D-insert, and D-reverse operators. Note that D-swap, D-insert, and D-reverse are identical to the traditional swap, insert, and reverse operators, respectively. Notation and terminologies used to define the mentioned operators are given below:(i)
Letu and v be integers used to point at the two member positions in an operation-based permutation.(ii)
Letd denote a distance limit of v from u. It is used for specifying d-swap, d-insert, and d-reverse.(iii)
LetD denote the number of all members in the solution-representing permutation, which equals the number of all operations in the MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(iv)
d-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(v)
d-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vi)
d-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vii)
D-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.(viii)
D-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u and v be two different integers randomly selected from 1 to D.(ix)
D-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.Before an execution, eight MPM-LOLA’s input parameters must be assigned values. The first input parameter, denoted byP, is the start operation-based permutation. The remaining seven input parameters consist of two parameters for specifying a perturbation operator, three parameters for generating its neighbor operators, and two parameters for selecting an optional machine. In MPM-LOLA, the perturbation operator is to randomly use one from D-swap, D-insert, and D-reverse on the start operation-based permutation n times (remind that n denotes the number of all jobs). In each of these n random selections, the roulette-wheel technique is applied to select one from D-swap, D-insert, and D-reverse. The probabilities of selecting D-swap and D-insert in the roulette wheel are the second and the third input parameters of MPM-LOLA, respectively. Consequently, the probability of selecting D-reverse is unity subtracted by the sum of the probabilities of selecting D-swap and D-insert.The fourth to the sixth input parameters are used to generate MPM-LOLA’s neighbor operators (i.e.,d-swap, d-insert, and d-reverse). The fourth input parameter, denoted by d, is the distance limit of v from u for specifying d-swap, d-insert, and d-reverse. Then, MPM-LOLA uses the roulette-wheel technique to randomly select one from d-swap, d-insert, and d-reverse to generate a neighbor solution-representing permutation. In the roulette wheel, the probabilities of selecting d-swap and d-insert are the fifth and the sixth input parameters, respectively. The probability of selecting d-reverse is thus unity subtracted by the sum of the probabilities of selecting d-swap and d-insert.The delay-time limit (δ) and the tiebreak criterion (TB) are the MPM-LOLA’s seventh and eighth input parameters, respectively. These two input parameters are used to select an optional machine for each operation in constructing a schedule. Thus, instead of using δ and TB by MPM-LOLA itself, MPM-LOLA transfers the values of δ and TB into its solution-decoding method (Algorithm 1).The overall procedure of MPM-LOLA is given in Algorithm2. Notation used in Algorithm 2 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(ii)
Letd denote the distance limit of v from u in the operation-based permutation for specifying d-swap, d-insert, and d-reverse.(iii)
LetρS and ρI, which are real numbers within [0, 1), denote the probabilities of selecting D-swap and D-insert, respectively. Thus, the probability of selecting D-reverse is 1 – ρS – ρI.(iv)
LetρNS and ρNI, which are real numbers within [0, 1), denote the probabilities of selecting d-swap and d-insert, respectively. Thus, the probability of selecting d-reverse is 1 – ρNS – ρNI.(v)
Letδ, which is a real number within [0, 1), denote the delay-time limit for selecting an optional machine for each operation.(vi)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine for each operation.(vii)
LetP denote the start operation-based permutation.(viii)
LetP0 denote the current best-found operation-based permutation. An initial P0 is generated from P via the perturbation operator.(ix)
LetS0, which is decoded from P0, denote the current best-found schedule. In addition, Makespan(S0) stands for the makespan of S0.(x)
LetP1 denote the current neighbor operation-based permutation.(xi)
LetS1, which is decoded from P1, denote the current neighbor schedule. In addition, Makespan(S1) stands for the makespan of S1.Algorithm 2: MPM-LOLA’s procedure.
Step 1. Receive values of its eight input parameters (i.e., P, ρS, ρI, d, ρNS, ρNI, δ, and TB) from MPM-UPLA (Algorithm 3).Step 2. Generate P0 from P by using Steps 2.1 to 2.4.Step 2.1. Let r ⟵ 1.Step 2.2. Randomly generate p ∼ U[0, 1).Step 2.3. Modify P by using D-swap if p < ρS, D-insert if ρS ≤ p < ρS + ρI, and D-reverse otherwise.Step 2.4. If r < n, let r ⟵ r + 1 and repeat from Step 2.2. Otherwise, let P0 ⟵ P and go to Step 3.Step 3. Execute Algorithm 1, with the taken values of δ and TB, for transforming P0 into S0.Step 4. Find a local optimal schedule by using Steps 4.1 to 4.5.Step 4.1. Let tL ⟵ 0.Step 4.2. Randomly generate p ∼ U[0, 1).Step 4.3. Generate P1 from P0 by using d-swap if p < ρNS, d-insert if ρNS ≤ p < ρNS + ρNI, and d-reverse otherwise.Step 4.4. Execute Algorithm 1, with the taken values of δ and TB, for transforming P1 into S1.Step 4.5. Update P0, S0, and tL by using Steps 4.5.1 to 4.5.3.Step 4.5.1. If Makespan(S1) < Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.1.Step 4.5.2. If Makespan(S1) = Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.2.Step 4.5.3. If Makespan(S1) > Makespan(S0), then let tL ⟵ tL + 1. If tL < D2, repeat from Step 4.2; otherwise, go to Step 5.Step 5. Return P0 and S0 as the final (best-found) operation-based permutation and the final (best-found) schedule, respectively, to MPM-UPLA (Algorithm 3).


### 3.2. MPM-UPLA

MPM-UPLA is an upper-level algorithm of the proposed two-level metaheuristic. It uses the same framework of the upper-level algorithms of [11, 12]. MPM-UPLA is thus a population-based search algorithm that acts as a parameter controller. It evolves the MPM-LOLA’s input-parameter values, so that MPM-LOLA can return its best performance on every single MPMJSP instance. At the t-th iteration, the MPM-UPLA’s population consists of N combinations of the MPM-LOLA’s input-parameter values, i.e., C1(t), C2(t), …, CN(t). In short, let a parameter-value combination stand for a combination of the MPM-LOLA’s input-parameter values. Let Cgt≡c1gt,c2gt,…,c9gt denote the g-th parameter-value combination (where g  = 1, 2, …, N) in the population at the t-th iteration. It represents the value combination of the MPM-LOLA’s input parameters, i.e., P, ρS, ρI, d, ρNS, ρNI, and TB.The delay-time limit,δ, is an important MPM-LOLA’s input parameter controlled by MPM-UPLA. However, the value of δ is not assigned as a member in Cgt, but it is controlled by the MPM-UPLA’s iteration index, t. At the first MPM-UPLA’s iteration (t = 1), the value of δ is set to be 0.0 for MPM-LOLA. For every next 50 MPM-UPLA’s iterations, the value of δ is increased by 0.2 for MPM-LOLA. This setting of δ was based on the result of a preliminary study of this research. It found that the control of δ using the MPM-UPLA’s iteration index usually performs better than the control of δ using Cgt.The transformations from theCgt’s members into MPM-LOLA’s parameter values are described below:(i)
Letc1gt represent P. In other words, P is directly equal to c1gt in the transformation.(ii)
Letc2gt, c3gt, and c4gt ∈ ℝ be used together to determine the values of ρS and ρI. Their transformations are given in (1) and (2).(1)ρS=max0,c2gtmax0,c2gt+max0,c3gt+max0,c4gt,(2)ρI=max0,c3gtmax0,c2gt+max0,c3gt+max0,c4gt.(iii)
Letc5gt ∈ ℝ be used to determine the value of d. In its transformation, let d be equal to the rounded integer from 1 + Dc5gt, where D is the number of all operations in the MPMJSP instance. After that, reassign d = 1 if d < 1, and reassign d = D if d > D.(iv)
Letc6gt, c7gt, and c8gt ∈ ℝ be used together to determine the values of ρNS and ρNI. Their transformations are given in (3) and (4).(3)ρNS=max0,c6gtmax0,c6gt+max0,c7gt+max0,c8gt,(4)ρNI=max0,c7gtmax0,c6gt+max0,c7gt+max0,c8gt.(v)
Letc9gt ∈ ℝ be used to determine the value of TB. In its transformation, let TB = lowest if c9gt < 0.5, and let TB = highest if c9gt ≥ 0.5.The overall procedure of MPM-UPLA is given in Algorithm3. Notation used in Algorithm 3 is defined below:(i)
LetN denote the number of all parameter-value combinations in the MPM-UPLA’s population.(ii)
LetCgt≡c1gt,c2gt,…,c9gt denote the g-th parameter-value combination (where g  = 1, 2, …, N) in the MPM-UPLA’s population at the t-th iteration.(iii)
LetScoreCgt denote the performance score of Cgt. Note that the lower the performance score, the better the performance.(iv)
After executing MPM-LOLA with the parameter values given byCgt, let its final (best-found) operation-based permutation and final (best-found) schedule be denoted by Pfg(t) and Sfg(t), respectively.(v)
LetMakespan(Sfg(t)) denote the makespan of Sfg(t).(vi)
LetCbest ≡ (c1best, c2best, …, c9best) denote the best parameter-value combination ever found by the population. In addition, let Score(Cbest) denote the performance score of Cbest.(vii)
LetSbest denote the best schedule ever found by the population.Algorithm 3: MPM-UPLA’s procedure.
Step 1. Receive a value of N and a stopping criterion from a user. Let t ⟵ 1, δ ⟵ 0.0, and Score(Cbest) ⟵ + ∞.Step 2. Generate Cgt≡c1gt,c2gt,…,c9gt, where g  = 1, 2, …, N, by using Steps 2.1 to 2.4.Step 2.1. Let g ⟵ 1.Step 2.2. Randomly generate c1gt from any possible operation-based permutation.Step 2.3. Randomly generate c2gt,c3gt,…,c9gt∼U0,1.Step 2.4. If g < N, let g ⟵ g + 1 and repeat from Step 2.2. Otherwise, go to Step 3.Step 3. Evaluate ScoreCgt, and update Cbest and Sbest by using Steps 3.1 to 3.6.Step 3.1. Let g ⟵ 1.Step 3.2. Transform Cgt into the values of P, ρS, ρI, d, ρNS, ρNI, and TB.Step 3.3. Execute MPM-LOLA (Algorithm 2) with the last-updated values of P, ρS, ρI, d, ρNS, ρNI, TB, and δ in order to receive Pfg(t) and Sfg(t).Step 3.4. Let ScoreCgt⟵MakespanSfgt.Step 3.5. If ScoreCgt≤ScoreCbest, then let Cbest⟵Cgt, ScoreCbest⟵ScoreCgt, and Sbest⟵Sfgt.Step 3.6. If g<N, let g⟵g+1 and repeat from Step 3.2. Otherwise, go to Step 4.Step 4. UpdateCgt+1 , where g=1,2,…,N, by using Steps 4.1 to 4.5.Step 4.1. Let g⟵1.Step 4.2. Let c1gt+1⟵Pfgt.Step 4.3. If (t + 1) mod 50 = 0, let δ ⟵ δ + 0.2. After that, reassign δ ⟵ 0.999 if δ ≥ 1.0.Step 4.4. If t+1 mod 50 = 0, randomly generate c2gt+1,c3gt+1,…,c9gt+1∼U0,1. Otherwise, generate cqgt+1, where q=2,3,…,9, by using the below equation. Let u1 and u2∼U0,1.cqgt+1=cqgt+0.05u1−0.01u2ifcqgt<cqbest,cqgt−0.05u1+0.01u2ifcqgt>cqbest,cqgt+0.01u1−0.01u2ifcqgt=cqbest.Step 4.5. If g<N, then let g⟵g+1 and repeat from Step 4.2. Otherwise, go to Step 5.Step 5. If the stopping criterion is not met, then let t ⟵ t + 1 and repeat from Step 2. Otherwise, return Sbest as the final result to the user.


## 3.1. MPM-LOLA

MPM-LOLA, as a variant of LOLA [11] and LOSAP [12], is a local search algorithm exploring in a hybrid neighborhood structure. Similar to LOLA and LOSAP, MPM-LOLA generates its neighborhood structure by using multiple optional operators. However, there are many changes of MPM-LOLA from its older variants. Although MPM-LOLA uses the delay-time limit (δ) like LOLA does, it uses δ in different way and purpose. While LOLA uses δ to select an operation, MPM-LOLA uses δ to select an optional machine for each operation. In the remaining other parts, MPM-LOLA is more similar to LOSAP than LOLA. The major changes of MPM-LOLA from LOSAP are summarized below:(i)
While the LOSAP’s solution-decoding method generates JSP’s solutions, the MPM-LOLA’s solution-decoding method generates MPMJSP’s solutions.(ii)
MPM-LOLA is similar to LOSAP in that its optional operators are modified from the traditional operators by limiting the distance ofv from u. However, while LOSAP has only three levels of distance limit, the distance limit of MPM-LOLA is adjustable to any possible range.(iii)
Unlike LOSAP, MPM-LOLA applies the roulette-wheel method to select a neighbor operator. It also applies the roulette-wheel method to select optional operators for generating a perturbation operator.For the purpose of clarification, the description of MPM-LOLA is divided into two parts: a description of its solution-decoding method and a description of its overall procedure. The solution-decoding method is described in Section3.1.1, and the overall procedure is described in Section 3.1.2.


### 3.1.1. Solution-Decoding Method

MPM-LOLA decodes a solution-representing permutation into a schedule by using the delay-time limit (δ) and the tiebreak criterion (TB). Note that TB is used only if there is more than one optional machine that satisfies δ. In this paper, every solution-representing permutation is in a form of the operation-based permutation [33, 34]. An operation-based permutation is a permutation of numbers 1, 2, …, n where the number i (i = 1, 2, …, n) appears ni times. Remind that n and ni denote the number of all jobs and the number of all operations of the job Ji, respectively. In the permutation, the number i in its k-th appearance represents the operation Oik. Then, a schedule is constructed by scheduling all operations one-by-one in the order given by the permutation. Each operation must be processed by its optional machine that satisfies δ and TB, and it must be started as early as this machine can. It is noticed that the use of δ in this paper is different from those in the other researches, e.g., [10, 11, 14–16]. While MPM-LOLA uses δ to select an optional machine for each operation, the other researches use δ to select an operation into the timetable.As mentioned above,δ ∈ [0, 1) and TB ∈ {lowest, highest} are used to select an optional machine for each operation. If δ = 0, each operation must be processed on its optional machine that can start processing earliest. When the value of δ is assigned larger, the maximum delay-time allowed for each operation is then longer; consequently, it may increase the number of optional machines that satisfy δ for each operation. If there is more than one optional machine that satisfies δ, then TB is required as a tie breaker. If TB is selected to be lowest, the lowest-indexed optional machine that satisfies δ is selected; otherwise, the highest-indexed optional machine that satisfies δ is selected.Algorithm1 presents the solution-decoding method used by MPM-LOLA. The algorithm uses δ and TB, as its input parameters, to transform an operation-based permutation into an MPMJSP’s solution. Note that Algorithm 1 may return a different schedule from the same operation-based permutation if the values of δ and TB are changed. Notation used in Algorithm 1 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji (i = 1, 2, …, n).(ii)
LetП denote the sequence of operations transformed from the operation-based permutation.(iii)
Let Φ denote the schedule transformed fromП.(iv)
LetOi′k′ denote the k′-th operation of the job Ji′, and it represents the as-yet-unscheduled operation that is currently in its turn to be scheduled.(v)
Letmi′k′ denote the number of all optional machines of Oi′k′.(vi)
LetEi′k′l denote the l-th optional machine of Oi′k′, where l = 1, 2, …, mi′k′.(vii)
LetE denote the chosen machine for processing Oi′k′. This machine must be chosen from all Ei′k′l (l = 1, 2, …, mi′k′).(viii)
Letδ be a real number within [0, 1) and denote the delay-time limit.(ix)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine to process Oi′k′. It is used only if there is more than one optional machine that satisfies δ. If TB = lowest, let E be the machine with the lowest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ. If TB = highest, let E be the machine with the highest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ.(x)
Letτi′k′ denote the processing time of Oi′k′.(xi)
LetσM denote the minimum of the earliest available times of all optional machines of Oi′k′.(xii)
LetσJ denote the earliest possible start time of Oi′k′ in the job Ji′. This means σJ is equal to the finished time of Oi′k′– 1. If Oi′k′ has no immediate-preceding operation, then σJ is equal to 0.(xiii)
Letσ denote the earliest possible start time of Oi′k′. It is equal to the maximum between σM and σJ.Algorithm 1: Solution-decoding method.
Step 1. Receive a δ’s value, a TB’s value, and an operation-based permutation needed to be transformed from MPM-LOLA (Algorithm 2).Step 2. Transform the operation-based permutation taken from Step 1 into П by changing the number i in its k-th appearance into the operation Oik (i = 1, 2, …, n; k = 1, 2, …, ni). For example, the operation-based permutation (3, 2, 3, 1, 1, 2) is transformed into П = (O31, O21, O32, O11, O12, O22).Step 3. Transform П into Φ by using Steps 3.1 to 3.6.Step 3.1. Let Φ ⟵ an empty schedule, and let t ⟵ 1.Step 3.2. Let Oi′k′ ⟵ the leftmost as-yet-unscheduled operation in П.Step 3.3. Find σM, σJ, and σ of Oi′k′.Step 3.4. Let E ⟵ the machine, chosen from all Ei′k′l (l = 1, 2, …, mi′k′), that can start processing not-later-than σ + δτi′k′. If there is more than one machine that can be chosen as E, then choose one of them that has the lowest l if TB = lowest; otherwise, choose one of them that has the highest l.Step 3.5. Modify Φ by assigning E to process Oi′k′. In the schedule, let E start processing Oi′k′ as early as possible.Step 3.6. If t < D, then t ⟵ t + 1 and repeat from Step 3.2. Otherwise, go to Step 4.Step 4. Return Φ as the complete schedule to MPM-LOLA (Algorithm 2).


### 3.1.2. Procedure of MPM-LOLA

MPM-LOLA generates its neighborhood structure based on multiple optional operators. These optional operators consist ofd-swap, d-insert, d-reverse, D-swap, D-insert, and D-reverse operators. Note that D-swap, D-insert, and D-reverse are identical to the traditional swap, insert, and reverse operators, respectively. Notation and terminologies used to define the mentioned operators are given below:(i)
Letu and v be integers used to point at the two member positions in an operation-based permutation.(ii)
Letd denote a distance limit of v from u. It is used for specifying d-swap, d-insert, and d-reverse.(iii)
LetD denote the number of all members in the solution-representing permutation, which equals the number of all operations in the MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(iv)
d-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(v)
d-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vi)
d-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vii)
D-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.(viii)
D-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u and v be two different integers randomly selected from 1 to D.(ix)
D-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.Before an execution, eight MPM-LOLA’s input parameters must be assigned values. The first input parameter, denoted byP, is the start operation-based permutation. The remaining seven input parameters consist of two parameters for specifying a perturbation operator, three parameters for generating its neighbor operators, and two parameters for selecting an optional machine. In MPM-LOLA, the perturbation operator is to randomly use one from D-swap, D-insert, and D-reverse on the start operation-based permutation n times (remind that n denotes the number of all jobs). In each of these n random selections, the roulette-wheel technique is applied to select one from D-swap, D-insert, and D-reverse. The probabilities of selecting D-swap and D-insert in the roulette wheel are the second and the third input parameters of MPM-LOLA, respectively. Consequently, the probability of selecting D-reverse is unity subtracted by the sum of the probabilities of selecting D-swap and D-insert.The fourth to the sixth input parameters are used to generate MPM-LOLA’s neighbor operators (i.e.,d-swap, d-insert, and d-reverse). The fourth input parameter, denoted by d, is the distance limit of v from u for specifying d-swap, d-insert, and d-reverse. Then, MPM-LOLA uses the roulette-wheel technique to randomly select one from d-swap, d-insert, and d-reverse to generate a neighbor solution-representing permutation. In the roulette wheel, the probabilities of selecting d-swap and d-insert are the fifth and the sixth input parameters, respectively. The probability of selecting d-reverse is thus unity subtracted by the sum of the probabilities of selecting d-swap and d-insert.The delay-time limit (δ) and the tiebreak criterion (TB) are the MPM-LOLA’s seventh and eighth input parameters, respectively. These two input parameters are used to select an optional machine for each operation in constructing a schedule. Thus, instead of using δ and TB by MPM-LOLA itself, MPM-LOLA transfers the values of δ and TB into its solution-decoding method (Algorithm 1).The overall procedure of MPM-LOLA is given in Algorithm2. Notation used in Algorithm 2 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(ii)
Letd denote the distance limit of v from u in the operation-based permutation for specifying d-swap, d-insert, and d-reverse.(iii)
LetρS and ρI, which are real numbers within [0, 1), denote the probabilities of selecting D-swap and D-insert, respectively. Thus, the probability of selecting D-reverse is 1 – ρS – ρI.(iv)
LetρNS and ρNI, which are real numbers within [0, 1), denote the probabilities of selecting d-swap and d-insert, respectively. Thus, the probability of selecting d-reverse is 1 – ρNS – ρNI.(v)
Letδ, which is a real number within [0, 1), denote the delay-time limit for selecting an optional machine for each operation.(vi)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine for each operation.(vii)
LetP denote the start operation-based permutation.(viii)
LetP0 denote the current best-found operation-based permutation. An initial P0 is generated from P via the perturbation operator.(ix)
LetS0, which is decoded from P0, denote the current best-found schedule. In addition, Makespan(S0) stands for the makespan of S0.(x)
LetP1 denote the current neighbor operation-based permutation.(xi)
LetS1, which is decoded from P1, denote the current neighbor schedule. In addition, Makespan(S1) stands for the makespan of S1.Algorithm 2: MPM-LOLA’s procedure.
Step 1. Receive values of its eight input parameters (i.e., P, ρS, ρI, d, ρNS, ρNI, δ, and TB) from MPM-UPLA (Algorithm 3).Step 2. Generate P0 from P by using Steps 2.1 to 2.4.Step 2.1. Let r ⟵ 1.Step 2.2. Randomly generate p ∼ U[0, 1).Step 2.3. Modify P by using D-swap if p < ρS, D-insert if ρS ≤ p < ρS + ρI, and D-reverse otherwise.Step 2.4. If r < n, let r ⟵ r + 1 and repeat from Step 2.2. Otherwise, let P0 ⟵ P and go to Step 3.Step 3. Execute Algorithm 1, with the taken values of δ and TB, for transforming P0 into S0.Step 4. Find a local optimal schedule by using Steps 4.1 to 4.5.Step 4.1. Let tL ⟵ 0.Step 4.2. Randomly generate p ∼ U[0, 1).Step 4.3. Generate P1 from P0 by using d-swap if p < ρNS, d-insert if ρNS ≤ p < ρNS + ρNI, and d-reverse otherwise.Step 4.4. Execute Algorithm 1, with the taken values of δ and TB, for transforming P1 into S1.Step 4.5. Update P0, S0, and tL by using Steps 4.5.1 to 4.5.3.Step 4.5.1. If Makespan(S1) < Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.1.Step 4.5.2. If Makespan(S1) = Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.2.Step 4.5.3. If Makespan(S1) > Makespan(S0), then let tL ⟵ tL + 1. If tL < D2, repeat from Step 4.2; otherwise, go to Step 5.Step 5. Return P0 and S0 as the final (best-found) operation-based permutation and the final (best-found) schedule, respectively, to MPM-UPLA (Algorithm 3).


## 3.1.1. Solution-Decoding Method

MPM-LOLA decodes a solution-representing permutation into a schedule by using the delay-time limit (δ) and the tiebreak criterion (TB). Note that TB is used only if there is more than one optional machine that satisfies δ. In this paper, every solution-representing permutation is in a form of the operation-based permutation [33, 34]. An operation-based permutation is a permutation of numbers 1, 2, …, n where the number i (i = 1, 2, …, n) appears ni times. Remind that n and ni denote the number of all jobs and the number of all operations of the job Ji, respectively. In the permutation, the number i in its k-th appearance represents the operation Oik. Then, a schedule is constructed by scheduling all operations one-by-one in the order given by the permutation. Each operation must be processed by its optional machine that satisfies δ and TB, and it must be started as early as this machine can. It is noticed that the use of δ in this paper is different from those in the other researches, e.g., [10, 11, 14–16]. While MPM-LOLA uses δ to select an optional machine for each operation, the other researches use δ to select an operation into the timetable.As mentioned above,δ ∈ [0, 1) and TB ∈ {lowest, highest} are used to select an optional machine for each operation. If δ = 0, each operation must be processed on its optional machine that can start processing earliest. When the value of δ is assigned larger, the maximum delay-time allowed for each operation is then longer; consequently, it may increase the number of optional machines that satisfy δ for each operation. If there is more than one optional machine that satisfies δ, then TB is required as a tie breaker. If TB is selected to be lowest, the lowest-indexed optional machine that satisfies δ is selected; otherwise, the highest-indexed optional machine that satisfies δ is selected.Algorithm1 presents the solution-decoding method used by MPM-LOLA. The algorithm uses δ and TB, as its input parameters, to transform an operation-based permutation into an MPMJSP’s solution. Note that Algorithm 1 may return a different schedule from the same operation-based permutation if the values of δ and TB are changed. Notation used in Algorithm 1 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji (i = 1, 2, …, n).(ii)
LetП denote the sequence of operations transformed from the operation-based permutation.(iii)
Let Φ denote the schedule transformed fromП.(iv)
LetOi′k′ denote the k′-th operation of the job Ji′, and it represents the as-yet-unscheduled operation that is currently in its turn to be scheduled.(v)
Letmi′k′ denote the number of all optional machines of Oi′k′.(vi)
LetEi′k′l denote the l-th optional machine of Oi′k′, where l = 1, 2, …, mi′k′.(vii)
LetE denote the chosen machine for processing Oi′k′. This machine must be chosen from all Ei′k′l (l = 1, 2, …, mi′k′).(viii)
Letδ be a real number within [0, 1) and denote the delay-time limit.(ix)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine to process Oi′k′. It is used only if there is more than one optional machine that satisfies δ. If TB = lowest, let E be the machine with the lowest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ. If TB = highest, let E be the machine with the highest l from all Ei′k′l (where l = 1, 2, …, mi′k′) that satisfy δ.(x)
Letτi′k′ denote the processing time of Oi′k′.(xi)
LetσM denote the minimum of the earliest available times of all optional machines of Oi′k′.(xii)
LetσJ denote the earliest possible start time of Oi′k′ in the job Ji′. This means σJ is equal to the finished time of Oi′k′– 1. If Oi′k′ has no immediate-preceding operation, then σJ is equal to 0.(xiii)
Letσ denote the earliest possible start time of Oi′k′. It is equal to the maximum between σM and σJ.Algorithm 1: Solution-decoding method.
Step 1. Receive a δ’s value, a TB’s value, and an operation-based permutation needed to be transformed from MPM-LOLA (Algorithm 2).Step 2. Transform the operation-based permutation taken from Step 1 into П by changing the number i in its k-th appearance into the operation Oik (i = 1, 2, …, n; k = 1, 2, …, ni). For example, the operation-based permutation (3, 2, 3, 1, 1, 2) is transformed into П = (O31, O21, O32, O11, O12, O22).Step 3. Transform П into Φ by using Steps 3.1 to 3.6.Step 3.1. Let Φ ⟵ an empty schedule, and let t ⟵ 1.Step 3.2. Let Oi′k′ ⟵ the leftmost as-yet-unscheduled operation in П.Step 3.3. Find σM, σJ, and σ of Oi′k′.Step 3.4. Let E ⟵ the machine, chosen from all Ei′k′l (l = 1, 2, …, mi′k′), that can start processing not-later-than σ + δτi′k′. If there is more than one machine that can be chosen as E, then choose one of them that has the lowest l if TB = lowest; otherwise, choose one of them that has the highest l.Step 3.5. Modify Φ by assigning E to process Oi′k′. In the schedule, let E start processing Oi′k′ as early as possible.Step 3.6. If t < D, then t ⟵ t + 1 and repeat from Step 3.2. Otherwise, go to Step 4.Step 4. Return Φ as the complete schedule to MPM-LOLA (Algorithm 2).


## 3.1.2. Procedure of MPM-LOLA

MPM-LOLA generates its neighborhood structure based on multiple optional operators. These optional operators consist ofd-swap, d-insert, d-reverse, D-swap, D-insert, and D-reverse operators. Note that D-swap, D-insert, and D-reverse are identical to the traditional swap, insert, and reverse operators, respectively. Notation and terminologies used to define the mentioned operators are given below:(i)
Letu and v be integers used to point at the two member positions in an operation-based permutation.(ii)
Letd denote a distance limit of v from u. It is used for specifying d-swap, d-insert, and d-reverse.(iii)
LetD denote the number of all members in the solution-representing permutation, which equals the number of all operations in the MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(iv)
d-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(v)
d-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vi)
d-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u be randomly selected from 1 to D. Then, let v be randomly selected from max(1, u – d) to min(u + d, D) except u.(vii)
D-swap is to swap two members in the u-th and the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.(viii)
D-insert is to remove a member from the u-th position in the permutation and then insert it into the v-th position. Let u and v be two different integers randomly selected from 1 to D.(ix)
D-reverse is to reverse the positions of all members from the u-th to the v-th positions in the permutation. Let u and v be two different integers randomly selected from 1 to D.Before an execution, eight MPM-LOLA’s input parameters must be assigned values. The first input parameter, denoted byP, is the start operation-based permutation. The remaining seven input parameters consist of two parameters for specifying a perturbation operator, three parameters for generating its neighbor operators, and two parameters for selecting an optional machine. In MPM-LOLA, the perturbation operator is to randomly use one from D-swap, D-insert, and D-reverse on the start operation-based permutation n times (remind that n denotes the number of all jobs). In each of these n random selections, the roulette-wheel technique is applied to select one from D-swap, D-insert, and D-reverse. The probabilities of selecting D-swap and D-insert in the roulette wheel are the second and the third input parameters of MPM-LOLA, respectively. Consequently, the probability of selecting D-reverse is unity subtracted by the sum of the probabilities of selecting D-swap and D-insert.The fourth to the sixth input parameters are used to generate MPM-LOLA’s neighbor operators (i.e.,d-swap, d-insert, and d-reverse). The fourth input parameter, denoted by d, is the distance limit of v from u for specifying d-swap, d-insert, and d-reverse. Then, MPM-LOLA uses the roulette-wheel technique to randomly select one from d-swap, d-insert, and d-reverse to generate a neighbor solution-representing permutation. In the roulette wheel, the probabilities of selecting d-swap and d-insert are the fifth and the sixth input parameters, respectively. The probability of selecting d-reverse is thus unity subtracted by the sum of the probabilities of selecting d-swap and d-insert.The delay-time limit (δ) and the tiebreak criterion (TB) are the MPM-LOLA’s seventh and eighth input parameters, respectively. These two input parameters are used to select an optional machine for each operation in constructing a schedule. Thus, instead of using δ and TB by MPM-LOLA itself, MPM-LOLA transfers the values of δ and TB into its solution-decoding method (Algorithm 1).The overall procedure of MPM-LOLA is given in Algorithm2. Notation used in Algorithm 2 is defined below:(i)
LetD denote the number of all operations in the being-solved MPMJSP instance. Thus, D = n1 + n2 + … + nn, where ni is the number of all operations of the job Ji.(ii)
Letd denote the distance limit of v from u in the operation-based permutation for specifying d-swap, d-insert, and d-reverse.(iii)
LetρS and ρI, which are real numbers within [0, 1), denote the probabilities of selecting D-swap and D-insert, respectively. Thus, the probability of selecting D-reverse is 1 – ρS – ρI.(iv)
LetρNS and ρNI, which are real numbers within [0, 1), denote the probabilities of selecting d-swap and d-insert, respectively. Thus, the probability of selecting d-reverse is 1 – ρNS – ρNI.(v)
Letδ, which is a real number within [0, 1), denote the delay-time limit for selecting an optional machine for each operation.(vi)
LetTB ∈ {lowest, highest} denote the tiebreak criterion for selecting an optional machine for each operation.(vii)
LetP denote the start operation-based permutation.(viii)
LetP0 denote the current best-found operation-based permutation. An initial P0 is generated from P via the perturbation operator.(ix)
LetS0, which is decoded from P0, denote the current best-found schedule. In addition, Makespan(S0) stands for the makespan of S0.(x)
LetP1 denote the current neighbor operation-based permutation.(xi)
LetS1, which is decoded from P1, denote the current neighbor schedule. In addition, Makespan(S1) stands for the makespan of S1.Algorithm 2: MPM-LOLA’s procedure.
Step 1. Receive values of its eight input parameters (i.e., P, ρS, ρI, d, ρNS, ρNI, δ, and TB) from MPM-UPLA (Algorithm 3).Step 2. Generate P0 from P by using Steps 2.1 to 2.4.Step 2.1. Let r ⟵ 1.Step 2.2. Randomly generate p ∼ U[0, 1).Step 2.3. Modify P by using D-swap if p < ρS, D-insert if ρS ≤ p < ρS + ρI, and D-reverse otherwise.Step 2.4. If r < n, let r ⟵ r + 1 and repeat from Step 2.2. Otherwise, let P0 ⟵ P and go to Step 3.Step 3. Execute Algorithm 1, with the taken values of δ and TB, for transforming P0 into S0.Step 4. Find a local optimal schedule by using Steps 4.1 to 4.5.Step 4.1. Let tL ⟵ 0.Step 4.2. Randomly generate p ∼ U[0, 1).Step 4.3. Generate P1 from P0 by using d-swap if p < ρNS, d-insert if ρNS ≤ p < ρNS + ρNI, and d-reverse otherwise.Step 4.4. Execute Algorithm 1, with the taken values of δ and TB, for transforming P1 into S1.Step 4.5. Update P0, S0, and tL by using Steps 4.5.1 to 4.5.3.Step 4.5.1. If Makespan(S1) < Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.1.Step 4.5.2. If Makespan(S1) = Makespan(S0), then let P0 ⟵ P1 and S0 ⟵ S1, and repeat from Step 4.2.Step 4.5.3. If Makespan(S1) > Makespan(S0), then let tL ⟵ tL + 1. If tL < D2, repeat from Step 4.2; otherwise, go to Step 5.Step 5. Return P0 and S0 as the final (best-found) operation-based permutation and the final (best-found) schedule, respectively, to MPM-UPLA (Algorithm 3).


## 3.2. MPM-UPLA

MPM-UPLA is an upper-level algorithm of the proposed two-level metaheuristic. It uses the same framework of the upper-level algorithms of [11, 12]. MPM-UPLA is thus a population-based search algorithm that acts as a parameter controller. It evolves the MPM-LOLA’s input-parameter values, so that MPM-LOLA can return its best performance on every single MPMJSP instance. At the t-th iteration, the MPM-UPLA’s population consists of N combinations of the MPM-LOLA’s input-parameter values, i.e., C1(t), C2(t), …, CN(t). In short, let a parameter-value combination stand for a combination of the MPM-LOLA’s input-parameter values. Let Cgt≡c1gt,c2gt,…,c9gt denote the g-th parameter-value combination (where g  = 1, 2, …, N) in the population at the t-th iteration. It represents the value combination of the MPM-LOLA’s input parameters, i.e., P, ρS, ρI, d, ρNS, ρNI, and TB.The delay-time limit,δ, is an important MPM-LOLA’s input parameter controlled by MPM-UPLA. However, the value of δ is not assigned as a member in Cgt, but it is controlled by the MPM-UPLA’s iteration index, t. At the first MPM-UPLA’s iteration (t = 1), the value of δ is set to be 0.0 for MPM-LOLA. For every next 50 MPM-UPLA’s iterations, the value of δ is increased by 0.2 for MPM-LOLA. This setting of δ was based on the result of a preliminary study of this research. It found that the control of δ using the MPM-UPLA’s iteration index usually performs better than the control of δ using Cgt.The transformations from theCgt’s members into MPM-LOLA’s parameter values are described below:(i)
Letc1gt represent P. In other words, P is directly equal to c1gt in the transformation.(ii)
Letc2gt, c3gt, and c4gt ∈ ℝ be used together to determine the values of ρS and ρI. Their transformations are given in (1) and (2).(1)ρS=max0,c2gtmax0,c2gt+max0,c3gt+max0,c4gt,(2)ρI=max0,c3gtmax0,c2gt+max0,c3gt+max0,c4gt.(iii)
Letc5gt ∈ ℝ be used to determine the value of d. In its transformation, let d be equal to the rounded integer from 1 + Dc5gt, where D is the number of all operations in the MPMJSP instance. After that, reassign d = 1 if d < 1, and reassign d = D if d > D.(iv)
Letc6gt, c7gt, and c8gt ∈ ℝ be used together to determine the values of ρNS and ρNI. Their transformations are given in (3) and (4).(3)ρNS=max0,c6gtmax0,c6gt+max0,c7gt+max0,c8gt,(4)ρNI=max0,c7gtmax0,c6gt+max0,c7gt+max0,c8gt.(v)
Letc9gt ∈ ℝ be used to determine the value of TB. In its transformation, let TB = lowest if c9gt < 0.5, and let TB = highest if c9gt ≥ 0.5.The overall procedure of MPM-UPLA is given in Algorithm3. Notation used in Algorithm 3 is defined below:(i)
LetN denote the number of all parameter-value combinations in the MPM-UPLA’s population.(ii)
LetCgt≡c1gt,c2gt,…,c9gt denote the g-th parameter-value combination (where g  = 1, 2, …, N) in the MPM-UPLA’s population at the t-th iteration.(iii)
LetScoreCgt denote the performance score of Cgt. Note that the lower the performance score, the better the performance.(iv)
After executing MPM-LOLA with the parameter values given byCgt, let its final (best-found) operation-based permutation and final (best-found) schedule be denoted by Pfg(t) and Sfg(t), respectively.(v)
LetMakespan(Sfg(t)) denote the makespan of Sfg(t).(vi)
LetCbest ≡ (c1best, c2best, …, c9best) denote the best parameter-value combination ever found by the population. In addition, let Score(Cbest) denote the performance score of Cbest.(vii)
LetSbest denote the best schedule ever found by the population.Algorithm 3: MPM-UPLA’s procedure.
Step 1. Receive a value of N and a stopping criterion from a user. Let t ⟵ 1, δ ⟵ 0.0, and Score(Cbest) ⟵ + ∞.Step 2. Generate Cgt≡c1gt,c2gt,…,c9gt, where g  = 1, 2, …, N, by using Steps 2.1 to 2.4.Step 2.1. Let g ⟵ 1.Step 2.2. Randomly generate c1gt from any possible operation-based permutation.Step 2.3. Randomly generate c2gt,c3gt,…,c9gt∼U0,1.Step 2.4. If g < N, let g ⟵ g + 1 and repeat from Step 2.2. Otherwise, go to Step 3.Step 3. Evaluate ScoreCgt, and update Cbest and Sbest by using Steps 3.1 to 3.6.Step 3.1. Let g ⟵ 1.Step 3.2. Transform Cgt into the values of P, ρS, ρI, d, ρNS, ρNI, and TB.Step 3.3. Execute MPM-LOLA (Algorithm 2) with the last-updated values of P, ρS, ρI, d, ρNS, ρNI, TB, and δ in order to receive Pfg(t) and Sfg(t).Step 3.4. Let ScoreCgt⟵MakespanSfgt.Step 3.5. If ScoreCgt≤ScoreCbest, then let Cbest⟵Cgt, ScoreCbest⟵ScoreCgt, and Sbest⟵Sfgt.Step 3.6. If g<N, let g⟵g+1 and repeat from Step 3.2. Otherwise, go to Step 4.Step 4. UpdateCgt+1 , where g=1,2,…,N, by using Steps 4.1 to 4.5.Step 4.1. Let g⟵1.Step 4.2. Let c1gt+1⟵Pfgt.Step 4.3. If (t + 1) mod 50 = 0, let δ ⟵ δ + 0.2. After that, reassign δ ⟵ 0.999 if δ ≥ 1.0.Step 4.4. If t+1 mod 50 = 0, randomly generate c2gt+1,c3gt+1,…,c9gt+1∼U0,1. Otherwise, generate cqgt+1, where q=2,3,…,9, by using the below equation. Let u1 and u2∼U0,1.cqgt+1=cqgt+0.05u1−0.01u2ifcqgt<cqbest,cqgt−0.05u1+0.01u2ifcqgt>cqbest,cqgt+0.01u1−0.01u2ifcqgt=cqbest.Step 4.5. If g<N, then let g⟵g+1 and repeat from Step 4.2. Otherwise, go to Step 5.Step 5. If the stopping criterion is not met, then let t ⟵ t + 1 and repeat from Step 2. Otherwise, return Sbest as the final result to the user.


## 4. Experiment’s Results

In this paper, an experiment was conducted to compare MPM-UPLA’s results with those of TS, PSO, and CP. Let TS, PSO, and CP represent the tabu-search algorithm [9], the particle swarm optimization algorithm [10], and the ILOG constraint programming optimizer [20], respectively. These three algorithms were chosen because they perform well on the same benchmark instance sets used in this paper’s experiment. In Sections 4 and 5, let MPM-UPLA stand for the whole two-level metaheuristic, i.e., MPM-UPLA combined with MPM-LOLA. The reason is that MPM-UPLA uses MPM-LOLA as its component when solving MPMJSP.In the comparison, this paper’s experiment used three benchmark instance sets, i.e., Edata, Rdata, and Vdata, taken from [9, 20, 21]. Each instance set consists of 66 instances, modified from the well-known JSP benchmark instances [35–39]. The difference among the three instance sets is the number of optional machines of each operation in their instances. In Edata, the average number of optional machines of each operation is 1.15, and the maximum number of optional machines of each operation is 2 or 3. In Rdata, the average number and the maximum number of optional machines of each operation are 2 and 3, respectively. In Vdata, the average number and the maximum number of optional machines of each operation are 0.5m and 0.8m, respectively (where m = the number of all machines in an instance).The parameter settings of MPM-UPLA used in the experiment are shown below:(i)
The population of MPM-UPLA consisted of three parameter-value combinations (i.e.,N = 3 in Algorithm 3).(ii)
The stopping criterion of MPM-UPLA was to stop when any of the below conditions was satisfied:(a)
The 1,000-th iteration (i.e.,t = 1,000 in Algorithm 3) was reached.(b)
The 150-th minute of computational time was reached.(c)
The known optimal solution was found. If the optimal solution has been yet unknown, its lower bound [20, 21] was used instead.(iii)
MPM-UPLA was coded in C# and executed on an Intel® Core™ i7-3520M @ 2.90 GHz with RAM of 4 GB (3.87 GB useable).(iv)
For each instance, MPM-UPLA was executed five trials with different random-seed numbers.With the above settings, the experiment’s results on Edata, Rdata, and Vdata are presented in Tables1 to 3, respectively. These tables first show the name, size, and best-known solution value of each instance. The best-known solution value, given by literature, stands for the upper bound of the optimal solution value. For each instance, each table then shows the best-found solution values of TS [9], PSO [10], CP [20], and MPM-UPLA. The best-found solution values of TS, PSO, and CP are their best solution values taken from their original articles [9, 10] and [20], respectively. For MPM-UPLA, its best-found solution value on each instance is a minimum of the best-found solution values from its five trials in this experiment. Each table also shows an average of the best-found solution values, the average number of used iterations, and the average computational time from the MPM-UPLA’s five trials on each instance.Table 1
Results on Edata.
Instancen, mBKSBest of TS [9]Best of PSO [10]Best of CP [20]MPM-UPLABestAvgNo of ItersTimeM66, 6555755555555.01< 1 sec.M1010, 10871917892877873875.010000:26:10M2020, 5108811091116108810901090.210000:31:11LA110, 5609611609609609609.01< 1 sec.LA210, 5655655655655655655.03< 1 sec.LA310, 5550573567567550550.0890:00:19LA410, 5568578582568568568.0250:00:05LA510, 5503503503503503503.01< 1 sec.LA615, 5833833833833833833.01< 1 sec.LA715, 5762765765765762762.03770:04:02LA815, 5845845845845845845.030:00:01LA915, 5878878878878878878.01< 1 sec.LA1015, 5866866866866866866.01< 1 sec.LA1120, 5110311061103110611031103.02460:05:09LA1220, 5960960960960960960.010:00:02LA1320, 5105310531053105310531053.010:00:01LA1420, 5112311511123112311231123.020:00:02LA1520, 5111111111111111111111111.020:00:03LA1610, 10892924893904892892.040:00:07LA1710, 10707757707707707707.030:00:04LA1810, 10842864847843842842.02500:06:00LA1910, 10796850820799796796.01610:04:20LA2010, 10857919859857857857.060:00:11LA2115, 10100910661057104410211025.010001:42:08LA2215, 10880919912887882883.210001:39:29LA2315, 10950980994950950950.0680:06:38LA2415, 10908952939913909909.210001:39:33LA2515, 10936970974955945945.210001:31:55LA2620, 10110611691173114311151123.05432:30:09LA2720, 10118112301247118811821188.85522:30:12LA2820, 10114212041195115311491149.05662:30:08LA2920, 10110712101175112811241130.25552:30:08LA3020, 10(1193)12531262124112201223.45512:30:19LA3130, 10(1532)15961620155215411541.01952:30:31LA3230, 10169817691743169816981698.020:01:19LA3330, 10154715751578156015471547.020:01:22LA3430, 10159916271662160916081608.82592:30:09LA3530, 10173617361736173617361736.010:01:06LA3615, 15116012471202116011601161.83071:49:22LA3715, 15139714531425139713971397.0410:11:14LA3815, 15114111851209114611431148.24242:30:18LA3915, 15118412261220118411861187.44232:30:14LA4015, 15114412141197117411501153.63912:30:05ABZ510, 101167N/AN/A117611671167.02350:06:08ABZ610, 10925N/AN/A925925925.0350:00:49ABZ720, 15(610)N/AN/A638619621.01502:30:44ABZ820, 15(637)N/AN/A654648650.01522:30:37ABZ920, 15644N/AN/A668655656.61552:30:26CAR111, 56176N/AN/A617661766182.07230:03:37CAR213, 46327N/AN/A645564326433.610000:05:05CAR312, 56856N/AN/A685668566875.87800:04:25CAR414, 47789N/AN/A778977897789.01< 1 sec.CAR510, 67229N/AN/A722972297229.0410:00:15CAR68, 97990N/AN/A847879907990.0620:00:33CAR77, 76123N/AN/A612361236123.060:00:01CAR88, 87689N/AN/A768976897689.090:00:04ORB110, 10977N/AN/A988977977.02230:06:25ORB210, 10865N/AN/A870865865.0530:01:21ORB310, 10951N/AN/A960952952.010000:26:46ORB410, 10984N/AN/A1016984984.02550:06:47ORB510, 10842N/AN/A865842842.02150:05:27ORB610, 10958N/AN/A1004958958.0930:02:48ORB710, 10387N/AN/A387389389.010000:26:27ORB810, 10894N/AN/A894894894.0150:00:23ORB910, 10933N/AN/A933933933.01210:03:14ORB1010, 10933N/AN/A937933933.02260:06:02Table 2
Results on Rdata.
Instancen, mBKSBest of TS [9]Best of PSO [10]Best of CP [20]MPM-UPLABestAvgNo of ItersTimeM66, 6474747474747.01< 1 sec.M1010, 10686737724686686686.0290:01:10M2020, 5102210281025102410221022.0220:00:46LA110, 5(571)574574573571571.010000:04:50LA210, 5529535534534530530.810000:04:51LA310, 5477481480478478478.010000:05:43LA410, 5502509506504502502.88780:04:31LA510, 5457460459458457457.66480:03:03LA615, 5799801800799799799.0150:00:13LA715, 5749752750750749749.01580:02:38LA815, 5765767767766765765.01830:02:54LA915, 5853859854854853853.01000:01:29LA1015, 5804806806805804804.02740:03:55LA1120, 5107110731072107210711071.030:00:07LA1220, 5936937936936936936.020:00:04LA1320, 5103810391039103810381038.020:00:03LA1420, 5107010711070107110701070.040:00:07LA1520, 5108910931090109110891089.0670:02:21LA1610, 10717717732717717717.020:00:05LA1710, 10646646654646646646.010:00:02LA1810, 10666674694666666666.0720:02:49LA1910, 10700725730703700701.25340:22:48LA2010, 10756756756757756756.010:00:03LA2115, 10(829)861916845844846.66172:30:04LA2215, 10(753)790839775772774.67542:30:05LA2315, 10(832)884892857850856.26652:30:04LA2415, 10(801)825870818821823.07232:30:06LA2515, 10(782)823858805802804.07852:30:04LA2620, 10(1059)10861114107410671068.22182:30:31LA2720, 10(1087)11091141110110951098.42492:30:15LA2820, 10(1077)10971135108410831086.02272:30:07LA2920, 10(996)10161046100610031004.62582:30:08LA3020, 10(1072)11051148108710871090.22572:30:15LA3130, 10⟶152015321549152515201523.2612:16:01LA3230, 10(1658)16681691166416591660.4652:30:56LA3330, 10(1498)15111530150214981500.2702:30:47LA3430, 10(1536)15421556154215361537.2702:31:01LA3530, 10(1550)15591577155615511551.8732:31:01LA3615, 15102310541119103410261033.02132:30:17LA3715, 15106211221190108410841086.02192:30:21LA3815, 1595410041063973976976.02492:30:18LA3915, 15101110411131101810241025.22582:30:26LA4015, 1595510091057984977984.01692:30:33ABZ510, 10954N/AN/A962959960.010000:48:07ABZ610, 10807N/AN/A807807807.040:00:08ABZ720, 15(527)N/AN/A544547548.8572:32:24ABZ820, 15(540)N/AN/A555561565.2672:31:02ABZ920, 15(539)N/AN/A562555565.2682:31:18CAR111, 5(5035)N/AN/A505750505053.410000:07:21CAR213, 4(5986)N/AN/A598759865986.010000:05:45CAR312, 5(5623)N/AN/A562656255629.210000:10:00CAR414, 4(6515)N/AN/A651865156515.210000:07:25CAR510, 65615N/AN/A576456805691.410000:09:24CAR68, 96147N/AN/A614761476147.0170:00:12CAR77, 74425N/AN/A443244254430.68030:04:07CAR88, 85692N/AN/A569256925692.0990:00:54ORB110, 10746N/AN/A763746746.0200:00:40ORB210, 10696N/AN/A703696698.48070:32:37ORB310, 10712N/AN/A720715716.010000:44:29ORB410, 10753N/AN/A753753753.080:00:22ORB510, 10639N/AN/A643639639.03250:15:04ORB610, 10754N/AN/A766754754.01450:05:35ORB710, 10302N/AN/A302302303.48660:38:49ORB810, 10639N/AN/A651641641.010000:42:24ORB910, 10694N/AN/A694694694.0330:01:27ORB1010, 10742N/AN/A750742743.48470:41:27Table 3
Results on Vdata.
Instancen, mBKSBest of TS [9]Best of PSO [10]Best of CP [20]MPM-UPLABestAvgNo of ItersTimeM66, 6474747474747.01< 1 sec.M1010, 10655655655655655655.010:00:01M2020, 5102210231024102310221022.040:00:10LA110, 5570573571570570570.24310:02:30LA210, 5529531530529529529.01340:00:43LA310, 5477482479478477477.88750:04:58LA410, 5502504504502502502.03450:01:48LA510, 5457464460458457457.45270:02:43LA615, 5799802799799799799.060:00:05LA715, 5749751750750749749.01030:01:47LA815, 5765766766766765765.0960:01:39LA915, 5853854855854853853.0280:00:28LA1015, 5804805805804804804.01240:02:04LA1120, 5107110731071107110711071.010:00:03LA1220, 5936940936936936936.010:00:03LA1320, 5103810401038103810381038.040:00:08LA1420, 5107010711070107010701070.020:00:03LA1520, 5108910911090109010891089.0360:01:21LA1610, 10717717717717717717.010:00:02LA1710, 10646646646646646646.010:00:02LA1810, 10663663663663663663.010:00:02LA1910, 10617617619617617617.030:00:10LA2010, 10756756756756756756.010:00:02LA2115, 10(802)826819804817822.25012:30:08LA2215, 10(735)745755736755756.45362:30:11LA2315, 10(812)826828815826831.25332:30:06LA2415, 10(775)796790775793797.45892:30:06LA2515, 10(753)770775756768770.25622:30:08LA2620, 10(1053)10581058105410731075.82672:30:24LA2720, 10108410881091108411061110.22602:30:20LA2820, 10106910731076107010911094.62532:30:20LA2920, 10(994)995100399510101013.62412:30:18LA3020, 10(1069)10711078107210851093.82222:30:17LA3130, 10152015211524152215381540.6822:31:00LA3230, 10(1658)16581664166116811686.6792:31:10LA3330, 10(1498)14981503150015111519.2792:31:12LA3430, 10153515361541153715571561.4842:30:49LA3530, 10154915531555155115631570.8742:31:05LA3615, 15948948955948948948.040:03:21LA3715, 15986986993986986986.0540:49:27LA3815, 15943943943943943943.010:00:38LA3915, 15922922945922922922.0270:24:02LA4015, 15955955955955955955.010:00:41ABZ510, 10859N/AN/A860859859.0120:00:53ABZ610, 10742N/AN/A742742742.010:00:04ABZ720, 15(495)N/AN/A495535536.0862:30:44ABZ820, 15(509)N/AN/A509554554.8842:30:58ABZ920, 15(499)N/AN/A500540541.8852:31:11CAR111, 55005N/AN/A501350075007.010000:08:30CAR213, 45929N/AN/A593059295929.02550:01:22CAR312, 5(5598)N/AN/A560056015601.410000:10:41CAR414, 46514N/AN/A651765146514.01990:01:22CAR510, 6(4913)N/AN/A493249354941.010000:11:21CAR68, 95486N/AN/A548654865486.010:00:01CAR77, 74281N/AN/A428142814281.010:00:00CAR88, 84613N/AN/A461346134613.020:00:02ORB110, 10695N/AN/A695695695.010:00:01ORB210, 10620N/AN/A620620620.010:00:04ORB310, 10648N/AN/A648648648.010:00:02ORB410, 10753N/AN/A753753753.010:00:02ORB510, 10584N/AN/A584584584.010:00:04ORB610, 10715N/AN/A715715715.010:00:01ORB710, 10275N/AN/A275275275.0100:00:32ORB810, 10573N/AN/A573573573.010:00:02ORB910, 10659N/AN/A659659659.010:00:03ORB1010, 10681N/AN/A681681681.010:00:03Notation and terminologies used for each instance in Tables1 to 3 are given as follows:(i)
LetInstance column present the name of each instance.(ii)
Letn and m denote the number of all jobs and the number of all machines, respectively, in the instance.(iii)
Let asolution denote an MPMJSP’s schedule, and let a solution value denote a makespan of an MPMJSP’s schedule.(iv)
LetBKS column present the best-known solution value given by literature, e.g., [20, 21]. If the best-known solution value has been proven to be an optimal solution value, it is presented without parentheses. Otherwise, it is an upper bound of the optimal solution value and is presented within parentheses.(v)
If the best-found solution value of MPM-UPLA is better than the best-known solution value given by literature, let the best-found solution value of MPM-UPLA become the new best-known solution value. When such a case occurs, an arrow symbol (⟶) is given in front of the value.(vi)
LetBest represent the best-found solution value of each algorithm. Best of MPM-UPLA was taken from the five trials in this experiment. Bests of TS, PSO, and CP were taken from [9, 10] and [20], respectively. N/A means the best-found solution value does not appear in the original article.(vii)
LetAvg represent the average of the best-found solution values of the five trials of MPM-UPLA.(viii)
LetNo of Iters and Time stand for the average number of iterations and the average computational time (in HH:MM:SS format), respectively, until the MPM-UPLA’s stopping criterion is met.For each instance set, Table4 shows Avg %BD of each algorithm on each instance category. Of each algorithm, %BD of each instance denotes a percent deviation of the best-found solution value from the best-known solution value. Then, Avg %BD denotes an average of %BDs of all instances in their category. In Table 4, each instance is classified into one of 13 instance categories, based on its source and size. The details of these 13 categories are given below:(i)
M6-20 consists of three instances, i.e., M6, M10, and M20.(ii)
LA1-5 consists of five 10-job/5-machine instances, i.e., LA1, LA2, …, LA5.(iii)
LA6-10 consists of five 15-job/5-machine instances, i.e., LA06, LA07, …, LA10.(iv)
LA11-15 consists of five 20-job/5-machine instances, i.e., LA11, LA12, …, LA15.(v)
LA16-20 consists of five 10-job/10-machine instances, i.e., LA16, LA17, …, LA20.(vi)
LA21-25 consists of five 15-job/10-machine instances, i.e., LA21, LA22, …, LA25.(vii)
LA26-30 consists of five 20-job/10-machine instances, i.e., LA26, LA27, …, LA30.(viii)
LA31-35 consists of five 30-job/10-machine instances, i.e., LA31, LA32, …, LA35.(ix)
LA36-40 consists of five 15-job/15-machine instances, i.e., LA36, LA37, …, LA40.(x)
ABZ5-6 consists of two 10-job/10-machine instances, i.e., ABZ5 and ABZ6.(xi)
ABZ7-9 consists of three 20-job/15-machine instances, i.e., ABZ7, ABZ8, and ABZ9.(xii)
CAR1-8 consists of eight instances, i.e., CAR1, CAR2, …, CAR8.(xiii)
ORB1-10 consists of ten 10-job/10-machine instances, i.e., ORB1, ORB2, …, ORB10.Table 4
Avg %BDs.
CategoryNo. of instancesn, mEdataRdataVdataTSPSOCPMPM-UPLATSPSOCPMPM-UPLATSPSOCPMPM-UPLAM6-203Vary3.621.660.230.142.671.940.070.000.030.070.030.00LA01-05510, 51.251.110.620.000.910.670.420.080.780.370.090.00LA06-10515, 50.080.080.080.000.370.180.100.000.200.120.080.00LA11-15520, 50.550.000.050.000.170.060.070.000.220.020.020.00LA16-20510, 105.460.790.370.000.952.360.110.000.000.060.000.00LA21-25515, 104.344.101.370.504.659.492.582.312.212.330.232.13LA26-30520, 105.925.642.161.062.305.531.150.830.300.700.111.82LA31-35530, 102.382.870.550.230.651.820.350.020.080.350.141.16LA36-40515, 155.013.850.610.174.5111.081.771.650.000.790.000.00ABZ5-6210, 10N/AN/A0.390.00N/AN/A0.420.26N/AN/A0.060.00ABZ7-9320, 15N/AN/A3.661.64N/AN/A3.423.55N/AN/A0.078.38CAR1-88VaryN/AN/A1.020.21N/AN/A0.420.19N/AN/A0.080.07ORB1-101010, 10N/AN/A1.390.06N/AN/A0.960.07N/AN/A0.000.00M6-LA4043Vary3.162.260.690.241.873.760.770.570.440.560.080.59SM-M6-LA4023nm < 1502.070.650.270.020.870.960.160.020.260.130.040.00M6-ORB1066VaryN/AN/A0.960.26N/AN/A0.870.57N/AN/A0.070.78SM- M6-ORB1043nm < 150N/AN/A0.670.07N/AN/A0.550.24N/AN/A0.040.01In addition to the 13 categories, Table4 includes four more instance categories, i.e., M6-LA40, SM-M6-LA40, M6-ORB10, and SM-M6-ORB10. These additional categories were used for comparing performance of the algorithms. SM in SM-M6-LA40 and SM-M6-ORB10 indicates that these categories contain only small-to-medium instances. Let instances be defined as small-to-medium instances if their nm < 150 and large instances otherwise (where n = the number of jobs and m = the number of machines). The details of these four additional categories are given below:(i)
M6-LA40 consists of the first 43 instances of all 66 instances, starting from M6 to LA40. These 43 instances were used by TS [9] and PSO [10] in their original articles.(ii)
SM-M6-LA40 consists of all 23 small-to-medium instances from M6-LA40.(iii)
M6-ORB10 consists of all 66 instances, starting from M6 to ORB10. These 66 instances were used by CP [20] in its original article.(iv)
SM-M6-ORB10 consists of all 43 small-to-medium instances from M6-ORB10.


## 5. Result Analysis and Discussion

This section analyzes and discusses the results shown in Section4. Like Section 4, MPM-UPLA in this section stands for the whole two-level metaheuristic, i.e., MPM-UPLA combined with MPM-LOLA. The performance of MPM-UPLA was compared with the performance of TS [9], PSO [10], and CP [20] via three performance indicators. These indicators are the number of instances achieved in finding the best-known solutions, the number of instances won by an algorithm against another, and the average percent deviation of the algorithm’s best-found solution value from the best-known solution value (Avg %BD). Of each instance, the best-known solution value means the best solution value found by the published literature. An only exception is in LA31 of Rdata, where its best-known solution value was taken from the best-found solution value of MPM-UPLA. The reason is that, in LA31 of Rdata, MPM-UPLA found the better solution than the previously published best-known solution.For each instance set, this section separates analyses on the first 43 instances from those on all 66 instances. The reason is that the results of TS and PSO were given on only the 43 instances in their original articles [9, 10], while the results of CP were given on the 66 instances in its original article [20]. In addition, this section separates analyses on small-to-medium instances from those on all given instances. Note that all instances with nm < 150 are defined as small-to-medium instances (where n = the number of jobs and m = the number of machines). Sections 5.1 to 5.3 show the analyses and discussions via the three given indicators. Then, Section 5.4 provides an overall summary from Sections 5.1 to 5.3.


### 5.1. The Number of Instances Achieved in Finding the Best-Known Solutions

Of each instance set, this section first compares the number of instances achieved in finding the best-known solutions by MPM-UPLA with those by TS, PSO, and CP on the first 43 instances. The numbers of instances achieved by each algorithm in Edata, Rdata, and Vdata were counted from Tables1, 2, and 3, respectively. For the first 43 instances, MPM-UPLA obviously outperforms the three other algorithms on all three instance sets, especially Rdata. Of each instance set, the comparison results are given below:(i)
For the first 43 instances of Edata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 10, 15, 22, and 27 instances, respectively.(ii)
For the first 43 instances of Rdata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 4, 4, 8, and 24 instances, respectively. MPM-UPLA also found a new best-known solution value (i.e., 1520) for LA31 of Rdata. This value is defined as the optimal solution value because it equals the optimal solution value’s lower bound given in [20].(iii)
For the first 43 instances of Vdata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 14, 13, 23, 28 instances, respectively.Of each instance set, this section then compares the number of instances achieved by MPM-UPLA with that by CP on all 66 instances. For all 66 instances, MPM-UPLA outperforms CP on all three instance sets, especially Rdata. Of each instance set, the comparison results are given below:(i)
For all 66 instances of Edata, CP and MPM-UPLA reach the best-known solutions on 32 and 44 instances, respectively.(ii)
For all 66 instances of Rdata, CP and MPM-UPLA reach the best-known solutions on 14 and 38 instances, respectively.(iii)
For all 66 instances of Vdata, CP and MPM-UPLA reach the best-known solutions on 39 and 45, respectively.Thus, as a conclusion, MPM-UPLA outperforms TS, PSO, and CP in finding the best-known solutions on all three instance sets, especially Rdata. On Rdata, the number of instances achieved by MPM-UPLA is more than double the number of instances achieved by each of the others. Moreover, MPM-UPLA also found the new best-known solution value on LA31 of Rdata.


### 5.2. The Number of Instances Won

This section first compares the number of instances won by MPM-UPLA with those by TS, PSO, and CP on the first 43 instances of each instance set. Note that in the first 43 instances, there are 23 small-to-medium instances included. The numbers of instances won in Edata, Rdata, and Vdata were counted from Tables1, 2, and 3, respectively. For the first 43 instances, MPM-UPLA obviously outperforms the three other algorithms on Edata and Rdata; MPM-UPLA outperforms TS and PSO but underperforms CP on Vdata. However, when considering only the 23 small-to-medium instances, MPM-UPLA outperforms CP on Vdata. Of each instance set, the comparison results are detailed below:(i)
Out of the first 43 instances of Edata, MPM-UPLA has 33 wins, 10 draws, and 0 losses against TS; it has 28 wins, 15 draws, and 0 losses against PSO. In addition, it has 21 wins, 20 draws, and 2 losses against CP.(ii)
Out of the first 43 instances of Rdata, MPM-UPLA has 39 wins, 4 draws, and 0 losses against each of TS and PSO. In addition, it has 29 wins, 11 draws, and 3 losses against CP.(iii)
Out of the first 43 instances of Vdata, MPM-UPLA has 19 wins, 13 draws, and 11 losses against TS; it has 18 wins, 14 draws, and 11 losses against PSO. In addition, it has 7 wins, 21 draws, and 15 losses against CP. However, when considering only the 23 small-to-medium instances, MPM-UPLA has 7 wins, 16 draws, and 0 losses against CP.Then, this section compares the number of instances won by MPM-UPLA with that by CP on all 66 instances of each instance set. Note that in the 66 instances, there are 43 small-to-medium instances included. For the 66 instances, MPM-UPLA outperforms CP on Edata and Rdata, but it underperforms CP on Vdata. However, when considering only the 43 small-to-medium instances, MPM-UPLA obviously outperforms CP on all three instance sets. For each instance set, the comparison results are detailed below:(i)
Out of all 66 instances of Edata, MPM-UPLA has 34 wins, 29 draws, and 3 losses against CP. Out of the 43 small-to-medium instances of Edata, MPM-UPLA has 17 wins, 24 draws, and 2 losses against CP.(ii)
Out of all 66 instances of Rdata, MPM-UPLA has 44 wins, 17 draws, and 5 losses against CP. Out of the 43 small-to-medium instances of Rdata, MPM-UPLA has 28 wins, 15 draws, and 0 losses against CP.(iii)
Out of all 66 instances of Vdata, MPM-UPLA has 11 wins, 35 draws, and 20 losses against CP. Out of the 43 small-to-medium instances of Vdata, MPM-UPLA has 11 wins, 30 draws, and 2 losses against CP.As a conclusion, in terms of the number of instances won, MPM-UPLA outperforms the three other algorithms on Edata and Rdata. For Vdata, MPM-UPLA outperforms TS and PSO but underperforms CP. However, when considering only small-to-medium instances, MPM-UPLA outperforms CP on Vdata.


### 5.3. Avg %BD

This section analyzesAvg %BDs in Table 4. To do so, it first analyzes Avg %BDs of the first 43 instances of each instance set. Then, it analyzes those of the 23 small-to-medium instances of the first 43 instances. In Table 4, the rows M6-LA40 and SM-M6-LA40 provide Avg % BDs of the first 43 instances and those of the 23 small-to-medium instances, respectively. For Avg %BDs of the first 43 instances, MPM-UPLA outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. When considering only the 23 small-to-medium instances, MPM-UPLA obviously outperforms the three other algorithms on all three instance sets. Of each instance set, the analysis results are detailed below:(i)
For the first 43 instances of Edata, MPM-UPLA’sAvg %BD (i.e., 0.24%) is much better than those of TS, PSO, and CP (i.e., 3.16%, 2.26%, and 0.69%, respectively). Based on these 43 instances, paired t tests concluded that the mean %BD of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 3 × 10−10, 1 × 10−8, and 0.0002, respectively). When considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.02%) is also much better than those of TS, PSO, and CP (i.e., 2.07%, 0.65%, and 0.27%, respectively).(ii)
For the first 43 instances of Rdata, MPM-UPLA’sAvg %BD (i.e., 0.57%) is much better than those of TS, PSO, and CP (i.e., 1.87%, 3.76%, and 0.77%, respectively). Based on these 43 instances, paired t tests concluded that the mean %BD of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 4 × 10−7, 1 × 10−7, and 0.00004, respectively). When considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.02%) is also much better than those of TS, PSO, and CP (i.e., 0.87%, 0.96%, and 0.16%, respectively).(iii)
For the first 43 instances of Vdata, MPM-UPLA’sAvg %BD (i.e., 0.59%) is worse than those of TS, PSO, and CP (i.e., 0.44%, 0.56%, and 0.08%, respectively). However, when considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.00%) is better than those of TS, PSO, and CP (i.e., 0.26%, 0.13%, and 0.04%, respectively). Based on the 23 small-to- medium instances, paired t tests concluded that the mean %BD of small-to-medium instances of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 0.001, 0.0007, and 0.004, respectively).Of each instance set, this section then comparesAvg %BDs of MPM-UPLA and CP from all 66 instances and from their 43 small-to-medium instances. In Table 4, the rows M6-ORB10 and SM-M6-ORB10 provide Avg %BDs of all 66 instances and those of the 43 small-to-medium instances, respectively. For all 66 instances, MPM-UPLA outperforms CP on Edata and Rdata, but it underperforms CP on Vdata. However, when considering only the 43 small-to-medium instances, MPM-UPLA obviously outperforms CP on all three instance sets. Of each instance set, the comparison results are detailed below:(i)
For all 66 instances of Edata, MPM-UPLA’sAvg %BD (i.e., 0.26%) is better than CP’s Avg %BD (i.e., 0.96%). A paired t-test concluded that the mean %BD of MPM-UPLA is significantly better than the mean %BD of CP (with p value of 0.00001). When considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.07%) is also better than CP’s Avg %BD (i.e., 0.67%).(ii)
For all 66 instances of Rdata, MPM-UPLA’sAvg %BD (i.e., 0.57%) is better than CP’s Avg %BD (i.e., 0.87%). A paired t-test concluded that the mean %BD of MPM-UPLA is significantly better than the mean %BD of CP (with p value of 0.00002). When considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.24%) is also better than CP’s Avg %BD (i.e., 0.55%).(iii)
For all 66 instances of Vdata, MPM-UPLA’sAvg %BD (i.e., 0.78%) is worse than CP’s Avg %BD (i.e., 0.07%). However, when considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.01%) is better than CP’s Avg %BD (i.e., 0.04%). Based on the 43 small-to-medium instances, a paired t-test concluded that the mean %BD of small-to-medium instances of MPM-UPLA is significantly better than that of CP (with p value of 0.002).As a conclusion, based onAvg %BDs, MPM-UPLA obviously outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. When considering only the small-to-medium instances, MPM-UPLA outperforms the three other algorithms on all three instance sets.


### 5.4. Overall Summary

In the number of instances achieved in finding the best-known solutions, MPM-UPLA outperforms the three other algorithms on all three sets of instances. In the number of instances won, MPM-UPLA outperforms the three other algorithms on Edata and Rdata; MPM-UPLA outperforms TS and PSO but underperforms CP on Vdata. However, when considering only small-to-medium instances, MPM-UPLA outperforms CP on Vdata in the number of instances won. InAvg %BD, MPM-UPLA outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. However, when considering only small-to-medium instances, MPM-UPLA outperforms the three other algorithms on Vdata. As a conclusion, MPM-UPLA usually performs very well on the MPMJSP instances where each operation has less than four optional machines (e.g., the instances in Edata and Rdata). When each operation has many optional machines (i.e., ≥ 0.5moptional machines), MPM-UPLA usually performs well on only small-to-medium instances (i.e., the instances of nm < 150).


## 5.1. The Number of Instances Achieved in Finding the Best-Known Solutions

Of each instance set, this section first compares the number of instances achieved in finding the best-known solutions by MPM-UPLA with those by TS, PSO, and CP on the first 43 instances. The numbers of instances achieved by each algorithm in Edata, Rdata, and Vdata were counted from Tables1, 2, and 3, respectively. For the first 43 instances, MPM-UPLA obviously outperforms the three other algorithms on all three instance sets, especially Rdata. Of each instance set, the comparison results are given below:(i)
For the first 43 instances of Edata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 10, 15, 22, and 27 instances, respectively.(ii)
For the first 43 instances of Rdata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 4, 4, 8, and 24 instances, respectively. MPM-UPLA also found a new best-known solution value (i.e., 1520) for LA31 of Rdata. This value is defined as the optimal solution value because it equals the optimal solution value’s lower bound given in [20].(iii)
For the first 43 instances of Vdata, the algorithms TS, PSO, CP, and MPM-UPLA reach the best-known solutions on 14, 13, 23, 28 instances, respectively.Of each instance set, this section then compares the number of instances achieved by MPM-UPLA with that by CP on all 66 instances. For all 66 instances, MPM-UPLA outperforms CP on all three instance sets, especially Rdata. Of each instance set, the comparison results are given below:(i)
For all 66 instances of Edata, CP and MPM-UPLA reach the best-known solutions on 32 and 44 instances, respectively.(ii)
For all 66 instances of Rdata, CP and MPM-UPLA reach the best-known solutions on 14 and 38 instances, respectively.(iii)
For all 66 instances of Vdata, CP and MPM-UPLA reach the best-known solutions on 39 and 45, respectively.Thus, as a conclusion, MPM-UPLA outperforms TS, PSO, and CP in finding the best-known solutions on all three instance sets, especially Rdata. On Rdata, the number of instances achieved by MPM-UPLA is more than double the number of instances achieved by each of the others. Moreover, MPM-UPLA also found the new best-known solution value on LA31 of Rdata.


## 5.2. The Number of Instances Won

This section first compares the number of instances won by MPM-UPLA with those by TS, PSO, and CP on the first 43 instances of each instance set. Note that in the first 43 instances, there are 23 small-to-medium instances included. The numbers of instances won in Edata, Rdata, and Vdata were counted from Tables1, 2, and 3, respectively. For the first 43 instances, MPM-UPLA obviously outperforms the three other algorithms on Edata and Rdata; MPM-UPLA outperforms TS and PSO but underperforms CP on Vdata. However, when considering only the 23 small-to-medium instances, MPM-UPLA outperforms CP on Vdata. Of each instance set, the comparison results are detailed below:(i)
Out of the first 43 instances of Edata, MPM-UPLA has 33 wins, 10 draws, and 0 losses against TS; it has 28 wins, 15 draws, and 0 losses against PSO. In addition, it has 21 wins, 20 draws, and 2 losses against CP.(ii)
Out of the first 43 instances of Rdata, MPM-UPLA has 39 wins, 4 draws, and 0 losses against each of TS and PSO. In addition, it has 29 wins, 11 draws, and 3 losses against CP.(iii)
Out of the first 43 instances of Vdata, MPM-UPLA has 19 wins, 13 draws, and 11 losses against TS; it has 18 wins, 14 draws, and 11 losses against PSO. In addition, it has 7 wins, 21 draws, and 15 losses against CP. However, when considering only the 23 small-to-medium instances, MPM-UPLA has 7 wins, 16 draws, and 0 losses against CP.Then, this section compares the number of instances won by MPM-UPLA with that by CP on all 66 instances of each instance set. Note that in the 66 instances, there are 43 small-to-medium instances included. For the 66 instances, MPM-UPLA outperforms CP on Edata and Rdata, but it underperforms CP on Vdata. However, when considering only the 43 small-to-medium instances, MPM-UPLA obviously outperforms CP on all three instance sets. For each instance set, the comparison results are detailed below:(i)
Out of all 66 instances of Edata, MPM-UPLA has 34 wins, 29 draws, and 3 losses against CP. Out of the 43 small-to-medium instances of Edata, MPM-UPLA has 17 wins, 24 draws, and 2 losses against CP.(ii)
Out of all 66 instances of Rdata, MPM-UPLA has 44 wins, 17 draws, and 5 losses against CP. Out of the 43 small-to-medium instances of Rdata, MPM-UPLA has 28 wins, 15 draws, and 0 losses against CP.(iii)
Out of all 66 instances of Vdata, MPM-UPLA has 11 wins, 35 draws, and 20 losses against CP. Out of the 43 small-to-medium instances of Vdata, MPM-UPLA has 11 wins, 30 draws, and 2 losses against CP.As a conclusion, in terms of the number of instances won, MPM-UPLA outperforms the three other algorithms on Edata and Rdata. For Vdata, MPM-UPLA outperforms TS and PSO but underperforms CP. However, when considering only small-to-medium instances, MPM-UPLA outperforms CP on Vdata.


## 5.3. Avg %BD

This section analyzesAvg %BDs in Table 4. To do so, it first analyzes Avg %BDs of the first 43 instances of each instance set. Then, it analyzes those of the 23 small-to-medium instances of the first 43 instances. In Table 4, the rows M6-LA40 and SM-M6-LA40 provide Avg % BDs of the first 43 instances and those of the 23 small-to-medium instances, respectively. For Avg %BDs of the first 43 instances, MPM-UPLA outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. When considering only the 23 small-to-medium instances, MPM-UPLA obviously outperforms the three other algorithms on all three instance sets. Of each instance set, the analysis results are detailed below:(i)
For the first 43 instances of Edata, MPM-UPLA’sAvg %BD (i.e., 0.24%) is much better than those of TS, PSO, and CP (i.e., 3.16%, 2.26%, and 0.69%, respectively). Based on these 43 instances, paired t tests concluded that the mean %BD of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 3 × 10−10, 1 × 10−8, and 0.0002, respectively). When considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.02%) is also much better than those of TS, PSO, and CP (i.e., 2.07%, 0.65%, and 0.27%, respectively).(ii)
For the first 43 instances of Rdata, MPM-UPLA’sAvg %BD (i.e., 0.57%) is much better than those of TS, PSO, and CP (i.e., 1.87%, 3.76%, and 0.77%, respectively). Based on these 43 instances, paired t tests concluded that the mean %BD of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 4 × 10−7, 1 × 10−7, and 0.00004, respectively). When considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.02%) is also much better than those of TS, PSO, and CP (i.e., 0.87%, 0.96%, and 0.16%, respectively).(iii)
For the first 43 instances of Vdata, MPM-UPLA’sAvg %BD (i.e., 0.59%) is worse than those of TS, PSO, and CP (i.e., 0.44%, 0.56%, and 0.08%, respectively). However, when considering only the 23 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.00%) is better than those of TS, PSO, and CP (i.e., 0.26%, 0.13%, and 0.04%, respectively). Based on the 23 small-to- medium instances, paired t tests concluded that the mean %BD of small-to-medium instances of MPM-UPLA is significantly better than those of TS, PSO, and CP (with p values of 0.001, 0.0007, and 0.004, respectively).Of each instance set, this section then comparesAvg %BDs of MPM-UPLA and CP from all 66 instances and from their 43 small-to-medium instances. In Table 4, the rows M6-ORB10 and SM-M6-ORB10 provide Avg %BDs of all 66 instances and those of the 43 small-to-medium instances, respectively. For all 66 instances, MPM-UPLA outperforms CP on Edata and Rdata, but it underperforms CP on Vdata. However, when considering only the 43 small-to-medium instances, MPM-UPLA obviously outperforms CP on all three instance sets. Of each instance set, the comparison results are detailed below:(i)
For all 66 instances of Edata, MPM-UPLA’sAvg %BD (i.e., 0.26%) is better than CP’s Avg %BD (i.e., 0.96%). A paired t-test concluded that the mean %BD of MPM-UPLA is significantly better than the mean %BD of CP (with p value of 0.00001). When considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.07%) is also better than CP’s Avg %BD (i.e., 0.67%).(ii)
For all 66 instances of Rdata, MPM-UPLA’sAvg %BD (i.e., 0.57%) is better than CP’s Avg %BD (i.e., 0.87%). A paired t-test concluded that the mean %BD of MPM-UPLA is significantly better than the mean %BD of CP (with p value of 0.00002). When considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.24%) is also better than CP’s Avg %BD (i.e., 0.55%).(iii)
For all 66 instances of Vdata, MPM-UPLA’sAvg %BD (i.e., 0.78%) is worse than CP’s Avg %BD (i.e., 0.07%). However, when considering only the 43 small-to-medium instances, MPM-UPLA’s Avg %BD (i.e., 0.01%) is better than CP’s Avg %BD (i.e., 0.04%). Based on the 43 small-to-medium instances, a paired t-test concluded that the mean %BD of small-to-medium instances of MPM-UPLA is significantly better than that of CP (with p value of 0.002).As a conclusion, based onAvg %BDs, MPM-UPLA obviously outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. When considering only the small-to-medium instances, MPM-UPLA outperforms the three other algorithms on all three instance sets.


## 5.4. Overall Summary

In the number of instances achieved in finding the best-known solutions, MPM-UPLA outperforms the three other algorithms on all three sets of instances. In the number of instances won, MPM-UPLA outperforms the three other algorithms on Edata and Rdata; MPM-UPLA outperforms TS and PSO but underperforms CP on Vdata. However, when considering only small-to-medium instances, MPM-UPLA outperforms CP on Vdata in the number of instances won. InAvg %BD, MPM-UPLA outperforms the three other algorithms on Edata and Rdata, but it underperforms the three other algorithms on Vdata. However, when considering only small-to-medium instances, MPM-UPLA outperforms the three other algorithms on Vdata. As a conclusion, MPM-UPLA usually performs very well on the MPMJSP instances where each operation has less than four optional machines (e.g., the instances in Edata and Rdata). When each operation has many optional machines (i.e., ≥ 0.5moptional machines), MPM-UPLA usually performs well on only small-to-medium instances (i.e., the instances of nm < 150).


## 6. Conclusion

In this paper, a two-level metaheuristic was proposed for solving MPMJSP. The two-level metaheuristic consists of MPM-UPLA and MPM-LOLA as its upper- and lower-level algorithms, respectively. MPM-UPLA, a population-based algorithm, acts as the MPM-LOLA’s parameter controller. MPM-LOLA is a local search algorithm, searching for an MPMJSP’s optimal solution. MPM-LOLA has many changes from its older variants, such as perturbation and neighbor operators. It also uses a unique method to select an optional machine for each operation. The MPM-UPLA’s function is to evolve the MPM-LOLA’s input-parameter values, so that MPM-LOLA can perform its best for every single instance. In this paper’s experiment, the performance of the two-level metaheuristic was evaluated on the three instance sets, i.e., Edata, Rdata, and Vdata. The experiment’s results indicated that the two-level metaheuristic performs very well on Edata and Rdata. For Vdata, the two-level metaheuristic usually performs well on only the category of small-to-medium instances. Thus, a future research should be focused to enhance the two-level metaheuristic’s performance, especially on large instances of Vdata.



---

*Source: 3487355-2022-06-01.xml*