Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 1

ISS N 2229-5518

Assignment of Personnels when Job Completion time follows Gamma distribution using Stochastic Programming Technique

Moham med F aisal Khan, Zaki Anwar, Qazi Shoeb Ahmad

ABSTRACT

Recruitment of persons to various jobs according to required talents in an organization plays an important role in the grow th of the organization. The f ormation of a nu mber of groups of the persons f rom the populat ion based on their ef f iciency in completion of jobs is being d one by using the t heory of

cluster analysis. In this paper w e f ormulate the problem of assignment of persons f rom various groups to diff erent jobs w ho may complete them in

min imu m time as stochastic programming proble m. The job complet ion times are assumed to f ollow s Gamma distribution. By using the chance constrained programming technique w e transf orm the stochastic programming problem to an equivalent deterministic problem w ith li near objective f unction and some non-linear (convex) constraints. First w e assume that the completion t ime variables are identically distributed Gamma variables. The model is then extended to the case of non-identically distributed time variables. The illustrative examples are also given f or both the models.

Ke y Words : Cluster analysis, Gamma distribution, Linear stochastic programming, Non-linear programming,

——————————  ——————————

1. INTRODUCTIO N

Gr owth and Development of any or ganization depends mainly on the talent of the persons r ecr uited for its var ious assignments. A talented per son w ill per for m his/her w or k mor e accur ately and w ill take less time in completion. The time of completion of a j ob is a ver y important factor and obviously it may be taken as a random var iable because the same per son under similar conditions will not necessar ily complete a same piece of w or k in another occasion in same time. In this paper w e consider the pr oblem of assignment of per sonnel in which time to complete the j ob by a per son follow s Gamma Distr ibution, and for mulate it as a stochastic li near pr ogr amming pr oblem(SLPP). The deter ministic equivalents of the SLPP’s ar e obtained in differ ent situations and the solution is obtained using a suitable softw ar e. The use of stochastic pr ogr amming in differ ent situations has been made by various author s, see for example , Biswal et al. (1998), Yadavalli, et al.(2007) and many others. A similar pr oblem has been discussed by Jeeva et al. (2004) w ith W eibull distr ibution.
Consider an or ganization w ith a finite number of j obs say, n . The or ganization w ants to r ecr uit per sons to these j obs, for
w hich they have r eceived a lar ge number of applications. The per sons ar e categor ized in var ious cl uster s using cluster analysis technique. W e ar e inter ested in obtaining the optimal number of per sons to be selected fr om differ ent clusters to per for m var ious j obs so as to minimize the completion time of all the j obs .The time taken by each person to com plete a given j ob is assumed to be a r andom var iable and follow s Gamma distr ibution. Gamma Distr ibution is commonly used to model the time to complete a j ob.(See Leonhar d and Davis,1995).
Suppose the applications r eceived for differ ent assignments w er e classified into m homogeneous gr oups accor ding to the similar ity of their qualifications. The classification may be per for med using K-means method of cluster analysis technique
(Gor den,A .D,1981). L et

C1 , C2 ,, Cm be the m homogeneous cluster s into w hich the population of applications has

been divided. W e w ill use the stochastic linear pr ogramming technique for finding the optimal assignment of applicants to var ious j obs.

2. GAMMA DI STRIBUT ION

A continuous r andom var iable T assuming only non-negative values is said to follow a gamma pr obability distr ibution if its pr obability density function is given by

f (t) 



( )

(t)  1 e t ,

t  0

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 2

ISS N 2229-5518

= 0 , elsew her e.

The par ameter s  and  ar e positive r eal number s i.e.   0 and   0 .W e use the notation

T ~ G(  ,  ).

Its moment gener ating function is given as

M (u)  E(eut )  (1 u )  .

T 

The

r th moment about or igin of T is given by

E(T r ) 

1 . (   )

 r ( )

Hence the mean and var iance of T ar e obtained as

E(T )  



and V (T )   .

 2

Note that if w e take

  1 , w e get exponential pr obability distr ibution and for   1 and   n

w e get

2 2

 2 distr ibution w ith n degr ees o f fr eedom.

3. FORMULATION OF THE PROBLE M

Let

tij

be the time taken for completing i th
j ob by a person fr om

j th

cluster (i  1,, n , j  1,, m) .W e assume that

tij ar e random var iables follow ing Gamma distr ibutions. Let

xij

be the number of individuals selected for

i th

j ob fr om

j th cluster . Our aim is to find

xij , i  1,, n , j  1,, m so as to complete the pr oj ect in minimum time. i.e. w e w ant to

n m

minimize  tij xij . Suppose that the or ganization w ould be happy if the completion time of i th j ob does not exceed ai

