# A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints

Authors: Pisut Pongchairerks
Journal: Complexity
 (2021)

---

## Abstract

This paper introduces a job-shop scheduling problem (JSP) with bidirectional circular precedence constraints, called BCJSP. In the problem, each job can be started from any operation and continued by its remaining operations in a circular precedence-relation chain via either a clockwise or counterclockwise direction. To solve BCJSP, this paper proposes a multilevel metaheuristic consisting of top-, middle-, and bottom-level algorithms. The top- and middle-level algorithms are population-based metaheuristics, while the bottom-level algorithm is a local search algorithm. The top-level algorithm basically controls a start operation and an operation-precedence-relation direction of each job, so that BCJSP becomes a JSP instance that is a subproblem of BCJSP. Moreover, the top-level algorithm can also be used to control input parameters of the middle-level algorithm, as an optional extra function. The middle-level algorithm controls input parameters of the bottom-level algorithm, and the bottom-level algorithm then solves the BCJSP’s subproblem. The middle-level algorithm evolves the bottom-level algorithm’s parameter values by using feedback from the bottom-level algorithm. Likewise, the top-level algorithm evolves the start operations, the operation-precedence-relation directions, and the middle-level algorithm’s parameter values by using feedback from the middle-level algorithm. Performance of two variants of the multilevel metaheuristic (i.e., with and without the mentioned extra function) was evaluated on BCJSP instances modified from well-known JSP instances. The variant with the extra function performs significantly better in number than the other. The existing JSP-solving algorithms can also solve BCJSP; however, their results on BCJSP are clearly worse than those of the two variants of the multilevel metaheuristic.


---

## Body

## 1. Introduction

The job-shop scheduling problem (JSP) [1, 2] and the open-shop scheduling problem (OSP) [3, 4] are well-known in practical applications. They are also interesting academic topics since they are NP-hard problems [5]. They both involve scheduling jobs onto machines in order to minimize makespan, i.e., the schedule’s length. Each job consists of a number of operations; each operation must be processed on a predetermined machine with a given processing time. Each machine cannot process more than one operation at a time, and it cannot be stopped during processing an operation. To complete each job in JSP, all of its operations must be processed in the sequence from the first to the last operations. This sequence is called an operation-precedence-relation chain. The operation-precedence-relation chain of each job is very strict and, thus, cannot be changed. In contrast to JSP, OSP has no operation-precedence-relation chains. This means all operations of each job in OSP can be processed in any orders. The job-shop scheduling problem with bidirectional circular precedence constraints (BCJSP) introduced in this paper is an intermediate problem between JSP and OSP. It is a generalized JSP where the operation-precedence-relation chain of each job is circular and bidirectional.BCJSP has a wide range of real applications, e.g., health check-up service, automobile repair shop, and instrument calibration service. In fact, when taking layouts and distances into account, many OSP’s applications become BCJSP’s applications. The health check-up service, as a BCJSP application, starts with multiple optional check-up programs offered to hospital customers. An optional check-up program consists of specific diagnoses, each of which is provided in a different room. For customer satisfaction, the best circular route of all diagnosis rooms has been predetermined by a hospital service manager for each check-up program. The manager may assign each customer to receive any diagnosis of his chosen program as the first diagnosis. However, the manager has to assign the customer to receive his next diagnosis in a nearest predetermined room, and so on. The customer finishes his check-up activities after successfully receiving all diagnoses of his chosen program. Notice that if the diagnosis rooms are very close to each other, the manager can then assign the customer to receive all diagnoses in any orders. Then, this application fits with OSP rather than BCJSP.There are a number of JSP and OSP’s variants recently presented in the literature, e.g., [6–11]. Some of them have some partially similar properties to the BCJSP’s properties. For example, the extended resource-constrained project scheduling problem [12] allows processing its activities bidirectionally, but not circularly. The flexible job-shop scheduling problem (FJSP) has more flexibility than JSP and is also defined as a generalized form of JSP. However, the flexibility of FJSP [13, 14] is due to a number of selectable machines for each operation, while the flexibility of BCJSP is due to the bidirectional circular precedence relations of operations.To solve BCJSP, this paper introduces a multilevel metaheuristic (called MUL) based on the adaptive parameter control concept [15]. MUL consists of the top-level algorithm (called TOP), the middle-level algorithm (called MID), and the bottom-level algorithm (called BOT). In the MUL’s top level, TOP controls the start operation and the operation-precedence-relation direction of every job in BCJSP. TOP is also usable to control the MID’s input parameters if requested. In the middle level, MID transfers the start operation and the operation-precedence-relation direction of every job given by TOP into BOT. However, the MID’s main function is to control the BOT’s input parameters. In the bottom level, BOT uses the start operations and the operation-precedence-relation directions to generate a JSP instance, which is a subproblem of the BCJSP instance. BOT then acts as a local search algorithm for solving the generated JSP instance. MID evolves the BOT’s input-parameter values based on feedback from BOT, while TOP evolves the operation-precedence-relation chains and the MID’s input-parameter values based on feedback from MID.The BOT combined with MID is similar to the two-level metaheuristic developed by [16]. A major difference of the MID-BOT combination from the algorithm of [16] is in the solution-decoding procedure. Once the MID-BOT combination is combined with TOP, they all together have become MUL. MUL can be defined as an adaptive multistart iterated local search algorithm for solving BCJSP. There are two variants of MUL proposed in this paper, i.e., the base-specification MUL (called MUL-B) and the top-specification MUL (called MUL-T). The only difference between the two variants is in their TOP-MID relationships. In both MUL-B and MUL-T, their TOPs control the start operation and the operation-precedence-relation direction of every job. In only MUL-T, its TOP also controls the MID’s input parameters. Performance of MUL-B and MUL-T was evaluated on the BCJSP instances, modified from the JSP instances of [17, 18, 19]. On the BCJSP instances, MUL-B’s and MUL-T’s results were compared with each other. Because the existing JSP-solving algorithms can be used to solve BCJSP, their results were also used in the performance comparisons. Note that the existing JSP-solving algorithms mean the algorithms developed for solving JSP in the literature, e.g., [1, 2, 16, 20, 21].The remainder of this paper is divided into six sections. Section2 provides an overview of the relevant publications of the research topic. Section 3 describes the job-shop scheduling problem with bidirectional circular precedence constraints (BCJSP). Section 4 presents the procedure of MUL, where the procedures of BOT, MID, and TOP are described in Sections 4.1–4.3, respectively. The differences between MUL-B and MUL-T, as the two variants of MUL, are also described in Section 4. Section 5 presents the experiment's results for MUL-B's and MUL-T's performance evaluations. Section 6 then discusses the experiment's results. Finally, Section 7 concludes the research’s findings.


## 2. Related Works

Metaheuristics can be classified into two categories based on their numbers of solutions used in each iteration, i.e., single-point-based and population-based search algorithms [22]. As its name implies, a single-point-based search algorithm starts with a single solution. Then, it moves from its current solution to another solution repeatedly. Local search is a well-known type of single-point-based search algorithms. A local search algorithm improves its solution gradually within a local region of the solution space. Although a local search algorithm aims to find just a local optimal solution, the algorithm with a good initial solution occasionally finds a global optimal solution.Iterated local search [23] is another well-known type of single-point-based search algorithms. It can be defined as a local search algorithm that can escape a local region of the solution space. During its exploration, an iterated local search algorithm uses a neighbor operator repeatedly to find a local optimal solution. After that, it tries to escape the current local region into another local region by using a perturbation operator. In general, an iterated local search algorithm starts with a single solution; however, some recent variants, e.g., [24, 25], have multistart properties.There are three operators, i.e., swap, insert, and inverse, commonly used as a neighbor operator and a perturbation operator [26]. To define these three operators, let h and v be two different random integers from 1 to the number of members in a solution-representing permutation. The swap operator is to swap between the two members in the h-th and thev-th positions. The insert operator is to remove a member from the h-th position and then insert it back at the v-th position. The inverse operator is to inverse the sequence of all members from the h-th to thev-th positions. Some iterated local search algorithms, e.g., [27, 28], use the swap operator or insert operator multiple times as their perturbation operators.As mentioned, the population-based search algorithm category is the alternative of the single-point-based search algorithm category. A population-based search algorithm starts with a set (i.e., a population) of solutions instead of a single solution. At each iteration, a population-based search algorithm evolves its population by using the information from its previous iterations. Some population-based search algorithms were purposely developed for solving discrete optimization problems, such as genetic algorithm [29] and ant colony optimization [30]. In contrast, some others were intentionally developed for exploring in real-number search spaces, such as particle swarm optimization [31], differential evolution [32], and cuckoo search [33] algorithms.A common drawback of most metaheuristics is that there is no single set of input-parameter values performing best for all problem’s instances. However, several techniques can be applied for handling such a drawback. One of these techniques is adaptive parameter control [15], where an upper-level metaheuristic acts as a parameter controller for a lower-level metaheuristic. (Note that upper-level metaheuristic is commonly called metaevolutionary algorithm [15, 34].) In addition, an upper-level metaheuristic can be applied to control parameters of a being-considered problem for generating its simpler subproblems [35, 36]. For applying the adaptive parameter control technique, the metaheuristics usually have only two levels [4, 15, 16, 37–39]. However, for solving highly complicated problems, they may require more than two levels [35, 36].A two-level metaheuristic of [37] was developed for solving JSP. It consists of the algorithms named UPLA and LOLA in its upper and lower levels, respectively. LOLA is a local search algorithm exploring in a solution space of parameterized-active schedules (hybrid schedules) [40–42], where each parameterized-active schedule is decoded from an operation-based permutation [29, 43]. UPLA is the population-based search algorithm intentionally developed for being a parameter controller. Its population consists of a number of value combinations of input parameters of LOLA. For updating an input-parameter-value combination, each input-parameter value is iteratively moved by a sum of two changeable opposite-direction vectors. The first vector’s direction is toward the memorized best-found value, whereas the second vector’s direction is away from it. The magnitudes of these two vectors are generated randomly between zeros and their given maximum values.The two-level metaheuristic of [16] is a recent variant of [37]. In this variant, MUPLA and LOSAP are the upper-level and lower-level metaheuristics, respectively. LOSAP [16] is a local search algorithm exploring in a probabilistic-based hybrid neighborhood structure. To generate each neighbor solution, LOSAP randomly uses one of the two predetermined neighbor operators by a preassigned probability. (Other applications of randomly using one of two different operators can be found in [44, 45].) Note that while LOLA’s solution space is a set of parameterized-active schedules, LOSAP’s solution space is just a set of semiactive schedules. It means that the LOSAP’s search ability is mainly based on its hybrid neighborhood structure, not based on a special solution space like LOLA. LOSAP has many optional operators proposed for being its perturbation and neighbor operators. In addition, LOSAP uses a different criterion from that of LOLA on accepting a new best-found solution.MUPLA [16] is a population-based metaheuristic designed to be a parameter controller for LOSAP. Thus, its population consists of a number of value combinations of the LOSAP’s input parameters. Each input-parameter-value combination contains specific values of the perturbation operator, the scheduling direction, the ordered pair of two neighbor operators, the probability of selecting a neighbor operator, and the start solution-representing permutation. A major change of MUPLA from UPLA is that each input-parameter-value combination in its population includes a specific start solution-representing permutation. Thus, the MUPLA combined with LOSAP acts as a multistart iterated local search algorithm, while the UPLA combined with LOLA is just an iterated local search algorithm.


## 3. Problem Definition

