Printer Friendly

Metaheuristics for Order Scheduling Problem with Unequal Ready Times.

1. Introduction

In recent years, various researchers have described customer order scheduling (OS) models (Framinan et al. and [1]). These models can be found in numerous manufacturing and service systems in which several designers, who have developed modules independently for several different products, convene as a product development team, and that team completes a product design only after all the modules have been designed. A practical example is that a manufacturer produces semifinished lenses and competes globally provided by Ahmadi et al. [2].

Regarding the literature on order scheduling with order ready times, only Leung et al. [3] discussed and analyzed the order ready times in a customer order scheduling model with regard to minimizing the total weighted completion time. Garg et al. [1] analyzed the complexities of order schedules to optimize the weighted flow time or offline weighted completion time. Therefore, in this paper we investigate a multiple-machine OS model with different order ready times in which the goal is to find a schedule to minimize the total completion time of n orders. Regarding the importance of ready times in wafer fabrication, readers may refer to Monch et al. [4]. Moreover, the jobs or orders to be processed may have different priorities such as the due dates or weights or ready times. In a model with different ready times, waiting for future order or job arrivals to raise the completeness of a batch is an efficient policy.

Within the relevant literature on taking the total weighted completion times into consideration, it has been shown as an NP-hard by Sung and Yoon [5]. Some effective heuristics were developed by Wang and Cheng [6] and Leung et al. [3, 7, 8] for approximate solutions, and a branch-and-bound algorithm was proposed by Yoon and Sung [9] for the exact solution. For the total completion time criterion minimization, Ahmadi et al. [2] showed that it is NP-hard and built some heuristics accordingly. More recently, Framinan and Perez-Gonzalez [10] studied an OS model with completion time objective but zero ready times. They proposed a constructive heuristic with the same complexity compared to the ECT. The key element of this heuristic lies in its ability to estimate the expected contribution of the unscheduled orders, therefore mitigating the greedy behavior of the ECT. In addition, they proposed two improvement mechanisms that are further embedded into a greedy search procedure (GSA) for finding high-quality solutions. For the OS models with the due dates, readers may refer to Leung et al. [11] for minimizing the maximum lateness and to Lee [12] for minimizing the total tardiness. Extending the problem by Lee [12], Xu et al. [13] assumed that order processing times can be shortened by a position-based learning factor. Framinan and Perez-Gonzalez [14] studied the same problem as Lee [12] did. As extremely fast (negligible time) solutions are required, Framinan and Perez-Gonzalez [14] derived a new constructive heuristic that incorporates a look-ahead mechanism to estimate the objective function at the time that the solution is being built. For the scenarios where longer decision intervals are allowed, they provided a novel matheuristic strategy to provide extremely good solutions. Wu et al. [15] addressed an OS problem with sum of-processing-time-based learning effect to minimize total tardiness of the orders. For other researches on OS models, readers may refer to Yang and Posner [16], Leung et al. [3, 17], and Leung, Li et al. [18] on identical but parallel machine settings. Lin et al. [19] utilized three variants of a particle swarm optimization (PSO) algorithm including a basic PSO, an opposite-based PSO, and a PSO with a declined inertia weight for a OS model with two agents and ready times. The criterion is to minimize the total completion time for the orders from agent A while the total completion time for the orders from agent B has a given upper bound. Wu et al. [20] considered an OS model to minimize the linear sum of the total flowtime and the maximum tardiness. In particular, they proposed a branch-and-bound (B&B) algorithm along with several dominance relations and a lower bound, three modified heuristics, and a hybrid iterated greedy algorithm to solve the problem. For some substantial works on approximation algorithms for 1[absolute value of ([r.sub.j])], [summation] [C.sub.j], readers may refer to Chekuri et al. [21], Hochbaum and Shmoys [22], Sevastianov and Woeginger [23], Alon et al. [24], and Schuurnman and Woeginger [25]. Readers may refer to Chen et al. [26] for a general overview of approximation techniques. The main contributions of this work are described as follows: an order scheduling problem of introducing ready times for each orders and minimizing the total completion time criterion is studied. A B&B method with four propositions and two lower bounds is derived for finding the exact solution. Four versions of simulated annealing algorithm (SA) and four versions of genetic algorithm (GA) are provided for searching the good-quality approximate solutions. The instance simulation experiments and some statistical methods are utilized to determine the performances for all proposed algorithms.

The rest of this study is organized as follows: Section 2 introduces the notation and formulates the problem. Section 3 provides some dominance propositions and two lower bounds used in a branch-and-bound (B&B) algorithm. Section 4 proposes four variants of a simulated annealing (SA) approach and four heuristic genetic algorithms (GA) for finding approximate solutions. Section 5 presents computational results to evaluate the performance of the eight proposed algorithms. The conclusion and suggestions for future study are provided in Section 6.

2. Problem Statement

This section first introduces some notation that is applied in this study.

n: total order number

m: total machine number

[M.sub.k] : machine k, k = 1, 2, ..., m

S = ([pi], i, j, [pi]') and S' = ([pi], j, i, [pi]'): schedules of n orders where [pi] and [pi]' denote partial sequences of the n orders

[t.sub.ik]: processing time for order i on machine k, k = 1, 2, ..., m; i = 1, 2, ..., n

[r.sub.i]: ready time for order i, i = 1, 2, ..., n

[s.sub.k]: completion time for the last order in n on machine k, k = 1, 2, ..., m

[C.sub.i](S): completion time of order i in S, i.e.,

[mathematical expression not reproducible]; (1)

[l] is the order which is arranged in the lth position in a given schedule.

The problem is formulated as follows. Suppose that n orders come in from n different clients at different times (ready times), and each order comprises m components. Let a facility with m different machines be operated in parallel form. A machine can produce its own item; that is, an item can be done on a dedicated machine. If each order has its own ready time, then unforced idleness is also allowed. Preemptions are not forbidden. Let [t.sub.ik] denote the processing time for component k of order i to be processed on machine k and let [r.sub.[i]] denote order i to be placed in the rth position in a given sequence. The objective is to seek a sequence to let the total completion time criterion be minimized. To find that the optimal sequence is equivalent to finding a schedule S that optimizes the objective function [[summation].sup.n.sub.i=1] [C.sub.i](S), an illustrative example follows.

Example 1. Given an instance problem with n = 2, m = 2. The processing times of each component of order [O.sub.i], i = 1, 2, on machine [M.sub.k], and the ready times of order [O.sub.i], i = 1, 2, are provided in Table 1.

Given an order schedule S = ([O.sub.1], [O.sub.2]), according to the definition of [C.sub.i](S), one have the following computation, and Figure 1 shows the Gantt diagram.

[mathematical expression not reproducible] (2)

3. Propositions and Lower Bound

Branch-and-bound (B&B) has received a considerable amount of attention for solving numerous combinatorial problems (Pinedo 2008; [27-29]). On the basis of the proof by Lenstra et al. [30] that the problem 1[absolute value of ([r.sub.j]] [summation][C.sub.j] is strongly NP-hard when each order has one component only, we know our proposed problem is also an NP-hard problem. Garg et al. [1] also demonstrated that even the unweighted completion time problem with a single ready time is NP-hard. Thus, two lower bounds and certain dominant properties can be applied in a B&B algorithm to find an optimal solution. Following that, four variants of a simulated annealing and four heuristic genetic algorithms are proposed for finding near-optimal solutions.

Let S = ([pi], i, j, [pi]') and S' = ([pi], j, i, [pi]') denote two schedules, in which [pi] and [pi]' are partial sequences. Assume that [C.sub.i](S) and [C.sub.j](S) are the completion times of orders i and j in S, whereas [C.sub.j](S') and [C.sub.i](S') denote the completion times of orders j and i in S'. To demonstrate that S dominates S', it suffices to show that [C.sub.i](S) + [C.sub.j](S) [less than or equal to] [C.sub.j](S') + [C.sub.i](S') and [C.sub.j](S) < [C.sub.i](S').

Proposition 2. If [r.sub.j] > [r.sub.i] [greater than or equal to] [max.sub.1[less than or equal to]k[less than or equal to]m]{[s.sub.k]}, [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.ik]} [less than or equal to] [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.jk]}, and [r.sub.i] + [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.ik]} [greater than or equal to] [r.sub.j], then S dominates S'.

Proof. From [r.sub.j] > [r.sub.i] [greater than or equal to] [max.sub.1[less than or equal to]k[less than or equal to]m]{[s.sub.k]}, we have

[mathematical expression not reproducible]. (3)

From [r.sub.i] + [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.ik]} [greater than or equal to] [r.sub.j] and [r.sub.j] > [r.sub.i], we have

[mathematical expression not reproducible] (4)

and

[mathematical expression not reproducible]. (5)

Because [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.ik]} [less than or equal to] [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.jk]} and [r.sub.j] > [r.sub.i], we have

