J Intell Manuf DOI 10.1007/s10845-015-1033-9

A new model for single machine scheduling with uncertain processing time Kai Hu · Xingfang Zhang · Mitsuo Gen · Jungbok Jo

Received: 27 August 2014 / Accepted: 3 January 2015 © Springer Science+Business Media New York 2015

Abstract Uncertain single machine scheduling problem for batches of jobs is an important issue for manufacturing systems. In this paper, we use uncertainty theory to study the single machine scheduling problem with deadlines where the processing times are described by uncertain variables with known uncertainty distributions. A new model for this problem is built to maximize expected total weight of batches of jobs. Then the model is transformed into a deterministic integer programming model by using the operational law for inverse uncertainty distributions. In addition, a property of the transformed model is provided and an algorithm is designed to solve this problem. Finally, a numerical example is given to illustrate the effectiveness of the model and the proposed algorithm. Keywords Integer programming · Uncertainty theory · Batch scheduling

Introduction Single machine scheduling problem is the simplest type of scheduling problem. Meanwhile, it is also one of the K. Hu · X. Zhang (B) School of Mathematical Sciences, Liaocheng University, Liaocheng 252059, PR China e-mail: [email protected] M. Gen Tokyo University of Science, Tokyo, Japan M. Gen Japan and Fuzzy Logic Systems Institute, Iizuka, Japan J. Jo Division of Computer and Information Engineering, Dongseo University, Busan, Korea

most important scheduling problems. During the past few decades, “single machine scheduling with competing agent” has become a popular topic. The general setting consists of more than one agents. These sets of jobs need to be scheduled on a single machine. Researchers presented many models about agents and processors on different conditions (Wang et al. 2012; Mohammad et al. 2012). Some of the researches focused on algorithms to minimize the weighted completion time. Wang et al. (1999) built a genetic algorithm to solve this problem. Zhou and Chen (2005) gave a genetic algorithm for weighted single machine scheduling problems to maximize the whole-set orders. Lee et al. (2009) designed an approximation algorithm for multi-agent scheduling to minimize the total weighted completion time. Agnetis et al. (2007) solved multi-agent problems with some of the above mentioned objectives. Kacem (2008) focused on an approximation algorithm for minimizing the weighted flow-time on a single machine with a fixed non-availability interval. Agnetis et al. (2009) introduced branch-and-bound algorithms for minimizing the total weighted completion time of one agent subject to an upper bound on several measures of another agent. Some of the researches also focused on minimizing the total weight of tardy jobs. Agnetis et al. (2004) considered the same problem and additional measurment (such as the number of tardy jobs and maximum regular functions), and focused on a single machine and on shops. Cheng et al. (2006) studied multi-agent scheduling on a single machine to minimize the total weight of tardy jobs. Besides, many studied machine scheduling problems flexible manufacturing system such as (Chen et al. 1999; Moslemipour and Lee 2012; Omar et al. 2008). All of the above researches supposed that the processing times of jobs are constant values. However, in real life, both machines and workers can improve their performance by repeating the production operations. Therefore, the actual

123

J Intell Manuf

processing time of a job is short if it is scheduled at the end of a queue. This phenomenon is known as the “learning effect” in the literature (Badiru 1992). In the above models, the processing time of a job on single machine is assumed to be a deterministic value in a given time. However, in a single machine scheduling problems, the actual processing time of a job is often non-deterministic (2013). Therefore, probability theory was employed to solve this problem, such as Jiq (2001), Zhou and Liu (2003), Seo et al. (2005) and Rothblum and Sethuraman (2008). They presented the models of a single machine scheduling with stochastic processing times. Since estimating probability distribution needs adequate historical data, it can’t be used under the circumstance of lacking experiential data. Thus, people also presented the models of single machine scheduling with fuzzy processing time based on fuzzy set theory (Peng and Liu 2004). Zhou and Liu (2007) presented modeling capacitated location-allocation problem with fuzzy demands. Recently, Liu (2007) also proposed a new theory called uncertainty theory that can deal with uncertainty under lacking historical data. Later, it was refined by Liu (2009). Nowadays, it has been applied to uncertain programming (Gao 2012; Zhang and Chen 2012; Zhang and Meng 2013; Liu 2014), uncertain process (Yao and Li 2012; Zhang et al. 2012), uncertain statistics (Wang et al. 2012), uncertain control (Deng and Zhu 2012), uncertain logic (Mor and Sheiov 2011; Zhang and Li 2014; Zhang et al. 2014), uncertain entropy (Chen et al. 2012; Dai and Chen 2012), uncertain game theory (Yang and Gao 2013). This paper studies the scheduling problem with uncertain processing time on a single machine to maximize the total weight of batches of jobs based on uncertainty theory. It is equivalent to a multi-agent scheduling problem on a single machine to minimize total weight of tardy jobs. The rest of this paper is organized as follows. In the “Preliminaries” section, recalls some basic concepts and results about uncertainty theory. “A new model for uncertain single machine scheduling” section presents a new model for uncertain single machine scheduling to maximize the total weight of batch of jobs. The processing time of each job on the machine is regarded as an uncertain variable with known uncertainty distribution. Then the model is transformed into a deterministic integer programming model. In the “Properties of the model” section provides the properties of the model. Furthermore, an algorithm called DWE algorithm for this model is designed. “DWE algorithm” section gives a numerical example of the model. At last, a brief summary is given.