BCJSP is an intermediate problem between JSP and OSP; however, it can be explained simpler as a JSP’s generalized variant. BCJSP aims to find a feasible schedule that minimizes makespan (i.e., a total length of the schedule). The problem comes withm given machines (i.e., M1, M2, …, Mm) and n given jobs (i.e., J1, J2, …, Jn). At the beginning (i.e., time 0), all jobs have already been arrived, and all machines have not yet been occupied. Each job Ji (where i = 1, 2, …, n) consists of m operations (i.e., Oi1, Oi2, …, Oim). Each operation must be processed by a predetermined machine with a predetermined processing time. Each machine cannot process more than one operation at a time, and it cannot be stopped or paused during processing an operation. In other words, an operation preemption is not allowed. BCJSP differs from JSP in that an operation-precedence-relation chain of each job Ji (where i = 1, 2, …, n) is circular and bidirectional, as shown in Figure 1.Figure 1
A diagram of the operation-precedence-relation chain of the jobJi in BCJSP.Figure1 shows the relationships of the operations Oi1, Oi2, …, Oim of the job Ji in BCJSP. For each job Ji, let the precedence relations of Oi1, Oi2, …, Oim be all together connected as a circular chain. It means that any operation from Oi1 to Oim can be selected as the start operation of the job Ji (i.e., the operation processed first in the job Ji). Then, to complete the job Ji, the remaining operations in the circular chain must be processed one-by-one in either a clockwise or counterclockwise direction. In Figure 1, the operations connected together by green arrows present the circular operation-precedence-relation chain in clockwise direction, while those by blue arrows present the chain in counterclockwise direction.A BCJSP instance can be divided into (2m)n JSP instances as all of its subproblems. Each subproblem is generated from the BCJSP instance by assigning a specific start operation and a specific operation-precedence-relation direction into every job. To generate a subproblem, let Oik be the start operation of the job Ji, which is selected from any operation of Oi1, Oi2, …, Oim. Then, let the operation-precedence-relation direction of the job Ji be selected from either clockwise or counterclockwise. If the clockwise direction is selected, let the operation-precedence-relation chain of the job Ji be Oik ⇒ Oik+1 ⇒ … ⇒ Oim ⇒ Oi1 ⇒ … ⇒ Oik−1; otherwise, let it be Oik ⇒ Oik−1 ⇒ … ⇒ Oi1 ⇒ Oim ⇒ … ⇒ Oik+1. In this paper, D ⇒ E means that D must be finished before E can be started.To clarify the above paragraph, consider a BCJSP instance that has three machines (i.e.,M1, M2, M3) and two jobs (i.e., J1 and J2). Each job Ji (where i = 1 and 2) then consists of three operations (i.e., Oi1, Oi2, and Oi3). To generate a subproblem, there are six options for the job J1’s operation-precedence-relation chain: (1) O11 ⇒ O12 ⇒ O13, (2) O12 ⇒ O13 ⇒ O11, (3) O13 ⇒ O11 ⇒ O12, (4) O13 ⇒ O12 ⇒ O11, (5) O12 ⇒ O11 ⇒ O13, and (6) O11 ⇒ O13 ⇒ O12. In addition, there are six options for the job J2’s operation-precedence-relation chain: (1) O21 ⇒ O22 ⇒ O23, (2) O22 ⇒ O23 ⇒ O21, (3) O23 ⇒ O21 ⇒ O22, (4) O23 ⇒ O22 ⇒ O21, (5) O22 ⇒ O21 ⇒ O23, and (6) O21 ⇒ O23 ⇒ O22. Of each job, the first three options are generated in clockwise direction, while the last three options are generated in counterclockwise direction. Based on the six options of each job, this BCJSP instance can be divided into 36 JSP instances as all of its subproblems.BCJSP is a generalization of JSP and is also much more complex than JSP. Every single BCJSP instance can be divided into (2m)n JSP instances as all of its subproblems. Because JSP with m = n = 3 has been proven to be NP-hard [5], BCJSP with m ≥ 3 and n ≥ 3 thus belongs to a class of NP-hard problems. In the literature, no algorithms excepting MUL-B and MUL-T have been developed for BCJSP. Although the existing JSP-solving algorithms without modifications can be used to solve BCJSP, they may not perform well on BCJSP. This is because, with the same m and n, a solution space of BCJSP is much larger than that of JSP.


## 4. Methods

As mentioned, MUL represents the proposed multilevel metaheuristic for solving BCJSP. It consists of BOT, MID, and TOP algorithms in its bottom, middle, and top levels, respectively. BOT is a local search algorithm, modified from LOSAP [16], for solving subproblems of the BCJSP instance. Each subproblem is a JSP instance modified from the BCJSP instance by assigning a specific start operation and a specific operation-precedence-relation direction into every job. MID, as a variant of MUPLA [16], is a population-based metaheuristic for controlling BOT’s input parameters. Another function of MID is to transfer the start operation and the operation-precedence-relation direction of every job from TOP into BOT. TOP is a population-based metaheuristic developed based on the framework of MUPLA [16]. TOP is used to control the start operation and the operation-precedence-relation direction of every job in the BCJSP instance. If requested, TOP can also control the MID’s input parameters as an extra optional function.In this paper, there are two variants of MUL, i.e., the base-specification MUL (MUL-B) and the top-specification MUL (MUL-T). MUL-B is the MUL whose TOP controls only the start operation and the operation-precedence-relation direction of every job in BCJSP. MUL-T is the MUL whose TOP controls the start operation and operation-precedence-relation direction of every job and also the MID’s input parameters. The details of BOT, MID, and TOP are described in Sections4.1–4.3, respectively.


### 4.1. BOT Algorithm

BOT is a local search algorithm for solving subproblems of the being-solved BCJSP instance; each subproblem is a JSP instance. BOT generates each subproblem from the BCJSP instance by assigning a specific start operation and a specific operation-precedence-relation direction into every job. LetAi and Bi represent the start operation and the operation-precedence-relation direction, respectively, of the job Ji (where i = 1, 2, …, n). For each job Ji, Ai can be any operation selected from Oi1, Oi2, …, Oim; in addition, Bi can be either a clockwise or counterclockwise direction. In this paper, BOT receives Ai and Bi from TOP via MID.To illustrate how to useAi and Bi, assume A1 = O12, A2 = O23, A3 = O31, B1 = counterclockwise, B2 = clockwise, and B3 = counterclockwise be assigned into a 2-machine/3-job BCJSP instance. By assigning A1 = O12 and B1 = counterclockwise, the job J1’s operation-precedence-relation chain becomes O12 ⇒ O11 ⇒ O13. By assigning A2 = O23 and B2 = clockwise, the job J2’s operation-precedence-relation chain becomes O23 ⇒ O21 ⇒ O22. By assigning A3 = O31 and B3 = counterclockwise, the job J3’s operation-precedence-relation chain becomes O31 ⇒ O33 ⇒ O32. As a result, a subproblem of the BCJSP instance in the form of JSP has successfully been generated.After BOT has successfully generated a JSP instance (which is a subproblem of the BCJSP specified byAi and Bi), BOT acts as a local search algorithm for solving the JSP instance. BOT uses operation-based permutations [29, 43] to represent semiactive schedules, where an operation-based permutation is a permutation with m repetitions of the numbers 1, 2, …, n. However, the transformation into a schedule for the BCJSP’s subproblem differs from the transformation used by [29, 43] for the classical JSP. The difference is due to the specific order of operations in the operation-precedence-relation chain assigned by Ai and Bi. For example, on a 2-machine/3-job BCJSP instance, assume a given permutation be (2, 1, 2, 3, 1, 1, 3, 3, 2). In addition, assume A1 = O12, A2 = O23, A3 = O31, B1 = counterclockwise, B2 = clockwise, and B3 = counterclockwise. From the given permutation, BOT constructs a semiactive schedule in the order of O23, O12, O21, O31, O11, O13, O33, O32, and O22. Notice that the schedule is not constructed in the order of O21, O11, O22, O31, O12, O13, O32, O33, and O23 like that used for the classical JSP.BOT, as modified from LOSAP [16], improves its solutions by using PT and PN. Let PT represent the perturbation operator, and let PN ≡ (PNf, PNs) represent the ordered pair of the first neighbor operator (PNf) and the second neighbor operator (PNs). BOT offers five options for PT, i.e., n-medium swap, n-large swap, n-medium inverse, n-large insert, and n-medium insert. In addition, BOT offers four options for PN ≡ (PNf, PNs), i.e., (1-small inverse, 1-medium insert), (1-large swap, 1-large insert), (1-medium swap, 1-medium insert), and (1-small swap, 1-small insert).In the names of the above-mentioned operators, the number in front of the hyphen sign indicates the number of repeated uses of the operator mentioned in back of the hyphen sign. For example, then-medium inverse operator is to use the medium inverse operator n times on a permutation. In addition, the words small, medium, and large are used to restrict the value of v from h (note that the uses of h and v for operators are already reviewed in Section 2). Let h and v be two different random integers within [1, mn], where mn is the number of all operations in the BCJSP instance. The words small and medium then provide additional limitations on generating v as follows: v must be generated within [h − 4, h + 4] for small, while v must be generated within [h − 0.2mn, h + 0.2mn] for medium. For large, there are no additional limitations.The procedure of BOT is presented in Algorithm1, and its flowchart is presented in Figure 2. The parameters and abbreviations used in Algorithm 1 and Figure 2 are defined as follows:(i)
Letm and n, respectively, be the number of all machines and the number of all jobs in BCJSP. Thus, mn is the number of all operations in BCJSP.(ii)
LetAi ∈ {Oi1, Oi2, …, Oim} represent the start operation of the job Ji.(iii)
LetBi ∈ {clockwise, counterclockwise} represent the operation-precedence-relation direction of the job Ji.(iv)
LetPT and P stand for the perturbation operator and the start operation-based permutation, respectively.(v)
LetPN ≡ (PNf, PNs) represent the ordered pair of the first neighbor operator (PNf) and the second neighbor operator (PNs).(vi)
LetPR be the probability of selecting the first neighbor operator (PNf) of PN. Consequently, the probability of selecting the second neighbor operator (PNs) is equal to unity minus PR.(vii)
LetP0 (which is a permutation with m repetitions of the numbers 1, 2, …, n) stand for the current best-found operation-based permutation.(viii)
Let Π0 be the permutation of mn operations decoded from P0.(ix)
LetS0 stand for the current best-found schedule decoded from Π0. In addition, let Makespan(S0) represent the makespan of S0.(x)
LetP1 (which is a permutation with m repetitions of the numbers 1, 2, …, n) stand for the current neighbor operation-based permutation.(xi)
Let Π1 be the permutation of mn operations decoded from P1.(xii)
LetS1 stand for the current neighbor schedule decoded from Π1. In addition, let Makespan(S1) represent the makespan of S1.Algorithm 1: The procedure of BOT.
(1)
Receive values of BOT’s input parameters (i.e.,PT, PN, PR, and P) from MID. In addition, receive Ai and Bi (where i = 1, 2, …, n) from MID.(2)
To generate a subproblem of the BCJSP instance, let the start operation and the operation-precedence-relation direction be assigned to every job by using Steps 2.1 to 2.4.(2.1) Leti ← 1.(2.2) LetOik ← Ai.(2.3) IfBi = clockwise, let the job Ji’s operation-precedence-relation chain be Oik ⇒ Oik+1 ⇒ … ⇒ Oim ⇒ Oi1 ⇒ Oi2 ⇒ … ⇒ Oik−1. Otherwise, let it be Oik ⇒ Oik−1 ⇒ … ⇒ Oi1 ⇒ Oim ⇒ Oim−1 ⇒ … ⇒ Oik+1.(2.4) Ifi < n, let i ← i + 1 and repeat from Step 2.2. Otherwise, go to Step 3.(3)
Generate an initialP0 by using PT on P. Then, transform P0 into S0 by using Steps 3.1 and 3.2.(3.1) Generate Π0 by changing the j-th repetition of the number i in P0 into the operation listed in the j-th order of the job Ji’s operation-precedence-relation chain. (Note that the job Ji’s operation-precedence-relation chain is given in Step 2.)(3.2) ConstructS0 by assigning the operations in the order given by Π0 (from left to right) into a timetable. In the timetable, each operation must be assigned to its predetermined machine at its earliest possible start time. (Note that the earliest possible start time of each operation is the maximum between the completion time of its immediate-predecessor operation in its job and the completion time of the current latest operation on its machine.)(4)
Find a local optimal schedule by using Steps 4.1 to 4.3.(4.1) Letr ← 0.(4.2) Randomly generateu ∼ U[0, 1). If u ≤ PR, then generate P1 by using PNf on P0; otherwise, generate P1 by using PNs on P0. Then, transform P1 into S1 by using Steps 4.2.1 and 4.2.2.(4.2.1) Generate Π1 by changing the j-th repetition of the number i in P1 into the operation listed in the j-th order of the job Ji’s operation-precedence-relation chain.(4.2.2) ConstructS1 by assigning the operations in the order given by Π1 (from left to right) into a timetable. In the timetable, each operation must be assigned to its predetermined machine at its earliest possible start time.(4.3) UpdateP0, S0, and r by using Steps 4.3.1 to 4.3.3.(4.3.1) IfMakespan(S1) < Makespan(S0), let P0 ← P1 and S0 ← S1, and repeat from Step 4.1.(4.3.2) IfMakespan(S1) = Makespan(S0), let P0 ← P1 and S0 ← S1, and repeat from Step 4.2.(4.3.3) IfMakespan(S1) > Makespan(S0), let r ← r + 1. Then, repeat from Step 4.2 if r < (mn)2/50; otherwise, go to Step 5.(5)
ReturnP0 and S0 as the final (best-found) operation-based permutation and the final (best-found) schedule, respectively, to MID.Figure 2
A flowchart of BOT.Although there are two proposed variants of MUL (i.e., MUL-B and MUL-T), the procedures of BOTs in MUL-B and MUL-T are both identical to Algorithm1. The differences between MUL-B and MUL-T are in their MIDs and TOPs.