i 1

j 1

time units. How ever , it w ould tolerate a violation of this condition w ith a small pr obability
follow ing constraints should be satisfied

pi .This means that the

 m 

P tij xij  ai 

 1-

p ' ,

i  1,, n . (3.1 )

 j 1 

Another r equir ement of the or ganization is that the expected total man hours fr om

j th

cluster should pr efer ably not

' '

exceed b j .The c or r esponding constr aints for this r equir ement with toler ance pr obabilities of violati on

p j ar e

 t x

 b 

 1-

p ' '

j  1,, n . (3.2 )

P  ij ij j  j

 i 1 

Also the minimum number of individuals r equir ed to complete the i th

j ob is given as x ' , i  1,...., n. So



j 1

xij

 x j , i  1,, n.

Fur ther the minimum number of individuals to be selected fr om each cluster ar e also fixed by the or ganization. Let the
number for



j th cluster be x ' ' . Then w e should have

xij  x j , j  1,, m .

i 1

Since the total number of per sons selected fr om var ious cluster s should be equal to the number of per sons assigned to var ious j obs, w e obviously have

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 3

ISS N 2229-5518

m n n m

  xij

   xij

j 1 i 1

i 1

j 1

Fur ther w e should have the r estr ictions

xij  0 and integer s i  1,, n, j  1,., m .

The pr oblem of finding the optimal number of individuals fr om var ious cluster s to complete the assigned j obs in minimum time is for mulated as the follow ing chance constr ained linear pr ogr amming pr oblem, (Char nes &Coop er , 1959). SLPP

n m 

E ( Z )  E(  tij xij )

(i) 

i 

Subject to

j 1 



P[ t x

j 1

 a ]  1  p ' ,

i  1,..., n

(ii ) 



P[ tij

1

xij

 b j

]  1  p '' ,

j  1,..., m



(iii ) 



(3.3 )

n m 

 xij

i 1

 x ' ' ,

 xij

j 1

 x '

(iv) 



xij  0 ,

i  1,..., n ,

j  1,..., m and integers

(v) 

Case I: Assume that tij ar e independent and identically distr ibuted Gamma Var iates , i.e.,

tij ~ G (  ,  ) then,

Mean(t

)   =

m(t

) and Variance(t

) = 

 v(t ) .

ij  ij

ij  2 ij

Let us define S j  tij xij ,

i 1

j  1,, m.

W e have

n  n

E(Sj) =  m(tij ) xij

=  xij , j  1,., m .

i 1

 i 1

Fur ther , as tij ar e independently distr ibuted, w e have

n  n

i 1

2  xij

i 1

j   m

Now the constr aints 3.3(iii) can be wr itten as

P[S

 b ]1  p ' ' ,

j  1,, m . (3.4 )

j j j

Since cluster sizes ar e assumed to b e lar ge w e have fr om Liapounoff’s c entr al limit theor em
Thus w e have (3.4) is equivalent to

S j ~ N (E(S j ),V (S j )) .



PZ j 

b j  E(S j ) 

  1  pj

. (3.5 )

 V (S j ) 

w her e Z j

S j  E(Si )

is a standar d nor mal var iate (SNV).

V (S j )

So w e have

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 4

ISS N 2229-5518

(Z j )   (Z (1 p ) ) , w her e  is the distr ibution function of SNV and Z (1 p ) is s.t.

P[Z j  Z (1 p )  1  p j ] .

j j j

Since  is a non-decr easing function , w e have

b j  E(S j )

V (S j )

 Z (1 p )

 n

b j   xij

 i 1 

Z (1 p ) . Henc e

 x 2 ij

 i 1

n n

  xij + Z (1 pj )

i 1

  x 2 ij

i 1

 b j

, j  1,., m

(3.6 )
The inequalities (3.6) ar e the deter ministic equivalents of the constr aints 3.3(iii).

In a similar manner the deter ministic equivalents of the constr aints 3.3(ii) ar e der ived as

  xij + Z (1 pi)

  x 2 ij

ai , i  1,, n

(3.7 )

j 1

Ther efor e the deter minants equivalent of SLPP is obtained as

 n m 

Minimize E(Z )    xij

i 1 j 1

(i) 



Subject to 



m m

  xij  Z (1 pi )

j 1

  xij

j 1

 ai , i  1,., n

(ii )





(3.8 )

n n 2 

  xij  Z (1 pj )

i 1

  xij

i 1

 b j , j  1,, m

(iii ) 



 xij

i 1

 x ' ' ,  x

j 1

 x '



(iv) 



xij

 0 , i  1,, n , j  1,, m and integers