Preliminaries In this section, we will introduce some basic concepts and results of uncertainty theory.

123

Definition 1 (Liu 2007) Let L be a σ -algebra on nonempty set Γ. A set function M is called an uncertain measure if it satisfies the following axioms: Axiom 1. (Normality Axiom) M{Γ } = 1, for the universal set Γ ; Axiom 2. (Duality Axiom) M{Λ} + M{Λc } = 1, for any event Λ; Axiom 3. (Subadditivity Axiom) For every countable sequence of events {Λi }, we have M

∞ 

 Λi

≤

i=1

∞ 

M{Λi }.

i=1

In this case, the triple (Γ, L, M) is called an uncertainty space. Let (Γk , Lk , Mk ) be uncertainty spaces for k = 1, 2, ... Write Γ = Γ1 × Γ 2 × · · · , L = L 1 × L 2 × · · · Then the product uncertain measure M on the product σ -algebra L is defined by the following product axiom (2009). Axiom 4. (Product Axiom) Let (Γk , Lk , Mk ) be uncertainty spaces for k = 1, 2, · · · Then the product uncertain measure M is an uncertain measure satisfying M

∞ 

 Λk

=

k=1

∞ 

Mk {Λk },

k=1

where Λk are arbitrarily chosen events from Lk for k = 1, 2, ..., respectively. Definition 2 (Liu 2007) An uncertain variable is a function ξ from an uncertainty space (Γ, L, M) to the set of real numbers such that {ξ ∈ B} is an event for any Borel set B. Definition 3 (Liu 2007) The uncertainty distribution Φ of an uncertain variable ξ is defined by Φ(x) = M{ξ ≤ x} for any real number x. Liu (2010) gave some types of uncertainty distributions to describe uncertain variables. They are linear uncertainty distribution, zigzag uncertainty distribution, empirical uncertainty distribution, normal uncertainty distribution and lognormal uncertainty distribution. The paper only uses linear and zigzag uncertainty distributions. Therefore, we only state them in the following text.

J Intell Manuf