### 4.2. MID Algorithm

MID is a population-based metaheuristic modified from MUPLA [16]. It is a channel to transfer Ai and Bi (where i = 1, 2, …, n) from TOP into BOT. However, a main function of MID is to be a parameter controller for BOT. At the t-th iteration, the MID’s population contains N members, i.e., C1(t), C2(t), …, CN(t). For g=1 to N, let Cgt≡ptgt,pngt,prgt,pgt represent a value combination of the BOT’s input parameters PT, PN, PR, and P, respectively. Each of ptgt+1, pngt+1, and prgt+1 is updated from its old value via two opposite-direction vectors. The first vector’s direction is toward the memorized best-found value, whereas the second vector’s direction is away from it. Differently, pgt+1 is set to the final operation-based permutation returned from the BOT with Cgt-given input-parameter values.The procedure of MID is presented in Algorithm2, and its flowchart is presented in Figure 3. The following list presents the definitions of parameters and abbreviations used in Algorithm 2 and Figure 3. In addition, the transformation (i.e., decoding method) of each member of Cgt is also given:(i)
Letn be the number of all jobs in BCJSP.(ii)
LetN be the number of all members in the MID’s population.(iii)
LetCgt≡ptgt,pngt,prgt,pgt represent the g-th member (where g = 1, 2, …, N) in the MID’s population at the t-th iteration. In addition, let ScoreCgt stand for the performance score of Cgt. Note that the lower the performance score, the better the performance.(iv)
Letptgt ∈ ℝ represent the perturbation operator (PT) of BOT. Equation (1) is used to transform ptgt into PT.(v)
Letpngt ∈ ℝ represent the ordered pair of the first and second neighbor operators (PN) of BOT. Equation (2) is used to transform pngt into PN.(vi)
Letprgt ∈ ℝ represent the probability of selecting the first neighbor operator (PR) of BOT. In the transformation, let PR ← prgt if 0 ≤ prgt ≤ 1; in addition, let PR ← 0 if prgt < 0, and let PR ← 1 if prgt > 1.(vii)
Letpgt represent the start operation-based permutation (P) of BOT, and let it be a member of all possible operation-based permutations. In the transformation, let P ← pgt.(viii)
For updatingptgt+1, let ypt and wpt be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if ptgt = ptbest, let wpt be the controlling weights of the maximum magnitudes of both vectors.(ix)
For updatingpngt+1, let ypn and wpn be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if pngt = pnbest, let wpn be the controlling weights of the maximum magnitudes of both vectors.(x)
For updatingprgt+1, let ypr and wpr be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if prgt = prbest, let wpr be the controlling weights of the maximum magnitudes of both vectors.(xi)
LetP0 and S0, respectively, stand for the final operation-based permutation and the final schedule returned from BOT. In addition, let Makespan(S0) stand for the makespan of S0.(xii)
LetCbest ≡ (ptbest, pnbest, prbest, pbest) and Sbest stand for the best Cgt and the best S0, respectively, ever found by the population. In addition, let Score(Cbest) stand for the performance score of Cbest.(1)PT=n‐medium swap ifptgt<0.20,n‐large swap if0.20≤ptgt<0.40,n‐medium inverse if0.40≤ptgt<0.60,n‐large insert if0.60≤ptgt<0.80,n‐medium insert ifptgt≥0.80,(2)PN=1‐small inverse,1‐medium insertifpngt<0.25,1‐large swap,1‐large insertif 0.25≤pngt<0.50,1‐medium swap,1‐medium insertif0.50≤pngt<0.75,1‐small swap,1‐small insertifpngt≥0.75.Algorithm 2: The procedure of MID.
(1)
ReceiveA1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt,wpn, and wpr from TOP.(2)
Lett ← 1 and Score(Cbest) ← +∞.(3)
GenerateCgt by randomly generating ptgt, pngt, and prgt ∼ U0,1 and randomly generating pgt from any possible operation-based permutation (g = 1, 2, …, N).(4)
EvaluateScoreCgt and update pgt+1, Cbest, and Sbest by using Steps 4.1 to 4.6.(4.1) Letg ← 1.(4.2) TransformCgt into the values of PT, PN, PR, and P of BOT.(4.3) Execute BOT with the values ofPT, PN, PR, and P (taken from Step 4.2) and the values of A1, A2, …, An, B1, B2, …, Bn (taken from Step 1). This is done for receiving P0 and S0 from BOT.(4.4) LetScoreCgt ← Makespan(S0), and let pgt+1 ← P0.(4.5) IfScoreCgt ≤ Score(Cbest), let Cbest ← Cgt, Score(Cbest) ← ScoreCgt, and Sbest ← S0.(4.6) Ifg < N, let g ← g + 1 and repeat from Step 4.2. Otherwise, go to Step 5.(5)
Updateptgt+1, pngt+1, and prgt+1, where g = 1, 2, …, N, by using Steps 5.1 to 5.3.(5.1) Letg ← 1.(5.2) Generateptgt+1, pngt+1, and prgt+1 by below three equations, respectively. Let u1 and u2 ∼ U0,1.ptgt+1=ptgt+0.02+0.01yptu1−0.005+0.01wptu2ifptgt<ptbest,ptgt−0.02+0.01yptu1+0.005+0.01wptu2ifptgt>ptbest,ptgt+0.005+0.01wptu1−0.005+0.01wptu2ifptgt=ptbest.pngt+1=pngt+0.02+0.01ypnu1−0.005+0.01wpnu2ifpngt<pnbest,pngt−0.02+0.01ypnu1+0.005+0.01wpnu2ifpngt>pnbest,pngt+0.005+0.01wpnu1−0.005+0.01wpnu2ifpngt=pnbest.prgt+1=prgt+0.02+0.01ypru1−0.005+0.01wpru2ifprgt<prbest,prgt−0.02+0.01ypru1+0.005+0.01wpru2ifprgt>prbest,prgt+0.005+0.01wpru1−0.005+0.01wpru2ifprgt=prbest.(5.3) Ifg < N, let g ← g + 1 and repeat from Step 5.2. Otherwise, go to Step 6.(6)
If the stopping criterion is not met, lett ← t + 1 and repeat from Step 4. Otherwise, return Sbest to TOP.Figure 3
A flowchart of MID.In Algorithm2, MID starts its procedure by receiving Ai, Bi (where i = 1, 2, …, n), and its input-parameter values (i.e., ypt, ypn, ypr, wpt, wpn, and wpr) from TOP. MID assigns t ← 1 and Score(Cbest) ← +∞; then, it generates Cgt randomly. To solve a BCJSP subproblem specified by Ai and Bi, MID then starts a repeated loop by executing BOT N times. In the g-th execution (where g = 1, 2, …, N), BOT is executed with Cgt-given parameter values to return P0 and S0; then, let ScoreCgt ← Makespan(S0) and pgt+1 ← P0. If MID finds any Cgt better than or equal to Cbest, then let this Cgt and its corresponding S0 become a new Cbest and a new Sbest, respectively. After that, MID completes Cgt+1 by using the two opposite-direction vectors to generate each of ptgt+1, pngt+1, and prgt+1. If the stopping criterion is not met, MID assigns t ← t + 1 and starts the repeated loop’s next round.As mentioned earlier, there are two variants of MUL, i.e., the base-specification MUL (MUL-B) and the top-specification MUL (MUL-T). The difference between MUL-B and MUL-T in their MIDs is given as follows. In MUL-T, the input parameters (i.e.,ypt, ypn, ypr, wpt, wpn, and wpr) of its MID are controlled by TOP. This means MID in MUL-T is identical to Algorithm 2. Differently, these input-parameter values of MID in MUL-B are constants. The procedure of MID in MUL-B is thus modified from Algorithm 2 by removing ypt, ypn, ypr, wpt, wpn, and wpr from Step 1 and changing ypt, ypn, ypr, wpt, wpn, and wpr in Step 5.2 to constants. In this paper, the values of ypt, ypn, ypr, wpt, wpn, and wpr of MID in MUL-B all are set to 0.5, as mentioned again in Section 5.


### 4.3. TOP Algorithm

Like MID, TOP is developed based on the framework of MUPLA [16]. The main function of TOP is to control the start operation and the operation-precedence-relation direction of every job in the being-solved BCJSP instance. As previously mentioned, Ai and Bi represent the start operation and the operation-precedence-relation direction, respectively, of the job Ji (where i = 1, 2, …, n, and n is the number of all jobs in BCJSP). After assigning Ai and Bi, the BCJSP instance has become a JSP instance that is a subproblem of the BCJSP instance. In addition to the main function, TOP can control the MID’s input parameters, i.e., ypt, ypn, ypr, wpt, wpn, and wpr, as its optional extra function.At theτ-th iteration, the TOP’s population contains M members, i.e., ζ1τ,ζ2τ,…,ζMτ. For q = 1 to M, let ζqτ≡α1qτ,α2qτ,…,αnqτ, β1qτ,β2qτ,…,βnqτ, γ1qτ,γ2qτ,…,γ6qτ represent a value combination of A1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr, respectively. Each member of ζqτ+1, such as α1qτ+1, is usually updated from its old value via two opposite-direction vectors; however, it is occasionally regenerated by a reinitialization. For the two opposite-direction vectors, the first vector’s direction is toward the memorized best-found value, whereas the second vector’s direction is away from it.The procedure of TOP is presented in Algorithm3, and its flowchart is presented in Figure 4. The following list shows the definitions of parameters and abbreviations used in Algorithm 3 and Figure 4. In addition, the transformation (i.e., decoding method) of each member of ζqτ is also given:(i)
Letm and n, respectively, be the number of all machines and the number of all jobs in the being-solved BCJSP.(ii)
LetAi and Bi, respectively, stand for the start operation and the operation-precedence-relation direction of the job Ji.(iii)
LetM be the number of all members in the TOP’s population.(iv)
Letζqτ≡α1qτ,α2qτ,…,αnqτ, β1qτ,β2qτ,…,βnqτ, γ1qτ,γ2qτ,…,γ6qτrepresent the q-th member (where q = 1, 2, …, M) in the TOP’s population at the τ-th iteration. In addition, let Scoreζqτ stand for the performance score of ζqτ. Note that the lower the performance score, the better the performance.(v)
Letαiqτ∈ℝ represent Ai (where i = 1, 2, …, n). To transform αiqτ into Ai, let k ← the integer part of mαiqτ + 1. After that, reassign k ← 1 if k < 1, and reassign k ← m if k > m. Finally, let Ai ← Oik.(vi)
Letβiqτ ∈ ℝ represent Bi (where i = 1, 2, …, n). In the transformation, let Bi ← clockwise if βiqτ < 0.5, and let Bi ← counterclockwise otherwise.(vii)
Letγ1qτ, γ2qτ, γ3qτ, γ4qτ, γ5qτ, and γ6qτ ∈ R represent the MID’s ypt, ypn, ypr, wpt, wpn, and wpr, respectively. In their transformations, let ypt ← γ1qτ, ypn ← γ2qτ, ypr ← γ3qτ, wpt ← γ4qτ, wpn ← γ5qτ, and wpr ← γ6qτ.(viii)
LetSbest and Makespan(Sbest) stand for the best schedule returned from MID and its makespan, respectively.(ix)
Letζbest ≡ (α1best, α2best, …, αnbest, β1best, β2best, …, βnbest, γ1best, γ2best, …, γ6best) be the best ζqτ ever found by the population. In addition, let Score(ζbest) stand for the performance score of ζbest.(x)
LetZ represent the best schedule ever found by the TOP’s population.Algorithm 3: The procedure of TOP.
(1)
Receive information of the being-solved BCJSP instance from the user.(2)
Letτ ← 1 and Score(ζbest) ← +∞.(3)
Generateζqτ, where q = 1, 2, …, M, by randomly generating αiqτ, βiqτ, and γkqτ ∼ U0,1 (i = 1, 2, …, n; k = 1, 2, …, 6).(4)
EvaluateScoreζqτ and update ζbest and Z by using Steps 4.1 to 4.6.(4.1) Letq ← 1.(4.2) Transformζqτ into the values of A1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr.(4.3)  Execute MID with the values ofA1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr taken from Step 4.2. This is done for receiving Sbest from MID.(4.4) LetScoreζqτ ← Makespan(Sbest).(4.5) IfScoreζqτ ≤ Score(ζbest), then let ζbest ← ζqτ, Score(ζbest) ← Scoreζqτ, and Z ← Sbest.(4.6) Ifq < M, then let q ← q + 1 and repeat from Step 4.2. Otherwise, go to Step 5.(5)
Updateζqτ+1, where q = 1, 2, …, M, by using Steps 5.1 to 5.3.(5.1) Letq ← 1.(5.2) Ifτ mod 25 = 0, then randomly generate αiqτ+1, βiqτ+1, and γkqτ+1 ∼ U0,1, where i = 1, 2, …, n and k = 1, 2, …, 6. Otherwise, generate αiqτ+1, βiqτ+1, and γkqτ+1 by below three equations, respectively (i = 1, 2, …, n and k = 1, 2, …, 6). Let u1 and u2 ∼ U0,1.αiqτ+1=αiqτ+0.025u1−0.01u2ifαiqτ<αibest,αiqτ−0.025u1+0.01u2ifαiqτ>αibest,αiqτ+0.01u1−0.01u2ifαiqτ=αibest.βiqτ+1=βiqτ+0.025u1−0.01u2ifβiqτ<βibest,βiqτ−0.025u1+0.01u2ifβiqτ>βibest,βiqτ+0.01u1−0.01u2ifβiqτ=βibest.γkqτ+1=γkqτ+0.025u1−0.01u2ifγkqτ<γkbest,γkqτ−0.025u1+0.01u2ifγkqτ>γkbest,γkqτ+0.01u1−0.01u2ifγkqτ=γkbest.(5.3) Ifq < M, then let q ← q + 1 and repeat from Step 5.2. Otherwise, go to Step 6.(6)
If the stopping criterion is not met, then letτ ← τ+1 and repeat from Step 4. Otherwise, return Z to the user.Figure 4
A flowchart of TOP.In Algorithm3, TOP starts its procedure by receiving information of a BCJSP instance from the user. TOP assigns τ ← 1 and Score(ζbest) ← +∞; then, it generates ζqτ randomly. After that, TOP starts a repeated loop by executing MID M times. In the q-th execution (where q = 1, 2, …, M), MID is executed with ζqτ-given parameter values to return Sbest; then, let Scoreζqτ ← Makespan(Sbest). If TOP finds any ζqτ better than or equal to ζbest, then let this ζqτ and its corresponding Sbest become a new ζbest and a new Z, respectively. After that, TOP chooses to update each member of ζqτ+1 by either the two opposite-direction vectors or the reinitialization. If the stopping criterion is not met, TOP assigns τ←τ+1 and starts the repeated loop’s next round.As mentioned, there are two variants of MUL, i.e., MUL-B and MUL-T. The difference between MUL-B and MUL-T in their TOPs is given as follows. In MUL-T,ζqτ of its TOP’s population consists of αiqτ, βiqτ, and γkqτ. This means TOP in MUL-T is identical to Algorithm 3. In MUL-B, ζq(τ) of its TOP’s population consists of only αiqτ and βiqτ. It means that ζqτ of TOP in MUL-B is equivalent to α1qτ,α2qτ,…,αnqτ,β1qτ,β2qτ,…,βnqτ. Thus, the procedure of TOP in MUL-B is modified from Algorithm 3 by removing γkqτ from Step 3; removing ypt, ypn, ypr, wpt,wpn and wpr from Steps 4.2 and 4.3; and removing γkqτ+1 and its generating equation from Step 5.2.


