Microsoft Word - Shree Ram Khadka


Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.53 
 
 

                                BIBECHANA 

                                        A Multidisciplinary Journal of Science, Technology and Mathematics 

                                  ISSN 2091-0762 (online) 

                                 Journal homepage: http://nepjol.info/index.php/BIBECHANA 

 

 

 
Bottlenecks to product rate variation problem with 
batching 
 
Shree Ram Khadka 

Central Department Mathematics,Tribhuvan University, Kathmandu, Nepal 
P.O.Box, 13143 
e-mail: shreeramkhadka@gmail.com 
Article history: Received 25 May, 2011; Accepted 8 June, 2011 

 
 

Abstract 

The product rate variation problem with batching minimizes the variation in the rate at which different 
models of a common base product are produced on the assembly lines with the assumption of 
significant setup and arbitrary processing times for each copy of each model. Establishment of 
bottlenecks to the problem is important for the feasible and the optimal solution to the problem. In this 
paper, the lower and the upper bottlenecks to the problem are established.  Moreover, small 
bottlenecks that lead to optimality to some instances are investigated. 

 
 
Keywords: Product rate variation problem; batching; sequencing problem; nonlinear                       
intege  programming 
 

 

 

1. Introduction 
 
The product rate variation problem (PRVP) with batching minimizes the variation in the rate at which 
different models of a common base product are produced in batches on the assembly lines [7,8]. The 
problem minimizes both the earliness and the tardiness penalties that respond to the customer 
demands for a variety of models without holding large inventories or incurring large shortages. This is 
a problem of finding a sequence of batches of different models distributed as evenly as possible on 
the assembly lines with the assumption of significant set up and arbitrary processing times. 
 
Significant setup and arbitrary processing times can be undertaken when the planning horizon is 
partitioned into a finite number of time-buckets with equal length. The time length of a time-bucket is 
called a takt-time. A time-bucket consists of a setup and a batch (a copy or several copies) of a 
model. The assumption that allows significant  
 
setup and arbitrary processing times forces the product rate variation problem to be a two-phase 
problem [7,8]. We call this problem as the product rate variation problem with batching.  

 
The first phase is the batching problem that determines the batch size and the number of batches of 
the models. The second phase is the sequencing problem that sequences the batches. The problem 
that determines the size and the number of batches and minimizes the maximum variation in the rate 
at which batches of different models of a common base product are produced is called the bottleneck 
product rate variation with batching problem. 
 



Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.54 
 
 
The problem has been formulated as a non-linear integer programming with the objective of 
minimizing the deviation between the actual and the ideal production under the assumption that the 
system has sufficient capacity with significant set up and arbitrary processing times each batch of a 
model is produced in a unit time-bucket [7,8]. The problem has mathematically interesting base model 
with theoretical value and real world applications, see [3]. 
 
The problem has been extensively studied and solved in pseudo-polynomial time. The total PRVP i.e. 

the problem with the objective of minimizing the total deviation has been solved in O(D�), [5] and the 
problem with the objective of minimizing the maximum deviation i.e. the bottleneck PRVP in O(DlogD) 
time [4].  Note that the solution to both cases of the problem is Pareto optimal. 
 
Establishment of bottlenecks is important to the optimization problem since the bottlenecks guaranty 
whether the optimal or feasible solution exists or not.  It is clear that there exists no even feasible 
solution below the lower bottleneck and every instance has optimal solution below the upper one.  
 
In this paper, the lower and the upper bottlenecks to the problem are established.  Moreover, small 
bottlenecks that lead to optimality to some instances are investigated. 
 
The plan of the paper is as follows. Section 2 reviews the mathematical model. In Section 3, the lower 
and the upper bottlenecks are established. Section 4 studies small bottlenecks that lead to optimality 
to some instances are investigated. The last section concludes the paper. 
 
2. Mathematical Formulation  
 
Let s
 and p
 be the setup and processing times of a model i, i = 1, . . . , n, respectively. The total 

demands D =  ∑ d

�

��   are manufactured over the planning horizon T partitioned into � time- buckets 

i.e. the number of batches with the takt-time t =  �
�. There may exist batches with no  models to be 

manufactured. Such empty batches are potentially useful for the improvement of the system 
performance [5]. The takt-time satisfies t ≥  s
 + p
,i = 1, . . . , n.  
 

We denote x� 
 , i = 0, 1, . . . , n; k = 1, . . . , � to be the actual cumulative number of batches for model i 
produced during the time-buckets 1 through k. The actual cumulative  
 

production of model i during the same time-buckets is γ
x�
 , where γ
 =  #$
#%$

  is the average number of 

copies of model i per batch. The ideal cumulative production of model i during 1 through k time-

buckets is γ
kr�
, where r�
 =  #%$
�   is the batch rate. The sequencing problem minimizes the deviation 

between the actual and the ideal productions. Let m be a positive integer. 
 
The mathematical programming for the sequencing phase of the bottleneck product rate variation 
problem with batching is 
 

minimize [F* =  max
, (γ
|x� 
 − kr�
| )*]                 (8) 

subject to  

   ∑ x� 
 = k�

�� ,           k = 1, … , �                        (9) 

 
                                   x� 
( 0�) ≤  x� 
 ,          i = 0,1, … , n;  k = 2, … , �                             (10) 

                                    x� 
� =  d3 
, x� 
4 =  0,  i = 0,1, … , n                            (11)                              

           x� 
 ≥ 0 ,  integer    i = 0,1, … , n;  k = 1, … , �                                   (12) 
 

Constraint (9) ensures that exactly k batches are produced during the periods 1 through k. Constraint 

(10) states that the total number of batches is a non decreasing function of k. Constraint (11) 
guarantees that the batches are exactly met. Constraints (9), (10) and (12) ensure that exactly one 
batch of a model is sequenced during a unit time-bucket. Note that the formulation of the sequencing 
phase of the problem is similar to the formulation in [6] for the bottleneck product rate variation 
problem. 



 
Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.55 

 
 
We denote Problem F* for the bottleneck product rate variation problem with batching with the 
objective function Fm and the constraints (9) to (12). 
 
3. Bottlenecks 
 
Establishment of bottlenecks is important to the optimization problem since the bottlenecks guaranty 
whether the optimal or feasible solution exists or not.  It is clear that there exists no even feasible 
solution below the lower bottleneck and every instance has optimal solution below the upper one.  
 

Let 5 be a bottleneck to the problem. 
 
Theorem 1. The lower bottleneck to the problem is (67(1 − 8̃:;<)):. 
 
Proof:   
 
A batch for some model i is sequenced at the first time-bucket. 
It holds min(67(1 − 8̃7)): ≤ 5. 

For any feasible solution,  min(67(1 − 8̃7)): ≤ 5. 

⟹ (67(1 − 8̃:;<)): ≤ 5. 
Thus, the lower bottleneck is (67(1 − 8̃:;<)):. 

 

Theorem 2. The upper bottleneck to the problem is (67 >1 − �
�?):. 

 
Proof:   
 

For 5 =  (67 >1 − �
�?):, @AB8̃7 + C

DE
√GH I 

=  JAB8̃7 + 1 − C
�K  

=  AB8̃7, for AB8̃7 being integer. 
If AB8̃7 is not an integer, 

@AB8̃7 + C
DE

√GH I  
= JAB8̃7 + 1 − C

�K 
≥ LAB8̃7M + 1, since AB8̃7 =  LAB8̃7M + (AB8̃7), where (AB8̃7) is the fractional part of AB8̃7. 
>  AB8̃7. 
Therefore, 

@AB8̃7 + C
DE

√GH I  ≥ AB8̃7. 

Again, OAB8̃7 − C
DE

√GH P  
=   QAB8̃7 − 1 + C

�R. 
=  AB8̃7, for AB8̃7 being integer. 

If AB8̃7 is not an integer, 

OAB8̃7 − C
DE