Definition 4 (Liu 2010) An uncertain variable ξ is called linear if it has a linear uncertainty distribution ⎧ 0, if x < a ⎨ Φ(x) = (x − a)/(b − a), if a ≤ x ≤ b ⎩ 1, if x > b denoted by L(a, b) where a, b are real number with a < b. Definition 5 (Liu 2010) An uncertain variable ξ is called zigzag if it has a zigzag uncertainty distribution ⎧ 0, if x ≤ a ⎪ ⎪ ⎨ (x − a)/2(b − a), if a ≤ x ≤ b Φ(x) = − 2b)/2(c − b), if b ≤ x ≤ c (x + c ⎪ ⎪ ⎩ 1, if x ≥ c denoted by Z (a, b, c) where a, b, c are real number with a < b < c. Definition 6 (Liu 2010) An uncertainty distribution Φ(x) is said to be regular if it is a continuous and strictly increasing function with respect to x at which 0 < Φ(x) < 1, and lim x→−∞ Φ(x) = 0, lim x→+∞ Φ(x) = 1. Definition 7 (Liu 2010) Let ξ be an uncertain variable. Then the expected value of ξ is defined by 0 +∞ M{ξ ≥ r }dr − M{ξ ≤ r }dr E[ξ ] = −∞

0

provided that at least one of the two integrals is finite. Definition 8 (Liu 2009) The uncertain variables ξ1 , ξ2 , . . . , ξm are said to be independent if  M

m

i=1

(i) n independent jobs need to be processed on a single machine in turn, and these jobs are divided into m batches G 1 , G 2 , ..., G m . Each batch G k with a weights w contains n k sub-jobs for k = 1, 2, ..., m, where km k=1 n k = n. (ii) The processing time of j-th job in k-th batch is an uncertain variable ξ jk with uncertainty distribution Φ jk for k = 1, 2, ..., m, j = 1, 2, ..., n k , respectively. The deadlines of G k are dk for k = 1, 2, ..., m, respectively. (iii) There is no delay time between two adjacent jobs. (iv) The machine processes only one job at one time, and each job should be processed only one time. With the above hypothesis, we will focus on the problem to seek a processing order such that the expected total weight of all batches of job is maximized according to the deadline of each batch job. The new model The optimal solution of the above problem can be reduced to the arrange of processing order of batches {G 1 , G 2 , ..., G m } on the machine. We use D to denote the set of all sequences of {1, 2, ..., m}. Let x = (x1 , x2 , ..., xm ) be an element of D. Then {G x1 , G x2 , ..., G xm } is a processing order of m batches of jobs. We introduce the following symbols and parameters: (i) Denote



n

(ξi ∈ Bi ) = min M{ξi ∈ Bi } 1≤i≤m

(1)

for any Borel sets B1 , B2 , . . . , Bm of real numbers. Theorem 1 (Liu 2010) Let ξ be an uncertain variable with regular uncertainty distribution Φ. If the expected value 1 exists, then E[ξ ] = 0 Φ −1 (α)dα. Theorem 2 (Liu 2010) Let ξ and η be independent uncertain variables with finite expected values. Then for any real numbers a and b, we have E[aξ + bη] = a E[ξ ] + bE[η]. Theorem 3 (Liu 2010) The zigzag uncertain variable ξ ∼ . Z (a, b, c) has an expected value E[ξ ] = a+2b+c 4

txk =

xk 

ξ j xk

j=1

as the uncertain processing time of batches G xk for k = 1, 2, . . . , m, respectively. And denote ηi (x) =

i 

n

txk =

k=1

ξ j xk

k=1 j=1

as the uncertain total completion time of all batches G x1 , G x2 , . . . , G xi for i = 1, 2, . . . , m, respectively. (ii) Denote 

A new model for uncertain single machine scheduling

xk i  

Ti (ηi (x)) =

1, if E[ηi (x)] ≤ dxi 0, otherwise,

Notations and problem formulation In this section, the assumptions for the single machine scheduling problem are:

as the truth value of batch G xi for i = 1, 2, . . . , m, i.e., Ti (ηi (x)) = 1 if G xi is completed in the deadline ; Ti (ηi (x)) = 0 if not, for i = 1, 2, . . . , m, respectively.

123

J Intell Manuf

(iii) Denote T (x) =

m 

wxi Ti (ηi (x)), x = (x1 , x2 , . . . , xm ) ∈ D

(1) If there exists j : 1 ≤ j ≤ k − 1 such that Wx 0 < Wx 0 j k and E[tx 0 ] + E[tx 0 ] + · · · + E[tx 0 ] + E[tx 0 ] + · · · + 1 2 j−1 j+1 E[tx 0 ] ≤ dx 0 , then k

k

i=1 0 x 1 = (x10 , x20 , . . . , x 0j−1 , x 0j+1 , . . . , xk0 , x 0j , xk+1 , . . . , xm0 )

as the total weight of batches of jobs. By (i–iii), we give a new model for the uncertain batch scheduling problem on one machine based on uncertainty theory as follows: ⎧ m  ⎪ ⎪ wxi Ti (ηi (x)) max f (x) = ⎪ ⎪ x ⎪ i=1 ⎪ ⎨ s.t.  1, if E[ηi (x)] ≤ dxi ⎪ ⎪ T (η (x)) = , i = 1, 2, . . . , m ⎪ i i ⎪ 0, otherwise, ⎪ ⎪ ⎩ x = (x1 , x2 , . . . , xm ) ∈ D. (2) By Theorems 1 and 2, it is transformed into the following determinate integer programming model:

⎧ m  ⎪ ⎪ max wxi Ti (ηi (x)) ⎪ ⎪ x ⎪ i=1 ⎪ ⎪ ⎪ ⎪ ⎨s.t. ⎧ xk  i n ⎪ 1 ⎨1, if  −1 (α)dα ≤ d ⎪ xi 0 Φ j xk ⎪ , i = 1, 2, . . . , m T (η (x)) = ⎪ i i k=1 j=1 ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ 0, otherwise, ⎪ ⎪ ⎩ x = (x1 , x2 , . . . , xm ) ∈ D.

is obtained by removing x 0j to the behind of xk0 in x 0 , and it satisfies f (x 0 ) =

m 

wxi Ti (ηi (x 0 )) ≤ f (x 1 )

i=1

=

m 

wxi Ti (ηi (x 1 )).

i=1

After that 0 x 2 = (x10 , x20 , . . . , x 0j−1 , x 0j+1 , . . . , xk0 , xk+1 , . . . , xm0 , x 0j )

is obtained by removing x 0j to the end of x 1 . And it satisfies f (x 1 ) =

m 

wxi Ti (ηi (x 1 )) ≤ f (x 2 )

i=1

(3)

=

m 

wxi Ti (ηi (x 2 )).

i=1

Properties of the model First, we recall a well-known property ((called Earliest Due Date (EDD) rule) of solution of the model (3). Theorem 4 (EDD rule) If the weight and expected processing times of batches of jobs are all equal, and the condition dx 0 ≤ dx 0 ≤ · · · ≤ dxm0 1

x =

j1

dxk0 , then

j2

k

l

x 1 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0j2 −1 , x 0j2 +1 , . . . , 0 xk0 , x 0j1 , x 0j2 , xk+1 , . . . , xm0 )

2

is satisfied, then the processed order 0

(2) If there exist j1 , j2 with 1 ≤ j1 < j2 ≤ k − 1 such that  Wx 0 + Wx 0 < Wx 0 and 1≤l≤k−1,l= j2 , j2 E(tx 0 ) ≤

(x10 , x20 , . . . , xk0 , . . . , xm0 )

is obtained by successively removing x 0j1 and x 0j2 respect to the behind of xk0 in x 0 , and it satisfies

is an optimal solution of model (3). Furthermore, we give one property of the model (3).

f (x 0 ) =

satisfies the following conditions: (i) dx 0 ≤ dx 0 ≤ · · · ≤ dxm0 ; 1

=

m 

wxi Ti (ηi (x 1 )).

i=1

After that,

2

(ii) Ti (x 0 ) = 1, i = 1, 2, . . . , k − 1, k ≤ m − 1, Tk (x 0 ) = 0. Then the following properties hold.

123

wxi Ti (ηi (x 0 )) ≤ f (x 1 )

i=1

Theorem 5 Suppose the processed order x 0 = (x10 , x20 , . . . , xk0 , . . . , xm0 )

m 

x 2 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0j2 −1 , x 0j2 +1 , . . . , 0 xk0 , xk+1 , . . . , xm0 , x 0j1 , x 0j2 )

