# A Fuzzy Nonlinear Programming Approach for Optimizing the Performance of a Four-Objective Fluctuation Smoothing Rule in a Wafer Fabrication Factory

Authors: Horng-Ren Tsai; Toly Chen
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

In theory, a scheduling problem can be formulated as a mathematical programming problem. In practice, dispatching rules are considered to be a more practical method of scheduling. However, the combination of mathematical programming and fuzzy dispatching rule has rarely been discussed in the literature. In this study, a fuzzy nonlinear programming (FNLP) approach is proposed for optimizing the scheduling performance of a four-factor fluctuation smoothing rule in a wafer fabrication factory. The proposed methodology considers the uncertainty in the remaining cycle time of a job and optimizes a fuzzy four-factor fluctuation-smoothing rule to sequence the jobs in front of each machine. The fuzzy four-factor fluctuation-smoothing rule has five adjustable parameters, the optimization of which results in an FNLP problem. The FNLP problem can be converted into an equivalent nonlinear programming (NLP) problem to be solved. The performance of the proposed methodology has been evaluated with a series of production simulation experiments; these experiments provide sufficient evidence to support the advantages of the proposed method over some existing scheduling methods.


---

## Body

## 1. Introduction

In complex manufacturing systems, such as wafer fabrication factories, job scheduling is subject to many sources of uncertainty or randomness [1]. Such uncertainty or randomness is partly due to manual operations, including the loading and unloading of jobs, the setup or repair of machines, and visual inspections. The other two sources of uncertainty, the unexpected releases of emergency orders and machine breakdowns, are beyond the control of a wafer fabrication factory. The literature provides probabilistic (stochastic) and fuzzy methods that can consider uncertainty or randomness. However, it is difficult to identify the probability distribution of each parameter, which means that a probabilistic (stochastic) method is not easy to use. In addition, fuzzy methods are advantageous because subjective factors can be considered, such as human interpretations of the scheduling performance and the tradeoffs of different scheduling objectives. For example, a job 3 months late and a job 3 days late are both late. However, the first job is difficult to accept, while the second is still acceptable. In other words, there are different degrees of acceptance, even if both jobs have been delayed. Second, to one scheduler, one objective may be much more important than the other, but to another scheduler, the two objectives may be equally important. The concepts of “acceptability” and “relative importance” can both be suitably modeled by a fuzzy method. For example, Murata et al. [2] used trapezoidal fuzzy numbers (TrFNs) to represent the satisfaction levels of due dates. In the literature, due dates, processing times, and precedence relations have been fuzzified [2–4].Many existing fuzzy scheduling methods take the form of fuzzy inference rules, such as “if the release time is early and the number of operations is large, then the job priority is high” [5, 6]. A fuzzy scheduling system usually uses a number of fuzzy inference rules and can be divided into two types: Mamdani [7] and Takagi-Sugeno-Kang (TSK). For example, Xiong et al. [5] scheduled a flexible manufacturing system (FMS) using two fuzzy dispatching rules of the TSK type. Murata et al. [2] used six fuzzy rules to move jobs between different priority classes. Lee et al. [8] established two fuzzy inference rules to select a combination of some existing dispatching rules for scheduling a flexible manufacturing system. Tan and Tang [9] applied Taguchi’s design of experiment (DOE) techniques to improve the design of some fuzzy dispatching rules for a test facility. In Benincasa et al. [6], up to 27 fuzzy inference rules (each with three inputs and one output) were established to schedule automated guided vehicles. Dong and Liu [3] built an adaptive neurofuzzy inference system (ANFIS) to schedule a job shop. For any two jobs, the inputs to the ANFIS were the differences between the two jobs, and the output from the ANFIS determined the sequence of the two jobs. If the output was greater than zero, then the first job was to be processed before the second job. Murata et al. [2] considered a job shop with 10 machines and jobs with different priorities. A fuzzy linear programming (FLP) problem was solved to optimize the total reward. However, the fuzziness came from the satisfaction level of the due date rather than from the parameters. A good review of the literature on fuzzy scheduling methods can be found in Dubois et al. [10].On the other hand, a scheduling problem can be formulated as a mathematical programming problem. For example, Biggs and Laughton [11] optimized a nonlinear programming (NLP) model for electric power scheduling. A recursive quadratic programming approach was proposed to solve the NLP problem. In Pedro [12], the Fm|prmu|Cmax problem was formulated as a mixed integer programming (MIP) model. The optimal solution of the mathematical programming problem gives the optimal schedule for the manufacturing system. However, sometimes the mathematical programming problem is not easy to solve, and some soft computing methods can be applied to search for the optimal solution of the mathematical programming problem [13–15]. For example, Chiang and Fu [16] minimized the number of tardy jobs for a job shop in which machines have sequence-dependent setup times. An NLP problem with a linear objective function and some quadratic constraints was solved by the application of a genetic algorithm (GA). Ishibuchi and Murata [13] applied a similar approach for multiobjective flow shop scheduling. In the NLP model of Connors et al. [17], the inventory level was estimated with a nonlinear equation and then the holding costs were minimized. Chen and Yao applied a deterministic fluid network [18] in order to find an optimal solution. Both Murata et al. [2] and Ishibuchi et al. [19] built FLP models to solve scheduling problems and maximized the satisfaction levels of the due dates. Murata et al. applied GA to solve the FLP problem. For the same purpose, Ishibuchi et al. [19] applied a hybrid GA with neighborhood search. Xia and Wu [15] combined particle swarm optimization (PSO) and simulated annealing (SA) for flexible job shop scheduling.A summary of existing fuzzy scheduling methods is shown in Table1. The existing approaches have the following problems.(1)
Dubois et al. [10] distinguished two categories of fuzzy scheduling methods: methods that represent preference profiles and methods that model uncertainty distributions. However, in most studies that use fuzzy methods, the fuzziness comes from the fuzzification of the scheduling objective (which belongs to the first category) or from the fuzzy rules that are subjectively chosen by the scheduler rather than from fuzzy parameters (which belong to the second category). In other words, processing time, due date, and precedence relations are all free from uncertainty in these studies.(2)
Although an NLP problem is not easy to solve, the soft computing method applied to solve the NLP problem may also pose a considerable challenge.(3)
The combination of NLP with fuzziness results in a FNLP approach that considers the uncertainty of parameters and does not need to make simplifying assumptions, and therefore has the potential to solve realistic scheduling problems effectively. However, very few studies applied FNLP methods. Most of them are used for scheduling small manufacturing systems [20].Table 1
Some fuzzy scheduling methods.
References
Fuzziness
Model
Soft computingmethod
Xiong et al. [5]
Fuzzy rule
MIP
TSK
Lee et al. [8]
Fuzzy rule
MIP
single-rule-based
Benincasa et al. [6]
Fuzzy rule
MIP
Mamdani
Ishibuchi et al. [19]
Fuzzified objective
FLP
Hybrid GA
Tan and Tang [9]
Fuzzy rule
MIP
Mamdani
Murata et al. [2]
Fuzzified objective
FLP
GA
Dong and Liu [3]
Fuzzy rule
MIP
ANFISTo tackle these problems, an FNLP approach is proposed in this study to optimize the performance of a job dispatching rule in a wafer fabrication factory. In other words, this study is not going to optimize the performance of a schedule for a wafer fabrication factory, which is known to be an NP-hard problem but to optimize the performance of a dispatching rule in a wafer fabrication factory. The use of some special types of fuzzy numbers establishes the corresponding subcategories for these FNLP models, such as the type-2 FNLP (with type-2 fuzzy numbers), the interval-valued FNLP (with interval fuzzy numbers), the intuitionistic FNLP (with intuitionistic fuzzy numbers), and the interval-valued intuitionistic FNLP [21], which has been of interest to researchers in recent years. Fares and Kaminska [22] solved two multiple-objective FNLP problems to find the optimal sets of circuit parameter values for a bipolar emitter follower circuit and an unbuffered two-stage complementary metal-oxide semiconductor (CMOS) op-amp. Chen and Wang [23] defined the yield competitiveness of a semiconductor product, which is uncertain and can be enhanced by allocating more capacity to the product; this functions in a nonlinear way. They therefore constructed an FNLP model to optimize the effects of capacity reallocation on the yield competitiveness of a semiconductor product, which was then converted to an NLP problem to be solved.In the proposed methodology, the fuzziness comes from the uncertainty of the remaining cycle time, that is, the time still needed to complete a job; this time is highly uncertain [24]. In the proposed methodology, the remaining cycle time of a job is estimated with a triangular fuzzy number (TFN). There are various types of fuzzy numbers with different shapes. Among them, a TFN is easily implemented and has been used for numerous applications (e.g., [23–25]). Subsequently, the remaining cycle time estimate is fed into a four-factor fluctuation smoothing rule [25] to sequence the jobs in front of a machine. The four-factor fluctuation smoothing rule is fuzzified in this way, and the slack of a job is also expressed by a TFN. The fuzzy fluctuation-smoothing dispatching rule has five adjustable parameters, the optimization of which constitutes an FNLP problem. To convert the FNLP problem into a more tractable form, α-cut operations are also applied.The unique features of the proposed methodology include the following.(1)
Combining fuzziness and NLP: scheduling decisions represented in terms of fuzzy sets are flexible in their implementations. NLP relaxes the strict assumptions and constraints of linear programming (LP) and is highly practicable.(2)
Considering the uncertainty in the remaining cycle time: dispatching rules that consider dynamic information, such as the remaining cycle time, are more effective for highly complex manufacturing systems [26]. To this end, an effective fuzzy back propagation network (FBPN) approach is applied.(3)
Establishing a fuzzy dispatching rule directly from the existing rules: a fuzzy dispatching rule is deduced by fuzzifying the four-objective fluctuation-smoothing dispatching rule [25] and diversifying the slack. This rule accepts the fuzzy remaining cycle time as an input and uses a fuzzy value to represent the slack of each job.(4)
Diversifying the slack by solving an FNLP model: the emergence of ties may lead to incorrect scheduling results. In the proposed methodology, to reduce the number of ties, the slacks of jobs are diversified by maximizing the standard deviation [27], which leads to a FNLP problem. The FNLP problem is not easy to solve; therefore, this study applies α-cut operations [28].(5)
Optimizing four objectives simultaneously: the proposed fuzzy rule fuses four dispatching rules in a nonlinear way. In contrast, most existing methods optimize the weighted sum of multiple objectives (e.g., [13, 15]).The rest of this paper is organized as follows. Section2 is divided into four parts: α-cut operations, effective FBPN, fuzzified dispatching, and FNLP. First, the concepts of α cuts and α-cut operations are introduced. The next part explains the effective FBPN approach that estimates the remaining cycle time of a job with a fuzzy number. The next part shows that the four-objective fluctuation smoothing rule is fuzzified so that it can accept the remaining cycle time estimate as an input. The final part of Section 2 explains the role of the FNLP. To obtain the best values of the parameters in the fuzzy four-objective fluctuation smoothing rule, and to diversify the slack, an FNLP model is built. To solve the FNLP problem, α-cut operations are applied. Section 3 details how a series of production simulation experiments are carried out to assess the advantages and disadvantages of the proposed methodology. Finally, the conclusions of this study are made in Section 4.