(v)

It may be easily seen that the non -linear functions on the left hand side o f constr aints 3.8(ii) and (iii) ar e convex. So the pr oblem (3.8) is a convex pr ogr amming pr oblem.
Case 2: Let us now assume that the par ameter s tij , ai and b j in SLPP (3.3 ) ar e all independent r andom var iables follow ing Gamma distr ibutions given as

tij ~ G(  , 

) , i  1,, n ,

j  1,, m

ai ~ G( 1 , 1 ) ,

b j ~ G(  2 ,  2 ) ,

i  1,, n

j  1,, m

The cor r esponding stochastic linear pr ogr amming pr oblem is the same SLPP as defined in (3.3).Now let us wr ite

S j  tij xij  b j ,

i 1

n1

j  1,, m , as

S j  tij xij

i 1

, where

x( n1) j

 1,

t( n1) j  b j , j  1,, m

(3.9 )

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 5

ISS N 2229-5518

Similar ly wr ite

m1

Si  tij xij  ai ,

j 1

i  1,, n , as

Si  tij xij

j 1

, where

xi ( m1)  1,

ti ( m1)  ai , i  1,, n

(3.10)
The constr aints 3.3(ii) and (iii) can thus be wr itten r espectively as
and

P[Si  0]  1  pi ' ,

P[S j  0]  1  p j ' ' ,

i  1,, n

j  1,, m

(3.11)
(3.12)
Again using Liapunoffs Centr al Limit Theor em in (3.11) and (3.12), w e get the inequalities

  E(S ) 

PZ i



 i   1  p ' ,

V (Si ) 

  E(S j ) 

i  1,, n

(3.13)

and PZ j 



  1  pj , j  1,, m

V (S j ) 

(3.14)
The inequality (3.13) is equivalent to

 E(S )

i  Z V (Si )