J Intell Manuf

is obtained by successively removing x 0j1 , x 0j2 in x 1 to the end of x 1 , and it satisfies

and dx 0 < E(tx 0 ) + E(tx 0 ) + · · · + E(tx 0 ) + E(tx 0 ). 1

k

f (x 1 ) = =

m  i=1 m 

2

k−1

k

(1) If there exists j with 1 ≤ j ≤ k −1 such that Wx 0 < Wx 0 j k and E(tx 0 ) + E(tx 0 ) + · · · + E(tx 0 ) + E(tx 0 ) + · · · + 1 2 j−1 j+1 E(tx 0 ) ≤ dx 0 , then

wxi Ti (ηi (x 1 )) ≤ f (x 2 ) wxi Ti (ηi (x 2 )).

k

k

i=1

, . . . , jh with 1 ≤ (3) In a general way, if there exists j1 , j2 j1 < j2 < · · · < jh ≤ k −1 such that 1≤l≤k−1 wx 0 < jl

wx 0 and k

 1≤l≤k−1,l= j1 , j2 ,..., jh

is obtained by removing xk01 in x 0 to the behind of xk0 in x 0 , and it satisfies Ti (x 1 ) = Ti (x 0 ), i = 1, 2, . . . , m

E(tx 0 ) ≤ dx 0 , l

0 , . . . , xm0 ) x 1 = (x10 , x20 , . . . , x 0j−1 , x 0j+1 , . . . , xk0 , x 0j , xk+1

k

and then f (x 1 ) − f (x 0 ) = wx0k − wx0 j > 0. x = 1

(x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0jh −1 , x 0jh +1 , . . . , 0 xk0 , x 0j1 , x 0j2 , . . . , x 0jh , xk+1 , . . . , xm0 )

is obtained by successively removing x 0j1 , x 0j2 , . . . , x 0jh in x 0 respectively to the behind of xk0 in x 0 , and it satisfies f (x 0 ) = =

m  i=1 m 

wxi Ti (ηi (x 0 )) ≤ f (x 1 ) wxi Ti (ηi (x 1 )).

j2

x 2 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0jh −1 , x 0jh +1 , . . . , 0 xk0 , xk+1 , . . . , xm0 , x 0j1 , x 0j2 , . . . , x 0jh ),

which is obtained by successively removing x 0j1 , . . . , x 0jh to the end of x 1 , and it satisfies

=

i=1 m 

Ti (x 2 ) ≥ Ti+1 (x 1 ), i = k, . . . , m − 1, Tm (x 2 ) = 0 hold. It follows from Wx 0 < Wx 0 that f (x 1 ) ≤ f (x 2 ). j k (2) If there exists 1 ≤ j1 < j2 ≤ k − 1 such that Wx 0 + j1  Wx 0 < Wx 0 and 1≤l≤k−1,l= j1 , j2 E(tx 0 ) ≤ dx 0 , then

After that

m 