√GH P  
≤  SLAB8̃7MT, since (AB8̃7) ≤ 1 − C

� 

<  AB8̃7. 
 Therefore, 

OAB8̃7 − C
DE

√GH P  ≤ AB8̃7   
Now, 

∑ (@AB8̃7 + C
DE

√GH I − O(A� − 1)8̃7 − C
DE

√GH P)V
7��   

≥ ∑ AB8̃7
V
7�� − ∑ (A� − 1)8̃7

V
7��     

≥  AB − A� + 1. 
And 

∑ (OAB8̃7 − C
DE

√GH P − @(A� − 1)8̃7 + C
DE

√GH I)V
7��   



Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.56 
 
 
≤  ∑ AB8̃7

V
7�� − ∑ (A� − 1)8̃7

V
7��    

≤  AB − A� + 1.   
 

The bottleneck  (67 >1 − �
�?): is an upper bottleneck since it satisfies the Hall’s theorem [4]. 

 
Importance of upper bottleneck is that every instance has an optimal sequence when the given 
bottleneck is the upper bottleneck. However, it is not guaranteed for smaller value. The upper 
bottleneck for any instance with n = 1 is trivially 0. The lower bottleneck is important because a 
feasible sequence that exists for lower bottleneck is optimal. 
 
An optimizer always seeks instances that give rise to optimal sequence for smaller bottleneck. 
 
4. Small Bottleneck 
 
Every instance has optimal sequence when the given bottleneck is the upper bottleneck. However, it 
is not guaranteed for smaller value. A feasible solution with a minimum B is optimal. So, it is always 

interesting and important to seek small bottleneck.  
 
It has been established that there is no instance with a feasible sequence for the bottleneck 5 <
 (DE

W ):. 

 
Theorem 3  No instance with X ≥ 2 of the problem has a feasible sequence for 5 <  (DE

W ):.  

 
Proof: 
 
The bottleneck (67(1 − 8̃:;<)): implies 

1 − 8̃:;<  ≤  C
DE

√YH . 