(1 p' )

, i  1,, n

(3.15)
Now fr om (3.10) w e have

E(Si )  E(tij xij  ai )

  xij 

j 1

 j 1 1

 ij

and V (Si )  V (tij xij  ai )  2

j 1

2 1

j 1 1

(3.15) then gives

 m 

  xij 

j 1 1  Z

, i  1,, n

 m 

(1 pi )

2  xij  2

j 1 1

m m

 1   xij  Z (1 p )

1  xij  1

 1 , i  1,, n

j 1

2 2 2

 i

j 1

Similar ly the inequalities (3.14) ar e equivalent to

 2 

 xij  Z (1 p' ' )

i 1

 2

 xij

i 1

  2

 2 ,

j  1,, m

Ther efor e the deter ministic equivalent of SLPP in this case is obtained as the follow ing non -linear pr ogr amming problem:

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 6

ISS N 2229-5518

 n m 

Min E (Z )    xij

(i) 

Subject to

i 1

j 1 



2 2 2 

1   xij  Z (1 p ' )

j 1

  xij  1

j 1

 1 , i  1,, n

(ii ) 





(3.16)

n n

2 2 2

 2   xij  Z (1 p '' )

i 1

 2  xij   2

i 1

  2 ,

j  1,, m

(iii ) 



 xij

i 1

 x ' ' , j  1,..., m ,  x

j 1

 x ' , i  1,, n

(iv) 



xij

 0 and integers , i  1,, n , j  1,, m.

(v)

4. THE CASE OF NO N-IDENT ICAL DIST RIBUTIO NS

Now w e consider the case w hen tij ar e independent but not identically distr ibuted:

Let tij ~ G(  ij , ij )

ie f (t

( ij

) 

) ij

e ij t ij 1 ,  ,   0

ij ( )

ij ij

= 0 , elsew her e.
The pr oblem of d eter mining the optimal number of individuals fr om var ious clusters to complete the assigned j obs under the pr escr ibed constraints is alr eady defined in (3.3)

The constr aint P[S j  a j ] 1  pj given in 3.3(iii), is equivalent to



P Z j 

b j  E(S j ) 

 1  pj . (4.1 )



Now

V (S j ) 

n n n

ij ij

E(S j ) =  E(tij ).xij

i 1

= 

i 1  ij

xij and V (S j ) = 

i 1  ij

2 ij

Ther efor e, the deter ministic equivalent of 3.3(iii) in this case is

 ij

xij 

Z (1 pj )

ij 2

2 ij

 b j ,

j  1,, m

(4.2 )

i 1  ij

Similar ly cor r esponding to the constr aint 3.3(ii) w e get

 ij

xij 

Z (1 pi )

ij 2

2 ij

 ai

, i  1,, n.

(4.3 )

j 1  ij

Henc e the non-linear deter ministic equivalent for SLPP w hen tij ar e independent and non-identically distr ibuted r andom
var iables follow ing Gamma distr ibutions is

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 7

ISS N 2229-5518

n m  ij 

Min E(Z )   

xij

(i) 

Subject

to,

i 1

j 1  ij 



 ij

1 ij

xij

 Z (1 p )



i 1

 ij 2

2 ij ij

 b j ,

j  1,, m



(ii ) 



m  ij



m  ij 2 

(4.4 )

  xij  Z (1 p )

  2 xij

 ai ,

i  1,, n

(iii ) 

j 1 ij

j 1 ij 

m 

 xij

i 1

 x ' ' ,

j  1,..., m ;

 xij

j 1

 x '

, i  1,, n

(iv) 



xij  0 and integers i  1,..., n , j  1,, m.

5. EXAMPLES

(v) 

Suppose that an or ganization has thr ee types of j obs. They advertised the posts with the qualifications so that ever y o ne must be able to do all the thr ee j obs. They r eceived a lar ge number of applications and gr ouped them into 3 clusters

C1 , C2 , and C3

using k-means method accor ding to the details of abilities given by the applicants in their applications.
Then the applicants fr om the cluster s w er e examined thr ough the inter view and each cluster is divided into binary clusters of selected and non -selected ones. The candidates fr om the selected clusters w er e ranked accor ding to their efficiency j udged by their per for mance in the interview
Let the finally selected cluster s be

K1 , K 2 , and K3

and the j obs be

J1 , J 2 , and J 3 .Let the time tij

to complete j ob

( J1 , J 2 , and J 3 ) by an individual fr om

par ameters   0.5,   10 .

j cluster ( K1 , K 2 , and K3 ) follow Gamma distr ibution w ith

. It is also given that the minimum number of candidates to be selected fr om each of the thr ee cluster s should be 2 and the minimum number of per sons assigned to a j ob should be 4.

' ' ' 2

x1  x2  x3  .

''  x ''

 x ''

 4 .

It is given that the total available time for completing each j ob is 160 hr s. Fur ther the upper limit for the expected man hour s fr om each cluster should not exceed 140 hr s.
Let us assume that the toler able pr obabilities of violations of the constr aints ar e all 0.05 i.e.

' ' ' '

' ' 0.05.

p1  p2  p3  p1

 p2  p3 

The cor r esponding pr oblem to be solved (obtained fr om 3.7) is

 3 3

Min E(Z ) =   xij

Subj ect to

10

1

xij

 Z 0.05

i 1

10

i 1

j 1

xij

 70

j  1,2,3

10

j 1

xij

 Z 0.05

10

j 1

xij

 80

i  1,2,3

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 8

ISS N 2229-5518

 xij  2 , j  1,2,3 ;

i 1

 xij  4 ,

j 1

i  1,2,3 ,

xij  0 & integers

The above NLP is solved using the package LIN GO. The optimal solution is obtained as follow s, w ith the minimum ob j ective value as 240:

x11  1

x21  1

x31  0

x12  1

x22  2

x32  2

x13  2

x23  1

x33  2

THE CA SE OF NON -IDENTI CAL DIST RIBUTIONS

Now let us assume that the j ob completion times tij follow non-identical gamma distr ibutions w ith parameters as given in table 5.1. Also the available times for the var ious j obs and the upper limits on the man hours fr om each cluster ar e given
in table (5.1) below .
Note that
a  Maximum time units to complete i th j ob.

b  Maximum man hour s available fr om j th cluster .

'  th

x ' ' 

Minimum number of individuals to complete the i j ob.
Minimum number of individuals to be selected fr om the

j th cluster .

Table 5.1: The value of  ij , ij and other constants

j	1	2	3
Cluster 	K1	K 2	K 3
i	Jobs 	 i1 i1	i 2 i 2	 i3 i3	( ai )	( xi ) '
1 2 3	J1 J 2 J 3	0.5 3 0.3 3 0.4 3	0.5 3 0.4 2 0.5 2	0.6 5 0.4 2 0.5 2	450 490 900	15 20 12
( b j )	900	800	500
' ' ( x j )	12	10	15

The Pr oblem to be solved, obtained fr om inserting the above par ameter s in (4.4) is given as

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 9

ISS N 2229-5518

Min E(Z ) 

0.5

 x11

 3

0.5

 x12

 5

0.6

 x31

 3

0.3

 x21

 2

0.4

 x22

 2

0.4

 x23

 3

0.4

 x31

 2

0.5

 x32

 2

0.5

 x33

Subject to

3  x

 3  x

 1.96

3  x 2 

3  x 2

 900

0.5

11 0.3

21 0.4 31

0.5 2

11 0.32

21 0.4 2 31

0.5

 x12

 2

0.4

 x22

 2

0.5

 x32

 1.96

0.5 2

2 2

12 0.4 2

2 2 2

22 0.5 2 32

 800

0.6

 x13

 5

0.4

 x23

 2

0.5

 x33

 1.96

0.6 2

 x 2 

0.4 2

2 2 2

23 0.5 2 33

 500

0.5

 x11

 3

0.5

 x12

 5

0.6

 x13

 1.96

0.5 2

 x 2 

0.5 2

2 5 2

12 0.6 2 13

 450

0.3

 x21

 2

0.4

 x22

 2

0.4

 x23

 1.96

0.32

2 2

21 0.4 2

2 2 2

22 0.4 2 23

 490

0.4

 x31

 2

0.5

 x32

 2

0.5

 x33

 1.96

0.4 2

2 2

31 0.5 2

2 2 2

32 0.5 2 33

 900

x11  x21  x31  25 ,

x21  x22  x23  20,

x12  x22  x32  25,

x31  x32  x33  25

x13  x23  x33  20,

x11  x12  x13  25

The above NLP is solved using the package LIN GO. The optimal solution is obtained as follow s, w ith the minimum obj ective value as 238:

x11  12

x21  0

x31  0

x12  3

x22  17

x32  0

x13  0

x23  3

x33  12

6. CONCLUS ION

In this paper w e have studied the r ecr uitment of per sonnel to var ious j obs w hen the j ob completion times follow identical Gamma distr ibutions. The best gr oup of per sons based on their efficiency in completion of j obs ar e deter mined by using cluster analysis technique. The Stochastic for mulation of the pr oblem has been br ought down to a deter ministic NLPP
thr ough Chance constrained pr ogr amming technique. The mod el d eveloped has also been extended to the case of non - identically distr ibuted time variables. The illustrative examples ar e given for both, identical and non -identical
distr ibutions. It is seen that the solut ions w ith minimum completion times ar e easily obtained.

REFERENCES

[1]. A.Char nes and W .W .Cooper (1959): Chance Constrained Pr ogr amming, Manage me nt Scie nce , 6, 227-243.
[2]. Biswal,M.P.,Bisw al,N.P and Li,Duan (1998): Pr obabilistic linear pr ogramming pr oblems with exponential random var iables: A technical note , Euro pean Journal of O pe ra tio nal resea rch , 111,589-597.
[3]. Gor den,A.D.(1981):Classif icatio n; Chapman and Hall: London, New Yor k.
[4]. Jeeva, M., Raj alaxmi, R., Char les, V. and Yadavalli, V.S.S. (2004): An applicatio n of stochastic pr ogr amming w ith W eibull distr ibution- cluster based optimum allocation of r ecr uitment in manpow er planning, Stochastic Analysis and Appl ica tio n, 22(3), 801-812.

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 3, Marc h-2012 10

ISS N 2229-5518

[5]. Leonhar d, C.A . and Davis, J.S (1995, Mar ch); Job -Shop development model: a case study, IEEE Softwa re, 12 (2), 86-
92.
[6]. Yadavalli, V.SS. , Malada,A.,Char les, V.(2007): Reliability stochastic optimization for an n-stage ser ies system w ith m chance constr aints, South Af rican Journal of Science, 103,502-504.
 Mohammed Faisal Khan r eceived M.Sc fr om Jamia Millia Islamia New Delhi,India in 2007,Qualified GAT E-2009
Exam w ith All India Rank 95 And Gate Per centile 96.41.he submitted his Ph.D fr om Depar tment of Mathematics, Integr al University, Lucknow ,India E-mail: faisalkhan004@yahoo.com
 Dr .Zaki Anw ar r eceived M.Sc and Ph.D in Statistics fr om Aligarh Muslim Univer sity, India. He is an Assistant Pr ofessor in the Depar tment of Statistics and O.R, A.M.U, India; He has mor e than 2 years of exp er ience in teaching and r esear ch. He has published 10 r esear ch paper s in r efer r ed national and inter nati onal j our nals.
 Dr .Qazi Shoeb Ahmad r eceived M.Sc and Ph.D in Oper ations Resear ch fr om Ali gar h Muslim Univer sity, India.
He is an Associate Pr ofessor in the Depar tment of Mathematics , Integr al University, India; He has mor e than 10 years of exper ience in teaching and r esear ch. He has published 15 r esear ch paper s in r eferr ed national and international j our nals. He has w r itten 7 books r elated to Mathematics and Statistics.