0 , . . . , xm0 , x 0j ) x 2 = (x10 , x20 , . . . , x 0j−1 , x 0j+1 , . . . , xk0 , xk+1

is got by moving x 0j to the end of x 1 , and

i=1

f (x 1 ) =

This shows that objective function value f (x) of the model (3) increases. After that,

wxi Ti (ηi (x 1 )) ≤ f (x 2 )

k

l

x 1 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0j2 −1 , x 0j2 +1 , . . . , 0 xk0 , x 0j1 , x 0j2 , xk+1 , . . . , xm0 )

is obtained by successively moving x 0j1 , x 0j2 in x 0 respectively to the behind of xk0 . It also satisfies Ti (x 1 ) = 1, i = 1, 2, . . . , k − 2, Tk−1 (x 1 ) = 0, Tk (x 1 ) = 0, Ti (x 1 ) = Ti (x 0 ), i = k + 1, . . . , m.

wxi Ti (ηi (x 2 )).

It follows from Wx 0 + Wx 0 < Wx 0 that

i=1

j1

(x10 , x20 , . . . , xm0 )

Proof Let = be an optimal solution of model (3). Then it follows from the conditions (i) and (ii) that x0

E(tx 0 ) + E(tx 0 ) + · · · + E(tx 0 ) ≤ dx 0 1

2

k

k−1

k−1

j2

k

f (x 1 ) − f (x 0 ) ≥ wxk − (wxk1 + wxk2 ) > 0. This shows that objective function value f (x) of the model (3) increases.

123

J Intell Manuf

After that,

DWE algorithm

x 2 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0j2 −1 , x 0j2 +1 , . . . ,

Now, by using the above Theorems 4 and 5, we design an algorithm called DWE algorithm as follows:

0 xk0 , xk+1 , . . . , xm0 , x 0j1 , x 0j2 )

is got by successively moving x 0j1 , x 0j2 in x 1 respectively to the end of x 1 , and Ti (x 2 ) ≥ Ti+2 (x 1 ), i = 1, . . . , m − 2, Tm−1 (x 2 ) = Tm (x 2 ) = 0 hold. It follows from Wx 0 + Wx 0 < Wx 0 that f (x 1 ) ≤ f (x 2 ). j1

j2

k

(3) Similar to the above proof,  if there exists 1 ≤ j1 < j2 < · · · < jh ≤ k − 1 such that 1≤l≤k−1,l= j , j2 ,..., jh wx 0 < l 1 wx 0 and k



E(tx 0 ) ≤ dx 0 ,

1≤l≤k−1,l= j1 , j2 ,..., jh

l

x 1 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0jh −1 , x 0jh +1 , . . . , 0 xk0 , x 0j1 , x 0j2 , . . . , x 0jh , xk+1 , . . . , xm0 )

is obtained by successively moving x 0j1 , x 0j2 , . . . , x 0jh to the behind of xk0 in x 0 . So the objective function value f (x) of the model (3) increases. After that, x 2 = (x10 , x20 , . . . , x 0j1 −1 , x 0j1 +1 , . . . , x 0jh −1 , x 0jh +1 , . . . , 0 xk0 , xk+1 , . . . , xm0 , x 0j1 , x 0j2 , . . . , x 0jh ),

is obtained by successively moving x 0j1 , x 0j2 , ..., x 0jh to the end of x 1 . So the objective function value f (x) of the model (3) increases.



123

1

2

sponding truth values Ti (x 1 ) are calculated by Theorem 4 for i = 1, 2, ..., m. Thus, an initialization approximate solution x 0 = (x10 , x20 , ..., xm0 ) of model (3) is got. Step 2. (Priority of big weight and small expected time) By Theorem 5, x 0 is replaced by x 1 . Step 3. (Delete the batch of job with small weight and 0 truth value) By Theorem 5, x 1 is replaced by x 2 . Step 4. Repeat Step 2 and Step 3, until optimal solution of the model (3) is got. Step 5. Output the optimal solution of the model (3).

A numerical example

k

then

Table 1 Indexes of batchs of jobs

Step 1. (Order of deadlines) If deadlines of jobs satisfy dx 0 ≤ dx 0 ≤ · · · ≤ dxm0 , then the order of the batch of 1 2 jobs is first arranged as G x 0 , G x 0 , ..., G xm0 , and the corre-

In this section, we will give a numerical example of the above model. Suppose that it is needed to process batches G 1 , G 2 , . . . , G 8 of jobs with weights w1 = 18 , w2 = 3 1 1 1 3 1 16 , w3 = 16 , w4 = 8 , w5 = 8 , w6 = 16 , w7 = 32 , w8 = 5 32 on a machine, respectively, and processing time of each job on the machine is a zigzag uncertain variable. Other parameters are given in Table 1. In Table 1, Φ jk = Z jk (a, b, c) is the zigzag uncertainty distribution of uncertain processing time ξ jk for j-th job of k-th batch for k = 1, 2, . . . , 8, j = 1, 2, 3, respectively. The data of 1-st line tells us, 1-st batch of job contains two jobs, the 1-st job has a zigzag uncertainty distribution Z 11 (11, 12, 13), the 2-nd job has a zigzag uncertainty distribution Z 21 (15, 16, 17), and its deadline is 48 h (i.e. its delivery time is less than or equal to 48 h). From Table 1, we gain t1 = ξ11 + ξ21 , t2 = ξ12 , t3 = ξ13 + ξ23 ,