## 4.1. BOT Algorithm

BOT is a local search algorithm for solving subproblems of the being-solved BCJSP instance; each subproblem is a JSP instance. BOT generates each subproblem from the BCJSP instance by assigning a specific start operation and a specific operation-precedence-relation direction into every job. LetAi and Bi represent the start operation and the operation-precedence-relation direction, respectively, of the job Ji (where i = 1, 2, …, n). For each job Ji, Ai can be any operation selected from Oi1, Oi2, …, Oim; in addition, Bi can be either a clockwise or counterclockwise direction. In this paper, BOT receives Ai and Bi from TOP via MID.To illustrate how to useAi and Bi, assume A1 = O12, A2 = O23, A3 = O31, B1 = counterclockwise, B2 = clockwise, and B3 = counterclockwise be assigned into a 2-machine/3-job BCJSP instance. By assigning A1 = O12 and B1 = counterclockwise, the job J1’s operation-precedence-relation chain becomes O12 ⇒ O11 ⇒ O13. By assigning A2 = O23 and B2 = clockwise, the job J2’s operation-precedence-relation chain becomes O23 ⇒ O21 ⇒ O22. By assigning A3 = O31 and B3 = counterclockwise, the job J3’s operation-precedence-relation chain becomes O31 ⇒ O33 ⇒ O32. As a result, a subproblem of the BCJSP instance in the form of JSP has successfully been generated.After BOT has successfully generated a JSP instance (which is a subproblem of the BCJSP specified byAi and Bi), BOT acts as a local search algorithm for solving the JSP instance. BOT uses operation-based permutations [29, 43] to represent semiactive schedules, where an operation-based permutation is a permutation with m repetitions of the numbers 1, 2, …, n. However, the transformation into a schedule for the BCJSP’s subproblem differs from the transformation used by [29, 43] for the classical JSP. The difference is due to the specific order of operations in the operation-precedence-relation chain assigned by Ai and Bi. For example, on a 2-machine/3-job BCJSP instance, assume a given permutation be (2, 1, 2, 3, 1, 1, 3, 3, 2). In addition, assume A1 = O12, A2 = O23, A3 = O31, B1 = counterclockwise, B2 = clockwise, and B3 = counterclockwise. From the given permutation, BOT constructs a semiactive schedule in the order of O23, O12, O21, O31, O11, O13, O33, O32, and O22. Notice that the schedule is not constructed in the order of O21, O11, O22, O31, O12, O13, O32, O33, and O23 like that used for the classical JSP.BOT, as modified from LOSAP [16], improves its solutions by using PT and PN. Let PT represent the perturbation operator, and let PN ≡ (PNf, PNs) represent the ordered pair of the first neighbor operator (PNf) and the second neighbor operator (PNs). BOT offers five options for PT, i.e., n-medium swap, n-large swap, n-medium inverse, n-large insert, and n-medium insert. In addition, BOT offers four options for PN ≡ (PNf, PNs), i.e., (1-small inverse, 1-medium insert), (1-large swap, 1-large insert), (1-medium swap, 1-medium insert), and (1-small swap, 1-small insert).In the names of the above-mentioned operators, the number in front of the hyphen sign indicates the number of repeated uses of the operator mentioned in back of the hyphen sign. For example, then-medium inverse operator is to use the medium inverse operator n times on a permutation. In addition, the words small, medium, and large are used to restrict the value of v from h (note that the uses of h and v for operators are already reviewed in Section 2). Let h and v be two different random integers within [1, mn], where mn is the number of all operations in the BCJSP instance. The words small and medium then provide additional limitations on generating v as follows: v must be generated within [h − 4, h + 4] for small, while v must be generated within [h − 0.2mn, h + 0.2mn] for medium. For large, there are no additional limitations.The procedure of BOT is presented in Algorithm1, and its flowchart is presented in Figure 2. The parameters and abbreviations used in Algorithm 1 and Figure 2 are defined as follows:(i)
Letm and n, respectively, be the number of all machines and the number of all jobs in BCJSP. Thus, mn is the number of all operations in BCJSP.(ii)
LetAi ∈ {Oi1, Oi2, …, Oim} represent the start operation of the job Ji.(iii)
LetBi ∈ {clockwise, counterclockwise} represent the operation-precedence-relation direction of the job Ji.(iv)
LetPT and P stand for the perturbation operator and the start operation-based permutation, respectively.(v)
LetPN ≡ (PNf, PNs) represent the ordered pair of the first neighbor operator (PNf) and the second neighbor operator (PNs).(vi)
LetPR be the probability of selecting the first neighbor operator (PNf) of PN. Consequently, the probability of selecting the second neighbor operator (PNs) is equal to unity minus PR.(vii)
LetP0 (which is a permutation with m repetitions of the numbers 1, 2, …, n) stand for the current best-found operation-based permutation.(viii)
Let Π0 be the permutation of mn operations decoded from P0.(ix)
LetS0 stand for the current best-found schedule decoded from Π0. In addition, let Makespan(S0) represent the makespan of S0.(x)
LetP1 (which is a permutation with m repetitions of the numbers 1, 2, …, n) stand for the current neighbor operation-based permutation.(xi)
Let Π1 be the permutation of mn operations decoded from P1.(xii)
LetS1 stand for the current neighbor schedule decoded from Π1. In addition, let Makespan(S1) represent the makespan of S1.Algorithm 1: The procedure of BOT.
(1)
Receive values of BOT’s input parameters (i.e.,PT, PN, PR, and P) from MID. In addition, receive Ai and Bi (where i = 1, 2, …, n) from MID.(2)
To generate a subproblem of the BCJSP instance, let the start operation and the operation-precedence-relation direction be assigned to every job by using Steps 2.1 to 2.4.(2.1) Leti ← 1.(2.2) LetOik ← Ai.(2.3) IfBi = clockwise, let the job Ji’s operation-precedence-relation chain be Oik ⇒ Oik+1 ⇒ … ⇒ Oim ⇒ Oi1 ⇒ Oi2 ⇒ … ⇒ Oik−1. Otherwise, let it be Oik ⇒ Oik−1 ⇒ … ⇒ Oi1 ⇒ Oim ⇒ Oim−1 ⇒ … ⇒ Oik+1.(2.4) Ifi < n, let i ← i + 1 and repeat from Step 2.2. Otherwise, go to Step 3.(3)
Generate an initialP0 by using PT on P. Then, transform P0 into S0 by using Steps 3.1 and 3.2.(3.1) Generate Π0 by changing the j-th repetition of the number i in P0 into the operation listed in the j-th order of the job Ji’s operation-precedence-relation chain. (Note that the job Ji’s operation-precedence-relation chain is given in Step 2.)(3.2) ConstructS0 by assigning the operations in the order given by Π0 (from left to right) into a timetable. In the timetable, each operation must be assigned to its predetermined machine at its earliest possible start time. (Note that the earliest possible start time of each operation is the maximum between the completion time of its immediate-predecessor operation in its job and the completion time of the current latest operation on its machine.)(4)
Find a local optimal schedule by using Steps 4.1 to 4.3.(4.1) Letr ← 0.(4.2) Randomly generateu ∼ U[0, 1). If u ≤ PR, then generate P1 by using PNf on P0; otherwise, generate P1 by using PNs on P0. Then, transform P1 into S1 by using Steps 4.2.1 and 4.2.2.(4.2.1) Generate Π1 by changing the j-th repetition of the number i in P1 into the operation listed in the j-th order of the job Ji’s operation-precedence-relation chain.(4.2.2) ConstructS1 by assigning the operations in the order given by Π1 (from left to right) into a timetable. In the timetable, each operation must be assigned to its predetermined machine at its earliest possible start time.(4.3) UpdateP0, S0, and r by using Steps 4.3.1 to 4.3.3.(4.3.1) IfMakespan(S1) < Makespan(S0), let P0 ← P1 and S0 ← S1, and repeat from Step 4.1.(4.3.2) IfMakespan(S1) = Makespan(S0), let P0 ← P1 and S0 ← S1, and repeat from Step 4.2.(4.3.3) IfMakespan(S1) > Makespan(S0), let r ← r + 1. Then, repeat from Step 4.2 if r < (mn)2/50; otherwise, go to Step 5.(5)
ReturnP0 and S0 as the final (best-found) operation-based permutation and the final (best-found) schedule, respectively, to MID.Figure 2
A flowchart of BOT.Although there are two proposed variants of MUL (i.e., MUL-B and MUL-T), the procedures of BOTs in MUL-B and MUL-T are both identical to Algorithm1. The differences between MUL-B and MUL-T are in their MIDs and TOPs.


## 4.2. MID Algorithm

