# Metaheuristics for Order Scheduling Problem with Unequal Ready Times

Authors: Jan-Yee Kung; Jiahui Duan; Jianyou Xu; I-Hong Chung; Shuenn-Ren Cheng; Chin-Chia Wu; Win-Chin Lin
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

In recent years, various customer order scheduling (OS) 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. In real-life situations, a customer order can have some requirements including due dates, weights of jobs, and unequal ready times. Once encountering different ready times, waiting for future order or job arrivals to raise the completeness of a batch is an efficient policy. Meanwhile, the literature releases that few studies have taken unequal ready times into consideration for order scheduling problem. Motivated by this limitation, this study addresses an OS scheduling model with unequal order ready times. The objective function is to find a schedule to optimize the total completion time criterion. To solve this problem for exact solutions, two lower bounds and some properties are first derived to raise the searching power of a branch-and-bound method. For approximate solution, four simulated annealing approaches and four heuristic genetic algorithms are then proposed. At last, several experimental tests and their corresponding statistical outcomes are also reported to examine the performance of all the proposed methods.


---

## Body

## 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 1rj∑Cj, 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: Section2 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 numberm: total machine numberMk: machinek, k=1,2,…,mS=(π,i,j,π′) and S′=(π,j,i,π′): schedules of n orders where π and π′ denote partial sequences of the n orderstik: processing time for order i on machinek, k=1,2,…,m; i=1,2,…,nri: ready time for orderi, i=1,2,…,nsk: completion time for the last order in π on machinek,k = 1, 2, …,mCi(S): completion time of order i inS, i.e.,(1)CiS=max1≤k≤m⁡max⁡sk,ri+tik;[l] is the order which is arranged in thelth position in a given schedule.The problem is formulated as follows. Suppose thatn 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 tik denote the processing time for component k of order i to be processed on machinek and let ri denote order i to be placed in therth 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 ∑i=1nCi(S), an illustrative example follows.Example 1.
Given an instance problem withn = 2,m = 2. The processing times of each component of order Oi,i = 1, 2, on machine Mk, and the ready times of order Oi,i = 1, 2, are provided in Table 1.
Given an order scheduleS = (O1, O2), according to the definition of Ci(S), one have the following computation, and Figure 1 shows the Gantt diagram.(2)C1S=max⁡r1+t11,r1+t12=max⁡2+1,2+3=5C2S=max⁡max⁡C1S,r2+t21,max⁡C1S,r2+t22=max⁡6+2,6+5=11Table 1
Data for Example1.
O1 O2 t i 1 1 2 t i 2 3 5 r i 2 6Figure 1
The Gantt diagram of the completion times of two orders.