Name

Distribution Φ1k

Distribution Φ2k

Distribution Φ3k

1-th batch

L11 (11, 13)

L21 (15, 17)

non

48

2-th batch

Z 12 (15, 16, 19)

non

non

24

Deadline (hour)dk

3-th batch

Z 13 (43, 45, 46)

Z 23 (15, 18, 19)

non

240

4-th batch

Z 24 (25, 28, 29)

Z 34 (14, 16, 17)

294

5-th batch

L14 (34, 36) L15 (12, 16)

L25 (15, 17)

Z 35 (15, 18, 19)

95

6-th batch

Z 16 (16, 18, 19)

Z 26 (15, 17, 18)

non

96

7-th batch

Z 17 (40, 45, 47)

Z 27 (15, 17, 18)

non

250

8-th batch

Z 18 (34, 36, 37)

Z 28 (27, 28, 30)

Z 38 (15, 16, 18)

297

J Intell Manuf

t4 = ξ14 + ξ24 + ξ34 , t5 = ξ15 + ξ25 + ξ35 ,

Table 2 Indexes of scheduling x 1

t6 = ξ16 + ξ26 , t7 = ξ17 + ξ27 , t8 = ξ14 + ξ24 + ξ34 .

Name

E[ti ]

2-th batch

16.5

16.5

24

1

1-th batch

28

44.5

48

1

5-th batch

47.5

92

95

1

6-th batch

34.5

216.5

96

0

3-th batch

62.25

188.75

240

1

7-th batch

61

249.75

250

1

4-th batch

78.25

328

294

0

8-th batch

80.25

408.25

297

0

di

Ti (x 1 )

By Theorems 2 and 3, we have E[t1 ] = 28, E[t2 ] = 16.5, E[t3 ] = 62.25, E[t4 ] = 78.25, E[t5 ] = 47.5, E[t6 ] = 34.5, E[t7 ] = 61, E[t8 ] = 80.25. Under the above hypothesis, we build the following model: ⎧ 8  ⎪ ⎪ ⎪ max wxi Ti (ηi (x)) ⎪ ⎪ ⎪ ⎪ x=(x1 ,x2 ,...,x8 ) i=1 ⎪ ⎨ s.t.  1, if E[ηi (x)] ≤ dxi ⎪ ⎪ Ti (ηi (x)) = ⎪ ⎪ ⎪ 0, otherwise, ⎪ ⎪ ⎪ ⎩ i = 1, 2, . . . , 8, x = (x1 , x2 , . . . , x8 ) ∈ D,

E[ηi (x 1 )]

di

Ti (x 1 )

Wi 3 16 1 8 1 8 3 16 1 16 1 32 1 8 5 32

(4) where D denotes the set of all sequences of {1, 2, . . . , 8}. By Theorems 1 and 2, the model (4) is transformed into the following deterministic integer programming model : ⎧ 8  ⎪ ⎪ max wxi Ti (ηi (x)) ⎪ ⎪ ⎪ x=(x1 ,x2 ,...,x8 ) i=1 ⎪ ⎪ ⎪ ⎪ ⎨ s.t. ⎧ xk  i n ⎪ 1 ⎨ 1, if  −1 (α)dα ≤ d ⎪ xi ⎪ 0 Φ j xk ⎪ Ti (ηi (x)) = ⎪ k=1 j=1 ⎪ ⎪ ⎪ ⎩ 0, otherwise ⎪ ⎪ ⎪ ⎩ i = 1, 2, . . . , 8, x = (x1 , x2 , . . . , x8 ) ∈ D. (5) Now we design the DWE Algorithm of the model (5). Steps of DWE Algorithm: Step 1. (Order of deadlines) Since deadlines satisfy 24 < 48 < 95 < 96 < 240 < 245 < 250 < 294 < 296, by Theorem 4, the order of the batches of jobs is arranged as G 2 , G 1 , G 5 , G 6 , G 3 , G 7 , G 4 , G 8 , and corresponding truth value Ti (x 1 ) is calculated for i = 1, 2, . . . , 8. Thus we choose x 1 = (2, 1, 5, 6, 3, 7, 4, 8) (see Table 2) as initialization approximate solution of the model (5). Step 2. (Priority of big weight and small expected time) Since E(t2 )+ E(t1 )+ E(t6 ) < d6 and w6 > w5 , by exchanging the order of 5-th batch and 6-th batch in x 1 , we get a new order x 2 = (2, 1, 6, 5, 3, 7, 4, 8) of the batch of jobs (see Table 3). Step 3. (Delete the batch of job with small weight and 0 truth value) Since T4 (x 1 ) = 0, w5 =