MID is a population-based metaheuristic modified from MUPLA [16]. It is a channel to transfer Ai and Bi (where i = 1, 2, …, n) from TOP into BOT. However, a main function of MID is to be a parameter controller for BOT. At the t-th iteration, the MID’s population contains N members, i.e., C1(t), C2(t), …, CN(t). For g=1 to N, let Cgt≡ptgt,pngt,prgt,pgt represent a value combination of the BOT’s input parameters PT, PN, PR, and P, respectively. Each of ptgt+1, pngt+1, and prgt+1 is updated from its old value via two opposite-direction vectors. The first vector’s direction is toward the memorized best-found value, whereas the second vector’s direction is away from it. Differently, pgt+1 is set to the final operation-based permutation returned from the BOT with Cgt-given input-parameter values.The procedure of MID is presented in Algorithm2, and its flowchart is presented in Figure 3. The following list presents the definitions of parameters and abbreviations used in Algorithm 2 and Figure 3. In addition, the transformation (i.e., decoding method) of each member of Cgt is also given:(i)
Letn be the number of all jobs in BCJSP.(ii)
LetN be the number of all members in the MID’s population.(iii)
LetCgt≡ptgt,pngt,prgt,pgt represent the g-th member (where g = 1, 2, …, N) in the MID’s population at the t-th iteration. In addition, let ScoreCgt stand for the performance score of Cgt. Note that the lower the performance score, the better the performance.(iv)
Letptgt ∈ ℝ represent the perturbation operator (PT) of BOT. Equation (1) is used to transform ptgt into PT.(v)
Letpngt ∈ ℝ represent the ordered pair of the first and second neighbor operators (PN) of BOT. Equation (2) is used to transform pngt into PN.(vi)
Letprgt ∈ ℝ represent the probability of selecting the first neighbor operator (PR) of BOT. In the transformation, let PR ← prgt if 0 ≤ prgt ≤ 1; in addition, let PR ← 0 if prgt < 0, and let PR ← 1 if prgt > 1.(vii)
Letpgt represent the start operation-based permutation (P) of BOT, and let it be a member of all possible operation-based permutations. In the transformation, let P ← pgt.(viii)
For updatingptgt+1, let ypt and wpt be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if ptgt = ptbest, let wpt be the controlling weights of the maximum magnitudes of both vectors.(ix)
For updatingpngt+1, let ypn and wpn be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if pngt = pnbest, let wpn be the controlling weights of the maximum magnitudes of both vectors.(x)
For updatingprgt+1, let ypr and wpr be the controlling weights of the maximum magnitudes of the first and second vectors, respectively. However, if prgt = prbest, let wpr be the controlling weights of the maximum magnitudes of both vectors.(xi)
LetP0 and S0, respectively, stand for the final operation-based permutation and the final schedule returned from BOT. In addition, let Makespan(S0) stand for the makespan of S0.(xii)
LetCbest ≡ (ptbest, pnbest, prbest, pbest) and Sbest stand for the best Cgt and the best S0, respectively, ever found by the population. In addition, let Score(Cbest) stand for the performance score of Cbest.(1)PT=n‐medium swap ifptgt<0.20,n‐large swap if0.20≤ptgt<0.40,n‐medium inverse if0.40≤ptgt<0.60,n‐large insert if0.60≤ptgt<0.80,n‐medium insert ifptgt≥0.80,(2)PN=1‐small inverse,1‐medium insertifpngt<0.25,1‐large swap,1‐large insertif 0.25≤pngt<0.50,1‐medium swap,1‐medium insertif0.50≤pngt<0.75,1‐small swap,1‐small insertifpngt≥0.75.Algorithm 2: The procedure of MID.
(1)
ReceiveA1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt,wpn, and wpr from TOP.(2)
Lett ← 1 and Score(Cbest) ← +∞.(3)
GenerateCgt by randomly generating ptgt, pngt, and prgt ∼ U0,1 and randomly generating pgt from any possible operation-based permutation (g = 1, 2, …, N).(4)
EvaluateScoreCgt and update pgt+1, Cbest, and Sbest by using Steps 4.1 to 4.6.(4.1) Letg ← 1.(4.2) TransformCgt into the values of PT, PN, PR, and P of BOT.(4.3) Execute BOT with the values ofPT, PN, PR, and P (taken from Step 4.2) and the values of A1, A2, …, An, B1, B2, …, Bn (taken from Step 1). This is done for receiving P0 and S0 from BOT.(4.4) LetScoreCgt ← Makespan(S0), and let pgt+1 ← P0.(4.5) IfScoreCgt ≤ Score(Cbest), let Cbest ← Cgt, Score(Cbest) ← ScoreCgt, and Sbest ← S0.(4.6) Ifg < N, let g ← g + 1 and repeat from Step 4.2. Otherwise, go to Step 5.(5)
Updateptgt+1, pngt+1, and prgt+1, where g = 1, 2, …, N, by using Steps 5.1 to 5.3.(5.1) Letg ← 1.(5.2) Generateptgt+1, pngt+1, and prgt+1 by below three equations, respectively. Let u1 and u2 ∼ U0,1.ptgt+1=ptgt+0.02+0.01yptu1−0.005+0.01wptu2ifptgt<ptbest,ptgt−0.02+0.01yptu1+0.005+0.01wptu2ifptgt>ptbest,ptgt+0.005+0.01wptu1−0.005+0.01wptu2ifptgt=ptbest.pngt+1=pngt+0.02+0.01ypnu1−0.005+0.01wpnu2ifpngt<pnbest,pngt−0.02+0.01ypnu1+0.005+0.01wpnu2ifpngt>pnbest,pngt+0.005+0.01wpnu1−0.005+0.01wpnu2ifpngt=pnbest.prgt+1=prgt+0.02+0.01ypru1−0.005+0.01wpru2ifprgt<prbest,prgt−0.02+0.01ypru1+0.005+0.01wpru2ifprgt>prbest,prgt+0.005+0.01wpru1−0.005+0.01wpru2ifprgt=prbest.(5.3) Ifg < N, let g ← g + 1 and repeat from Step 5.2. Otherwise, go to Step 6.(6)
If the stopping criterion is not met, lett ← t + 1 and repeat from Step 4. Otherwise, return Sbest to TOP.Figure 3
A flowchart of MID.In Algorithm2, MID starts its procedure by receiving Ai, Bi (where i = 1, 2, …, n), and its input-parameter values (i.e., ypt, ypn, ypr, wpt, wpn, and wpr) from TOP. MID assigns t ← 1 and Score(Cbest) ← +∞; then, it generates Cgt randomly. To solve a BCJSP subproblem specified by Ai and Bi, MID then starts a repeated loop by executing BOT N times. In the g-th execution (where g = 1, 2, …, N), BOT is executed with Cgt-given parameter values to return P0 and S0; then, let ScoreCgt ← Makespan(S0) and pgt+1 ← P0. If MID finds any Cgt better than or equal to Cbest, then let this Cgt and its corresponding S0 become a new Cbest and a new Sbest, respectively. After that, MID completes Cgt+1 by using the two opposite-direction vectors to generate each of ptgt+1, pngt+1, and prgt+1. If the stopping criterion is not met, MID assigns t ← t + 1 and starts the repeated loop’s next round.As mentioned earlier, there are two variants of MUL, i.e., the base-specification MUL (MUL-B) and the top-specification MUL (MUL-T). The difference between MUL-B and MUL-T in their MIDs is given as follows. In MUL-T, the input parameters (i.e.,ypt, ypn, ypr, wpt, wpn, and wpr) of its MID are controlled by TOP. This means MID in MUL-T is identical to Algorithm 2. Differently, these input-parameter values of MID in MUL-B are constants. The procedure of MID in MUL-B is thus modified from Algorithm 2 by removing ypt, ypn, ypr, wpt, wpn, and wpr from Step 1 and changing ypt, ypn, ypr, wpt, wpn, and wpr in Step 5.2 to constants. In this paper, the values of ypt, ypn, ypr, wpt, wpn, and wpr of MID in MUL-B all are set to 0.5, as mentioned again in Section 5.


## 4.3. TOP Algorithm

Like MID, TOP is developed based on the framework of MUPLA [16]. The main function of TOP is to control the start operation and the operation-precedence-relation direction of every job in the being-solved BCJSP instance. As previously mentioned, Ai and Bi represent the start operation and the operation-precedence-relation direction, respectively, of the job Ji (where i = 1, 2, …, n, and n is the number of all jobs in BCJSP). After assigning Ai and Bi, the BCJSP instance has become a JSP instance that is a subproblem of the BCJSP instance. In addition to the main function, TOP can control the MID’s input parameters, i.e., ypt, ypn, ypr, wpt, wpn, and wpr, as its optional extra function.At theτ-th iteration, the TOP’s population contains M members, i.e., ζ1τ,ζ2τ,…,ζMτ. For q = 1 to M, let ζqτ≡α1qτ,α2qτ,…,αnqτ, β1qτ,β2qτ,…,βnqτ, γ1qτ,γ2qτ,…,γ6qτ represent a value combination of A1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr, respectively. Each member of ζqτ+1, such as α1qτ+1, is usually updated from its old value via two opposite-direction vectors; however, it is occasionally regenerated by a reinitialization. For the two opposite-direction vectors, the first vector’s direction is toward the memorized best-found value, whereas the second vector’s direction is away from it.The procedure of TOP is presented in Algorithm3, and its flowchart is presented in Figure 4. The following list shows the definitions of parameters and abbreviations used in Algorithm 3 and Figure 4. In addition, the transformation (i.e., decoding method) of each member of ζqτ is also given:(i)
Letm and n, respectively, be the number of all machines and the number of all jobs in the being-solved BCJSP.(ii)
LetAi and Bi, respectively, stand for the start operation and the operation-precedence-relation direction of the job Ji.(iii)
LetM be the number of all members in the TOP’s population.(iv)
Letζqτ≡α1qτ,α2qτ,…,αnqτ, β1qτ,β2qτ,…,βnqτ, γ1qτ,γ2qτ,…,γ6qτrepresent the q-th member (where q = 1, 2, …, M) in the TOP’s population at the τ-th iteration. In addition, let Scoreζqτ stand for the performance score of ζqτ. Note that the lower the performance score, the better the performance.(v)
Letαiqτ∈ℝ represent Ai (where i = 1, 2, …, n). To transform αiqτ into Ai, let k ← the integer part of mαiqτ + 1. After that, reassign k ← 1 if k < 1, and reassign k ← m if k > m. Finally, let Ai ← Oik.(vi)
Letβiqτ ∈ ℝ represent Bi (where i = 1, 2, …, n). In the transformation, let Bi ← clockwise if βiqτ < 0.5, and let Bi ← counterclockwise otherwise.(vii)
Letγ1qτ, γ2qτ, γ3qτ, γ4qτ, γ5qτ, and γ6qτ ∈ R represent the MID’s ypt, ypn, ypr, wpt, wpn, and wpr, respectively. In their transformations, let ypt ← γ1qτ, ypn ← γ2qτ, ypr ← γ3qτ, wpt ← γ4qτ, wpn ← γ5qτ, and wpr ← γ6qτ.(viii)
LetSbest and Makespan(Sbest) stand for the best schedule returned from MID and its makespan, respectively.(ix)
Letζbest ≡ (α1best, α2best, …, αnbest, β1best, β2best, …, βnbest, γ1best, γ2best, …, γ6best) be the best ζqτ ever found by the population. In addition, let Score(ζbest) stand for the performance score of ζbest.(x)
LetZ represent the best schedule ever found by the TOP’s population.Algorithm 3: The procedure of TOP.
(1)
Receive information of the being-solved BCJSP instance from the user.(2)
Letτ ← 1 and Score(ζbest) ← +∞.(3)
Generateζqτ, where q = 1, 2, …, M, by randomly generating αiqτ, βiqτ, and γkqτ ∼ U0,1 (i = 1, 2, …, n; k = 1, 2, …, 6).(4)
EvaluateScoreζqτ and update ζbest and Z by using Steps 4.1 to 4.6.(4.1) Letq ← 1.(4.2) Transformζqτ into the values of A1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr.(4.3)  Execute MID with the values ofA1, A2, …, An, B1, B2, …, Bn, ypt, ypn, ypr, wpt, wpn, and wpr taken from Step 4.2. This is done for receiving Sbest from MID.(4.4) LetScoreζqτ ← Makespan(Sbest).(4.5) IfScoreζqτ ≤ Score(ζbest), then let ζbest ← ζqτ, Score(ζbest) ← Scoreζqτ, and Z ← Sbest.(4.6) Ifq < M, then let q ← q + 1 and repeat from Step 4.2. Otherwise, go to Step 5.(5)
Updateζqτ+1, where q = 1, 2, …, M, by using Steps 5.1 to 5.3.(5.1) Letq ← 1.(5.2) Ifτ mod 25 = 0, then randomly generate αiqτ+1, βiqτ+1, and γkqτ+1 ∼ U0,1, where i = 1, 2, …, n and k = 1, 2, …, 6. Otherwise, generate αiqτ+1, βiqτ+1, and γkqτ+1 by below three equations, respectively (i = 1, 2, …, n and k = 1, 2, …, 6). Let u1 and u2 ∼ U0,1.αiqτ+1=αiqτ+0.025u1−0.01u2ifαiqτ<αibest,αiqτ−0.025u1+0.01u2ifαiqτ>αibest,αiqτ+0.01u1−0.01u2ifαiqτ=αibest.βiqτ+1=βiqτ+0.025u1−0.01u2ifβiqτ<βibest,βiqτ−0.025u1+0.01u2ifβiqτ>βibest,βiqτ+0.01u1−0.01u2ifβiqτ=βibest.γkqτ+1=γkqτ+0.025u1−0.01u2ifγkqτ<γkbest,γkqτ−0.025u1+0.01u2ifγkqτ>γkbest,γkqτ+0.01u1−0.01u2ifγkqτ=γkbest.(5.3) Ifq < M, then let q ← q + 1 and repeat from Step 5.2. Otherwise, go to Step 6.(6)
If the stopping criterion is not met, then letτ ← τ+1 and repeat from Step 4. Otherwise, return Z to the user.Figure 4
A flowchart of TOP.In Algorithm3, TOP starts its procedure by receiving information of a BCJSP instance from the user. TOP assigns τ ← 1 and Score(ζbest) ← +∞; then, it generates ζqτ randomly. After that, TOP starts a repeated loop by executing MID M times. In the q-th execution (where q = 1, 2, …, M), MID is executed with ζqτ-given parameter values to return Sbest; then, let Scoreζqτ ← Makespan(Sbest). If TOP finds any ζqτ better than or equal to ζbest, then let this ζqτ and its corresponding Sbest become a new ζbest and a new Z, respectively. After that, TOP chooses to update each member of ζqτ+1 by either the two opposite-direction vectors or the reinitialization. If the stopping criterion is not met, TOP assigns τ←τ+1 and starts the repeated loop’s next round.As mentioned, there are two variants of MUL, i.e., MUL-B and MUL-T. The difference between MUL-B and MUL-T in their TOPs is given as follows. In MUL-T,ζqτ of its TOP’s population consists of αiqτ, βiqτ, and γkqτ. This means TOP in MUL-T is identical to Algorithm 3. In MUL-B, ζq(τ) of its TOP’s population consists of only αiqτ and βiqτ. It means that ζqτ of TOP in MUL-B is equivalent to α1qτ,α2qτ,…,αnqτ,β1qτ,β2qτ,…,βnqτ. Thus, the procedure of TOP in MUL-B is modified from Algorithm 3 by removing γkqτ from Step 3; removing ypt, ypn, ypr, wpt,wpn and wpr from Steps 4.2 and 4.3; and removing γkqτ+1 and its generating equation from Step 5.2.