[C.sub.i](S) [less than or equal to] [C.sub.j](S') and [C.sub.j](S) < [C.sub.i](S'). (6)

Therefore, S dominates S'.

Proposition 3. If [r.sub.i], [greater than or equal to] [max.sub.1[less than or equal to]k[less than or equal to]m]{[s.sub.k]} and [r.sub.i] + [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.ik]} < [r.sub.j], then S dominates S'.

Proposition 4. If [min.sub.1[less than or equal to]k[less than or equal to]m]{[s.sub.k]} [greater than or equal to] max{[r.sub.i],[r.sub.j]} and [max.sub.1[less than or equal to]k[less than or equal to]m]{[k.sub.k] + [t.sub.ik]} < [max.sub.1[less than or equal to]k[less than or equal to]m]{[k.sub.k] + [t.sub.jk]}, then S dominates S'.

Proposition 5. If max{[s.sub.k],[r.sub.j]} [greater than or equal to] max{[s.sub.k],[r.sub.i]} and [t.sub.ik] [less than or equal to] [t.sub.jk] for k = 1,2, ..., m, then S dominates S'.

The proofs of Propositions 3-5 are omitted because they are similar to that of Proposition 2.

Next, a lower bound is another element to raise the efficiency of a B&B algorithm; the algorithm can be expedited by eliminating the partial nodes. In the following, two lower bounds will be proposed for the B&B method. Let AS be a partial sequence, in which the order of the first v jobs is determined and let US be the unscheduled part consisting of [n.sub.1] = (n-v) jobs. Furthermore, let [s.sub.k] be the starting time of the first order in US for machine k, and [bar.s] = [[summation].sup.m.sub.k=1] [s.sub.k]/m. Following the definition of (1), we have

[mathematical expression not reproducible], (7)

From the above discussions, we have

[mathematical expression not reproducible]. (8)

Regarding the second right-hand term of (8), according to Hardy et al. [31], the value of [mathematical expression not reproducible] may be optimized when the orders {[n.sub.1]-i + 1} and {[[summation].sup.m.sub.k=1][t.sub.[v+i]k}] are ordered in opposite ways. Therefore, the first lower bound ([LB.sub.1]) can be obtained as follows.

[mathematical expression not reproducible], (9)

where [mathematical expression not reproducible] denotes the nondecreasing form of {[t.sub.v+i*]}, and x + [n.sub.1] = n.

Adopting similar steps, another lower bound is easily derived as follows.

[mathematical expression not reproducible], (10)

where [mathematical expression not reproducible] for the remaining orders in US.

To tighten the lower bound, the maximum value from (9) and (10) can be set as the lower bound of AS; i.e.,

[mathematical expression not reproducible]. (11)

4. Four Variants of SA and Four GA Algorithms

Metaheuristics have been widely utilized to numerous discrete or continuous NP-hard dynamic combinatorial models. For more examples, readers may refer to Kirkpatrick et al. [32] and Holland [33], among other works. Because the problem under study is considerably difficult, to minimize the solution time cost increased by the solving process, we developed four simulated annealing (SA) approaches and four genetic algorithms (GAs) for near-optimal solutions. Notably, both SA and GA are not simple heuristics; they are metaheuristics. This is crucial because heuristics are usually simple algorithms, but they are complex metaheuristics and they are also difficult to build and carry when comparing with simple heuristics.

The SA is one of the most common metaheuristics to apply for many discrete or continuous optimization problems (see [32, 34]). The main procedures of SA are described in the following.

The main steps of SA procedure:

Do while (iteration time < 500*n)

(i) Input three initial sequences in SA.

(ii) For each initial sequence, improve it with the pairwise interchange neighborhood generation method.

(iii) Determine if a new sequence is preferable to the original sequence; if the new sequence is preferable, then replace the original sequence with the new sequence; however, if the new sequence is not preferable to the original sequence, the original sequence is accepted if P(accept) > q, where 0 < q < 1 and P(accept) = exp(-[alpha] x [DELTA]T), [alpha] = k/[beta], and [beta] = 10 is an experimental constant.

End do

GA widely used another metaheuristic using an intelligent random searching policy to solve numerous difficult NP-hard problems. The important steps are including a structure, a population, a fitness function, reproduction mechanism, and a crossover operator to generate offspring. For more details, readers may refer to Holland [33] and Essafi et al. [35]. The procedure of the proposed GA is detailed as follows.

The steps of GA procedure:

Do while (generation sizes < 500)

(i) Input three initial sequences to generate N = 20 populations in GA.

(ii) Compute the total completion time for each population and then calculate fitness function values of the strings as [mathematical expression not reproducible], where [S.sub.i](v) is the ith string chromosome in the vth generation; determine the selection probability of a schedule as P([S.sub.i](v)) = f([S.sub.i](v))/ [[summation].sup.N.sub.l=1] f([S.sub.l](v)).

(iii) Use a linear order crossover in the GA (see Falkenauer and Bouffouix, [36]), and set the crossover rate [P.sub.c] at 1.

(iv) Set the value of mutation ([P.sub.m]) at 0.35.

(v) Excluding the ideal schedule with a minimum total completion time of n orders, create the other offspring from the parent sequences by using the roulette wheel method.

End do