## 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 1rj∑Cj 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.LetS=(π,i,j,π′) and S′=(π,j,i,π′) denote two schedules, in which π and π′ are partial sequences. Assume that Ci(S) and Cj(S) are the completion times of orders i and j inS, whereas Cj(S′) and Ci(S′) denote the completion times of orders j and i in S′. To demonstrate that S dominates S′, it suffices to show that Ci(S)+Cj(S)≤Cj(S′)+Ci(S′) and Cj(S)<Ci(S′).Proposition 2.
Ifrj>ri≥max1≤k≤m{sk}, max1≤k≤m{tik}≤max1≤k≤m{tjk}, and ri+max1≤k≤m{tik}≥rj, then S dominates S′.Proof.
Fromrj>ri≥max1≤k≤m{sk}, we have(3)CiS=max1≤k≤m⁡ri+tikandCjS′=max1≤k≤m⁡rj+tjk.
Fromri+max1≤k≤m{tik}≥rj and rj>ri, we have (4)CjS=max1≤k≤m⁡ri+max1≤k≤m⁡tik+tjk
and(5)CiS′=max1≤k≤m⁡rj+max1≤k≤m⁡tjk+tik.Because max1≤k≤m{tik}≤max1≤k≤m{tjk} and rj>ri, we have(6)CiS≤CjS′andCjS<CiS′.Therefore, S dominates S′.Proposition 3.
Ifri≥max1≤k≤m{sk} and ri+max1≤k≤m{tik}<rj, then S dominates S′.Proposition 4.
Ifmin1≤k≤m{sk}≥max{ri,rj} and max1≤k≤m{sk+tik}<max1≤k≤m{sk+tjk}, then S dominates S′.Proposition 5.
Ifmax{sk,rj}≥max{sk,ri} and tik≤tjk for k=1,2,…,m, then S dominates S′.The proofs of Propositions3–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. LetAS be a partial sequence, in which the order of the first v jobs is determined and let US be the unscheduled part consisting of n1 = (n-v) jobs. Furthermore, let sk be the starting time of the first order inUS for machinek, and s-=∑k=1msk/m. Following the definition of (1), we have(7)Cv+1S=maxk=1,…,m⁡tv+1k+max⁡rv+1,Cv>s-+∑k=1mtv+1km,Cv+2S=maxk=1,…,m⁡tv+2k+max⁡rv+2,Cv+1>s-+∑k=1mtv+1k+∑k=1mtv+2km,⋯Cv+n1S=maxk=1,…,m⁡tv+2k+max⁡rv+2,Cv+1>s-+∑i=1n1∑k=1mtv+ikm.From the above discussions, we have(8)∑i=1n1Cv+n1S>n1s-+∑i=1n1n1-i+1∑k=1mtv+ikm.Regarding the second right-hand term of (8), according to Hardy et al. [31], the value of ∑i=1n1(n1-i+1)∑k=1mt[v+i]k may be optimized when the orders {n1-i+1} and ∑k=1mtv+ik are ordered in opposite ways. Therefore, the first lower bound (LB1) can be obtained as follows.(9)LB1=∑i=1vCiS+n1Cv+∑i=1n1n1-i+1tv+i•m,where tv+i•=∑k=1mt[v+i]k fori = 1,2,.., n1, t(v+1)•≤t(v+2)•≤…≤t(v+n1)• denotes the nondecreasing form of {tv+i•}, and v+n1=n.Adopting similar steps, another lower bound is easily derived as follows.(10)LB2=∑i=1vCiS+n1rv+1+∑i=1n1∑k=1mtv+ikm,where r(v+1)≤r(v+2)≤…≤r(v+n1) 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 ofAS; i.e., (11)LB=∑i=1vCiS+max⁡n1Cv+∑i=1n1n1-i+1tv+i•m,n1rv+1+∑i=1n1∑k=1mtv+ikm.