## 5. Results

The performance of the two proposed variants of MUL (i.e., MUL-B and MUL-T) was evaluated via an experiment on 53 BCJSP instances. These BCJSP instances were modified from the well-known JSP instances, i.e., FT06, FT10, and FT20 instances of [17]; LA01 to LA40 instances of [18]; and ORB01 to ORB10 instances of [19]. The modification of each instance was done by letting the operation-precedence-relation chains of all jobs be circular and bidirectional. In this paper, let BCFT06, BCFT10, and BCFT20 represent the BCJSP instances modified from FT06, FT10, and FT20, respectively. Let BCLA01 to BCLA40 represent the BCJSP instances modified from LA01 to LA40, respectively. Then, let BCORB01 to BCORB10 represent the BCJSP instances modified from ORB01 to ORB10, respectively. For each BCJSP instance, let its original JSP instance stand for the JSP instance later modified to become it. For example, FT06 is the original JSP instance of BCFT06.Because of the BCJSP’s novelty, no algorithms excepting MUL have intentionally been developed for BCJSP. Thus, to evaluate the performance of MUL-B and MUL-T, their performance was compared with each other and with the performance of the existing JSP-solving algorithms. Without modifications, the existing JSP-solving algorithms can solve BCJSP as well. However, they hardly find good solutions for BCJSP. This is because, for each BCJSP instance, the solution space of its original JSP instance is just a subset of its whole solution space. Consequently, for each BCJSP instance, the JSP-solving algorithms cannot return better solutions than the optimal solution of its original JSP instance. This is the reason that the original JSP instance’s optimal solution is used as the best possible result from all JSP-solving algorithms on each BCJSP instance.The settings of MUL-B and MUL-T for the experiment are summarized as follows:(i)
MUL-B and MUL-T were coded in C# and executed on an Intel® Core™ i5-3320M CPU processor @ 2.60 GHz with RAM of 4 GB (3.87 GB usable).(ii)
In each of MUL-B and MUL-T, let the population of MID consist of two members (i.e.,N = 2 in Algorithm 2), and let MID be stopped after the 10-th iteration (i.e., t = 10 is the maximum iteration in Algorithm 2).(iii)
In only MUL-B, the constant value of 0.5 was assigned to the MID's input parametersypt, ypn, ypr, wpt, wpn, and wpr.(iv)
In each of MUL-B and MUL-T, let the population of TOP consist of two members (i.e.,M = 2 in Algorithm 3), and let TOP be stopped if it could not find an improving solution (a better solution) within 100 consecutive iterations.(v)
Each of MUL-B and MUL-T was executed for three runs on each BCJSP instance with different random seed numbers.Reasons for the above-mentioned parameter settings are given as follows. For limiting MUL-B’s and MUL-T’s computational time, the population sizes of their MIDs and TOPs were set to 2, the smallest possible size. With the same reason, their MIDs were set to stop after their 10-th iterations. However, for avoiding premature stops, their TOPs were set to stop after 100 consecutive iterations without finding a better solution. For performing as well as MUPLA [16], the parameters ypt, ypn, ypr, wpt, wpn, and wpr of MID in MUL-B were set to 0.5. This made the equations in Step 5.2 of Algorithm 2 become identical to those of MUPLA [16].The experiment’s results on the 53 BCJSP instances are presented in Table1. Terms and abbreviations used in Table 1 and in its discussion are defined as follows:(i)
Let a solution and a solution value stand for a schedule and a schedule’s makespan, respectively.(ii)
For each BCJSP instance, let its original JSP instance mean the JSP instance that was later modified to become it. For example, LA01 is the original JSP instance of BCLA01.(iii)
LetIns column present the name of each BCJSP instance.(iv)
LetJSP Opt column present the optimal solution value of the original JSP instance of each BCJSP instance. The values in this column were given by published articles, e.g., [20, 21].(v)
For each of MUL-B and MUL-T, letBest and Avg stand for its best final solution value and its average final solution value, respectively, over three runs.(vi)
LetUB stand for the upper bound of the optimal solution value of each BCJSP instance. UB in this paper is a minimum among the values of JSP Opt, Best of MUL-B, and Best of MUL-T.(vii)
For each of MUL-B and MUL-T, let %BD stand for a percent deviation of its Best from UB, and let %AD stand for a percent deviation of its Avg from UB.(viii)
For eachJSP Opt, let %JD stand for its percent deviation from UB.(ix)
For each of MUL-B and MUL-T, letAvg Iters column present the average number of iterations used until stopped on each instance. In parentheses, this column presents the average minimum number of iterations required to find the last improving solution. Note that the number of iterations used by each of MUL-B and MUL-T means the number of iterations used by its TOP.(ix)
For each of MUL-B and MUL-T, letAvg time column present an average computational time consumed until stopped on each instance in HH: MM: SS form. In parentheses, this column presents an average minimum computational time required to find the last improving solution.Table 1
Experiment’s results.
InsUBJSP Opt%JDMUL-BMUL-TBest%BDAvg%ADAvg itersAvg timeBest%BDAvg%ADAvg itersAvg timeBCFT06475517.02482.1349.34.89178 (78)0:00:10 (0:00:04)470.0048.73.62217 (117)0:00:12 (0:00:06)BCFT1073993025.857805.55786.06.36150 (50)0:07:21 (0:02:25)7390.00756.02.30183 (83)0:08:56 (0:04:14)BCFT20111911654.1111190.001119.00.00101 (1)0:08:18 (0:00:03)11190.001119.00.00101 (1)0:08:15 (0:00:04)BCLA016666660.006660.00666.00.00112 (12)0:00:29 (0:00:03)6660.00666.00.00112 (12)0:00:30 (0:00:03)BCLA026356553.156350.00635.00.00114 (14)0:00:30 (0:00:03)6350.00635.00.00103 (3)0:00:27 (0:00:00.4)BCLA035885971.535880.00588.00.00115 (15)0:00:30 (0:00:04)5880.00588.00.00103 (3)0:00:26 (0:00:01)BCLA045375909.875370.00537.00.00135 (35)0:00:38 (0:00:10)5370.00537.00.00190 (90)0:00:55 (0:00:25)BCLA055935930.005930.00593.00.00101 (1)0:00:26 (0:00:00.3)5930.00593.00.00103 (3)0:00:26 (0:00:01)BCLA069269260.009260.00926.00.00101 (1)0:02:21 (0:00:01)9260.00926.00.00101 (1)0:02:22 (0:00:01)BCLA078698902.428690.00869.00.00101 (1)0:02:22 (0:00:01)8690.00869.00.00101 (1)0:02:14 (0:00:01)BCLA088638630.008630.00863.00.00101 (1)0:02:35 (0:00:01)8630.00863.00.00101 (1)0:02:40 (0:00:01)BCLA099519510.009510.00951.00.00101 (1)0:02:38 (0:00:02)9510.00951.00.00101 (1)0:02:30 (0:00:01)BCLA109589580.009580.00958.00.00101 (1)0:02:22 (0:00:01)9580.00958.00.00101 (1)0:02:21 (0:00:01)BCLA11122212220.0012220.001222.00.00101 (1)0:07:15 (0:00:05)12220.001222.00.00101 (1)0:06:51 (0:00:03)BCLA12103910390.0010390.001039.00.00101 (1)0:08:38 (0:00:06)10390.001039.00.00101 (1)0:08:46 (0:00:03)BCLA13115011500.0011500.001150.00.00101 (1)0:08:12 (0:00:05)11500.001150.00.00101 (1)0:08:02 (0:00:05)BCLA14129212920.0012920.001292.00.00101 (1)0:07:02 (0:00:03)12920.001292.00.00101 (1)0:06:43 (0:00:04)BCLA15120712070.0012070.001207.00.00101 (1)0:07:27 (0:00:05)12070.001207.00.00101 (1)0:07:21 (0:00:03)BCLA1679894518.427980.00806.01.00162 (62)0:08:00 (0:03:11)8101.50814.02.01153 (53)0:07:20 (0:02:37)BCLA177177849.347352.51735.02.51141 (41)0:07:04 (0:02:00)7170.00731.72.05234 (134)0:11:43 (0:06:47)BCLA1876584810.857650.00775.71.40191 (91)0:09:25 (0:04:20)7680.39777.71.66168 (68)0:08:22 (0:03:23)BCLA197838427.547830.00802.32.46184 (84)0:09:25 (0:04:21)8012.30808.03.19248 (148)0:12:17 (0:07:18)BCLA2081090211.368120.25823.01.60157 (57)0:07:35 (0:02:48)8100.00828.72.31182 (82)0:08:59 (0:04:01)BCLA2196710468.179811.45985.71.93212 (112)1:05:44 (0:34:46)9670.00979.71.31181 (81)0:55:07 (0:24:20)BCLA229009273.009111.22925.32.81172 (72)0:54:31 (0:23:14)9000.00905.00.56150 (50)0:47:03 (0:15:45)BCLA23103210320.0010320.001032.00.00141 (41)0:43:54 (0:12:49)10320.001032.00.00141 (41)0:42:37 (0:13:01)BCLA249329350.329380.64948.31.75180 (80)0:55:37 (0:24:16)9320.00950.31.96174 (74)0:54:07 (0:23:12)BCLA259079777.729181.21935.03.09226 (126)1:09:46 (0:39:20)9070.00927.02.21253 (153)1:17:00 (0:46:58)BCLA26121812180.0012180.001218.00.00146 (46)2:35:48 (0:47:58)12180.001218.00.00119 (19)2:09:40 (0:20:37)BCLA27120712352.3212180.911222.01.24162 (62)2:58:45(1:08:36)12070.001222.71.30162 (62)3:02:29(1:10:44)BCLA28121612160.0012160.001217.70.14223 (123)4:03:14 (2:16:13)12160.001216.00.00177 (77)3:13:08 (1:24:44)BCLA29110511524.2511050.001105.00.00152 (52)2:46:47 (0:55:04)11050.001115.00.90188 (88)3:26:20 (1:37:06)BCLA30135513550.0013550.001355.00.00101 (1)1:43:32 (0:00:51)13550.001355.00.00101 (1)1:39:45 (0:00:36)BCLA31178417840.0017840.001784.00.00101 (1)7:50:40 (0:02:52)17840.001784.00.00101 (1)8:55:01 (0:04:44)BCLA32185018500.0018500.001850.00.00102 (2)10:21:25 (0:07:08)18500.001850.00.00102 (2)10:30:37 (0:10:30)BCLA33171917190.0017190.001719.00.00101 (1)9:13:34 (0:07:22)17190.001719.00.00101 (1)9:35:45 (0:06:18)BCLA34172117210.0017210.001721.00.00101 (1)10:45:44 (0:06:43)17210.001721.00.00101 (1)11:06:51 (0:08:12)BCLA35188818880.0018880.001888.00.00101 (1)7:31:40 (0:02:25)18880.001888.00.00101 (1)8:07:04 (0:04:14)BCLA36118612686.9111860.001210.72.08196 (96)3:59:35 (1:52:51)12071.771218.02.70177 (77)3:40:50 (1:37:49)BCLA371247139712.0312470.001271.31.95220 (120)4:36:09 (2:24:27)12923.611295.33.87171 (71)3:38:52 (1:33:27)BCLA38111411967.3611654.581173.05.30198 (98)4:11:10 (2:04:43)11140.001145.02.78195 (95)4:15:04 (2:07:00)BCLA39118612333.9611860.001196.00.84195 (95)4:06:29 (1:57:48)11910.421192.70.56214 (114)4:26:56 (2:19:38)BCLA40115012226.2611560.521182.32.81166 (66)3:24:58 (1:24:33)11500.001179.32.55145 (45)2:58:02 (0:56:47)BCORB01789105934.228122.92818.33.71248 (148)0:12:31 (0:07:30)7890.00810.32.70150 (50)0:07:45 (0:02:35)BCORB0276388816.387630.00783.02.62164 (64)0:08:24 (0:03:19)7974.46803.75.33173 (73)0:09:01 (0:03:47)BCORB03741100535.637410.00764.33.14192 (92)0:09:29 (0:04:28)7734.32780.75.36333 (233)0:16:43 (0:11:39)BCORB04831100520.948390.96849.72.25163 (63)0:08:01 (0:03:07)8310.00839.31.00217 (117)0:10:54 (0:05:48)BCORB0570588725.827050.00717.31.74213 (113)0:10:26 (0:05:42)7273.12729.03.40180 (80)0:08:51 (0:03:56)BCORB06817101023.628220.61835.32.24136 (36)0:06:40 (0:01:43)8170.00832.31.87187 (87)0:09:27 (0:04:21)BCORB0735339712.463560.85358.71.61201 (101)0:09:45 (0:04:58)3530.00358.01.42155 (55)0:07:35 (0:02:42)BCORB0867189933.986750.60684.31.98208 (108)0:10:14 (0:05:19)6710.00683.31.83186 (86)0:09:19 (0:04:10)BCORB0977293420.987730.13792.02.59154 (54)0:07:50 (0:02:42)7720.00789.32.24179 (79)0:09:15 (0:04:01)BCORB1078094421.038124.10825.75.86193 (93)0:09:30 (0:04:34)7800.00788.71.12266 (166)0:13:24 (0:08:19)Table2 then summarizes the results shown in Table 1. In Table 2, the 53 BCJSP instances are classified into nine categories based on the numbers of machines (m) and the numbers of jobs (n). Terms and abbreviations used in Table 2 are defined as follows:(i)
Category column presents each category of the 53 BCJSP instances in the form m × n, where m is the number of machines and n is the number of jobs.(ii)
Members column presents all instances that are members of each category. Then, No. of Ins column presents the number of all instances in each category.(iii)
LetAvg %JD stand for an average %JD over all instances in each category.(iv)
For each of MUL-B and MUL-T, letAvg %BD and Avg %AD stand for an average %BD and an average %AD, respectively, over all instances in each category.(v)
For each of MUL-B and MUL-T, letAvg Iters column present the average number of iterations used until stopped. In parentheses, this column presents the average minimum number of iterations required to find the last improving solution. Note that the number of iterations used by each of MUL-B and MUL-T means the number of iterations used by its TOP.(vi)
For each of MUL-B and MUL-T, letAvg time column present an average computational time consumed until stopped. In parentheses, this column presents an average minimum computational time required to find the last improving solution.(vii)
In the competition between MUL-B and MUL-T, letW, D, and L in W-D-L present the numbers of instances won, drawn, and lost, respectively. On each instance, MUL-B is judged to win MUL-T if the MUL-B’s %BD is better than the MUL-T’s %BD, and vice versa. In addition, they are judged to draw if their %BDs are equal.Table 2
A summary of experiment’s results.
CategoryMembersNo. of InsAvg %JDMUL-BMUL-TAvg %BDW-D-LAvg %ADAvg itersAvg timeAvg %BDW-D-LAvg %ADAvg itersAvg time5 × 10BCLA01–0552.910.000-5-00.00115 (15)0:00:31 (0:00:04)0.000-5-00.00122 (22)0:00:33 (0:00:06)5 × 15BCLA06–1050.480.000-5-00.00101 (1)0:02:28 (0:00:01)0.000-5-00.00101 (1)0:02:25 (0:00:01)5 × 20BCFT20, BCLA11–1560.690.000-6-00.00101 (1)0:07:49 (0:00:05)0.000-6-00.00101 (1)0:07:40 (0:00:04)6 × 6BCFT06117.022.130-0-14.89178 (78)0:00:10 (0:00:04)0.001-0-03.62217 (117)0:00:12 (0:00:06)10× 10BCFT10, BCLA16–20, BCORB01–101620.531.166-0-102.69178 (78)0:08:51 (0:03:54)1.0110-0-62.49200 (100)0:09:59 (0:04:45)10 × 15BCLA21–2553.840.900-1-41.92186 (86)0:57:54 (0:26:53)0.004-1-01.21180 (80)0:55:11 (0:24:39)10 × 20BCLA26–3051.310.180-4-10.28157 (57)2:49:37 (1:01:44)0.001-4-00.44149 (49)2:42:16 (0:54:45)10 × 30BCLA31–3550.000.000-5-00.00101 (1)9:08:37 (0:05:18)0.000-5-00.00101 (1)9:39:04 (0:06:48)15 × 15BCLA36–4057.301.023-0-22.60195 (95)4:03:40 (1:56:52)1.162-0-32.49180 (80)3:47:57 (1:42:56)AllAll 53 instances538.090.599-26-181.36149 (49)1:40:03 (0:21:05)0.4118-26-91.21154 (54)1:40:49 (0:19:22)Figure5 presents the rates of solution improvements over iterations of MUL-B and MUL-T. In making the figure, Avg-%AD-over-iteration plots and Avg-%BD-over-iteration plots were plotted and compared with Avg %JD. Let Avg %JD be calculated from an average %JD over 53 instances. For each of MUL-B and MUL-T, let Avg-%AD-over-iteration plot and Avg-%BD-over-iteration plot present the average %AD over 53 instances and the average %BD over 53 instances, respectively, from the first to the 350-th iterations. One obstacle of plotting each plot was that each algorithm was usually stopped before the 350-th iteration, as shown in Table 1. To deal with the obstacle, since the algorithms were stopped, the last values of %AD and %BD had been used in the plots until the 350-th iterations.Figure 5
Avg %ADs and Avg %BDs over iterations of MUL-B and MUL-T compared with Avg %JD.