## 2. Methodology

The flow chart of Figure1 illustrates the steps of the proposed methodology.Figure 1
The flowchart of the proposed methodology.Subsequently, the variables and parameters that will be used in the proposed methodology are defined as follows.(1)
CTj: the cycle time of job j.(2)
CTEj~: the estimated cycle time of job j; CTEj~=(CTEj1,CTEj2,CTEj3).(3)
DDj: the due date of job j.(4)
Rj: the release time of job j;j=1~n.(5)
RCTju: the remaining cycle time of job j from step u.(6)
RCTEju~: the estimated remaining cycle time of job j from step u; RCTEju~=(RCTEju1,RCTEju2,RCTEju3).(7)
RPTju: the remaining processing time of job j from step u.(8)
SCTju: the step cycle time of job j until step u.(9)
SKju or SK~ju: the slack of job j at step u.(10)
t: the current time.(11)
TPTj: the total processing time of job j.(12)
λ: mean release rate.(13)
xjp: the inputs to the three-layer BPN of job j,p=1~P.(14)
hl: the output from hidden-layer node l,l=1~L.(15)
wlo: the connection weight between hidden-layer node l and the output node.(16)
wplh: the connection weight between input node p and hidden-layer node l, P=1~P;l=1~L.(17)
θlh: the threshold on hidden-layer node l.(18)
θ~o: the threshold on the output node; θ~o=(θ1o,θ2o,θ3o).All fuzzy parameters in the proposed methodology are given in TFNs


### 2.1.α Cuts and α-Cut Operations