In the present work, to obtain the final solution as quickly as possible, three initial sequences are adopted in SA or GA. In SA_min or GA_min, orders are arranged in nondecreasing sequence of [r.sub.j] + [min.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.jk]}, whereas, in SA_max or GA_max, orders are arranged in nondecreasing sequence of [r.sub.j] + [max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.jk]}. In SA_mean or GA_mean, orders are arranged in nondecreasing sequence of [r.sub.j] + [[summation].sup.m.sub.k=1]([t.sub.jk]/m).

The weighted earliest completion time (WECT) heuristic from Leung et al. [3] is incorporated into SA and GA; they are recoded as SA_wect and GA_wect, respectively. Because the objective of this study is to minimize the total completion function of all n orders, instead of the total weighted completion time, we set all [w.sub.i] = 1. Let N denote the set of n orders. Initially, place the order returned from [min.sub.i[member of]N]{[max.sub.1[less than or equal to]k[less than or equal to]m]{[t.sub.jk] + [r.sub.i])} in the first position and find its completion time, denoted as [C.sub.[1]]. Next, delete the scheduled order from N, and place the order returned from [min.sub.j[member of]N]{([C.sub.j] - [C.sub.[1]])} in the second position. Repeat this process similarly for all orders. This is called the WECT method. For more details, readers may refer to Leung et al. [3].

5. Computational Experiments

Several experimental tests were conducted to determine the performance of the B&B, the four SAs, and four GAs. Those proposed algorithms are written in FORTRAN.

According to the scheme of Lee [12] and Leung et al. [3, 8, 17], the order processing times are created from the uniform distribution U (1,100) in every case. According to the scheme of Reeves [37], the order ready times are created from another uniform distribution U (0, 100n[lambda]) where n is the order-size and [lambda] was a control variable. The value of [lambda] was set at 0.25, 0.5, and 0.75.

To determine the B&B performance, we report the mean and maximum numbers of nodes and the mean and maximum CPU times (in seconds), respectively. For the variants of SA or GA algorithms based on small numbers of orders (n = 12, 14, or 16), we report the mean and maximum error percentages in which the average error percentage (AEP) was defined as AEP = ([H.sub.i]-[O.sup.*])/[O.sup.*] x 100%, where [H.sub.i] was the value of the total completion time yielded from SA or GA and [O.sup.*] was the value of total completion time yielded from the B&B algorithm.

For the variants of SA or GA algorithms based on large numbers of orders (n = 50 or 100), we recorded the mean and maximum relative percentages of deviation (RPDs) in which the RPD was defined as RPD = [([H.sub.i]-[H.sup.*])/[H.sup.*]] x 100%, where [H.sub.i] was the value of total completion time yielded from SA or GA and [H.sup.*] was the smallest objective value selected from among the four SAs and the four GAs.

The two parts of the computational experiment involved small numbers of orders and large numbers of orders.

For the small numbers of orders, we set the numbers of machines at m = 2, 3, and 4. The number of orders was tested at n = 12, 14, and 16. A set of 100 instances was randomly generated for each case.

In the experiment, the B&B was set to skip to the next data set if the number of nodes exceeded [10.sup.8]. The computational results of the B&B method are presented in Table 2, where the last column FS reports the number of instances for which the B&B achieved the optimal solution. The results from Table 2 can be examined in detail; the changes of number of nodes obtained by the B&B method with variations in the parameters n, m, and [lambda] are illustrated in Tables 3 and 4. From Table 3, it can be found that the number of nodes tends to decrease for each fixed value of n as the value of [lambda] increases. On the contrary, it appears from Table 4 that the number of nodes tends to increase for each fixed value of n as the value of m increases except for n=16.

The computational results obtained by the four SAs and four GAs are given in Table 5, and the AEPs are obtained by these algorithms as the parameters n, m, and [lambda] vary. From Table 5, it can be seen that the AEP values obtained by all algorithms tend to linearly decrease as A increases for n = 12 and n = 14. For n = 16, the AEP values obtained by these algorithms first increase but then decrease as [lambda] increases. Table 5 also indicates that the variation range of AEP obtained by each algorithm is relatively small and the results reveal no trace concerning the impact of m on the AEP.

Regarding the performance of these algorithms, the box plots in Figure 6 display the AEP distributions of the eight algorithms. To compare the statistically significant differences in solution quality levels for solutions from the four SAs and the four GAs, we applied analysis of variance (ANOVA); the p value was less than 0.05, as seen in Table 6. We then employed SAS package software to do Fisher's least significant difference (LSD) tests; the outcomes are shown in Table 7. At the 0.05 level of significance, the AEP means were divided into three groups. The AEPs of SA-mean and SA-max were in the smallest (optimal) group, and AEP of the GA-wect was the largest (worst), whereas the AEPs of the other five algorithms were in the middle group. The SA-max and SA-mean algorithms can be recommended for small numbers of orders.

In experiments with large numbers of orders, we set the numbers of orders at n = 50 and 100 and the numbers of machines at m = 5, 10, and 20. One hundred instances were randomly created for each case.

The performance results of the four SAs and the four GAs are presented in Tables 10 and 11, and the RPDs and corresponding CPU times obtained by these algorithms as the parameters n, m, and [lambda] varied are illustrated in Figures 2-5. Concerning the RPD metric, no pattern is evident in Figure 2 regarding the impact of [lambda] on the performance levels of these SAs and GAs. The reason is that for n = 50 the RPD slightly increases (except for SA-mean) as [lambda] increases, whereas for n = 100 the RPD slightly decreases (GA-max first increases but then decreases) as [lambda] increases. From Figure 3, it is found that for n = 50 the RPD obtained by each algorithm first increases but then decreases quickly as m increases. For n = 100, the RPD values obtained by SAs remain unchanged but the RPD values obtained by GAs tend to decrease linearly as m increases. In addition, from Figures 2 and 3, it can be concluded that the performance levels of SAs are superior to those of GAs. Regarding the CPU time metric, Figures 4 and 5 indicate that the values of [lambda] have little impact on the CPU times used by SAs and GAs; however, as m increases, the CPU times used by these algorithms quickly increase.

As shown in Figure 7, the box plots of RPDs illustrate the performance levels of the eight algorithms for large numbers of orders. It is obvious that the four SA algorithms outperformed the GAs, and the GA-wect performed the worst. However, another ANOVA, shown in Table 8, and another set of Fisher's least significant difference tests, shown in Table 9, indicate that, at the 0.05 significance level, there are no differences among the algorithms except for GA-wect. Furthermore, the box plots in Figure 7 also indicate that the RPDs of the four SAs have less dispersion; thus, the SA algorithms solve these problems with both accuracy and stability when the numbers of orders are large.

6. Conclusions