1 = min wk , 8 1≤k≤8

in Table 3, batch G 5 should be deleted, or it is arranged to last in x 2 , i.e., a new order x 3 = (2, 1, 6, 3, 7, 4, 8, 5) of batch 23 (see Table 4). of jobs is given, and f (x 3 ) = 32

Table 3 Index of scheduling x 2 Name

E[ti ]

E[ηi (x 1 )]

2-th batch

16.5

16.5

24

1

1-th batch

28

44.5

48

1

6-th batch

34.5

79

96

1

5-th batch

47.5

126.5

95

0

3-th batch

62.25

188.75

240

1

7-th batch

61

249.75

250

1

4-th batch

78.25

328

294

0

8-th batch

80.25

408.25

297

0

di

Ti (x 1 )

Wi 3 16 1 8 3 16 1 8 1 16 1 32 1 8 5 32

Table 4 Index of scheduling x 3 Name

E[ti ]

E[ηi (x 1 )]

2-th batch

16.5

16.5

24

1

1-th batch

28

44.5

48

1

6-th batch

34.5

79

96

1

3-th batch

62.25

141.25

240

1

7-th batch

61

202.25

250

1

4-th batch

78.25

280.5

294

1

8-th batch

80.25

360.75

297

0

5-th batch

47.5

408.25

95

0

Wi 3 16 1 8 3 16 1 16 1 32 1 8 5 32 1 8

123

J Intell Manuf Table 5 Index of scheduling x 4 Name

E[ti ]

2-th batch

16.5

16.5

24

1

1-th batch

28

44.5

48

1

6-th batch

34.5

79

96

1

4-th batch

78.25

157.25

294

1

8-th batch

80.25

237.50

297

1

5-th batch

47.5

126.5

95

0

3-th batch

62.25

188.75

240

0

7-th batch

61

249.75

250

0

E[ηi

(x 1 )]

di

Ti

(x 1 )

Wi 3 16 1 8 3 16 1 8 5 32 1 8 1 16 1 32

Step 4 (Repeat Step 2 and Step 3) Since E(t2 ) + E(t1 ) + E(t6 ) + E(t3 ) + E(t4 ) + E(t8 ) = 299.75 > d8 = 297, E(t2 ) + E(t1 ) + E(t6 ) + E(t4 ) + E(t8 ) = 237.5 < d8 = 297, and w8 > w3 + w7 , we get a new order x 4 = 25 is (2, 1, 6, 4, 8, 5, 3, 7) of the batch of jobs, and f (x 4 ) = 32 got by moving 7-th batch and 3-rd batch to back 5-th batch in x 3 (see Table 5). Step 5. (Report the optimal solution of the model) The optimal solution of model (5) is x 4 = (2, 1, 6, 4, 8, 5, 3, 7), 25 . and f (x 4 ) = 32

Conclusions A new model to maximize the total weight of the batches of jobs on a single machine was proposed based on uncertainty theory in this paper. The proposed model was transformed into a deterministic integer programming model. An algorithm called DWE algorithm to solve the model was designed. The effectiveness of the model and the algorithm were illustrated by a numerical example. Acknowledgments This work was supported by National Natural Science Foundation of China Grant Nos. 11471152 and 61273044, and Fuzzy Logic Systems Institute, Japan (JSPS-the Grant-in-Aid for Scientific Research C; No. 24510219).

References Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with competing agents. Operations Research, 52, 229–242. Agnetis, A., Mirchandani, P. B., Acciarelli, P. D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.

123