Theα-cut operations are applied to solve the FNLP problem. For this reason, the concepts of α cuts and α-cut operations are introduced as follows.Definition 1 (α cuts).
A
~ is a fuzzy number. The α cut of A~ is an interval number given by
(1)A(α)={x∣x∈R,μA~(x)≥α}=[AL(α),AR(α)].Definition 2 (arithmetic of fuzzy numbers based onα-cut operations).
Given two fuzzy numbersA~ and B~, and their α cuts A(α) and B(α), the arithmetic operations of A~ and B~ based on their α cuts are as follows:
(2)A(α)(+)B(α)=[AL(α),AR(α)](+)[BL(α),BR(α)]=[AL(α)+BL(α),AR(α)+BR(α)],(3)A(α)(-)B(α)=[AL(α),AR(α)](-)[BL(α),BR(α)]=[AL(α)-BR(α),AR(α)-BL(α)],(4)A(α)(×)B(α)=[AL(α),AR(α)](×)[BL(α),BR(α)]=[min(AL(α)BL(α),AL(α)BR(α),AR(α)BL(α),AR(α)BR(α)),max(AL(α)BL(α),AL(α)BR(α),AR(α)BL(α),AR(α)BR(α))],(5)kA(α)=[kAL(α),kAR(α)],k≥0,(6)A2(α)={[0,max(AL2(α),AR2(α))],IfAL≤0≤AR,[min(AL2(α),AR2(α)),max(AL2(α),AR2(α))],otherwise.(7)A(α)(/)B(α)=[AL(α),AR(α)](/)[BL(α),BR(α)]=[AL(α)BR(α),AR(α)BL(α)]AL(α)≥0,BL(α)>0,
where (+), (-), (×), and (/) denote fuzzy addition, subtraction, multiplication, and division, respectively. Equation (5) is equivalent to
(8)A2(α)=[(AL2(α),AR2(α))max(AL(α)AR(α),0)·min(AL(α)AR(α),AR(α)AL(α)),max(AL2(α),AR2(α))]
if AL(α),AR(α)≠0. The min() and max() function can be replaced by
(9)x=min(a,b)⟺x≤a;x≤b;(x-a)(x-b)=0,x=max(a,b)⟺x≥a;x≥b;(x-a)(x-b)=0.Theorem 3 (average of fuzzy numbers based onα cuts).
Givenn fuzzy numbers A~j=[AjL(α),AjR(α)], j=1~n, the average of these fuzzy numbers can be derived as
(10)A¯(α)=[A-L(α),A-R(α)]=[∑j=1nAjL(α)n,∑j=1nAjR(α)n].Proof.
Theorem3 can be directly derived from (2) and (5).


### 2.2. The Effective FBPN Approach for Estimating the Remaining Cycle Time

Before any job is scheduled, the remaining cycle time of each job needs to be estimated. In this work, the effective FBPN approach is applied and the remaining cycle time is estimated with a fuzzy value.In the effective FBPN approach, jobs are classified intoK categories using fuzzy c-means (FCM). First, in order to facilitate the subsequent calculations and problem solving, all raw data are normalized [29]. Then, we place the (normalized) attributes of jobj in vector xj=[xjp].FCM classifies jobs by minimizing the following objective function:(11)Min∑k=1K∑j=1nμj(k)mej(k)2,
where K is the required number of categories; n is the number of jobs; μj(k) indicates that job j belongs to category k; ej(k) measures the distance from job j to the centroid of category k; m∈[1,∞) is a parameter to adjust the fuzziness and is usually set to 2. The procedure of FCM is as follows(1)
Produce a preliminary clustering result: the performance of FCM is sensitive to the initial conditions.(2)
(Iterations) calculate the centroid of each category as(12)x-(k)={x-(k)p};p=1~P,x-(k)p=∑j=1nμj(k)mxjp∑j=1nμj(k)m,μj(k)=1∑q=1K(ej(k)/ej(q))2/(m-1),ej(k)=∑allp(xjp-x-(k)p)2,wherex-(k) is the centroid of category k. μj(k)(t) is the membership function that indicates job i belongs to category k after the tth iteration.(3)
Remeasure the distance from each job to the centroid of each category, and then recalculate the corresponding membership.(4)
Stop if the following condition is met. Otherwise, return to step (2):(13)maxkmaxj|μj(k)(t)-μj(k)(t-1)|<d,
where d is a real number representing the threshold for the convergence of membership.Finally, the separate distance test (S test) proposed by Xie and Beni [30] can be applied to determine the optimal number of categories K:
(14)MinSsubjecttoJm=∑k=1K∑j=1nμj(k)mej(k)2emin2=mink1≠k2(∑allp(x-(k1)p-x-(k2)p)2)S=Jmn×emin2K∈Z+.
The K value that minimizes S determines the optimal number of categories.After clustering, a three-layer FBPN is used to estimate the cycle times of jobs for each category. The configuration of the three-layer FBPN is as follows. First, the inputs are theP parameters associated with the jth job. Subsequently, there is only a single hidden layer; the hidden layer has twice as many neurons as the input layer. In addition, Chen and Wang [31] and Chen and Lin [32] have described how an NLP model can be constructed to adjust the connection weights and thresholds in an FBPN; this problem is not easy to solve. In the proposed methodology, only the threshold on the output node (θ~o) will be adjusted. This way is much simpler and can also achieve good results. In other words, only θ~o is fuzzy, while the other parameters are crisp. In this way, the fuzzy remaining cycle time estimate is generated with minimal effort. This makes the FBPN approach an effective one. The output from the three-layer FBPN is the (normalized) estimated remaining cycle time (N(RCTEju~)) of the training examples, where N() is the normalization function.The procedure for determining the parameter values is now described. First, to determine the value of each parameter andθ2o, the FBPN is treated as a crisp network. Some algorithms are applicable for this purpose, such as gradient descent algorithms, conjugate gradient algorithms, the Levenberg-Marquardt algorithm, and others. In this study, the Levenberg-Marquardt algorithm is applied. The Levenberg-Marquardt algorithm was designed for training with second-order speed without having to compute the Hessian matrix. It uses approximation and updates the network parameters in a Newton-like way [33].Subsequently,θ3o is to be determined, so that the actual value will be less than the upper bound of the network output. Assume that the adjustment made to the threshold on the output node is denoted as Δθo=θ3o-θ2o. The optimal value of Δθo should be set as follows:
(15)Δθo*=minj(ln(1N(RCTju)-1)-ln(1oj2-1)).
In a similar way, θ1o can be determined so that each actual value will be greater than the appropriate lower bound. The optimal value of Δθo can be obtained as:
(16)Δθo*=maxj(ln(1N(RCTju)-1)-ln(1oj2-1)).
This FBPN approach can generate a very precise interval of the remaining cycle time for each job, thereby reducing the risk of misscheduling. An instance has been analyzed in Figure 2 to evaluate the performance of this method. To provide a comparison, a statistical analysis method is also applied to this instance, in which the relationship between the remaining cycle time and job attributes is fitted with a multiple regression equation. The results are shown in Figure 3. Compared with the effective FBPN approach, the statistical analysis method is not only inaccurate but also not precise enough. The remaining cycle time estimated by the statistical analysis method is therefore prone to errors, which may result in incorrect scheduling.Figure 2
The estimation results by the effective FBPN approach.Figure 3
The estimation results by the statistical analysis approach.


### 2.3. The Fuzzy Four-Objective Dispatching Rule

Lu et al. [26] proposed two fluctuation smoothing rules—the fluctuation smoothing policy for mean cycle time (FSMCT) and the fluctuation smoothing policy for variation of cycle time (FSVCT). FSMCT is aimed at minimizing the mean cycle time, while FSVCT is aimed at minimizing the variance of cycle time:(FSMCT)(17)SKju(FSMCT)=jλ-RCTEju,(FSVCT)(18)SKju(FSVCT)=Rj-RCTEju.
Jobs with the smallest slack values are given the highest priorities.If the remaining cycle time is estimated with a TFN, then we have two fuzzy fluctuation smoothing rules as(fuzzy FSMCT)(19)SK~ju(FSMCT)=jλ-RCTE~ju,(fuzzy FSVCT)(20)SK~ju(FSVCT)=Rj-RCTE~ju.To determine the sequence of jobs, the fuzzy slacks must be compared. To this end, various methods have been proposed in the literature, such as a method based on the probability measure [34], a coefficient of variance (CV) index [35], a method that uses the area between the centroid point and the original point [36], and a method based on the fuzzy mean and standard deviation [37]. For a comparison of these methods, refer to Zhu and Xu [37]. In this study, the method based on the fuzzy mean and standard deviation is applied because it is relatively simple and can yield reasonable comparison results. To put this in context, the following theorem is introduced.Theorem 4.
The fuzzy mean and standard deviation of a triangular fuzzy numberA~ = (x0-a, x0, x0+b) can be derived as
(21)μA~=x0+b-a3,σA~=a2+ab+b218.Proof.
Refer to Zhu and Xu [37]. It is, in fact, the center-of-gravity (COG) method.The following definition details a method based on the fuzzy mean and standard deviation.Definition 5.
For any two fuzzy numbersA~ and B~∈F(R), the sequence of A~ and B~ can be determined according to their fuzzy means and standard deviations as follows.(1)
μA~>μB~ if and only if A~≻B~.(2)
μA~<μB~ if and only if A~≺B~.(3)
IfμA~=μB~, then
(i)
σA~>σB~ if and only if A~≺B~.(ii)
σA~<σB~ if and only if A~≻B~.(iii)
σA~=σB~ if and only if A~=B~.Consider the example in Table2. The sequencing results by the two fuzzified rules areFuzzy FSMCT: 7→ 11 → 16 → 6 → 13 → 4 → 19 → 1 → 3 → 14 → 2 → 9 → 10 → 8 → 12 →18 → 15 → 17 → 5.Fuzzy FSVCT: 7→ 13 → 19 → 16 → 11 → 1 → 6 → 4 → 9 → 15 → 17 → 8 → 3 → 12 → 2 → 14 → 18 → 5 → 10.Table 2
An example (λ = 1.18).
Number
R
j
j
RCTE
~
j
u
SK
~
j
u (FFSMCT)
SK
~
j
u (FFSVCT)
1
102
159
(1200, 1399, 1458)
(−1324, −1265, −1066)
(−1357, −1297, −1099)
2
756
37
(976, 1127, 1176)
(−1145, −1096, −945)
(−421, −371, −221)
3
826
37
(1086, 1223, 1299)
(−1269, −1192, −1055)
(−474, −397, −261)
4
652
86
(1618, 1822, 1976)
(−1904, −1750, −1546)
(−1325, −1170, −967)
5
208
55
(455, 530, 557)
(−511, −484, −410)
(−350, −322, −248)
6
783
84
(1742, 2040, 2158)
(−2088, −1969, −1671)
(−1376, −1257, −960)
7
800
96
(2039, 2366, 2549)
(−2468, −2285, −1959)
(−1750, −1566, −1240)
8
478
52
(848, 942, 992)
(−949, −898, −805)
(−515, −464, −371)
9
469
65
(992, 1116, 1176)
(−1122, −1061, −938)
(−708, −647, −524)
10
699
32
(853, 995, 1031)
(−1005, −968, −827)
(−333, −296, −155)
11
836
85
(1830, 2151, 2311)
(−2240, −2079, −1759)
(−1476, −1315, −995)
12
497
45
(794, 883, 918)
(−881, −845, −757)
(−422, −386, −298)
13
596
101
(1700, 2047, 2170)
(−2086, −1962, −1615)
(−1575, −1451, −1105)
14
798
34
(975, 1146, 1256)
(−1228, −1118, −948)
(−459, −348, −178)
15
197
79
(659, 743, 800)
(−734, −677, −593)
(−604, −546, −463)
16
804
85
(1819, 2092, 2318)
(−2247, −2020, −1748)
(−1515, −1288, −1016)
17
163
78
(560, 647, 708)
(−643, −581, −495)
(−546, −484, −398)
18
457
44
(685, 810, 839)
(−803, −773, −649)
(−383, −353, −229)
19
523
100
(1547, 1851, 2042)
(−1958, −1767, −1463)
(−1520, −1328, −1025)Chen [25] combined four traditional dispatching rules—EDD, critical ratio (CR), the fluctuation smoothing policy for mean cycle time (FSMCT)—and the fluctuation smoothing policy for variation of cycle time (FSVCT), and proposed the four-objective dispatching rule. In the four-objective dispatching rule, the slack of job j at processing step u is defined as
(22)SKju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju-minjRCTEjumaxjRCTEju-minjRCTEju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,
where α,β,γ, and η and are positive real numbers that satisfy the following constraints:
(23)Ifα=1thenβ,γ,ϑ=0;η=-1,andviceversa,Ifβ=1thenα=0;γ,η,ϑ=-1,andviceversa,Ifη=1thenα,β=0;γ,ϑ=1,andviceversa.
Jobs with the smallest slack values will be given the highest priorities. There are many possible models that can form the combinations of α,β,γ,η, and ϑ. For example,
(24)(Linearmodel)α=1-2β-γ;γ=ϑ=η+α,(Nonlinearmodel)α=(1-2β-γ)u,u∈Z+;γ=ϑ=(η+α)v,v=1,3,5,…,(Logarithmicmodel1)α=ln(2-2β-γ)ln2;γ=ϑ=ln(1.5η+α+2.5)ln2-1.
The values of α and β are within [01].If the remaining cycle time is estimated with a triangular fuzzy number, then (22) becomes
(25)SK~ju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTE~ju-minjRCTE~jumaxjRCTE~ju-minjRCTE~ju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ.
Job j is processed before job k if SK~ju<SK~ku. In Wang et al. [27], to diversify the slack, the standard deviation of the slack was maximized:
(26)σSKju=∑j=1n(SKju-SK¯u)2n-1.
When the job slack is a fuzzy value,
(27)σSK~ju=∑j=1n(SK~ju-SK~¯u)2n-1.
Maximizing σSK~ju is equivalent to maximizing ∑j=1n(SK~ju-SK~¯u)2. Finally, the following FNLP problem is to be solved:
(28)MaxZ~1=∑j=1n(SK~ju-SK~¯u)2subjecttoSK~ju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTE~ju-minjRCTE~jumaxjRCTE~ju-minjRCTE~ju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoj=1~nsubjecttoα=1-2β-γ;γ=ϑ=η+αsubjectto(or)α=(1-2β-γ)u,u∈Z+;subjecttoγ=ϑ=(η+α)v,v=1,3,5,…subjectto(or)α=ln(2-2β-γ)ln2;subjecttoγ=ϑ=ln(1.5η+α+2.5)ln2-1subjectto0≤α,β≤1.
The proposed FNLP problem is intractable and may need to be converted into an equivalent NLP problem to be solved. First, (27) can be decomposed to
(29)SK~ju=(SKju1,SKju2,SKju3),SKju1=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β,·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju1-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,SKju2=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju2-minjRCTEju2maxjRCTEju2-minjRCTEju2)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,SKju3=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju3-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ.
The α-cut of SK~ju is
(30)SKju(α)=[SKjuL(α),SKjuR(α)]=[SKju1+α(SKju2-SKju1),SKju3+α(SKju2-SKju3)].
Subsequently, the objective function is equal to
(31)Z~1=∑j=1n(SK~ju-SK~¯u)2=∑j=1n(SK~ju-∑k=1nSK~kun)2=1n2∑j=1n((n-1)SK~ju-∑k=1j-1SK~ku-∑k=j+1nSK~ku)2.
The α-cut of Z~1 is
(32)[Z1L(α),Z1R(α)]=1n2∑j=1n[∑k=j+1nSKkuL(α)(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α),(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α)]2.
Applying (8) to (32) gives
(33)Z1L(α)=1n2∑j=1nmax(ξ(α)ζ(α),0)·min(ξ(α)ζ(α),ζ(α)ξ(α)),(34)Z1R(α)=1n2∑j=1nmax(ξ2(α),ζ2(α)),
where
(35)ξ(α)=(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α),ζ(α)=(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α).
Equation (33) is equivalent to
(36)Z1L(α)=1n2∑j=1nΞ(α)·Θ(α),Ξ(α)≥=ξ(α)ζ(α),Ξ(α)≥=0,Ξ(α)(Ξ(α)-(α)ζ(α))=0,Θ(α)≤ξ(α)ζ(α),Θ(α)≤ζ(α)ξ(α),(Θ(α)-ζ(α)ξ(α))(Θ(α)-ξ(α)ζ(α))=0.
Similarly, (34) can be replaced by
(37)Z1R(α)=1n2∑j=1nΥ(α),Υ(α)≥=ξ2(α),Υ(α)≥=ζ2(α),(Υ(α)-ξ2(α))(Υ(α)-ζ2(α))=0.
In order to facilitate the solving of the problem, the usual practice is to defuzzify the fuzzy objective function Z~1, using the center-of-gravity defuzzification [28]:
(38)D(Z~1)=∑α=01αZ1L(α)+∑α=01αZ1R(α)∑α=01α+∑α=01α=∑α=01αZ1L(α)+∑α=01αZ1R(α)11,
where D() is the defuzzification function. Finally, the following NLP model is optimized instead of the original FNLP problem:
(39)MaxZ2=∑α=01αZ1L(α)+∑α=01αZ1R(α)11subjecttoZ1L(α)=1n2∑j=1nΞ(α)·Θ(α)subjecttoΞ(α)≥=ξ(α)ζ(α)subjecttoΞ(α)≥=0subjecttoΞ(α)(Ξ(α)-(α)ζ(α))=0subjecttoΘ(α)≤ξ(α)ζ(α)subjecttoΘ(α)≤ζ(α)ξ(α)subjectto(Θ(α)-ζ(α)ξ(α))(Θ(α)-ξ(α)ζ(α))=0subjecttoZ1R(α)=1n2∑j=1nΥ(α)subjecttoΥ(α)≥=ξ2(α)subjecttoΥ(α)≥=ζ2(α)subjectto(Υ(α)-ξ2(α))(Υ(α)-ζ2(α))=0subjecttoξ(α)=(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α)subjecttoζ(α)=(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α)subjecttoSKjuL(α)=SKju1+α(SKju2-SKju1)subjecttoSKjuR(α)=SKju3+α(SKju2-SKju3)subjecttoSKju1=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju1-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoSKju2=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju2-minjRCTEju2maxjRCTEju2-minjRCTEju2)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoSKju3=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju3-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoj=1~nsubjectto(Linearmodel)α=1-2β-γ;subjecttoγ=ϑ=η+αsubjectto0≤α,β≤1Consider the example in Table3. Both the proposed methodology and Wang et al.’s method are applied to this example. In the proposed methodology, the optimal objective function value Z2* is 187272 when the parameters α,β,γ,η, and ϑ are equal to 0.980, 0.560, -1.100,-1.100, and -2.082, respectively. The slacks of the jobs are shown in Figure 4. Please note that in this figure the x-axis is converted to logarithmic values for clarity. In contrast to this, Wang et al.’s method cannot consider the uncertainty in the remaining cycle time, and therefore only the center value of the remaining cycle time is considered. The slacks obtained by using Wang et al.’s method are shown in Figure 5, in which σSKju*=93. The optimal values of the parameters α,β,γ,η, and ϑ are equal to 0.938, 0.587, -1.112,-1.112, and -2.050, respectively. Obviously, one has the following.(1)
After considering the uncertainty of the remaining cycle time, the best values of the five parameters changed, and the slacks of jobs became different. This might result in different sequencing results.(2)
There were 14 ties in Wang et al.’s method. Conversely, after considering the uncertainty in the remaining cycle time, the proposed methodology successfully diversified the slacks of the jobs and reduced the number of ties to 11. In this regard, the advantage of the proposed methodology over Wang et al.’s approach is 21%.(3)
In the method of Wang et al., if there is a long tail in the remaining cycle time of a job on the right-hand side, then the slack of the job will be underestimated. Conversely, the slack will be overestimated if there is a long tail on the left-hand side.Table 3
An example.
Number
R
j
j
RCTE
~
j
u
SCT
j
u
RPT
j
u
1
102
159
(1200, 1399, 1458)
881
560
2
756
37
(976, 1127, 1176)
227
451
3
826
37
(1086, 1223, 1299)
157
489
4
652
86
(1618, 1822, 1976)
331
729
5
208
55
(455, 530, 557)
775
212
6
783
84
(1742, 2040, 2158)
200
816
7
800
96
(2039, 2366, 2549)
183
946
8
478
52
(848, 942, 992)
505
377
9
469
65
(992, 1116, 1176)
514
446
10
699
32
(853, 995, 1031)
284
398
11
836
85
(1830, 2151, 2311)
147
860
12
497
45
(794, 883, 918)
486
353
13
596
101
(1700, 2047, 2170)
387
819
14
798
34
(975, 1146, 1256)
185
458
15
197
79
(659, 743, 800)
786
297
16
804
85
(1819, 2092, 2318)
179
837
17
163
78
(560, 647, 708)
820
259
18
457
44
(685, 810, 839)
526
324
19
523
100
(1547, 1851, 2042)
460
740Figure 4
The fuzzy slacks obtained by the proposed methodology.Figure 5
The fuzzy slacks obtained by using Wang et al.’s method.