Multifacility order scheduling model has become a vital challenge in numerous practical service and manufacturing situations. Unlike previous studies, which have assumed that all orders are available at time zero, this study investigates orders with different ready times and provides several contributions. First, two lower bounds and several dominant properties are developed, based on which a B&B algorithm is proposed to solve the problem with a small number of orders. Second, four SA variants and four GA variants are presented to obtain near-optimal solutions for problems with large numbers of orders. Computational experiments based on extensive test problems were conducted to evaluate the performance levels of the proposed B&B algorithm and the various SAs and GAs, as well as the impacts of parameters on their performance levels. The experimental outcomes reported that, with the help of the lower bounds and properties, the B&B can tackle problem instances up to n = 16 within a considerable time. In addition, the tested outcomes also illustrate that the four SA variants and the four GA variants deliver satisfactory performance in terms of efficacy and efficiency for problem instances with both small and large numbers of orders. Based on the outcomes obtained by the algorithms, it is recommended that SA-mean or SA-max be utilized to solve the proposed problem because they both outperform GAs and can quickly achieve favorable solutions with a very small value of AEPs. It can be also seen that the problem scale that can be solved by the proposed B&B algorithm only up to n = 16 is limited. The dominance relations or lower bounds of the B&B method appear to be not strong or tight enough. A future study may develop more powerful dominance relations or lower bounds.

https://doi.org/10.1155/2018/4657368

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This paper was supported in part by Taiwan's Ministry of Science and Technology under Grant no. MOST105-2221-E-035-053-MY3.

References

[1] N. Garg, A. Kumar, and V. Pandit, "Order Scheduling Models: Hardness and Algorithms, FSTTCS," in Foundations of Software Technology and Theoretical Computer Science, vol. 4855 of Lecture Notes in Computer Science, pp. 96-107, 2007.

[2] R. Ahmadi, U. Bagchi, and T. A. Roemer, "Coordinated scheduling of customer orders for quick response," Naval Research Logistics (NRL), vol. 52, no. 6, pp. 493-512, 2005.

[3] J. Y. Leung, H. Li, and M. Pinedo, "Scheduling orders for multiple product types to minimize total weighted completion time," Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, vol. 155, no. 8, pp. 945-970, 2007.

[4] L. Monch, H. Balasubramanian, J. W. Fowler, and M. E. Pfund, "Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times," Computers & Operations Research, vol. 32, no. 11, pp. 2731-2750, 2005.

[5] C. S. Sung and S. H. Yoon, "Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines," International Journal of Production Economics, vol. 54, no. 3, pp. 247-255, 1998.

[6] G. Wang and T. C. E. Cheng, "Customer order scheduling to minimize total weighted completion time," Omega, vol. 35, no. 5, pp. 623-626, 2007.

[7] J. Y. Leung, H. Li, and M. Pinedo, "Order scheduling in an environment with dedicated resources in parallel," Journal of Scheduling, vol. 8, no. 5, pp. 355-386, 2005.

[8] J. Y. Leung, C. Y. Lee, C. W. Ng, and G. . Young, "Preemptive multiprocessor order scheduling to minimize total weighted flowtime," European Journal of Operational Research, vol. 190, no. 1, pp. 40-51, 2008.

[9] S. H. Yoon and C. S. Sung, "Fixed pre-assembly scheduling on multiple fabrication machines," International Journal of Production Economics, vol. 96, no. 1, pp. 109-118, 2005.

[10] J. M. Framinan and P. Perez-Gonzalez, "New approximate algorithms for the customer order scheduling problem with total completion time objective," Computers & Operations Research, vol. 78, pp. 181-192, 2017.

[11] J. Y. Leung, H. Li, and M. Pinedo, "Scheduling orders for multiple product types with due date related objectives," European Journal of Operational Research, vol. 168, no. 2, pp. 370-389, 2006.

[12] I. S. Lee, "Minimizing total tardiness for the order scheduling problem," International Journal of Production Economics, vol. 144, no. 1, pp. 128-134, 2013.

[13] J. Xu, C. C. Wu, Y. Yin, C. L. Zhao, Y. T. Chiou, and W. C. Lin, "An order scheduling problem with position-based learning effect," Computers & Operations Research, vol. 74, pp. 175-186, 2016.

[14] J. M. Framinan and P. Perez-Gonzalez, "Order scheduling with tardiness objective: improved approximate solutions," European Journal of Operational Research, vol. 266, no. 3, pp. 840-850, 2018.

[15] C. Wu, W. Lin, X. Zhang, I. Chung, T. Yang, and K. Lai, "Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect," Journal of the Operational Research Society, pp. 1476-9360, 2018.

[16] J. Yang and M. E. Posner, "Scheduling parallel machines for the customer order problem," Journal of Scheduling, vol. 8, no. 1, pp. 49-74, 2005.

[17] J. Y. Leung, H. Li, and M. Pinedo, "Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel," Naval Research Logistics (NRL), vol. 53, no. 4, pp. 243-260, 2006.

[18] J. Y. Leung, H. Li, and M. Pinedo, "Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time," Annals of Operations Research, vol. 159, pp. 107-123, 2008.

[19] W. C. Lin, Y. Yin, S. R. Cheng, T. C. E. Cheng, C. H. Wu, and C. C. Wu, "Particle swarm optimization and opposite-based particle swarm optimization for two-agent multi-facility customer order scheduling with ready times," Applied Soft Computing, vol. 52, pp. 877-884, 2017.

[20] C.-C. Wu, S.-C. Liu, T.-Y. Lin, T.-H. Yang, I.-H. Chung, and W.-C. Lin, "Bicriterion total flowtime and maximum tardiness minimization for an order scheduling problem," Computers & Industrial Engineering, vol. 117, pp. 152-163, 2018.

[21] C. Chekuri, R. Motwani, B. Natarajan, and C. Stein, "Approximation techniques for average completion time scheduling," in Proceedings of the annual ACM-SIAM symposium on discrete algorithm (SODA), pp. 609-617, 1997.

[22] D. S. Hochbaum and D. B. Shmoys, "Using dual approximation algorithms for scheduling problems: theoretical and practical results," Journal of the ACM, vol. 34, no. 1, pp. 144-162, 1987.

[23] S. V. Sevastianov and G. J. Woeginger, "Makespan minimization in open shops: a polynomial time approximation scheme," Mathematical Programming, vol. 82, no. 1-2, Ser. B, pp. 191-198, 1998.

[24] N. Alon, Y. Azar, G. J. Woeginger, and T. Yadid, "Approximation schemes for scheduling on parallel machines," Journal of Scheduling, vol. 1, no. 1, pp. 55-66, 1998.

[25] P. Schuurman and G. J. Woeginger, "Polynomial time approximation algorithms for machine scheduling: ten open problems," Journal of Scheduling, vol. 2, no. 5, pp. 203-213, 1999.

[26] B. Chen, C. N. Potts, and G. J. Woeginger, "A review of machine scheduling: complexity, algorithms and approximability," in Handbook of Combinatorial Optimization, D-Z. Du and P. Paradalos, Eds., vol. 3, pp. 21-169, Kluwer Academic Press, Boston, MA, usa, 1998.

[27] S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop, Ellis Horwood Limited, 1982.

[28] M. Abouei Ardakan, A. Hakimian, and M. T. Rezvan, "A branch-and-bound algorithm for minimising the number of tardy jobs in a two-machine flow-shop problem with release dates," International Journal of Computer Integrated Manufacturing, vol. 27, no. 6, pp. 519-528, 2014.

[29] O. Mashkani and G. Moslehi, "Minimising the total completion time in a single machine scheduling problem under bimodal flexible periodic availability constraints," International Journal of Computer Integrated Manufacturing, vol. 29, no. 3, pp. 323-341, 2016.