## 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 ifPaccept>q, where 0<q<1 and Paccept=exp⁡-α×ΔT, α=k/β, and β=10 is an experimental constant. End doGA 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 asf(Si(v))=max1≤l≤N{∑j=1nCj(Sl(v))}-∑j=1nCj(Si(v)), where Si(v) is theith string chromosome in thevth generation; determine the selection probability of a schedule as P(Si(v))=f(Si(v))/∑l=1Nf(Sl(v)). (iii)
Use a linear order crossover in the GA (see Falkenauer and Bouffouix, [36]), and set the crossover rate Pc at 1. (iv)
Set the value of mutation (Pm) at 0.35. (v)
Excluding the ideal schedule with a minimum total completion time ofn orders, create the other offspring from the parent sequences by using the roulette wheel method. End doIn 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 ofrj+min1≤k≤m{tjk}, whereas, in SA_max or GA_max, orders are arranged in nondecreasing sequence of rj+max1≤k≤m{tjk}. In SA_mean or GA_mean, orders are arranged in nondecreasing sequence of rj+∑k=1m(tjk/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 wi=1. Let N denote the set of n orders. Initially, place the order returned from mini∈N{max1≤k≤m(tik+ri)} in the first position and find its completion time, denoted as C[1]. Next, delete the scheduled order fromN, and place the order returned from minj∈N{(Cj-C[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λ) where n is the order-size and λ was a control variable. The value of λ 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=(Hi-O∗)/O∗×100%, where Hi was the value of the total completion time yielded from SA or GA and O∗ 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=(Hi-H∗)/H∗×100%, where Hi was the value of total completion time yielded from SA or GA and H∗ 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 atm = 2, 3, and 4. The number of orders was tested atn = 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 108. The computational results of the B&B method are presented in Table 2, where the last columnFS 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 parametersn,m, andλ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λ 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 forn=16.Table 2
Computational results of the branch-and-bound method.
n m λ Number of nodes CPU time (seconds) FS mean max mean max 12 2 0.25 73056.61 2766243 0.717 24.508 100 0.5 7509.79 329861 0.084 3.401 100 0.75 1216.78 14199 0.019 0.172 100 3 0.25 325210.3 5908745 3.926 63.461 100 0.5 18605.52 386331 0.237 4.898 100 0.75 3250.92 39243 0.057 0.624 100 4 0.25 1889929 29703900 26.156 358.132 100 0.5 36485.91 1125381 0.55 14.758 100 0.75 5020.36 57669 0.099 0.936 100 14 2 0.25 843689.3 21839448 11.369 277.105 100 0.5 17778.5 362433 0.267 4.602 100 0.75 6004.25 73865 0.119 1.154 100 3 0.25 6090544 69349704 105.13 1209.756 100 0.5 218458.6 8975480 3.702 149.324 100 0.75 37785.98 689467 0.778 15.678 100 4 0.25 33331922 435865824 659.244 8244.48 100 0.5 204696.6 6275558 4.187 126.234 100 0.75 55313.7 1829593 1.331 33.812 100 16 2 0.25 3666306 47015688 63.802 780.504 86 0.5 124890.3 4700103 2.473 87.454 100 0.75 226230.2 11121498 5.07 251.271 100 3 0.25 15812686 98160472 271.753 1947.797 64 0.5 2029674 47596468 40.71 764.967 99 0.75 792803.5 36248012 22.483 1078.575 100 4 0.25 11951878 79378032 269.248 1781.984 39 0.5 2418552 31824482 65.916 959.827 98 0.75 438707.6 20652540 19.078 921.186 100Table 3
The impact ofλ in the branch-and-bound algorithm.
n λ 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 300Table 4
The impact ofm 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 237The computational results obtained by the four SAs and four GAs are given in Table5, and the AEPs are obtained by these algorithms as the parametersn,m, andλvary. From Table 5, it can be seen that the AEP values obtained by all algorithms tend to linearly decrease asλincreases forn =12 andn =14. Forn =16, the AEP values obtained by these algorithms first increase but then decrease asλ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.Table 5
Computational results of the SAs and GAs for small number of orders.
n m λ SA-min SA-mean SA-max SA-wect GA-min GA-mean GA-max GA-wect error error error error error error error error mean max mean max mean max mean max mean max mean max mean max mean max 12 2 0.25 0.006 0.031 0.004 0.032 0.004 0.075 0.006 0.038 0.004 0.043 0.005 0.038 0.004 0.042 0.007 0.063 0.5 0.004 0.019 0.002 0.020 0.002 0.026 0.003 0.013 0.003 0.019 0.002 0.020 0.003 0.038 0.003 0.020 0.75 0.002 0.010 0.001 0.006 0.001 0.008 0.002 0.013 0.000 0.017 0.000 0.005 0.000 0.012 0.001 0.013 3 0.25 0.006 0.028 0.006 0.065 0.005 0.034 0.005 0.028 0.005 0.035 0.004 0.045 0.005 0.048 0.006 0.070 0.5 0.003 0.022 0.002 0.024 0.002 0.022 0.004 0.019 0.002 0.033 0.002 0.020 0.002 0.029 0.002 0.024 0.75 0.002 0.011 0.001 0.005 0.001 0.005 0.002 0.017 0.000 0.009 0.001 0.009 0.000 0.006 0.001 0.028 4 0.25 0.007 0.042 0.005 0.042 0.004 0.034 0.007 0.044 0.007 0.041 0.007 0.033 0.005 0.049 0.006 0.041 0.5 0.003 0.030 0.002 0.014 0.002 0.015 0.003 0.020 0.003 0.022 0.002 0.017 0.002 0.025 0.003 0.030 0.75 0.002 0.010 0.001 0.007 0.001 0.007 0.002 0.013 0.000 0.012 0.001 0.012 0.000 0.007 0.001 0.014 14 2 0.25 0.007 0.036 0.005 0.042 0.006 0.048 0.007 0.046 0.010 0.052 0.009 0.044 0.011 0.070 0.012 0.055 0.5 0.003 0.020 0.002 0.024 0.002 0.028 0.003 0.025 0.003 0.023 0.004 0.035 0.003 0.031 0.005 0.029 0.75 0.002 0.010 0.001 0.006 0.001 0.006 0.002 0.012 0.001 0.017 0.000 0.008 0.001 0.009 0.002 0.023 3 0.25 0.007 0.027 0.005 0.038 0.006 0.045 0.007 0.041 0.007 0.058 0.009 0.042 0.006 0.037 0.010 0.077 0.5 0.004 0.015 0.003 0.027 0.003 0.016 0.004 0.028 0.003 0.018 0.004 0.027 0.005 0.028 0.007 0.078 0.75 0.002 0.016 0.001 0.008 0.001 0.009 0.002 0.015 0.001 0.011 0.001 0.010 0.001 0.011 0.002 0.024 4 0.25 0.008 0.038 0.006 0.031 0.006 0.048 0.007 0.043 0.009 0.050 0.009 0.039 0.009 0.047 0.011 0.055 0.5 0.005 0.018 0.002 0.018 0.003 0.019 0.004 0.020 0.004 0.026 0.004 0.023 0.004 0.023 0.006 0.030 0.75 0.002 0.012 0.001 0.008 0.001 0.023 0.002 0.012 0.001 0.009 0.001 0.010 0.001 0.008 0.002 0.030 16 2 0.25 0.009 0.035 0.007 0.039 0.006 0.037 0.008 0.031 0.014 0.057 0.011 0.051 0.014 0.053 0.022 0.069 0.5 0.003 0.021 0.002 0.015 0.002 0.023 0.003 0.013 0.004 0.026 0.004 0.025 0.004 0.029 0.010 0.055 0.75 0.002 0.009 0.001 0.008 0.001 0.006 0.002 0.013 0.001 0.035 0.001 0.012 0.001 0.014 0.005 0.056 3 0.25 0.008 0.023 0.008 0.055 0.006 0.032 0.008 0.022 0.013 0.047 0.012 0.070 0.011 0.038 0.016 0.049 0.5 0.005 0.026 0.003 0.023 0.003 0.022 0.005 0.018 0.005 0.028 0.006 0.029 0.005 0.027 0.010 0.061 0.75 0.002 0.013 0.001 0.006 0.001 0.009 0.002 0.011 0.001 0.022 0.001 0.014 0.001 0.015 0.007 0.060 4 0.25 0.007 0.018 0.004 0.017 0.005 0.035 0.006 0.028 0.010 0.032 0.012 0.037 0.011 0.032 0.013 0.044 0.5 0.004 0.023 0.002 0.009 0.002 0.012 0.003 0.012 0.005 0.022 0.005 0.040 0.005 0.030 0.011 0.088 0.75 0.003 0.014 0.001 0.005 0.001 0.006 0.002 0.014 0.001 0.013 0.001 0.009 0.001 0.006 0.005 0.035Regarding the performance of these algorithms, the box plots in Figure6 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.Table 6
ANOVA for the AEP for small number of orders.
Source of Variation DF Sum of Squares Mean Square F Value P r > F Model 13 0.002 0.0002 55.37 <.0001 Algorithm 7 0.0003 0 14.51 <.0001 Size 2 0.0002 0.0001 41.24 <.0001 machine 2 0 0 0.05 0.9551 lamda 2 0.0015 0.0008 267.84 <.0001 Error 202 0.0006 0 Corrected Total 215 0.0026Table 7
Results of Fisher’s LSD for differences among algorithms for small number of orders.
Pairwise Comparison Pairwise mean Difference LSD(α=0.05)=0.0009 Between Algorithms | A E P i - - A E P j - | Difference > LSD? SA-min vs. SA-mean 0.0044 - 0.0028 YES SA-min vs. SA-max 0.0044 - 0.0029 YES SA-min vs. SA-wect 0.0044 - 0.0041 NO SA-min vs. GA-min 0.0044 - 0.0043 NO SA-min vs. GA-mean 0.0044 - 0.0044 NO SA-min vs. GA-max 0.0044 - 0.0043 NO SA-min vs. GA-wect 0.0044 - 0.0069 YES SA-mean vs. SA-max 0.0028 - 0.0029 NO SA-mean vs. SA-wect 0.0028 - 0.0041 YES SA-mean vs. GA-min 0.0028 - 0.0043 YES SA-mean vs. GA-mean 0.0028 - 0.0044 YES SA-mean vs. GA-max 0.0028 - 0.0043 YES SA-mean vs. GA-wect 0.0028 - 0.0069 YES SA-max vs. SA-wect 0.0029 - 0.0041 YES SA-max vs. GA-min 0.0029 - 0.0043 YES SA-max vs. GA-mean 0.0029 - 0.0044 YES SA-max vs. GA-max 0.0029 - 0.0043 YES SA-max vs. GA-wect 0.0029 - 0.0069 YES SA-wect vs. GA-min 0.0041 - 0.0043 NO SA-wect vs. GA-mean 0.0041 - 0.0044 NO SA-wect vs. GA-max 0.0041 - 0.0043 NO SA-wect vs. GA-wect 0.0041 - 0.0069 YES GA-min vs. GA-mean 0.0043 - 0.0044 NO GA-min vs. GA-max 0.0043 - 0.0043 NO GA-min vs. GA-wect 0.0043 - 0.0069 YES GA-mean vs. GA-max 0.0044 - 0.0043 NO GA-mean vs. GA-wect 0.0044 - 0.0069 YES GA-max vs. GA-wect 0.0043 - 0.0069 YESIn experiments with large numbers of orders, we set the numbers of orders atn = 50 and 100 and the numbers of machines atm = 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 Tables10 and 11, and the RPDs and corresponding CPU times obtained by these algorithms as the parametersn,m, andλvaried are illustrated in Figures 2–5. Concerning the RPD metric, no pattern is evident in Figure 2 regarding the impact ofλon the performance levels of these SAs and GAs. The reason is that forn =50 the RPD slightly increases (except for SA-mean) asλincreases, whereas forn =100 the RPD slightly decreases (GA-max first increases but then decreases) asλincreases. From Figure 3, it is found that forn =50 the RPD obtained by each algorithm first increases but then decreases quickly as m increases. Forn =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λ 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.Figure 2
Change of RPD for eachn asλincreases for SAs and GAs for large number of orders.Figure 3
Change of RPD for eachn as m increases for SAs and GAs for large number of orders.Figure 4
Change of CPU time for eachn asλincreases for SAs and GAs for large number of orders.Figure 5
Change of CPU time for eachn as m increases for SAs and GAs for large number of orders.Figure 6
Box plots of AEP for the algorithms for small number of orders.As shown in Figure7, 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.Table 8
ANOVA for the RPD for large number of orders.
Source of Variation DF Sum of Squares Mean Square F Value P r > F Model 12 3.3776 0.2815 39.89 <.0001 Algorithm 7 3.3258 0.4751 67.33 <.0001 Size 1 0.0285 0.0285 4.04 0.0466 machine 2 0.0135 0.0067 0.95 0.3878 lamda 2 0.0099 0.0049 0.7 0.4983 Error 131 0.9244 0.0071 Corrected Total 143 4.302Table 9
Results of Fisher’s LSD for differences among algorithms for large number of orders.
Pairwise Comparison Pairwise mean Difference LSD(α=0.05)=0.0554 Between Algorithms | R P D i - - R P D j - | Difference > LSD? SA-min vs. SA-mean 0.0168 - 0.0067 NO SA-min vs. SA-max 0.0168 - 0.0013 NO SA-min vs. SA-wect 0.0168 - 0.0017 NO SA-min vs. GA-min 0.0168 - 0.0039 NO SA-min vs. GA-mean 0.0168 - 0.0038 NO SA-min vs. GA-max 0.0067 - 0.0039 NO SA-min vs. GA-wect 0.0067 - 0.4821 YES SA-mean vs. SA-max 0.0067 - 0.0013 NO SA-mean vs. SA-wect 0.0067 - 0.0017 NO SA-mean vs. GA-min 0.0067 - 0.0039 NO SA-mean vs. GA-mean 0.0067 - 0.0038 NO SA-mean vs. GA-max 0.0067 - 0.0039 NO SA-mean vs. GA-wect 0.0067 - 0.4821 YES SA-max vs. SA-wect 0.0013 - 0.0017 NO SA-max vs. GA-min 0.0013 - 0.0039 NO SA-max vs. GA-mean 0.0013 - 0.0038 NO SA-max vs. GA-max 0.0013 - 0.0039 NO SA-max vs. GA-wect 0.0013 - 0.4821 YES SA-wect vs. GA-min 0.0017 - 0.0039 NO SA-wect vs. GA-mean 0.0017 - 0.0038 NO SA-wect vs. GA-max 0.0017 - 0.0039 NO SA-wect vs. GA-wect 0.0017 - 0.4821 YES GA-min vs. GA-mean 0.0039 - 0.0038 NO GA-min vs. GA-max 0.0039 - 0.0039 NO GA-min vs. GA-wect 0.0039 - 0.4821 YES GA-mean vs. GA-max 0.0038 - 0.0039 NO GA-mean vs. GA-wect 0.0038 - 0.4821 YES GA-max vs. GA-wect 0.0039 - 0.4821 YESTable 10
The RDP results of the SAs and GAs for large number of orders.
n m λ SA-min SA-mean SA-max SA-wect GA-min GA-mean GA-max GA-wect RPD RPD RPD RPD RPD RPD RPD RPD mean max mean max mean max mean max mean max mean max mean max mean max 50 2 0.25 0.007 0.025 0.003 0.012 0.002 0.019 0.007 0.026 0.057 0.094 0.056 0.078 0.056 0.084 0.183 0.381 0.5 0.005 0.010 0.001 0.006 0.001 0.005 0.005 0.012 0.019 0.053 0.018 0.061 0.018 0.047 0.340 0.532 0.75 0.003 0.007 0.001 0.003 0.001 0.005 0.003 0.010 0.003 0.015 0.003 0.012 0.003 0.016 0.335 0.645 3 0.25 0.068 0.254 0.006 0.060 0.061 0.249 0.068 0.250 0.108 0.294 0.108 0.287 0.108 0.315 0.222 0.421 0.5 0.056 0.216 0.019 0.224 0.051 0.213 0.056 0.216 0.069 0.221 0.068 0.228 0.068 0.227 0.396 0.732 0.75 0.052 0.271 0.039 0.313 0.050 0.267 0.052 0.270 0.052 0.270 0.052 0.271 0.052 0.270 0.392 0.704 4 0.25 0.008 0.019 0.002 0.009 0.002 0.012 0.008 0.018 0.042 0.074 0.043 0.081 0.042 0.074 0.153 0.324 0.5 0.006 0.012 0.001 0.007 0.001 0.028 0.006 0.020 0.017 0.049 0.017 0.053 0.017 0.052 0.346 0.533 0.75 0.049 0.253 0.042 0.395 0.046 0.250 0.049 0.252 0.048 0.258 0.048 0.254 0.048 0.257 0.397 0.665 100 2 0.25 0.008 0.016 0.001 0.008 0.002 0.008 0.008 0.017 0.086 0.134 0.086 0.126 0.086 0.118 0.440 0.729 0.5 0.005 0.011 0.001 0.057 0.001 0.025 0.005 0.012 0.023 0.070 0.023 0.069 0.023 0.062 0.792 1.087 0.75 0.003 0.007 0.000 0.004 0.000 0.002 0.003 0.006 0.002 0.014 0.002 0.011 0.002 0.010 0.770 1.027 3 0.25 0.008 0.017 0.001 0.011 0.002 0.012 0.007 0.015 0.067 0.092 0.067 0.100 0.068 0.099 0.406 0.664 0.5 0.005 0.013 0.001 0.005 0.001 0.046 0.006 0.012 0.021 0.049 0.021 0.042 0.022 0.050 0.793 1.041 0.75 0.003 0.006 0.000 0.002 0.001 0.003 0.003 0.006 0.001 0.006 0.001 0.006 0.001 0.005 0.774 1.088 4 0.25 0.008 0.015 0.001 0.006 0.001 0.007 0.008 0.014 0.057 0.080 0.057 0.083 0.057 0.084 0.388 0.598 0.5 0.005 0.011 0.001 0.017 0.002 0.054 0.005 0.014 0.021 0.047 0.021 0.046 0.021 0.046 0.769 0.997 0.75 0.003 0.007 0.001 0.002 0.000 0.002 0.003 0.007 0.001 0.005 0.001 0.006 0.001 0.006 0.782 1.195Table 11
CPU times (seconds) of the SAs and GAs for large number of orders.
n m λ SA-min SA-mean SA-max SA-wect GA-min GA-mean GA-max GA-wect CPU time CPU time CPU time CPU time CPU time CPU time CPU time CPU time mean max mean max mean max mean max mean max mean max mean max mean max 50 2 0.25 0.071 0.094 0.058 0.078 0.059 0.078 0.092 0.109 0.130 0.140 0.130 0.140 0.132 0.156 0.163 0.187 0.5 0.071 0.125 0.058 0.062 0.060 0.094 0.095 0.125 0.129 0.140 0.131 0.156 0.131 0.140 0.161 0.187 0.75 0.071 0.078 0.058 0.078 0.059 0.078 0.095 0.109 0.128 0.140 0.129 0.140 0.129 0.156 0.161 0.187 3 0.25 0.125 0.140 0.058 0.078 0.100 0.109 0.134 0.172 0.219 0.234 0.218 0.234 0.220 0.250 0.299 0.359 0.5 0.124 0.140 0.058 0.062 0.100 0.109 0.133 0.156 0.239 0.312 0.243 0.312 0.257 0.328 0.302 0.343 0.75 0.126 0.140 0.058 0.078 0.103 0.125 0.132 0.156 0.294 0.359 0.290 0.328 0.299 0.359 0.296 0.359 4 0.25 0.180 0.203 0.145 0.156 0.143 0.156 0.185 0.203 0.341 0.452 0.340 0.437 0.349 0.421 0.387 0.468 0.5 0.181 0.203 0.148 0.172 0.146 0.172 0.189 0.234 0.405 0.468 0.407 0.468 0.411 0.484 0.422 0.484 0.75 0.185 0.203 0.058 0.078 0.170 0.203 0.224 0.281 0.401 0.484 0.390 0.437 0.391 0.452 0.399 0.484 100 2 0.25 0.266 0.281 0.219 0.265 0.230 0.296 0.317 0.390 0.297 0.359 0.289 0.359 0.294 0.343 0.248 0.312 0.5 0.266 0.328 0.217 0.250 0.263 0.328 0.275 0.296 0.315 0.390 0.310 0.359 0.320 0.374 0.282 0.343 0.75 0.271 0.328 0.218 0.234 0.272 0.343 0.280 0.296 0.311 0.374 0.310 0.343 0.312 0.359 0.313 0.359 3 0.25 0.483 0.515 0.394 0.421 0.459 0.562 0.555 0.671 0.543 0.655 0.537 0.640 0.546 0.640 0.524 0.655 0.5 0.480 0.546 0.394 0.437 0.410 0.530 0.625 0.702 0.483 0.608 0.471 0.593 0.484 0.593 0.508 0.593 0.75 0.493 0.530 0.406 0.468 0.400 0.452 0.622 0.686 0.433 0.452 0.434 0.452 0.434 0.452 0.506 0.593 4 0.25 0.705 0.796 0.560 0.608 0.636 0.749 0.886 0.998 0.741 0.889 0.738 0.889 0.748 0.874 0.740 0.889 0.5 0.701 0.749 0.558 0.608 0.567 0.624 0.852 0.983 0.591 0.624 0.589 0.624 0.591 0.624 0.688 0.796 0.75 0.717 0.780 0.587 0.624 0.585 0.624 0.752 0.796 0.631 0.655 0.632 0.671 0.634 0.686 0.623 0.686Figure 7
Box plots of RPD for the algorithms for large number of orders.


## 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 ton= 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 ton = 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.



---

*Source: 4657368-2018-09-18.xml*