## 2.1.α Cuts and α-Cut Operations

Theα-cut operations are applied to solve the FNLP problem. For this reason, the concepts of α cuts and α-cut operations are introduced as follows.Definition 1 (α cuts).
A
~ is a fuzzy number. The α cut of A~ is an interval number given by
(1)A(α)={x∣x∈R,μA~(x)≥α}=[AL(α),AR(α)].Definition 2 (arithmetic of fuzzy numbers based onα-cut operations).
Given two fuzzy numbersA~ and B~, and their α cuts A(α) and B(α), the arithmetic operations of A~ and B~ based on their α cuts are as follows:
(2)A(α)(+)B(α)=[AL(α),AR(α)](+)[BL(α),BR(α)]=[AL(α)+BL(α),AR(α)+BR(α)],(3)A(α)(-)B(α)=[AL(α),AR(α)](-)[BL(α),BR(α)]=[AL(α)-BR(α),AR(α)-BL(α)],(4)A(α)(×)B(α)=[AL(α),AR(α)](×)[BL(α),BR(α)]=[min(AL(α)BL(α),AL(α)BR(α),AR(α)BL(α),AR(α)BR(α)),max(AL(α)BL(α),AL(α)BR(α),AR(α)BL(α),AR(α)BR(α))],(5)kA(α)=[kAL(α),kAR(α)],k≥0,(6)A2(α)={[0,max(AL2(α),AR2(α))],IfAL≤0≤AR,[min(AL2(α),AR2(α)),max(AL2(α),AR2(α))],otherwise.(7)A(α)(/)B(α)=[AL(α),AR(α)](/)[BL(α),BR(α)]=[AL(α)BR(α),AR(α)BL(α)]AL(α)≥0,BL(α)>0,
where (+), (-), (×), and (/) denote fuzzy addition, subtraction, multiplication, and division, respectively. Equation (5) is equivalent to
(8)A2(α)=[(AL2(α),AR2(α))max(AL(α)AR(α),0)·min(AL(α)AR(α),AR(α)AL(α)),max(AL2(α),AR2(α))]
if AL(α),AR(α)≠0. The min() and max() function can be replaced by
(9)x=min(a,b)⟺x≤a;x≤b;(x-a)(x-b)=0,x=max(a,b)⟺x≥a;x≥b;(x-a)(x-b)=0.Theorem 3 (average of fuzzy numbers based onα cuts).
Givenn fuzzy numbers A~j=[AjL(α),AjR(α)], j=1~n, the average of these fuzzy numbers can be derived as
(10)A¯(α)=[A-L(α),A-R(α)]=[∑j=1nAjL(α)n,∑j=1nAjR(α)n].Proof.
Theorem3 can be directly derived from (2) and (5).


## 2.2. The Effective FBPN Approach for Estimating the Remaining Cycle Time

Before any job is scheduled, the remaining cycle time of each job needs to be estimated. In this work, the effective FBPN approach is applied and the remaining cycle time is estimated with a fuzzy value.In the effective FBPN approach, jobs are classified intoK categories using fuzzy c-means (FCM). First, in order to facilitate the subsequent calculations and problem solving, all raw data are normalized [29]. Then, we place the (normalized) attributes of jobj in vector xj=[xjp].FCM classifies jobs by minimizing the following objective function:(11)Min∑k=1K∑j=1nμj(k)mej(k)2,
where K is the required number of categories; n is the number of jobs; μj(k) indicates that job j belongs to category k; ej(k) measures the distance from job j to the centroid of category k; m∈[1,∞) is a parameter to adjust the fuzziness and is usually set to 2. The procedure of FCM is as follows(1)
Produce a preliminary clustering result: the performance of FCM is sensitive to the initial conditions.(2)
(Iterations) calculate the centroid of each category as(12)x-(k)={x-(k)p};p=1~P,x-(k)p=∑j=1nμj(k)mxjp∑j=1nμj(k)m,μj(k)=1∑q=1K(ej(k)/ej(q))2/(m-1),ej(k)=∑allp(xjp-x-(k)p)2,wherex-(k) is the centroid of category k. μj(k)(t) is the membership function that indicates job i belongs to category k after the tth iteration.(3)
Remeasure the distance from each job to the centroid of each category, and then recalculate the corresponding membership.(4)
Stop if the following condition is met. Otherwise, return to step (2):(13)maxkmaxj|μj(k)(t)-μj(k)(t-1)|<d,
where d is a real number representing the threshold for the convergence of membership.Finally, the separate distance test (S test) proposed by Xie and Beni [30] can be applied to determine the optimal number of categories K:
(14)MinSsubjecttoJm=∑k=1K∑j=1nμj(k)mej(k)2emin2=mink1≠k2(∑allp(x-(k1)p-x-(k2)p)2)S=Jmn×emin2K∈Z+.
The K value that minimizes S determines the optimal number of categories.After clustering, a three-layer FBPN is used to estimate the cycle times of jobs for each category. The configuration of the three-layer FBPN is as follows. First, the inputs are theP parameters associated with the jth job. Subsequently, there is only a single hidden layer; the hidden layer has twice as many neurons as the input layer. In addition, Chen and Wang [31] and Chen and Lin [32] have described how an NLP model can be constructed to adjust the connection weights and thresholds in an FBPN; this problem is not easy to solve. In the proposed methodology, only the threshold on the output node (θ~o) will be adjusted. This way is much simpler and can also achieve good results. In other words, only θ~o is fuzzy, while the other parameters are crisp. In this way, the fuzzy remaining cycle time estimate is generated with minimal effort. This makes the FBPN approach an effective one. The output from the three-layer FBPN is the (normalized) estimated remaining cycle time (N(RCTEju~)) of the training examples, where N() is the normalization function.The procedure for determining the parameter values is now described. First, to determine the value of each parameter andθ2o, the FBPN is treated as a crisp network. Some algorithms are applicable for this purpose, such as gradient descent algorithms, conjugate gradient algorithms, the Levenberg-Marquardt algorithm, and others. In this study, the Levenberg-Marquardt algorithm is applied. The Levenberg-Marquardt algorithm was designed for training with second-order speed without having to compute the Hessian matrix. It uses approximation and updates the network parameters in a Newton-like way [33].Subsequently,θ3o is to be determined, so that the actual value will be less than the upper bound of the network output. Assume that the adjustment made to the threshold on the output node is denoted as Δθo=θ3o-θ2o. The optimal value of Δθo should be set as follows:
(15)Δθo*=minj(ln(1N(RCTju)-1)-ln(1oj2-1)).
In a similar way, θ1o can be determined so that each actual value will be greater than the appropriate lower bound. The optimal value of Δθo can be obtained as:
(16)Δθo*=maxj(ln(1N(RCTju)-1)-ln(1oj2-1)).
This FBPN approach can generate a very precise interval of the remaining cycle time for each job, thereby reducing the risk of misscheduling. An instance has been analyzed in Figure 2 to evaluate the performance of this method. To provide a comparison, a statistical analysis method is also applied to this instance, in which the relationship between the remaining cycle time and job attributes is fitted with a multiple regression equation. The results are shown in Figure 3. Compared with the effective FBPN approach, the statistical analysis method is not only inaccurate but also not precise enough. The remaining cycle time estimated by the statistical analysis method is therefore prone to errors, which may result in incorrect scheduling.Figure 2
The estimation results by the effective FBPN approach.Figure 3
The estimation results by the statistical analysis approach.


## 2.3. The Fuzzy Four-Objective Dispatching Rule

Lu et al. [26] proposed two fluctuation smoothing rules—the fluctuation smoothing policy for mean cycle time (FSMCT) and the fluctuation smoothing policy for variation of cycle time (FSVCT). FSMCT is aimed at minimizing the mean cycle time, while FSVCT is aimed at minimizing the variance of cycle time:(FSMCT)(17)SKju(FSMCT)=jλ-RCTEju,(FSVCT)(18)SKju(FSVCT)=Rj-RCTEju.
Jobs with the smallest slack values are given the highest priorities.If the remaining cycle time is estimated with a TFN, then we have two fuzzy fluctuation smoothing rules as(fuzzy FSMCT)(19)SK~ju(FSMCT)=jλ-RCTE~ju,(fuzzy FSVCT)(20)SK~ju(FSVCT)=Rj-RCTE~ju.To determine the sequence of jobs, the fuzzy slacks must be compared. To this end, various methods have been proposed in the literature, such as a method based on the probability measure [34], a coefficient of variance (CV) index [35], a method that uses the area between the centroid point and the original point [36], and a method based on the fuzzy mean and standard deviation [37]. For a comparison of these methods, refer to Zhu and Xu [37]. In this study, the method based on the fuzzy mean and standard deviation is applied because it is relatively simple and can yield reasonable comparison results. To put this in context, the following theorem is introduced.Theorem 4.
The fuzzy mean and standard deviation of a triangular fuzzy numberA~ = (x0-a, x0, x0+b) can be derived as
(21)μA~=x0+b-a3,σA~=a2+ab+b218.Proof.
Refer to Zhu and Xu [37]. It is, in fact, the center-of-gravity (COG) method.The following definition details a method based on the fuzzy mean and standard deviation.Definition 5.
For any two fuzzy numbersA~ and B~∈F(R), the sequence of A~ and B~ can be determined according to their fuzzy means and standard deviations as follows.(1)
μA~>μB~ if and only if A~≻B~.(2)
μA~<μB~ if and only if A~≺B~.(3)
IfμA~=μB~, then
(i)
σA~>σB~ if and only if A~≺B~.(ii)
σA~<σB~ if and only if A~≻B~.(iii)
σA~=σB~ if and only if A~=B~.Consider the example in Table2. The sequencing results by the two fuzzified rules areFuzzy FSMCT: 7→ 11 → 16 → 6 → 13 → 4 → 19 → 1 → 3 → 14 → 2 → 9 → 10 → 8 → 12 →18 → 15 → 17 → 5.Fuzzy FSVCT: 7→ 13 → 19 → 16 → 11 → 1 → 6 → 4 → 9 → 15 → 17 → 8 → 3 → 12 → 2 → 14 → 18 → 5 → 10.Table 2
An example (λ = 1.18).
Number
R
j
j
RCTE
~
j
u
SK
~
j
u (FFSMCT)
SK
~
j
u (FFSVCT)
1
102
159
(1200, 1399, 1458)
(−1324, −1265, −1066)
(−1357, −1297, −1099)
2
756
37
(976, 1127, 1176)
(−1145, −1096, −945)
(−421, −371, −221)
3
826
37
(1086, 1223, 1299)
(−1269, −1192, −1055)
(−474, −397, −261)
4
652
86
(1618, 1822, 1976)
(−1904, −1750, −1546)
(−1325, −1170, −967)
5
208
55
(455, 530, 557)
(−511, −484, −410)
(−350, −322, −248)
6
783
84
(1742, 2040, 2158)
(−2088, −1969, −1671)
(−1376, −1257, −960)
7
800
96
(2039, 2366, 2549)
(−2468, −2285, −1959)
(−1750, −1566, −1240)
8
478
52
(848, 942, 992)
(−949, −898, −805)
(−515, −464, −371)
9
469
65
(992, 1116, 1176)
(−1122, −1061, −938)
(−708, −647, −524)
10
699
32
(853, 995, 1031)
(−1005, −968, −827)
(−333, −296, −155)
11
836
85
(1830, 2151, 2311)
(−2240, −2079, −1759)
(−1476, −1315, −995)
12
497
45
(794, 883, 918)
(−881, −845, −757)
(−422, −386, −298)
13
596
101
(1700, 2047, 2170)
(−2086, −1962, −1615)
(−1575, −1451, −1105)
14
798
34
(975, 1146, 1256)
(−1228, −1118, −948)
(−459, −348, −178)
15
197
79
(659, 743, 800)
(−734, −677, −593)
(−604, −546, −463)
16
804
85
(1819, 2092, 2318)
(−2247, −2020, −1748)
(−1515, −1288, −1016)
17
163
78
(560, 647, 708)
(−643, −581, −495)
(−546, −484, −398)
18
457
44
(685, 810, 839)
(−803, −773, −649)
(−383, −353, −229)
19
523
100
(1547, 1851, 2042)
(−1958, −1767, −1463)
(−1520, −1328, −1025)Chen [25] combined four traditional dispatching rules—EDD, critical ratio (CR), the fluctuation smoothing policy for mean cycle time (FSMCT)—and the fluctuation smoothing policy for variation of cycle time (FSVCT), and proposed the four-objective dispatching rule. In the four-objective dispatching rule, the slack of job j at processing step u is defined as
(22)SKju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju-minjRCTEjumaxjRCTEju-minjRCTEju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,
where α,β,γ, and η and are positive real numbers that satisfy the following constraints:
(23)Ifα=1thenβ,γ,ϑ=0;η=-1,andviceversa,Ifβ=1thenα=0;γ,η,ϑ=-1,andviceversa,Ifη=1thenα,β=0;γ,ϑ=1,andviceversa.
Jobs with the smallest slack values will be given the highest priorities. There are many possible models that can form the combinations of α,β,γ,η, and ϑ. For example,
(24)(Linearmodel)α=1-2β-γ;γ=ϑ=η+α,(Nonlinearmodel)α=(1-2β-γ)u,u∈Z+;γ=ϑ=(η+α)v,v=1,3,5,…,(Logarithmicmodel1)α=ln(2-2β-γ)ln2;γ=ϑ=ln(1.5η+α+2.5)ln2-1.
The values of α and β are within [01].If the remaining cycle time is estimated with a triangular fuzzy number, then (22) becomes
(25)SK~ju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTE~ju-minjRCTE~jumaxjRCTE~ju-minjRCTE~ju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ.
Job j is processed before job k if SK~ju<SK~ku. In Wang et al. [27], to diversify the slack, the standard deviation of the slack was maximized:
(26)σSKju=∑j=1n(SKju-SK¯u)2n-1.
When the job slack is a fuzzy value,
(27)σSK~ju=∑j=1n(SK~ju-SK~¯u)2n-1.
Maximizing σSK~ju is equivalent to maximizing ∑j=1n(SK~ju-SK~¯u)2. Finally, the following FNLP problem is to be solved:
(28)MaxZ~1=∑j=1n(SK~ju-SK~¯u)2subjecttoSK~ju=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTE~ju-minjRCTE~jumaxjRCTE~ju-minjRCTE~ju)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoj=1~nsubjecttoα=1-2β-γ;γ=ϑ=η+αsubjectto(or)α=(1-2β-γ)u,u∈Z+;subjecttoγ=ϑ=(η+α)v,v=1,3,5,…subjectto(or)α=ln(2-2β-γ)ln2;subjecttoγ=ϑ=ln(1.5η+α+2.5)ln2-1subjectto0≤α,β≤1.
The proposed FNLP problem is intractable and may need to be converted into an equivalent NLP problem to be solved. First, (27) can be decomposed to
(29)SK~ju=(SKju1,SKju2,SKju3),SKju1=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β,·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju1-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,SKju2=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju2-minjRCTEju2maxjRCTEju2-minjRCTEju2)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ,SKju3=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju3-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑ.
The α-cut of SK~ju is
(30)SKju(α)=[SKjuL(α),SKjuR(α)]=[SKju1+α(SKju2-SKju1),SKju3+α(SKju2-SKju3)].
Subsequently, the objective function is equal to
(31)Z~1=∑j=1n(SK~ju-SK~¯u)2=∑j=1n(SK~ju-∑k=1nSK~kun)2=1n2∑j=1n((n-1)SK~ju-∑k=1j-1SK~ku-∑k=j+1nSK~ku)2.
The α-cut of Z~1 is
(32)[Z1L(α),Z1R(α)]=1n2∑j=1n[∑k=j+1nSKkuL(α)(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α),(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α)]2.
Applying (8) to (32) gives
(33)Z1L(α)=1n2∑j=1nmax(ξ(α)ζ(α),0)·min(ξ(α)ζ(α),ζ(α)ξ(α)),(34)Z1R(α)=1n2∑j=1nmax(ξ2(α),ζ2(α)),
where
(35)ξ(α)=(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α),ζ(α)=(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α).
Equation (33) is equivalent to
(36)Z1L(α)=1n2∑j=1nΞ(α)·Θ(α),Ξ(α)≥=ξ(α)ζ(α),Ξ(α)≥=0,Ξ(α)(Ξ(α)-(α)ζ(α))=0,Θ(α)≤ξ(α)ζ(α),Θ(α)≤ζ(α)ξ(α),(Θ(α)-ζ(α)ξ(α))(Θ(α)-ξ(α)ζ(α))=0.
Similarly, (34) can be replaced by
(37)Z1R(α)=1n2∑j=1nΥ(α),Υ(α)≥=ξ2(α),Υ(α)≥=ζ2(α),(Υ(α)-ξ2(α))(Υ(α)-ζ2(α))=0.
In order to facilitate the solving of the problem, the usual practice is to defuzzify the fuzzy objective function Z~1, using the center-of-gravity defuzzification [28]:
(38)D(Z~1)=∑α=01αZ1L(α)+∑α=01αZ1R(α)∑α=01α+∑α=01α=∑α=01αZ1L(α)+∑α=01αZ1R(α)11,
where D() is the defuzzification function. Finally, the following NLP model is optimized instead of the original FNLP problem:
(39)MaxZ2=∑α=01αZ1L(α)+∑α=01αZ1R(α)11subjecttoZ1L(α)=1n2∑j=1nΞ(α)·Θ(α)subjecttoΞ(α)≥=ξ(α)ζ(α)subjecttoΞ(α)≥=0subjecttoΞ(α)(Ξ(α)-(α)ζ(α))=0subjecttoΘ(α)≤ξ(α)ζ(α)subjecttoΘ(α)≤ζ(α)ξ(α)subjectto(Θ(α)-ζ(α)ξ(α))(Θ(α)-ξ(α)ζ(α))=0subjecttoZ1R(α)=1n2∑j=1nΥ(α)subjecttoΥ(α)≥=ξ2(α)subjecttoΥ(α)≥=ζ2(α)subjectto(Υ(α)-ξ2(α))(Υ(α)-ζ2(α))=0subjecttoξ(α)=(n-1)SKjuL(α)-∑k=1j-1SKkuR(α)-∑k=j+1nSKkuR(α)subjecttoζ(α)=(n-1)SKjuR(α)-∑k=1j-1SKkuL(α)-∑k=j+1nSKkuL(α)subjecttoSKjuL(α)=SKju1+α(SKju2-SKju1)subjecttoSKjuR(α)=SKju3+α(SKju2-SKju3)subjecttoSKju1=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju1-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoSKju2=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju2-minjRCTEju2maxjRCTEju2-minjRCTEju2)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoSKju3=(j-1n-1)α·(RPTju-minjRPTjumaxjRPTju-minjRPTju)β·(Rj-minjRjmaxjRj-minjRj)γ·(RCTEju3-minjRCTEju1maxjRCTEju3-minjRCTEju1)η·(SCTju-minjSCTjumaxjSCTju-minjSCTju)ϑsubjecttoj=1~nsubjectto(Linearmodel)α=1-2β-γ;subjecttoγ=ϑ=η+αsubjectto0≤α,β≤1Consider the example in Table3. Both the proposed methodology and Wang et al.’s method are applied to this example. In the proposed methodology, the optimal objective function value Z2* is 187272 when the parameters α,β,γ,η, and ϑ are equal to 0.980, 0.560, -1.100,-1.100, and -2.082, respectively. The slacks of the jobs are shown in Figure 4. Please note that in this figure the x-axis is converted to logarithmic values for clarity. In contrast to this, Wang et al.’s method cannot consider the uncertainty in the remaining cycle time, and therefore only the center value of the remaining cycle time is considered. The slacks obtained by using Wang et al.’s method are shown in Figure 5, in which σSKju*=93. The optimal values of the parameters α,β,γ,η, and ϑ are equal to 0.938, 0.587, -1.112,-1.112, and -2.050, respectively. Obviously, one has the following.(1)
After considering the uncertainty of the remaining cycle time, the best values of the five parameters changed, and the slacks of jobs became different. This might result in different sequencing results.(2)
There were 14 ties in Wang et al.’s method. Conversely, after considering the uncertainty in the remaining cycle time, the proposed methodology successfully diversified the slacks of the jobs and reduced the number of ties to 11. In this regard, the advantage of the proposed methodology over Wang et al.’s approach is 21%.(3)
In the method of Wang et al., if there is a long tail in the remaining cycle time of a job on the right-hand side, then the slack of the job will be underestimated. Conversely, the slack will be overestimated if there is a long tail on the left-hand side.Table 3
An example.
Number
R
j
j
RCTE
~
j
u
SCT
j
u
RPT
j
u
1
102
159
(1200, 1399, 1458)
881
560
2
756
37
(976, 1127, 1176)
227
451
3
826
37
(1086, 1223, 1299)
157
489
4
652
86
(1618, 1822, 1976)
331
729
5
208
55
(455, 530, 557)
775
212
6
783
84
(1742, 2040, 2158)
200
816
7
800
96
(2039, 2366, 2549)
183
946
8
478
52
(848, 942, 992)
505
377
9
469
65
(992, 1116, 1176)
514
446
10
699
32
(853, 995, 1031)
284
398
11
836
85
(1830, 2151, 2311)
147
860
12
497
45
(794, 883, 918)
486
353
13
596
101
(1700, 2047, 2170)
387
819
14
798
34
(975, 1146, 1256)
185
458
15
197
79
(659, 743, 800)
786
297
16
804
85
(1819, 2092, 2318)
179
837
17
163
78
(560, 647, 708)
820
259
18
457
44
(685, 810, 839)
526
324
19
523
100
(1547, 1851, 2042)
460
740Figure 4
The fuzzy slacks obtained by the proposed methodology.Figure 5
The fuzzy slacks obtained by using Wang et al.’s method.