For feasible sequence, Z3:([, \) ≤ ]3:([, \), where 

Z3:([, \) and ]3:([, \) are the earliest and the latest sequencing times, respectively. 

⟹ ^_ C
DE √`H

abE
 c 

d0�e C
DE √`H

f̃E
+ 1 

⟹ 1 − 8̃7  ≤ B
gE

√5H
 for all [. 

⟹ 1 − 8̃:7V  ≤ B
gE

√5H
  

⟹ ∑ 8̃h́
V
7��  ≤ B

gE
√5H

, 8̃h́ ≠  8̃:7V 

⟹ 8̃:;< ≤ ∑ 8̃h́
V
7��  ≤ B

gE
√5H

  

⟹ 1 − 8̃:;<  ≥ 1 −  B
gE

√5H
. 

 Then, 1 −  B
gE

√5H ≤ 1 − 
�
gE

√5H
 

⟹  DE
W ≤  √5H

. 

This shows that any instance with the bottleneck less than (gE
� ): does not yield any feasible sequence. 

 

For any feasible solution, (67|[kf̃E]0kf̃E|): ≤  (67|<�El0kf̃E|):, [ = 1, . . . , X, where [A8̃7] is the closest integer 

to A8̃7. It is observed that |[A8̃7] − A8̃7| =  C
m if � is even and |[A8̃7] − A8̃7| = �_C

m�   if �  is odd [1]. This 

shows that any instance, X ≥ 2, with even � of the problem has lower bottleneck (DE
m ):

and has lower 

bottleneck (DE
W ):

 for the instance, X ≥ 2, with odd �. 

For X ≥ 2, a standard instance (1, 2, 2B, . . . ,  270�), [ =  1, . . . , X, has optimal sequence with bottleneck 

less than (DE
m ):

[2]. 

 

Theorem 4  The instance (1, 2, 2B, . . . ,  270�), [ =  1, . . . , X, X ≥ 2 has an optimal sequence with 

5 <  (DE
m ):

. 

 



Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.57 
 
 
Proof: 
 

We consider the bottleneck 5 =  (67(C
m − C

m�)):  and assume that ([, \) be sequenced in the ideal 

position Om^_C
mabE

P.  
For this instance, 5 =  (67(mn_C_C

mn_C )):  <  (DE
m ):

 and 

Om^_C
mabE

P = 2V07(2\ − 1), [ = 1, . . . , X;  \ = 1, . . . , pq7. 

We show that the instance has a feasible sequence with this bottleneck. 

Consider, 
d0 C

DE √`H

f̃E
=  ^_mn_C_C

mn_C
mE_C
mn_C

  

=  2V07(2\ − 1) +  C_(m^_C)
mE   

≤ 2V07(2\ − 1)  

=  d0�emn_C_C
mn_C

mE_C
mn_C

+ 1  

=  ^_Cr C
DE √`H

abE
e�  

 

One can write Z3:([, \) 

≤ 2V07(2\ − 1)   
≤ ]3:([, \), since 2V07(2\ − 1) is an integer. 
Thus, the instance has a feasible sequence to the problem. 
Now, we show that ([, \) does not compete with (ś, t́ ) with [ ≠ ś and j ≠ t́. 
Assume that ([, \) and (ś, t́ ) be sequenced at the same position. 

⟹ Om^_C
mabE

P =  Omú_C
mabv́

P 
⟹ O(m^_C)(mn_C)

mE P =  O(mú_C)(mn_C)
mv́ P, for pq7 =  270�, [ = 1, . . . , X. 

⟹  Q(2\ − 1)2V07 − (2\ − 1)207R =  Q(2t́ − 1)2V0h́ − (2t́ − 1)20h́R . 
⟹  mú_C

mv́ =  Bẃ0�
Bv́   

Since both (2\ − 1) and (2t́ − 1) are odd, neither 27 divides (2\ − 1) nor 2h́  divides (2t́ − 1). 

This implies [ = ś and = t́ . 
Thus, the copies do not compete one another for the position. A feasible sequence of which the 
copies do not compete one another for the position is optimal. 

 
5. Conclusion 
 
Establishment of bottlenecks is important to the optimization problem since the bottlenecks guaranty 
whether the optimal or feasible solution exists or not.  It is clear that there exists no even feasible 
solution below the lower bottleneck and every instance has optimal solution below the upper one.  
 
The lower and the upper bottlenecks to the problem has been established to be (67(1 − 8̃:;<)): and 

(67(1 − C
�)):, respectively.  It has been investigated that the only instance with optimality for the 

bottleneck less than (DE
m ): is (1, 2, 2B, . . . ,  270�), [ =  1, . . . , X, X ≥ 2. Further, there exists no such 

instance for the bottleneck less than (DE
W ): . 

 
References 
 
[1]  N. Brauner, and Y. Crama, Discrete Applied Mathematics, 134 (2004), 25. 
[2]  N. Brauner, V. Jost and W. Kubiak, On symmetric Fraenkel’s and small deviations  conjecture,  
      Les Cahiers du Laboratoire Leibniz-IMAG, 54, Grenoble, France, 2004. 
[3]  T. N. Dhamala and S. R. Khadka, Iranian Journal of Optimization, 1, 3, (2009)266. 
[4]  S. R. Khadka  and T. N. Dhamala, Iranian Journal of Optimization, 3 (2010) 477. 
[5]  W. Kubiak and M. Yavuz, Manufacturing and Service Operations Management, 10, 3, (2008) 506. 



Shree Ram Khadka / BIBECHANA 8 (2012) 53-58 : BMHSS, p.58 
 
 
[6] G. Steiner and J. S. Yeomans, Management Science, 39, 6, (1993)728. 
[7]  M. Yavuz,  E. Akcali and S. Tufekci, International Journal of Production Research, 44, 15,   
     (2006)3061. 
[8]  M. Yavuz and S. Tufekci, International Journal of Production Research, 45, 17, (2007) 389