[30] J. K. Lenstra, A. H. Rinnooy Kan, and P. Brucker, "Complexity of machine scheduling problems," in Annals of Discrete Mathematics, vol. 1, pp. 343-362, North-Holland, Amsterdam, The Netherlands, 1977.

[31] G. H. Hardy, J. E. Littlewood, and G. Polya, Inequalities, Cambridge University Press, London, UK, 1967.

[32] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671-680, 1983.

[33] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

[34] D. Ben-Arieh and O. Maimon, "Annealing method for PCB assembly scheduling on two sequential machines," International Journal of Computer Integrated Manufacturing, vol. 5, no. 6, pp. 361-367, 1992.

[35] I. Essafi, Y. Mati, and S. Dauzere-Peres, "A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem," Computers & Operations Research, vol. 35, no. 8, pp. 2599-2616, 2008.

[36] E. Falkenauer and S. Bouffouix, "A genetic algorithm for job shop," in Proceedings of the 1991 IEEE International Conference on Robotics and Automation, pp. 824-829, April 1991.

[37] C. Reeves, "Heuristics for scheduling a single machine subject to unequal job release times," European Journal of Operational Research, vol. 80, no. 2, pp. 397-403, 1995.

Jan-Yee Kung, (1) Jiahui Duan, (2) Jianyou Xu, (3) I-Hong Chung, (4) Shuenn-Ren Cheng, (1,5) Chin-Chia Wu (iD), (4) and Win-Chin Lin (iD) (4)

(1) Department of Business Administration, Cheng Shiu University, Kaohsiung 1037, Taiwan

(2) Business School, Sichuan University, Chengdu 610064, China

(3) College of Information Science and Engineering, Northeastern University, Shenyang 110819, China

(4) Department of Statistics, Feng Chia University, Taichung 40724, Taiwan

(5) Shandong Yingcai University, Shandong, Jinan 250104, China

Correspondence should be addressed to Win-Chin Lin; linwc@fcu.edu.tw

Received 9 June 2018; Revised 14 August 2018; Accepted 4 September 2018; Published 18 September 2018

Academic Editor: Filippo Cacace

Caption: Figure 1: The Gantt diagram of the completion times of two orders.

Caption: Figure 2: Change of RPD for each n as [lambda] increases for SAs and GAs for large number of orders.

Caption: Figure 3: Change of RPD for each n as m increases for SAs and GAs for large number of orders.

Caption: Figure 4: Change of CPU time for each n as [lambda] increases for SAs and GAs for large number of orders.

Caption: Figure 5: Change of CPU time for each n as m increases for SAs and GAs for large number of orders.

Caption: Figure 6: Box plots of AEP for the algorithms for small number of orders.

Caption: Figure 7: Box plots of RPD for the algorithms for large number of orders.
Table 1: Data for Example 1.

                 [O.sub.1]    [O.sub.2]

[t.sub.i1]           1            2
[t.sub.i2]           3            5
[r.sub.i]            2            6

Table 2: Computational results of the branch-and-bound method.

                            Number of nodes
n       m     [lambda]
                            mean         max

12      2       0.25      73056.61     2766243
                0.5       7509.79       329861
                0.75      1216.78       14199

        3       0.25      325210.3     5908745
                0.5       18605.52      386331
                0.75      3250.92       39243

        4       0.25      1889929      29703900
                0.5       36485.91     1125381
                0.75      5020.36       57669

14      2       0.25      843689.3     21839448
                0.5       17778.5       362433
                0.75      6004.25       73865

        3       0.25      6090544      69349704
                0.5       218458.6     8975480
                0.75      37785.98      689467

        4       0.25      33331922    435865824
                0.5       204696.6     6275558
                0.75      55313.7      1829593

16      2       0.25      3666306      47015688
                0.5       124890.3     4700103
                0.75      226230.2     11121498

        3       0.25      15812686     98160472
                0.5       2029674      47596468
                0.75      792803.5     36248012

        4       0.25      11951878     79378032
                0.5       2418552      31824482
                0.75      438707.6     20652540

                            CPU time (seconds)
n       m     [lambda]                                 FS
                            mean         max

12      2       0.25       0.717        24.508        100
                0.5        0.084        3.401         100
                0.75       0.019        0.172         100

        3       0.25       3.926        63.461        100
                0.5        0.237        4.898         100
                0.75       0.057        0.624         100

        4       0.25       26.156      358.132        100
                0.5         0.55        14.758        100
                0.75       0.099        0.936         100

14      2       0.25       11.369      277.105        100
                0.5        0.267        4.602         100
                0.75       0.119        1.154         100

        3       0.25       105.13      1209.756       100
                0.5        3.702       149.324        100
                0.75       0.778        15.678        100

        4       0.25      659.244      8244.48        100
                0.5        4.187       126.234        100
                0.75       1.331        33.812        100

16      2       0.25       63.802      780.504         86
                0.5        2.473        87.454        100
                0.75        5.07       251.271        100

        3       0.25      271.753      1947.797        64
                0.5        40.71       764.967         99
                0.75       22.483      1078.575       100

        4       0.25      269.248      1781.984        39
                0.5        65.916      959.827         98
                0.75       19.078      921.186        100

Table 3: The impact of [lambda] in the branch-and-bound algorithm.

n       [lambda]       node       CPU time        FS

12        0.25        762732       10.26         300
          0.5         20867         0.29         300
          0.75         3163         0.06         300

14        0.25       13422052      258.58        300
          0.5         146978        2.72         300
          0.75        33035         0.74         300

16        0.25       10476957      201.6         189
          0.5        1524372       36.36         297
          0.75        485913       15.54         300

Table 4: The impact of m in the branch-and-bound algorithm.

n       m        node       CPU time        FS

12      2       27261         0.27         300
        3       115689        1.41         300
        4       643812        8.94         300

14      2       289157        3.92         300
        3      2115596       36.54         300
        4      11197311      221.59        300

16      2      1339142       23.78         286
        3      6211721       111.65        263
        4      4936379       118.08        237

Table 5: Computational results of the SAs and GAs for small number
of orders.

                                SA-min             SA-mean
n       m     [lambda]          error               error

                           mean       max      mean       max

12      2       0.25       0.006     0.031     0.004     0.032
                 0.5       0.004     0.019     0.002     0.020
                0.75       0.002     0.010     0.001     0.006

        3       0.25       0.006     0.028     0.006     0.065
                 0.5       0.003     0.022     0.002     0.024
                0.75       0.002     0.011     0.001     0.005

        4       0.25       0.007     0.042     0.005     0.042
                 0.5       0.003     0.030     0.002     0.014
                0.75       0.002     0.010     0.001     0.007

14      2       0.25       0.007     0.036     0.005     0.042

                 0.5       0.003     0.020     0.002     0.024
                0.75       0.002     0.010     0.001     0.006

        3       0.25       0.007     0.027     0.005     0.038
                 0.5       0.004     0.015     0.003     0.027
                0.75       0.002     0.016     0.001     0.008

        4       0.25       0.008     0.038     0.006     0.031
                 0.5       0.005     0.018     0.002     0.018
                0.75       0.002     0.012     0.001     0.008