## 3. Simulation Experiment

A real wafer fabrication factory mainly used for the production of dynamic random access memory (DRAM) was simulated. The wafer fabrication factory is located in Taiwan’s Taichung Science Park and has a monthly capacity of about 25,000 wafers. However, the following assumptions were made to generate data that are less noisy than real-world data.(1)
The distributions of the times between machine breakdowns are exponential.(2)
The distribution of the time required to repair a machine is uniform.(3)
The percentages of jobs with different priorities released into the wafer fabrication factory are controlled.(4)
A job has equal chances to be processed on each alternative machine or head that is available at a step.(5)
A job cannot proceed to the next step until the processing of every wafer in the job has been finished.(6)
No preemption is allowed.In the simulated wafer fabrication factory, there are more than 10 types of memory products and more than 500 workstations for performing single-wafer or batch operations using 58 nm~110 nm technologies. Jobs released into the fabrication factory are assigned three types of priorities, that is, “normal,” “hot,” and “super hot.” Usually, a job will only be “super hot” if it is part of an emergency order; “super hot” jobs will be processed first. The large scale and the reentrant process flows of this wafer fabrication factory exacerbate the difficulties of job dispatching. Currently, the longest average cycle time exceeds three months with a variation of more than 300 hours. The managers of this wafer fabrication factory are therefore seeking better dispatching rules to replace FIFO and EDD, in order to shorten the average cycle times and ensure on-time delivery to customers.One hundred replications of the simulation were successively run. The simulation horizon of each replication was twenty-four months. The warm-up period was the first four months. The time required for each simulation replication was about 45 minutes using a PC with Intel Dual E2200 2.2 GHz CPUs and 1.99 G RAM.To make comparisons with some existing approaches, eight methods were tested. FIFO, EDD, shortest remaining processing time (SRPT), CR, FSVCT, FSMCT, the nonlinear fluctuation smoothing rule (NFS), and the four-objective slack-diversifying rule (4o-SDR) [25] were applied to schedule the simulated wafer fabrication factory. The data of 1000 jobs were collected and separated by product types and priorities.For FIFO, jobs were sequenced on each machine first by their priorities, then by their arrival times at the machine. For EDD, jobs were also sequenced first by their priorities, then by their due dates. The performance of EDD depends on how jobs’ due dates are determined. In the experiment, the due date of each job was determined as follows:(40)DDj=Rj+(Ψ-1.5*priority)*TPTj,
where Ψ indicates the cycle time multiplier.FSVCT and FSMCT consisted of two stages. First, jobs were scheduled based on FIFO, in which the remaining cycle times of all jobs were recorded and averaged at each step. Then, FSVCT/FSMCT policy was applied to schedule the jobs based on the average remaining cycle times obtained earlier. In other words, jobs were sequenced on each machine first by their priorities, and then by their slack values, which were determined by (17) and (18). With SRPT, the remaining processing time of each job was calculated. Then, jobs were sequenced first by their priorities, then by their remaining processing times. With CR, jobs were sequenced first by their priorities, then by their critical ratios. NFS is a nonlinear fusion of FSMCT and FSVCT. In the simulation experiment, a weight of 0.8 was given to FSMCT. With 4o-SDR, the remaining cycle time of a job was estimated using the fuzzy c-means and back propagation network (FCM-BPN) approach [31]; it was a crisp value. The five adjustable parameters were set to (α,β,γ,η,ϑ)=(0.6,0.2,0,-0.6,0) after initial scenarios had been examined.In the proposed methodology, the remaining cycle time of a job was estimated using the effective FBPN approach; it was a fuzzy value. After the fuzzy remaining cycle time estimate had been fed into the fuzzy four-objective fluctuation smoothing rule, an FNLP problem was solved to determine the values of the five parameters in the rule, so as to optimize the scheduling performance.The average cycle time, cycle time standard deviation, the number of tardy jobs, and the maximum lateness of all cases were calculated to assess the scheduling performance. The results are summarized in Tables4, 5, 6, and 7.Table 4
The performance levels of various approaches for average cycle time.
Average cycle time (hrs)
A  (normal)
A  (hot)
A  (super hot)
B  (normal)
B  (hot)
FIFO
1254
400
317
1278
426
EDD
1094
345
305
1433
438
SRPT
948
350
308
1737
457
CR
1148
355
300
1497
440
FSMCT
1313
347
293
1851
470
FSVCT
1014
382
315
1672
475
NFS
1456
407
321
1452
421
4o-SDR
1183
347
271
1160
339
The proposed methodology
932
274
265
810
269Table 5
The performance levels of various approaches for maximum lateness.
The maximum lateness (hrs)
A  (normal)
A  (hot)
A  (super hot)
B  (normal)
B  (hot)
FIFO
401
-
122
164
221
172
EDD
295
-
181
144
336
185
SRPT
584
-
142
174
718
194
CR
302
-
159
138
423
192
FSMCT
875
-
165
125
856
171
FSVCT
706
-
112
174
686
260
NFS
627
10
161
331
151
4o-SDR
360
-
152
118
21
94
The proposed methodology
287
-
1
45
112
25
106Table 6
The performance levels of various approaches for cycle time standard deviation.
Cycle time standard deviation (hrs)
A  (normal)
A  (hot)
A  (super hot)
B  (normal)
B  (hot)
FIFO
55
24
25
87
51
EDD
129
25
22
50
63
SRPT
248
31
22
106
53
CR
69
29
18
58
53
FSMCT
419
33
16
129
104
FSVCT
280
37
27
201
77
NFS
64
40
19
37
26
4o-SDR
71
41
22
30
29
The proposed methodology
68
20
23
27
34Table 7
The performance levels of various approaches for number of tardy jobs.
Number of tardy jobs
A  (normal)
A  (hot)
A  (super hot)
B  (normal)
B  (hot)
FIFO
79
0
12
16
5
EDD
71
0
12
19
5
SRPT
37
0
12
19
5
CR
79
0
12
19
5
FSMCT
58
0
12
19
5
FSVCT
56
0
12
18
5
NFS
58
0
12
19
5
4o-SDR
79
0
12
19
5
The proposed methodology
37
0
12
19
5According to the experimental results, the following points can be made.(1)
In various respects, the proposed methodology was obviously superior to the existing dispatching rules. For example, the fuzzy four-objective fluctuation smoothing rule was the best at reducing the average cycle time for all cases. Its advantage over the current rule FIFO was 26% on average. The average cycle time is one of the most important scheduling goals of a wafer fabrication factory; such experimental results are very valuable. Of the traditional scheduling rules, SRPT performed well for reducing the average cycle times but posed the risk of high cycle time variation.(2)
On-time delivery is another important scheduling objective. The maximum lateness is often used to assess this. The proposed methodology can effectively reduce the maximum lateness and so can enhance on-time delivery. This tends to improve the firm’s customer relationships. The performance levels of the two traditional methods in this field, EDD and CR, were not as good as expected.(3)
Through reduced cycle time variability, we can more accurately estimate the cycle time and promise our customer a more reliable due date. The fuzzy four-objective fluctuation smoothing rule has very good performance in this respect, with an average advantage of 28% over the existing scheduling rules.(4)
The number of tardy jobs is another indicator by which one can assess on-time delivery. The proposed methodology outperformed the existing methods in most cases.In order to confirm the advantages of the proposed methodology over the existing methods, a Wilcoxon signed-rank test [38] was used to test the following hypotheses.Ha0:
When shortening the average cycle time, the scheduling performance of the proposed methodology is the same as that of the existing approach being compared.Ha1:
When shortening the average cycle time, the scheduling performance of the proposed methodology is better than that of the existing approach being compared.Hb0:
When reducing the maximum lateness, the scheduling performance of the proposed methodology is the same as that of the existing approach being compared.Hb1:
When reducing the maximum lateness, the scheduling performance of the proposed methodology is better than that of the existing approach being compared.Hc0:
When reducing the cycle time standard deviation, the scheduling performance of the proposed methodology is the same as that of the existing approach being compared.Hc1:
When reducing the cycle time standard deviation, the scheduling performance of the proposed methodology is better than that of the existing approach being compared.Hd0:
When reducing the number of tardy jobs, the scheduling performance of the proposed methodology is the same as that of the existing approach being compared.Hd1:
When reducing the number of tardy jobs, the scheduling performance of the proposed methodology is better than that of the existing approach being compared.The results are summarized in Table8. The null hypothesis Ha0 was rejected at α=0.025, which showed that the fuzzy slack-diversifying fluctuation-smoothing rule was superior to seven existing approaches at reducing the average cycle time. With regard to maximum lateness, the advantage of the fuzzy slack-diversifying fluctuation-smoothing rule over FIFO, SRPT, and FSVCT was significant. Similar results could be observed with cycle time standard deviation. However, the advantage of the fuzzy slack-diversifying fluctuation-smoothing rule was not statistically significant for the number of tardy jobs.Table 8
Results of the Wilcoxon sign-rank test.
H
a
0  (the average cycle time)
H
b
0   (the maximum lateness)
H
c
0   (cycle time standard deviation)
H
d
0   (the number of tardy jobs)
FIFO
2.02**
2.02**
1.21
0.54
EDD
2.02**
1.21
1.75*
1.21
SRPT
2.02**
2.02**
1.75*
0.67
CR
2.02**
1.75*
1.48
1.21
FSMCT
2.02**
1.48
1.75*
1.21
FSVCT
2.02**
2.02**
2.02**
0.54
NFS
2.02**
2.02**
0.54
1.21
4o-SDR
2.02**
−0.08
0.34
0.76
*
P < 0.05.
**P < 0.025.
***P < 0.01.