## 6. Discussion

### 6.1. Result Comparisons of MUL-B and MUL-T with Other Algorithms

As mentioned previously, no existing algorithms excepting MUL-B and MUL-T have been developed to solve BCJSP. This means no other existing BCJSP-solving algorithms could be used for comparison against MUL-B and MUL-T. It is the cause that, in this research, the MUL-B’s and MUL-T’s results were compared againstJSP Opt. For each BCJSP instance, JSP Opt in Table 1 denotes the optimal solution value of its original JSP instance. (Note that, for example, FT06 is the original JSP instance of BCFT06.) Rather than comparison with many JSP-solving algorithms, let JSP Opt be a representative of the best possible result from all existing JSP-solving algorithms on BCJSP.As shown in Table1, MUL-B returns better solution values than JSP Opt on 32 instances, equivalent values on 20 instances, and worse values on one instance. This means MUL-B performs better than the best performance of the existing JSP-solving algorithms on 32 instances, has equivalent performance on 20 instances, and has worse performance on one instance. MUL-T returns better solution values than JSP Opt on 33 instances, equivalent values on 20 instances, and worse values on none of the instances. This means MUL-T performs better than the best performance of the existing JSP-solving algorithms on 33 instances, has equivalent performance on 20 instances, and has worse performance on none of the instances.Note that, in Table1, %JD, %BD, and %AD represent the percent deviations from UB of JSP Opt, Best, and Avg, respectively. One-sided paired t tests conclude that the population mean %BDs of MUL-B and MUL-T are both significantly better than the population mean %JD (with p values of 4 × 10−7 and 3 × 10−7, respectively). Moreover, the population mean %ADs of MUL-B and MUL-T are also significantly better than the population mean %JD (with p values of 10 × 10−7 and 5 × 10−7, respectively). As an interpretation, the two variants of MUL outperform the existing JSP-solving algorithms on BCJSP.A cause for the above-mentioned results is that MUL-B and MUL-T can both explore the whole solution space of the BCJSP instance, while the existing JSP-solving algorithms can explore only the original JSP instance’s solution space. For each BCJSP instance, the solution space of its original JSP instance is just a small subset of its whole solution space. Then, a BCJSP instance usually has multiple better solutions than the optimal solution of its original JSP instance. Consequently, MUL-B and MUL-T both possibly find better solutions than the original JSP instance’s optimal solution, whereas the existing JSP-solving algorithms cannot.


### 6.2. Result Comparisons between MUL-B and MUL-T

As shown in Tables1 and 2, MUL-T performs slightly better than MUL-B in the average solution quality. Over 53 instances, Avg %BD of MUL-T (i.e., 0.41%) is slightly better than Avg %BD of MUL-B (i.e., 0.59%). Likewise, Avg %AD of MUL-T (i.e., 1.21%) is slightly better than Avg %AD of MUL-B (i.e., 1.36%). However, based on one-sided paired t tests, no sufficient evidence suggests that the population mean %BD of MUL-T is better than that of MUL-B (with p value of 0.24). In addition, no enough evidence suggests that the population mean %AD of MUL-T is better than that of MUL-B (with p value of 0.19).By counting the instances won in Table1, the outperformance of MUL-T over MUL-B can be detected more clearly. On each instance, let MUL-T be judged to win MUL-B if the MUL-T’s %BD is lower than the MUL-B’s %BD, and vice versa. Over 53 instances, MUL-T wins MUL-B on 18 instances, draws on 26 instances, and loses on nine instances. As noticed, the number of instances won by MUL-T (i.e., 18) is twice of the number of instances won by MUL-B (i.e., 9). Although a proportion of drawn instances (i.e., 26 out of total 53) is very high, most of the drawn instances are small or easy to solve (e.g., the instances in the 5 × 10, 5 × 15, 5 × 20, and 10 × 30 categories in Table 2). To determine whether the total number of all instances won by MUL-T is greater than that by MUL-B, a one-sided binomial test was conducted at a significance level of 0.1. Let a sample size be the number of instances not drawn from the total 53 instances (i.e., 27). The test’s result concludes that, from all not-drawn instances, the number of all instances won by MUL-T is significantly greater than that by MUL-B (with p value of 0.061).As mentioned previously, the main difference between MUL-B and MUL-T is in their TOPs. The MUL-B’s and MUL-T’s TOPs both control the start operations and the operation-precedence-relation directions in BCJSP. However, only TOP of MUL-T additionally controls the MID’s input parameters as the extra function. The outperformance of MUL-T over MUL-B abovementioned indicates that this extra function can enhance the performance of MUL. This means the MID’s performance can be enhanced by using TOP to control its input parameters. Once the MID's performance has been enhanced, MID can provide better input-parameter values for BOT. Consequently, BOT can find better solutions.


### 6.3. Number of Iterations and Computational Time Consumed

For MUL-B and MUL-T, the numbers of used iterations directly affect computational time spent. The more the number of iterations used, the longer the computational time consumed. Table1 presents the average number of iterations and the average computational time of the three runs of each algorithm. For each instance, Avg Iters and Avg time columns present the average number of iterations and the average computational time, respectively, used until the stopping criterion is met. (Note that the stopping criterion was to stop when TOP could not find an improving solution within 100 consecutive iterations.) In parentheses, Avg Iters and Avg time columns show the average minimum number of iterations and the average minimum computational time, respectively, required to find the last improving solution. A summary of the data from Table 1 just-mentioned can be found in Table 2.As mentioned above, the stopping criterion for each algorithm was to stop when its TOP could not find an improving solution within 100 consecutive iterations. The purpose of using this stopping criterion is to avoid a premature stop for each algorithm. However, it probably results in an unnecessary high consumption of the number of iterations and of computational time. For example, on BCLA34, MUL-B and MUL-T both find their best-found solutions at their first iterations; however, they have to proceed until the 101-st iterations. For computational time on BCLA34, the both algorithms find their best-found solutions within 10 minutes; however, they have to stop after around 11 hours. Such cases also happen on many other instances, not only BCLA34.Because the given stopping criterion causes a very long computational time, the user should not wait until MUL-B and MUL-T meet their stopping criteria. The user can break off the algorithms' executions at any time to receive their current best-found solutions. To choose a breaking-off time, the user may use information from the values in parentheses ofAvg Iters and Avg time columns in Table 1. Avg Iters column indicates that, on more than 50% of all instances, the algorithms find their last improving solutions within 55 iterations; on all instances excepting BCORB03, they find their last improving solutions within 170 iterations. Avg time column indicates that, on more than 50% of all instances, the algorithms find their last improving solutions within 4.5 minutes; on all instances, they find their last improving solutions within 145 minutes.As suggested fromAvg Iters column, MUL-B and MUL-T should be broken off during the 55-th to the 170-th iterations. In addition, as suggested from Avg time column, they should be broken off during the 4.5-th to the 145-th minutes. Thus, as a minimum requirement, the user should break off each algorithm at the 55-th iteration or the 4.5-th minute of computational time, whichever comes first. If an optimal or near-optimal solution is required, the user is suggested to break off each algorithm at the 170-th iteration or the 145-th minute of computational time, whichever comes first. Moreover, the user may decide to break off each algorithm at any iteration index during the 55-th to the 170-th iterations or at any time during the 4.5-th to the 145-th minutes. The decision is made based on his trade-off between the computational time and the possibility of finding an improving solution. Note that the computational time in the above suggestions may be changed if the user’s computer has a different specification from the computer used in this research.


### 6.4. Solution Improvement Rate over Iteration

Since started,Avg-%AD-over-iteration plots and Avg-%BD-over-iteration plots of MUL-B and MUL-T in Figure 5 have already been below Avg %JD (i.e., 8.09%). At their first iterations, Avg %AD of MUL-B, Avg %AD of MUL-T, Avg %BD of MUL-B, and Avg %BD of MUL-T are 6.72%, 6.67%, 5.03%, and 4.53%, respectively. Since then, the values of the four plots have still been reduced continuously. The four plots in the mentioned order finally become 1.36%, 1.21%, 0.59%, and 0.41%, respectively, at their final values. Obviously, all their final values are much lower than Avg %JD. This means MUL-B and MUL-T perform better than the JSP-solving algorithms on BCJSP because Avg %JD is the best possible result of the JSP-solving algorithms.All given plots in Figure5 behave similarly to each other in their patterns. These plots can be divided into three periods based on their similar patterns. The first period of each plot, where the value is reduced very quickly, is approximately started from the first iteration to the 55-th iteration. The second period, where the value is reduced gradually, is approximately started from the 55-th iteration to the 170-th iteration. The third period, where the value is reduced hardly, is approximately started from the 170-th iteration onwards. After the 170-the iteration, the plot has become more and more stable. The patterns of the plots emphasize that the user should break off each algorithm during the 55-th to the 170-th iterations, where the number of more iterations is a trade-off for the higher possibility of finding an improving solution.


## 6.1. Result Comparisons of MUL-B and MUL-T with Other Algorithms

As mentioned previously, no existing algorithms excepting MUL-B and MUL-T have been developed to solve BCJSP. This means no other existing BCJSP-solving algorithms could be used for comparison against MUL-B and MUL-T. It is the cause that, in this research, the MUL-B’s and MUL-T’s results were compared againstJSP Opt. For each BCJSP instance, JSP Opt in Table 1 denotes the optimal solution value of its original JSP instance. (Note that, for example, FT06 is the original JSP instance of BCFT06.) Rather than comparison with many JSP-solving algorithms, let JSP Opt be a representative of the best possible result from all existing JSP-solving algorithms on BCJSP.As shown in Table1, MUL-B returns better solution values than JSP Opt on 32 instances, equivalent values on 20 instances, and worse values on one instance. This means MUL-B performs better than the best performance of the existing JSP-solving algorithms on 32 instances, has equivalent performance on 20 instances, and has worse performance on one instance. MUL-T returns better solution values than JSP Opt on 33 instances, equivalent values on 20 instances, and worse values on none of the instances. This means MUL-T performs better than the best performance of the existing JSP-solving algorithms on 33 instances, has equivalent performance on 20 instances, and has worse performance on none of the instances.Note that, in Table1, %JD, %BD, and %AD represent the percent deviations from UB of JSP Opt, Best, and Avg, respectively. One-sided paired t tests conclude that the population mean %BDs of MUL-B and MUL-T are both significantly better than the population mean %JD (with p values of 4 × 10−7 and 3 × 10−7, respectively). Moreover, the population mean %ADs of MUL-B and MUL-T are also significantly better than the population mean %JD (with p values of 10 × 10−7 and 5 × 10−7, respectively). As an interpretation, the two variants of MUL outperform the existing JSP-solving algorithms on BCJSP.A cause for the above-mentioned results is that MUL-B and MUL-T can both explore the whole solution space of the BCJSP instance, while the existing JSP-solving algorithms can explore only the original JSP instance’s solution space. For each BCJSP instance, the solution space of its original JSP instance is just a small subset of its whole solution space. Then, a BCJSP instance usually has multiple better solutions than the optimal solution of its original JSP instance. Consequently, MUL-B and MUL-T both possibly find better solutions than the original JSP instance’s optimal solution, whereas the existing JSP-solving algorithms cannot.


## 6.2. Result Comparisons between MUL-B and MUL-T

As shown in Tables1 and 2, MUL-T performs slightly better than MUL-B in the average solution quality. Over 53 instances, Avg %BD of MUL-T (i.e., 0.41%) is slightly better than Avg %BD of MUL-B (i.e., 0.59%). Likewise, Avg %AD of MUL-T (i.e., 1.21%) is slightly better than Avg %AD of MUL-B (i.e., 1.36%). However, based on one-sided paired t tests, no sufficient evidence suggests that the population mean %BD of MUL-T is better than that of MUL-B (with p value of 0.24). In addition, no enough evidence suggests that the population mean %AD of MUL-T is better than that of MUL-B (with p value of 0.19).By counting the instances won in Table1, the outperformance of MUL-T over MUL-B can be detected more clearly. On each instance, let MUL-T be judged to win MUL-B if the MUL-T’s %BD is lower than the MUL-B’s %BD, and vice versa. Over 53 instances, MUL-T wins MUL-B on 18 instances, draws on 26 instances, and loses on nine instances. As noticed, the number of instances won by MUL-T (i.e., 18) is twice of the number of instances won by MUL-B (i.e., 9). Although a proportion of drawn instances (i.e., 26 out of total 53) is very high, most of the drawn instances are small or easy to solve (e.g., the instances in the 5 × 10, 5 × 15, 5 × 20, and 10 × 30 categories in Table 2). To determine whether the total number of all instances won by MUL-T is greater than that by MUL-B, a one-sided binomial test was conducted at a significance level of 0.1. Let a sample size be the number of instances not drawn from the total 53 instances (i.e., 27). The test’s result concludes that, from all not-drawn instances, the number of all instances won by MUL-T is significantly greater than that by MUL-B (with p value of 0.061).As mentioned previously, the main difference between MUL-B and MUL-T is in their TOPs. The MUL-B’s and MUL-T’s TOPs both control the start operations and the operation-precedence-relation directions in BCJSP. However, only TOP of MUL-T additionally controls the MID’s input parameters as the extra function. The outperformance of MUL-T over MUL-B abovementioned indicates that this extra function can enhance the performance of MUL. This means the MID’s performance can be enhanced by using TOP to control its input parameters. Once the MID's performance has been enhanced, MID can provide better input-parameter values for BOT. Consequently, BOT can find better solutions.


## 6.3. Number of Iterations and Computational Time Consumed

For MUL-B and MUL-T, the numbers of used iterations directly affect computational time spent. The more the number of iterations used, the longer the computational time consumed. Table1 presents the average number of iterations and the average computational time of the three runs of each algorithm. For each instance, Avg Iters and Avg time columns present the average number of iterations and the average computational time, respectively, used until the stopping criterion is met. (Note that the stopping criterion was to stop when TOP could not find an improving solution within 100 consecutive iterations.) In parentheses, Avg Iters and Avg time columns show the average minimum number of iterations and the average minimum computational time, respectively, required to find the last improving solution. A summary of the data from Table 1 just-mentioned can be found in Table 2.As mentioned above, the stopping criterion for each algorithm was to stop when its TOP could not find an improving solution within 100 consecutive iterations. The purpose of using this stopping criterion is to avoid a premature stop for each algorithm. However, it probably results in an unnecessary high consumption of the number of iterations and of computational time. For example, on BCLA34, MUL-B and MUL-T both find their best-found solutions at their first iterations; however, they have to proceed until the 101-st iterations. For computational time on BCLA34, the both algorithms find their best-found solutions within 10 minutes; however, they have to stop after around 11 hours. Such cases also happen on many other instances, not only BCLA34.Because the given stopping criterion causes a very long computational time, the user should not wait until MUL-B and MUL-T meet their stopping criteria. The user can break off the algorithms' executions at any time to receive their current best-found solutions. To choose a breaking-off time, the user may use information from the values in parentheses ofAvg Iters and Avg time columns in Table 1. Avg Iters column indicates that, on more than 50% of all instances, the algorithms find their last improving solutions within 55 iterations; on all instances excepting BCORB03, they find their last improving solutions within 170 iterations. Avg time column indicates that, on more than 50% of all instances, the algorithms find their last improving solutions within 4.5 minutes; on all instances, they find their last improving solutions within 145 minutes.As suggested fromAvg Iters column, MUL-B and MUL-T should be broken off during the 55-th to the 170-th iterations. In addition, as suggested from Avg time column, they should be broken off during the 4.5-th to the 145-th minutes. Thus, as a minimum requirement, the user should break off each algorithm at the 55-th iteration or the 4.5-th minute of computational time, whichever comes first. If an optimal or near-optimal solution is required, the user is suggested to break off each algorithm at the 170-th iteration or the 145-th minute of computational time, whichever comes first. Moreover, the user may decide to break off each algorithm at any iteration index during the 55-th to the 170-th iterations or at any time during the 4.5-th to the 145-th minutes. The decision is made based on his trade-off between the computational time and the possibility of finding an improving solution. Note that the computational time in the above suggestions may be changed if the user’s computer has a different specification from the computer used in this research.


## 6.4. Solution Improvement Rate over Iteration

Since started,Avg-%AD-over-iteration plots and Avg-%BD-over-iteration plots of MUL-B and MUL-T in Figure 5 have already been below Avg %JD (i.e., 8.09%). At their first iterations, Avg %AD of MUL-B, Avg %AD of MUL-T, Avg %BD of MUL-B, and Avg %BD of MUL-T are 6.72%, 6.67%, 5.03%, and 4.53%, respectively. Since then, the values of the four plots have still been reduced continuously. The four plots in the mentioned order finally become 1.36%, 1.21%, 0.59%, and 0.41%, respectively, at their final values. Obviously, all their final values are much lower than Avg %JD. This means MUL-B and MUL-T perform better than the JSP-solving algorithms on BCJSP because Avg %JD is the best possible result of the JSP-solving algorithms.All given plots in Figure5 behave similarly to each other in their patterns. These plots can be divided into three periods based on their similar patterns. The first period of each plot, where the value is reduced very quickly, is approximately started from the first iteration to the 55-th iteration. The second period, where the value is reduced gradually, is approximately started from the 55-th iteration to the 170-th iteration. The third period, where the value is reduced hardly, is approximately started from the 170-th iteration onwards. After the 170-the iteration, the plot has become more and more stable. The patterns of the plots emphasize that the user should break off each algorithm during the 55-th to the 170-th iterations, where the number of more iterations is a trade-off for the higher possibility of finding an improving solution.


## 7. Conclusions

MUL is the multilevel metaheuristic developed to solve the job-shop scheduling problem with bidirectional circular precedence constraints (BCJSP). MUL consists of TOP, MID, and BOT algorithms in its top, middle, and bottom levels, respectively. TOP is the population-based metaheuristic developed to control the start operation and the operation-precedence-relation direction of each job in BCJSP. If requested, TOP can also control the MID’s input parameters. MID is the population-based metaheuristic developed to control the BOT’s input parameters. BOT generates a subproblem of the BCJSP instance, in the form of JSP, by using the start operations and the operation-precedence-relation directions given by TOP. BOT then acts as a local search algorithm to solve the generated subproblem. The population in MID is evolved by the feedback from BOT, while the population in TOP is evolved by the feedback from MID. In this paper, there are two proposed variants of MUL, i.e., MUL-B and MUL-T. These two variants both use their TOPs to control the start operation and the operation-precedence-relation direction of each job. However, only MUL-T additionally uses its TOP to control the MID’s input parameters. Because MUL-B and MUL-T were intentionally developed for BCJSP, they perform much better than the existing JSP-solving algorithms on BCJSP. When comparing the two MUL variants, MUL-T outperforms MUL-B slightly in the average solution quality and significantly in the number of instances won.



---

*Source: 3237342-2021-11-09.xml*