16      2       0.25       0.009     0.035     0.007     0.039
                 0.5       0.003     0.021     0.002     0.015
                0.75       0.002     0.009     0.001     0.008

        3       0.25       0.008     0.023     0.008     0.055
                 0.5       0.005     0.026     0.003     0.023
                0.75       0.002     0.013     0.001     0.006

        4       0.25       0.007     0.018     0.004     0.017
                 0.5       0.004     0.023     0.002     0.009
                0.75       0.003     0.014     0.001     0.005

                               SA-max              SA-wect
n       m     [lambda]          error               error

                           mean       max      mean       max

12      2       0.25       0.004     0.075     0.006     0.038
                 0.5       0.002     0.026     0.003     0.013
                0.75       0.001     0.008     0.002     0.013

        3       0.25       0.005     0.034     0.005     0.028
                 0.5       0.002     0.022     0.004     0.019
                0.75       0.001     0.005     0.002     0.017

        4       0.25       0.004     0.034     0.007     0.044
                 0.5       0.002     0.015     0.003     0.020
                0.75       0.001     0.007     0.002     0.013

14      2       0.25       0.006     0.048     0.007     0.046
                 0.5       0.002     0.028     0.003     0.025
                0.75       0.001     0.006     0.002     0.012

        3       0.25       0.006     0.045     0.007     0.041
                 0.5       0.003     0.016     0.004     0.028
                0.75       0.001     0.009     0.002     0.015

        4       0.25       0.006     0.048     0.007     0.043
                 0.5       0.003     0.019     0.004     0.020
                0.75       0.001     0.023     0.002     0.012

16      2       0.25       0.006     0.037     0.008     0.031
                 0.5       0.002     0.023     0.003     0.013
                0.75       0.001     0.006     0.002     0.013

        3       0.25       0.006     0.032     0.008     0.022
                 0.5       0.003     0.022     0.005     0.018
                0.75       0.001     0.009     0.002     0.011

        4       0.25       0.005     0.035     0.006     0.028
                 0.5       0.002     0.012     0.003     0.012
                0.75       0.001     0.006     0.002     0.014

                               GA-min              GA-mean
n       m     [lambda]          error               error

                           mean       max      mean       max

12      2       0.25       0.004     0.043     0.005     0.038
                 0.5       0.003     0.019     0.002     0.020
                0.75       0.000     0.017     0.000     0.005

        3       0.25       0.005     0.035     0.004     0.045
                 0.5       0.002     0.033     0.002     0.020
                0.75       0.000     0.009     0.001     0.009

        4       0.25       0.007     0.041     0.007     0.033
                 0.5       0.003     0.022     0.002     0.017
                0.75       0.000     0.012     0.001     0.012

14      2       0.25       0.010     0.052     0.009     0.044
                 0.5       0.003     0.023     0.004     0.035
                0.75       0.001     0.017     0.000     0.008

        3       0.25       0.007     0.058     0.009     0.042
                 0.5       0.003     0.018     0.004     0.027
                0.75       0.001     0.011     0.001     0.010

        4       0.25       0.009     0.050     0.009     0.039
                 0.5       0.004     0.026     0.004     0.023
                0.75       0.001     0.009     0.001     0.010

16      2       0.25       0.014     0.057     0.011     0.051
                 0.5       0.004     0.026     0.004     0.025
                0.75       0.001     0.035     0.001     0.012

        3       0.25       0.013     0.047     0.012     0.070
                 0.5       0.005     0.028     0.006     0.029
                0.75       0.001     0.022     0.001     0.014

        4       0.25       0.010     0.032     0.012     0.037
                 0.5       0.005     0.022     0.005     0.040
                0.75       0.001     0.013     0.001     0.009

                               GA-max              GA-wect
n       m     [lambda]          error               error

                           mean       max      mean       max

12      2       0.25       0.004     0.042     0.007     0.063
                 0.5       0.003     0.038     0.003     0.020
                0.75       0.000     0.012     0.001     0.013

        3       0.25       0.005     0.048     0.006     0.070
                 0.5       0.002     0.029     0.002     0.024
                0.75       0.000     0.006     0.001     0.028

        4       0.25       0.005     0.049     0.006     0.041
                 0.5       0.002     0.025     0.003     0.030
                0.75       0.000     0.007     0.001     0.014

14      2       0.25       0.011     0.070     0.012     0.055
                 0.5       0.003     0.031     0.005     0.029
                0.75       0.001     0.009     0.002     0.023

        3       0.25       0.006     0.037     0.010     0.077
                 0.5       0.005     0.028     0.007     0.078
                0.75       0.001     0.011     0.002     0.024

        4       0.25       0.009     0.047     0.011     0.055
                 0.5       0.004     0.023     0.006     0.030
                0.75       0.001     0.008     0.002     0.030

16      2       0.25       0.014     0.053     0.022     0.069
                 0.5       0.004     0.029     0.010     0.055
                0.75       0.001     0.014     0.005     0.056

        3       0.25       0.011     0.038     0.016     0.049
                 0.5       0.005     0.027     0.010     0.061
                0.75       0.001     0.015     0.007     0.060

        4       0.25       0.011     0.032     0.013     0.044
                 0.5       0.005     0.030     0.011     0.088
                0.75       0.001     0.006     0.005     0.035

Table 6: ANOVA for the AEP for small number of orders.

Source of Variation    DF     Sum of Squares   Mean Square

Model                  13         0.002          0.0002
Algorithm               7         0.0003            0
Size                    2         0.0002         0.0001
machine                 2           0               0
lamda                   2         0.0015         0.0008
Error                  202        0.0006            0
Corrected Total        215        0.0026

Source of Variation    F Value       Pr > F

Model                   55.37        <.0001
Algorithm               14.51        <.0001
Size                    41.24        <.0001
machine                  0.05        0.9551
lamda                   267.84       <.0001
Error
Corrected Total

Table 7: Results of Fisher's LSD for differences among algorithms
for small number of orders.

Pairwise Comparison         Pairwise mean Difference           LSD
Between Algorithms            [absolute value of            ([alpha] =
                               ([bar.[AEP.sub.i]]-            0.05) =
                               [bar.[AEP.sub.j]])]            0.0009
                                                            Difference
                                                              > LSD?

