1.INTRODUCTION
Bilevel structure is the simplest class of multilevel formulation. Many planning and scheduling problems of supply chain management and production management can be modeled with this structure. Bilevel scheduling problem is a problem when the decision made on how to schedule jobs considers two levels objectives, upper and lower, as a hierarchy structure. The decision of the upper level generally influences the decision on the lower level. The bilevel scheduling problem is found in many cases, for example: the case of multilevel production systems by Lin et al. (1997) and Semnani and Zamanifar (2010), the case of cellular manufacturing by Logendran et al. (1995), and the case of jobshop scheduling by Kasemset and Kachitvichyanukul (2010).
When the multilevel structure was applied, solution procedures as exact and heuristics algorithm have been developed by many researchers, but the first technique, exact algorithm, is difficult to get the solution in reasonable computational time so a heuristics method has been widely developed in many research works. The examples of wellknown heuristics techniques are: genetic algorithm (GA) applied by Kimms (1999) and Pezzella et al. (2008); particle swarm optimization (PSO) applied by Zhang et al. (2009), Kuo and Huang (2009), and Chander et al. (2011); ant colony optimization used by Semnani and Zamanifar (2010); and combined heuristics used by Logendran et al. (1995) and Kuo and Han (2011).
Particle swarm optimization or PSO is a population based search method. The effectiveness of PSO was compared with GA and differential evolution in Kachitvichyanukul (2012) and PSO was mention that its mechanism facilitated in solution improvement within short computational time compared with GA. PSO was widely applied in many scheduling problems, for examples, flowshop scheduling by RahimiVahed and Mirghorbani (2007) and Pan et al. (2008); jobshop scheduling (JSP) by Sha and Hsu (2006), Lei (2008), Lian et al. (2006), Xia and Wu (2005), Pongchairerks and Kachitvichyanukul (2009), Zhang et al. (2009), Pratchayaborirak and Kachitvichyanukul (2011), Wisittipanich and Kachitvichyanukul (2013). However, most researchers in this field used PSO in a single and multiple objective optimizations, in contrast, there was only a few researchers working on multilevel programming problems. In addition, the initial step of basic PSO is to setup PSOparameter, i.e., acceleration constants, number of iteration, number of particle, etc., as optimal values to accelerate the solution improving during PSO process. The parameter optimization for PSO is a tedious job. Many research works applied the concept of design of experiment (DOE) to find optimal value of PSOparameter.
One method to avoid the step of parameter optimization is to design multilevel PSO proposed by Pongchairerks and Kachitvichyanukul (2009) that separated the top level PSO to finetune and assigned the parameter values for PSO and the lower level PSO developed for finding JSP solution. However, this approach has the disadvantage of long computational time.
The initiation of adaptive PSO (APSO) is developed to circumvent the step of parameter optimization. An idea of a selfadaptive PSO is developed to allow an automatic parameter setting within the PSO process. Many research works dealt with APSO for adaptive inertia weight as proposed by Shi and Eberhart (1998), Ueno et al. (2005), Gao and Ren (2007), Arumugam and Rao (2008) and Ai and Kachitvichyanukul (2008a); and for acceleration constants proposed by Ai and Kachitvichyanukul (2008b).
The main contribution of this research is to present the application of APSO to solving the bilevel jobshop scheduling problem. This APSO is applied to solve the same problem that was solved by using the basic PSO. The comparisons are made on three parameters: 1) the upper level objective value, 2) the lower level objective value, and 3) the iteration number in which the best solution is first identified. Three parameters are used to display the performance of PSO and APSO in order to compare the quality of the solution and the speed in finding the nearoptimal solution.
The organization of this paper is as follows. Preliminaries, including problem formulation, PSO and adaptive concept, are explained in Section 2. Numerical illustration and conclusion are presented in Sections 3 and 4.
2.PRELIMINARIES
2.1.The Bilevel Multiobjective JobShop Scheduling Formulation
The bilevel multiobjective jobshop scheduling was first proposed by Kasemset and Kachitvichyanukul (2010). The mathematical model was formulated as bilevel form with the upper level of this model that aims to minimize the total idle time on bottleneck machines (B_{n}) as Eq. (1) based on the concept of Theory of Constraints (TOC) that aims to maximize the utilization of bottlenecks. The lower level objective is to improve the schedule performance measures formulated as multiple objectives by minimizing the aggregated maximum value of completion time (C_{max}), tardiness (T_{max}), and earliness (E _{max}) using weighting technique as Eq. (1) to (5). When, W_{1}, W_{2}, and W_{3} are the weights for C_{max}, T _{max}, and E _{max}, respectively.
Objective:
Minimize
Minimize
and;When i, j, and b represent jobs, machines, and bottleneck machines, respectively. X _{ij} are decision variables representing starting time of job i on machine j. U_{i} and D_{i} are demand and due date of job i. s_{ij}and p _{ij}are set up time and processing time of job i on machine j. Those objectives are subjected to the set of constraint of precedence constraints, machine conflict constraints, job ready time constraint, earliest starting time constraints calculated from transfer lot size, nonnegativity constraints and binary constraints. The completed mathematical model and numerical examples are presented in detail as in Kasemset and Kachitvichyanukul (2010).
When solving small size JSP, optimal solution can be derived by using any optimizer program. However, when the size of problem is increased, the solution cannot be obtained by optimizers due to long computational time. Thus, PSO based method was proposed by Kasemset and Kachitvichyanukul (2012) to facilitate in solving JSP when the size of problem was increased. The PSO based method is considered to facilitate in searching for a near optimal solution within reasonable computational time.
2.2.PSO Based Method for Solving Bilevel Multiobjective JSP
PSO is a population based search method introduced by Kennedy and Eberhart (1995). A particle inside the swarm is similar to a chromosome in a population of the GA, but the difference point between PSO and GA is that there are no genetic operations, i.e., crossover and mutation, during PSO process.
PSO process starts with randomly initializing the swarm. The dimension of each particle is designed to match with the solution of any problem. During the process, each particle moves through the solution space with its own assigned velocity accelerated toward its previous best position called pbest (personal best) and the best position of the swarm called gbest (global best). The exchanged experience allows the particles to move to better solutions.
In the basic PSO algorithm, each iteration step mainly consists of only two set of updating equations: velocity as in Eq. (6) and position as in Eq. (7)
The velocity equation as Eq. (6) consists of three elements its velocity, cognitive behavior, and social behavior (detail can be found in Ai and Kachitvichyanukul, 2007).
The PSO based method for bilevel multiobjective JSP proposed by Kasemset and Kachitvichyanukul (2012) were developed based on basic PSO, but there are two unique points designed for handling the bilevel model and transfer lot concept that are: 1) The movement of particles occurs by considering two fitness values representing both level objective values from bilevel formulation. 2) The schedule representation step is differently designed comparing with any PSO method for JSPs because the starting time, X_{ij}, should be derived by considering one additional parameter called “Earliest Starting Time” and this parameter can be calculated based on transfer lot concept proposed in Kasemset and Kachitvichyanukul (2010).
The PSO based method for bilevel multiobjective JSP from Kasemset and Kachitvichyanukul (2012) is briefly described as three main steps.

Encoding and decoding scheme: This PSO applied operationbased representation and random keys representation proposed addresses in Cheng et al. (1996) for decoding process. The advantages of these methods are that every schedule decoded always yield a feasible schedule.
For an n job and m machine JSP, a chromosome contains n×m genes. Then, a solution is encoded using random keys representation. Each gene contains number of position and random number. Then, all genes are sorted in ascending order before starting operationbased representation by repeating genes based on number of operations of each job. For n job and m machine, each job appears on the chromosome exactly m times. After that, all genes are sorted back to its position number to present a sequence of operations and ready for schedule representation in the following step.

Schedule representation: The decoded particle is transformed to a schedule. In this step, the starting time of each job on each machine (X _{ij}) is calculated. When X _{ij} are known, the finish time of each job can be calculated and the performance measurements, C_{max}, T_{max} and E _{max}, can be also determined in the next step.

Fitness value evaluation and updating: As previously mention, when X _{ij}are calculated, the finish time of each job can be derived, so B_{n}, C_{max}, T_{max}, and E_{max} can be calculated following Eqs. (1) and (3)–(5). In this step, two fitness values, B_{n} and F_{t} (following Eq. (2)), are used for particle’s movement. To select gbest, B_{n} is firstly considered due to its higher priority as the upper level objective. When there are many particles with minimum B_{n}, F_{t} will then be considered. This is the unique point of PSO based method for bilevel formulation.
Addressed by Ai and Kachitvichyanukul (2008b), the problem when basic PSO is adopted is how to set up initial parameters of PSO, i.e., inertia weight, acceleration constants (c_{p} and c_{g}), number of particles and other parameters as optimal values. Those parameters surely have effects on the quality of the solution obtained from PSO, so in many research works, the concept of DOE is needed to find the optimal value of those parameters.
One method to avoid the step of parameter optimization is the concept of parameteradaptive or selfadaptive parameter. PSO with selfadaptive parameter, called APSO, is developed to circumvent the step of parameter optimization. The detail of APSO used in this research is briefly explained in the next section.
2.3.Concept of Selfadaptive Parameter in PSO
The concept of APSO is developed to avoid the process of PSOparameter selection because the steps for finding the optimal set of parameters are not easy to be carried out. When the problem is changed, the set of these parameters may be different.
Key parameters in PSO can be listed as;

Inertia weight (w): Particles move with the new velocity from the combination vectors. Inertia weight is a weight to control the magnitude of the current velocity on updating the new velocity. This parameter is one factor playing important role in the velocity update as in Eq. (6) and this parameter controls the search behavior of the swarm, as well.

Acceleration constants: For basic PSO, acceleration constants are c_{p} and c_{g} giving relative importance of p_{best} and g_{best} position when the velocity is updated. Each constant controls the distance that a particle is allowed to move from its current position to any best position. Other acceleration constants (i.e., c_{l} respects to the local best, c_{n} respects to nearneighbor best, etc.) can be also used depended on structure of modified PSO.

Number of particles: Number of particles or popula tion size represents the number of particles in the system. This parameter has effects on fitness value and computational time. Generally, a small population size leads to poor convergence while a large population size yields good convergence but time consuming.
Beside those parameters previously mention, other parameters, i.e., number of iterations, reinitialization related factors, and so on, are also affected the performance of PSO. In this research, APSO proposed by Ai and Kachitvichyanukul (2008a , b)are used to solve the bilevel JSP. This APSO applied the concept of selfadaptive parameter for inertia weight and acceleration constants (c_{p} and c_{g}). The short explanations are address for these two parameters as follows.
2.3.1.Adaptive inertia weight
Proposed by Ai and Kacitvichyanukul (2008a), the inertia weight is set in the range of minimum (wm^{in}) and maximum value (w^{max}). Whenever the swarm velocity index ($\overline{\mathrm{\omega}}$) as in Eq. (8) is lower than the desired velocity index (ω^{*}) as in Eq. (9), the inertia weight is increased, and reversely when the swarm velocity index is greater than the desired velocity index, the inertia weight is decreased. The amount of increases and decreases of inertia weight depends on the difference between the velocity index of the swarm and the desired velocity index.
The updating of inertia weight is as follow Eqs. (10)–(13).
2.3.2.Adaptive acceleration constants
The concept of adaptive acceleration used in this research is modified from Ai and Kachitvichyanukul (2008b). For this research, adaptive concept is used only for cp and cg while the original work proposed to use adaptive concept for four acceleration constants. The concept used here starts with determining the difference between the corresponding objective function of particle's position and the objective function of respective term. In minimizing problem, the large difference means high priority of that term. Then, particles intend to move toward to that term.
The acceleration constants can be determined as the proportion of the respective degree of importance to the constant c^{*}, which is defined as the sum of the acceleration constants. The degree of importance of the whole swarm consisting L particles can be express as Eqs. (14)–(15).
For any iteration, Z_{l} is the fitness value of particle l and Z_{p} and Z_{g} are the fitness value of the pbest and gbest at current iteration. The acceleration constants can be derived as the proportion of degree of importance and updated using exponential weighted moving average technique for avoiding rapid changing of parameters following Eqs. (16)–(18).
In this research paper, c_{p} and c_{g} are adaptive parameters. The process of adaptive c_{p} and c_{g} can be presented as pseudocode as in Figure 1.
From Figure 1, starting from particles initialization or encoding process, particles are improved since step 04 based on Eqs. (6) and (7) as a concept of basic PSO. After that, they are decoded and evaluated using two fitness functions following Eq. (1) for Bn value and Eq. (2) for Ft value. Then, Bn is used for the first priority to set pbest and gbest and Ft is used as the second priority as step 07–14. Then, inertia weight, c_{p} and c_{g} are updated as step 15–18. This process is continued until the number of iteration is completed.
3.NUMERICAL ILLUSTRATION
The test problem from Kasemset (2009) is solved by applied both PSO and APSO. This test problem is the modified JSP with ten jobs and ten machines (10×10) considering monthly demand, job duedate, transfer lot size and setup time of each operation. The detail of job sequences is provided in Appendix.
Bottleneck machines are known as machine number 2, 7, and 9. (The detail of bottleneck identification can be found in detail as addressed in Kasemset (2009) and Kasemset and Kachitvichyanukul (2007). Based on the bilevel formulation, the upper level objective is to minimize the total idle time of three bottleneck machines and the lower level objective is to minimize the aggregated value of C_{max}, T_{max}, and E_{max} with W_{1}, W_{2}, and W_{3} = 1.
3.1.Solving by PSO
Previously, this 10×10 JSP is solved by PSO based method proposed by Kasemset and Kacitvichyanukul (2012) with parameter setting as shown in Table 1.
The result conclusion of PSO proposed by Kasemset and Kacitvichyanukul (2012) shown in Table 2. Three parameters are collected as 1) 1^{st} level objective value (B_{n}), 2) 2^{nd} level objective value (F_{t}), and 3) iteration number in which the best solution is first identified.
3.2.Solving by APSO
APSO is used to solve the test problem and the results are also collected 30 replications. Parameters, excepted c_{p} and c_{g}, are used as previous PSO test. Initially, c_{p} and c_{g} are equally set at 1, c* is 4 and α is 0.8. The test results are shown in Table 3.
3.3.Results Comparison
3.3.1.Bn comparison
The B_{n} results of PSO and APSO are presented as the difference in mean comparison shown in Table 4.
From Table 4, oneside upper B_{n}mean comparison is tested between PSO and APSO. The test hypothesizes are set as follow:
H_{0}: Mean Bn solved by PSO is equal to mean B_{n} solved by APSO.
H_{1}: Mean Bn solved by PSO is greater than mean B_{n} solved by APSO
The pvalue from the test is 0.0018 and less than the significant level (α) 0.05, so the null hypothesis is rejected. Thus, it can be concluded that mean B_{n} solved by PSO differs from mean B_{n} solved by APSO. In fact, there is strong evidence that mean B_{n} solved by PSO exceeds mean B_{n} solved by APSO. For this test problem, APSO can help in B_{n} improvement.
3.3.2.Ft comparison
The F_{t} results are presented as the difference in mean comparison as shown in Table 5.
From Table 5, oneside upper F_{t}mean comparison is tested between PSO and APSO. The test hypothesizes are set as follow:
H_{0}: Mean F_{t} solved by PSO is equal to mean F_{t} solved by APSO.
H_{1}: Mean F_{t} solved by PSO is greater than mean F_{t} solved by APSO.
The pvalue is 0.2031 and greater than the significant level (α) 0.05, so the null hypothesis is accepted. It can be concluded that there is no difference in F_{t}mean from both methods. It implies that APSO cannot help in F_{t} improvement for this test problem.
3.3.3.Iteration number in which the best solution is first identified
The number of iteration found the best solution of each replication for 30 replications of PSO and APSO are compared and presented as the difference in mean comparison shown in Table 6
To confirm this, Table 6 shows oneside upper of this value mean comparison as the test hypothesizes are:
H_{0}: Mean iteration number from PSO is equal to mean iteration number from APSO.
H_{1}: Mean iteration number from PSO is greater than mean iteration number from APSO.
The test pvalue is less than 0.0001. When pvalue is very small, the null hypothesis is rejected. Thus, there is strong evidence that mean iteration number from PSO exceeds mean iteration number from APSO. For this test problem, it can be concluded that the convergence speed of APSO is faster than PSO.
Three comparisons addressed here show that APSO outperforms PSO in term of better Bn value and the iteration number in which the best solution is first identified in this research work.
3.4.Solving by PSO with cp and cg set from APSO
To confirm the performance of APSO, the additional test is set to test that APSO can help in finding the optimal PSOparameter. From Table 3 in Section 4.2, results from APSO, average c_{p} and c_{g} are 0.794 and 1.059, respectively. Table 7 shows the results of 30 replication solved by PSO with adjusted c_{p} and c_{g}.
The parameter mean comparisons between basic PSO and PSO with c_{p} and c_{g} values set from APSO are shown in Table 8. The test hypothesizes are set as follow:
PSO: particle swarm optimization, APSO: adaptive PSO.
These results show that B_{n} and the iteration number in which the best solution is first identified are significantly different (using α = 0.05). For F_{t} value, it cannot be concluded that there is any difference in mean of F_{t} from both methods.
These test results led us to conclude that APSO is useful in finding the optimal c_{p} and c_{g} for improving the Bn value and convergence speed of PSO.
4.CONCLUSION
This study presented the use of PSO and APSO in bilevel problem solving. PSO and APSO are used to solve the same problem of 10×10 bilevel JSP. The results are represented as the comparisons of three factors: 1) 1^{st} level objective value (B_{n}), 1) 2^{nd} level objective value (F _{t}), and 3) iteration number in which the best solution is first identified.
The results show that the solutions solved by APSO are better than PSO in terms of B_{n} and the iteration number in which the best solution is first identified when the mean comparison of the two parameters are tested at α = 0.05. In contrast, F _{t} values from both methods are not significantly different. For B_{n} and the iteration number in which the best solution is first identified, the comparisons confirm that the solution quality of PSO and APSO is significantly different, which indicates that APSO can improve the solution of the bilevel problem in this study.
In an additional test, when c_{p} and c_{g} are set for PSO from average values of those parameters from APSO, the performance of PSO was improved in terms of B_{n} and the convergence speed, as well. The results demonstrate that the advantage of APSO allows researchers to remove the step of parameter optimization and parameter setting required when the basic PSO is used with the equivalent solution quality and the number of iteration needed.