## 4. Conclusions and Directions for Future Research

Multiobjective scheduling is an important task in a wafer fabrication factory. It is also a difficult task owing to the uncertainty and complexity of the wafer fabrication system. This study demonstrates that an FNLP approach can consider such uncertainties and optimize the performance of multiobjective scheduling in a wafer fabrication factory.The proposed methodology starts from the estimation of the remaining cycle time for each job. To this end, an effective FBPN approach has been proposed. The estimated remaining cycle time from the FBPN is a fuzzy number. After the fuzzy remaining cycle time estimate is fed to the four-factor fluctuation smoothing rule, the rule is fuzzified, and the slack of each job is expressed by a fuzzy number. To reduce the number of ties, the slacks of jobs need to be diversified, which results in an FNLP problem. Since the FNLP problem is not easy to solve, someα-cut operations are applied to convert it into an equivalent NLP problem.After a simulation study, the following points are concluded(1)
The simulation experiment results showed that the proposed method indeed enhanced the scheduling performance of the wafer fabrication factory in four respects—average cycle time, maximum lateness, cycle time standard deviation, and number of tardy jobs.(2)
Consideration of the uncertainty in the remaining cycle time has a considerable degree of influence on scheduling performance. The proposed FBPN approach not only enhances the accuracy of estimating the remaining cycle time but can also generate a precise range for the remaining cycle time. This effectively avoids incorrect scheduling.(3)
The experimental results in this study also confirmed that the scheduling performance of a complex production system can be significantly improved by optimizing the existing dispatching rule with an FNLP model.However, the proposed methodology only optimizes the performance of a dispatching rule in a wafer fabrication factory; this does not optimize every aspect of scheduling for a wafer fabrication factory. Although slack diversification optimizes the four-objective fluctuation smoothing rule, there are other approaches that can achieve the same effect. Further, some soft computing techniques can be applied to solve the FNLP problem. All of these issues constitute directions for future research.



---

*Source: 720607-2013-04-22.xml*