SA-min vs. SA-mean     [absolute value of 0.0044-0.0028]       YES
SA-min vs. SA-max      [absolute value of 0.0044-0.0029]       YES
SA-min vs. SA-wect     [absolute value of 0.0044-0.0041]        NO
SA-min vs. GA-min      [absolute value of 0.0044-0.0043]        NO
SA-min vs. GA-mean     [absolute value of 0.0044-0.0044]        NO
SA-min vs. GA-max      [absolute value of 0.0044-0.0043]        NO
SA-min vs. GA-wect     [absolute value of 0.0044-0.0069]       YES
SA-mean vs. SA-max     [absolute value of 0.0028-0.0029]        NO
SA-mean vs. SA-wect    [absolute value of 0.0028-0.0041]       YES
SA-mean vs. GA-min     [absolute value of 0.0028-0.0043]       YES
SA-mean vs. GA-mean    [absolute value of 0.0028-0.0044]       YES
SA-mean vs. GA-max     [absolute value of 0.0028-0.0043]       YES
SA-mean vs. GA-wect    [absolute value of 0.0028-0.0069]       YES
SA-max vs. SA-wect     [absolute value of 0.0029-0.0041]       YES
SA-max vs. GA-min      [absolute value of 0.0029-0.0043]       YES
SA-max vs. GA-mean     [absolute value of 0.0029-0.0044]       YES
SA-max vs. GA-max      [absolute value of 0.0029-0.0043]       YES
SA-max vs. GA-wect     [absolute value of 0.0029-0.0069]       YES
SA-wect vs. GA-min     [absolute value of 0.0041-0.0043]        NO
SA-wect vs. GA-mean    [absolute value of 0.0041-0.0044]        NO
SA-wect vs. GA-max     [absolute value of 0.0041-0.0043]        NO
SA-wect vs. GA-wect    [absolute value of 0.0041-0.0069]       YES
GA-min vs. GA-mean     [absolute value of 0.0043-0.0044]        NO
GA-min vs. GA-max      [absolute value of 0.0043-0.0043]        NO
GA-min vs. GA-wect     [absolute value of 0.0043-0.0069]       YES
GA-mean vs. GA-max     [absolute value of 0.0044-0.0043]        NO
GA-mean vs. GA-wect    [absolute value of 0.0044-0.0069]       YES
GA-max vs. GA-wect     [absolute value of 0.0043-0.0069]       YES

Table 8: ANOVA for the RPD for large number of orders.

Source of Variation      DF      Sum of Squares   Mean Square

Model                    12          3.3776         0.2815
Algorithm                 7          3.3258         0.4751
Size                      1          0.0285         0.0285
machine                   2          0.0135         0.0067
lamda                     2          0.0099         0.0049
Error                    131         0.9244         0.0071
Corrected Total          143         4.302

Source of Variation     F Value       Pr > F

Model                    39.89        <.0001
Algorithm                67.33        <.0001
Size                      4.04        0.0466
machine                   0.95        0.3878
lamda                     0.7         0.4983
Error
Corrected Total

Table 9: Results of Fisher's LSD for differences among algorithms
for large number of orders.

Pairwise Comparison         Pairwise mean Difference           LSD
Between Algorithms             [absolute value of           ([alpha] =
                               ([bar.[RPD.sub.i]]-            0.05) =
                               [bar.[RPD.sub.j]])]            0.0554
                                                            Difference
                                                              > LSD?

SA-min vs. SA-mean     [absolute value of 0.0168-0.0067]        NO
SA-min vs. SA-max      [absolute value of 0.0168-0.0013]        NO
SA-min vs. SA-wect     [absolute value of 0.0168-0.0017]        NO
SA-min vs. GA-min      [absolute value of 0.0168-0.0039]        NO
SA-min vs. GA-mean     [absolute value of 0.0168-0.0038]        NO
SA-min vs. GA-max      [absolute value of 0.0067-0.0039]        NO
SA-min vs. GA-wect     [absolute value of 0.0067-0.4821]       YES
SA-mean vs. SA-max     [absolute value of 0.0067-0.0013]        NO
SA-mean vs. SA-wect    [absolute value of 0.0067-0.0017]        NO
SA-mean vs. GA-min     [absolute value of 0.0067-0.0039]        NO
SA-mean vs. GA-mean    [absolute value of 0.0067-0.0038]        NO
SA-mean vs. GA-max     [absolute value of 0.0067-0.0039]        NO
SA-mean vs. GA-wect    [absolute value of 0.0067-0.4821]       YES
SA-max vs. SA-wect     [absolute value of 0.0013-0.0017]        NO
SA-max vs. GA-min      [absolute value of 0.0013-0.0039]        NO
SA-max vs. GA-mean     [absolute value of 0.0013-0.0038]        NO
SA-max vs. GA-max      [absolute value of 0.0013-0.0039]        NO
SA-max vs. GA-wect     [absolute value of 0.0013-0.4821]       YES
SA-wect vs. GA-min     [absolute value of 0.0017-0.0039]        NO
SA-wect vs. GA-mean    [absolute value of 0.0017-0.0038]        NO
SA-wect vs. GA-max     [absolute value of 0.0017-0.0039]        NO
SA-wect vs. GA-wect    [absolute value of 0.0017-0.4821]       YES
GA-min vs. GA-mean     [absolute value of 0.0039-0.0038]        NO
GA-min vs. GA-max      [absolute value of 0.0039-0.0039]        NO
GA-min vs. GA-wect     [absolute value of 0.0039-0.4821]       YES
GA-mean vs. GA-max     [absolute value of 0.0038-0.0039]        NO
GA-mean vs. GA-wect    [absolute value of 0.0038-0.4821]       YES
GA-max vs. GA-wect     [absolute value of 0.0039-0.4821]       YES

Table 10: The RDP results of the SAs and GAs for large number of
orders.

                                  SA-min                 SA-mean
n       m     [lambda]             RPD                     RPD

                            mean         max        mean         max

50      2       0.25        0.007       0.025       0.003       0.012
                 0.5        0.005       0.010       0.001       0.006
                0.75        0.003       0.007       0.001       0.003

        3       0.25        0.068       0.254       0.006       0.060
                 0.5        0.056       0.216       0.019       0.224
                0.75        0.052       0.271       0.039       0.313

        4       0.25        0.008       0.019       0.002       0.009
                 0.5        0.006       0.012       0.001       0.007
                0.75        0.049       0.253       0.042       0.395

100     2       0.25        0.008       0.016       0.001       0.008
                 0.5        0.005       0.011       0.001       0.057
                0.75        0.003       0.007       0.000       0.004

        3       0.25        0.008       0.017       0.001       0.011
                 0.5        0.005       0.013       0.001       0.005
                0.75        0.003       0.006       0.000       0.002

        4       0.25        0.008       0.015       0.001       0.006
                 0.5        0.005       0.011       0.001       0.017
                0.75        0.003       0.007       0.001       0.002

                                  SA-max                 SA-wect
n       m     [lambda]             RPD                     RPD

                            mean         max        mean         max

50      2       0.25        0.002       0.019       0.007       0.026
                 0.5        0.001       0.005       0.005       0.012
                0.75        0.001       0.005       0.003       0.010

        3       0.25        0.061       0.249       0.068       0.250
                 0.5        0.051       0.213       0.056       0.216
                0.75        0.050       0.267       0.052       0.270

        4       0.25        0.002       0.012       0.008       0.018
                 0.5        0.001       0.028       0.006       0.020
                0.75        0.046       0.250       0.049       0.252

100     2       0.25        0.002       0.008       0.008       0.017
                 0.5        0.001       0.025       0.005       0.012
                0.75        0.000       0.002       0.003       0.006

        3       0.25        0.002       0.012       0.007       0.015
                 0.5        0.001       0.046       0.006       0.012
                0.75        0.001       0.003       0.003       0.006

        4       0.25        0.001       0.007       0.008       0.014
                 0.5        0.002       0.054       0.005       0.014
                0.75        0.000       0.002       0.003       0.007

                                  GA-min                 GA-mean