Agnetis, A., Pascale, G., & Pacciarelli, D. (2009). A Lagrangian approach to single-machine scheduling problem with two competing agents. Journal of Scheduling, 12, 401–415. Badiru, A. B. (1992). Computational survey of univariate and multivariate learning curve models. IEEE Transaction Engineering Management, 39, 176–188. Chen, F., Huang, J., & Centeno, M. (1999). Intelligent scheduling and control of rail-guided vehicles and load/unload operations in a flexible manufacturing system. Journal of Intelligent Manufacturing, 10, 405–421. Chen, X., & Ralescu, D. A. (2011). A note on truth value in uncertain logic. Expert Systems with Applications, 38, 15582–15586. Chen, X., Kar, S., & Ralescu, D. A. (2012). Cross-entropy measure of uncertain variables. Information Sciences, 201, 53–60. Cheng, T. C., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 36, 2273–2281. Dai, W., & Chen, X. (2012). Entropy of function of uncertain variables. Mathematical and Computer Modelling, 55, 754–760. Deng, L., & Zhu, Y. G. (2012). Uncertain optimal control with jump. ICIC Express Letters Part B: Applications, 3(2), 419–424. Gao, Y. (2012). Uncertain models for single facility location problems on networks. Applied Mathematical Modelling, 36(6), 2592–2599. Jiq, C. (2001). Stochastic single machine scheduling with an exponentially distributed due date. Operations Research Letters, 28, 199–203. Kacem, I. (2008). Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval. Computers & Industrial Engineering, 54(3), 401–410. Lee, K., Choi, B. C., Leung, J. Y., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109, 913–917. Liu, B. (2007). Uncertainty theory (2nd ed.). Berlin: Springer. Liu, B. (2009). Some research problems in uncertainty theory. Journal of Uncertain Systems, 3, 3–10. Liu, B. (2010). Uncertainty theory: A branch of mathematics for modeling human uncertainty. Berlin: Springer. Liu, B. (2014). Uncertain random graph and uncertain random network. Journal of Uncertain Systems, 8(2), 3–12. Liu, B. (2015). Uncertainty theory (4th ed.). Berlin: Springer. Mohammad, D. A., Doraid, D., & Mahmoud, A. B. (2012). Dynamic programming model for multi-stage single-product Kanbancontrolled serial production line. Journal of Intelligent Manufacturing, 23, 37–48. Mor, B., & Sheiov, G. (2011). Single machine batchscheduling with two competing agents to minimize total flow time. European Journal of Operational Research, 215, 524–531. Moslemipour, G., & Lee, T. S. (2012). Intelligent design of a dynamic machine layout in uncertain environment of flexible manufacturing systems. Journal of Intelligent Manufacturing, 23, 1849–1860. Omar, L., Virgilio, L., & Israel, V. (2008). Intelligent and collaborative Multi-Agent System to generate and schedule production orders. Journal of Intelligent Manufacturing, 19, 677–687. Peng, J., & Liu, B. (2004). Parallel machine scheduling models with fuzzy processing times. Information Sciences, 166, 59–66. Rothblum, G., & Sethuraman, J. (2008). Stochastic scheduling in an in-forest. Discrete Optimization, 5, 457–466. Seo, D. K., Klein, C. M., & Jang, W. (2005). Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models. Computers & Industrial Engineering, 48(2), 153–161. Wang, D., Gen, M., & Cheng, R. (1999). Scheduling grouped jobs on single machine with genetic algorithm. Computers & Industrial Engineering, 36(2), 309–324.

J Intell Manuf Wang, I., Yang, T., & Chang, Y. (2012). Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints. Journal of Intelligent Manufacturing, 23, 2271–2280. Wang, X. S., Gao, Z. C., & Guo, H. Y. (2012). Uncertain hypothesis testing for two experts’ empirical data. Mathematical and Computer Modelling, 55, 1478–1482. Yang, X., & Gao, J. (2013). Uncertain differential games with application to capitalism. Journal of Uncertainty Analysis and Applications, 1, 7. Yang, X., & Gao, J. (2014). Uncertain core for coalitional Game with uncertain payoffs. Journal of Uncertain Systems, 8(2), 13–21. Yao, K., & Li, X. (2012). Uncertain alternating renewal process and its application. IEEE Transactions on Fuzzy Systems, 20(6), 1154– 1160. Zhang X., Li, L., & Meng, G. (2014). A modified uncertain entailment model. Journal of Intelligent & Fuzzy Systems, to be published. Zhang, X., & Li, X. (2014). A semantic study of the first-order predicate logic with uncertainty involved. Fuzzy Optimization and Decision Making, to be published. Zhang, X., Ning, Y., & Meng, G. (2012). Delayed renewal process with uncertain interarrival times. Fuzzy Optimization Decision Making, 12, 79–87.

Zhang, X., & Chen, X. (2012). A new uncertain programming model for project problem. INFORMATION: An International Interdisciplinary Journal, 15(10), 3901–3911. Zhang, X., & Meng, G. (2013). Maximal united utility degree model for fund distributing in higher school. Industrial Engineering & Management Systems, 12(1), 35–39. Zhou, J., & Liu, B. (2003). New stochastic models for capacitated location-allocation problem. Computers & Industrial Engineering, 45, 111–125. Zhou, S. Y., & Chen, R. Q. (2005). A genetic algorithm: Weighted single machine scheduling problems to maximize the whole-set orders. Systems Engineering, 5, 22–24. Zhou, S. Y., & Sheng, P. F. (2006). A genetic algorithm for maximizing the weighted number of whole set order. Industrial Engineering and Management, 6, 75–79. Zhou, J., & Liu, B. (2007). Modeling capacitated location-allocation problem with fuzzy demands. Computers & Industrial Engineering, 53, 454–468.

123