n       m     [lambda]             RPD                     RPD

                            mean         max        mean         max

50      2       0.25        0.057       0.094       0.056       0.078
                 0.5        0.019       0.053       0.018       0.061
                0.75        0.003       0.015       0.003       0.012

        3       0.25        0.108       0.294       0.108       0.287
                 0.5        0.069       0.221       0.068       0.228
                0.75        0.052       0.270       0.052       0.271

        4       0.25        0.042       0.074       0.043       0.081
                 0.5        0.017       0.049       0.017       0.053
                0.75        0.048       0.258       0.048       0.254

100     2       0.25        0.086       0.134       0.086       0.126
                 0.5        0.023       0.070       0.023       0.069
                0.75        0.002       0.014       0.002       0.011

        3       0.25        0.067       0.092       0.067       0.100
                 0.5        0.021       0.049       0.021       0.042
                0.75        0.001       0.006       0.001       0.006

        4       0.25        0.057       0.080       0.057       0.083
                 0.5        0.021       0.047       0.021       0.046
                0.75        0.001       0.005       0.001       0.006

                                  GA-max                 GA-wect
n       m     [lambda]             RPD                     RPD

                            mean         max        mean         max

50      2       0.25        0.056       0.084       0.183       0.381
                 0.5        0.018       0.047       0.340       0.532
                0.75        0.003       0.016       0.335       0.645

        3       0.25        0.108       0.315       0.222       0.421
                 0.5        0.068       0.227       0.396       0.732
                0.75        0.052       0.270       0.392       0.704

        4       0.25        0.042       0.074       0.153       0.324
                 0.5        0.017       0.052       0.346       0.533
                0.75        0.048       0.257       0.397       0.665

100     2       0.25        0.086       0.118       0.440       0.729
                 0.5        0.023       0.062       0.792       1.087
                0.75        0.002       0.010       0.770       1.027

        3       0.25        0.068       0.099       0.406       0.664
                 0.5        0.022       0.050       0.793       1.041
                0.75        0.001       0.005       0.774       1.088

        4       0.25        0.057       0.084       0.388       0.598
                 0.5        0.021       0.046       0.769       0.997
                0.75        0.001       0.006       0.782       1.195

Table 11: CPU times (seconds) of the SAs and GAs for large number of
orders.

                                 SA-min                SA-mean
n       m     [lambda]          CPU time              CPU time

                            mean       max        mean       max

50      2       0.25       0.071      0.094      0.058      0.078
                 0.5       0.071      0.125      0.058      0.062
                0.75       0.071      0.078      0.058      0.078

        3       0.25       0.125      0.140      0.058      0.078
                 0.5       0.124      0.140      0.058      0.062
                0.75       0.126      0.140      0.058      0.078

        4       0.25       0.180      0.203      0.145      0.156
                 0.5       0.181      0.203      0.148      0.172
                0.75       0.185      0.203      0.058      0.078

100     2       0.25       0.266      0.281      0.219      0.265
                 0.5       0.266      0.328      0.217      0.250
                0.75       0.271      0.328      0.218      0.234

        3       0.25       0.483      0.515      0.394      0.421
                 0.5       0.480      0.546      0.394      0.437
                0.75       0.493      0.530      0.406      0.468

        4       0.25       0.705      0.796      0.560      0.608
                 0.5       0.701      0.749      0.558      0.608
                0.75       0.717      0.780      0.587      0.624

                                 SA-max                SA-wect
n       m     [lambda]          CPU time              CPU time

                            mean       max        mean       max

50      2       0.25       0.059      0.078      0.092      0.109
                 0.5       0.060      0.094      0.095      0.125
                0.75       0.059      0.078      0.095      0.109

        3       0.25       0.100      0.109      0.134      0.172
                 0.5       0.100      0.109      0.133      0.156
                0.75       0.103      0.125      0.132      0.156

        4       0.25       0.143      0.156      0.185      0.203
                 0.5       0.146      0.172      0.189      0.234
                0.75       0.170      0.203      0.224      0.281

100     2       0.25       0.230      0.296      0.317      0.390
                 0.5       0.263      0.328      0.275      0.296
                0.75       0.272      0.343      0.280      0.296

        3       0.25       0.459      0.562      0.555      0.671
                 0.5       0.410      0.530      0.625      0.702
                0.75       0.400      0.452      0.622      0.686

        4       0.25       0.636      0.749      0.886      0.998
                 0.5       0.567      0.624      0.852      0.983
                0.75       0.585      0.624      0.752      0.796

                                 GA-min               GA-mean
n       m     [lambda]          CPU time              CPU time

                            mean       max        mean       max

50      2       0.25       0.130      0.140      0.130      0.140
                 0.5       0.129      0.140      0.131      0.156
                0.75       0.128      0.140      0.129      0.140

        3       0.25       0.219      0.234      0.218      0.234
                 0.5       0.239      0.312      0.243      0.312
                0.75       0.294      0.359      0.290      0.328

        4       0.25       0.341      0.452      0.340      0.437
                 0.5       0.405      0.468      0.407      0.468
                0.75       0.401      0.484      0.390      0.437

100     2       0.25       0.297      0.359      0.289      0.359
                 0.5       0.315      0.390      0.310      0.359
                0.75       0.311      0.374      0.310      0.343

        3       0.25       0.543      0.655      0.537      0.640
                 0.5       0.483      0.608      0.471      0.593
                0.75       0.433      0.452      0.434      0.452

        4       0.25       0.741      0.889      0.738      0.889
                 0.5       0.591      0.624      0.589      0.624
                0.75       0.631      0.655      0.632      0.671

                                 GA-max               GA-wect
n       m     [lambda]          CPU time              CPU time

                            mean       max        mean       max

50      2       0.25       0.132      0.156      0.163      0.187
                 0.5       0.131      0.140      0.161      0.187
                0.75       0.129      0.156      0.161      0.187

        3       0.25       0.220      0.250      0.299      0.359
                 0.5       0.257      0.328      0.302      0.343
                0.75       0.299      0.359      0.296      0.359

        4       0.25       0.349      0.421      0.387      0.468
                 0.5       0.411      0.484      0.422      0.484
                0.75       0.391      0.452      0.399      0.484

100     2       0.25       0.294      0.343      0.248      0.312
                 0.5       0.320      0.374      0.282      0.343
                0.75       0.312      0.359      0.313      0.359

        3       0.25       0.546      0.640      0.524      0.655
                 0.5       0.484      0.593      0.508      0.593
                0.75       0.434      0.452      0.506      0.593

        4       0.25       0.748      0.874      0.740      0.889
                 0.5       0.591      0.624      0.688      0.796
                0.75       0.634      0.686      0.623      0.686
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Kung, Jan-Yee; Duan, Jiahui; Xu, Jianyou; Chung, I-Hong; Cheng, Shuenn-Ren; Wu, Chin-Chia; Lin, Win-
Publication:Discrete Dynamics in Nature and Society
Date:Jan 1, 2018
Words:10039
Previous Article:Corrigendum to "Global Stability of Malaria Transmission Dynamics Model with Logistic Growth".
Next Article:Uniqueness of L-Functions Concerning Certain Differential Polynomials.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters