# A Heuristic Approach ton×m Flow Shop Scheduling Problem in Which Processing Times Are Associated with Their Respective Probabilities with No-Idle Constraint

Authors: Deepak Gupta; Harminder Singh
Journal: ISRN Operations Research
 (2013)

---

## Abstract

This paper is an attempt to study generaln×m flow shop scheduling problem in which processing time of jobs is associated with probabilities under no-idle constraint. The objective of this paper is to develop a heuristic algorithm to n×m flowshop scheduling so that no machine remains idle during working for any given sequence of jobs. The proposed algorithm is simple, and easy to understand and provides an important tool in many practical situations for minimizing the expected hiring cost of the machines for a fixed sequence of job processing. A numerical illustration is also given to justify the proposed algorithm.


---

## Body

## 1. Introduction

In flow shop scheduling problems, the objective is to obtain a sequence of jobs which when processed on the machines will optimize some well-defined criteria. Every job will go on these machines in a fixed order of machines. The research into flow shop problems has drawn a great attention in the last decades with the aim to increase the effectiveness of industrial production. Johnson [1] gave procedure for finding the optimal schedule for n-jobs, two-machine flow-shop problem with minimization of the makespan (i.e., total elapsed time) as the objective. Ignall and Scharge [2] applied Branch and Bound technique for obtaining a sequence which minimizes the total flow time. In addition Adiri and Pohoryles [3] elucidated no-idle scheduling to minimize the sum of completion time. Rajendran and Chaudhuri [4] have given conditions to obtain a sequence which minimizes total flow time subject to minimum makespan in a two-stage flow shop problem. Szwarc [5], Yoshida and Hitomi [6], Anup [7], and so forth, derived the optimal algorithm for two/three or multistage flow shop problems taking into account the various constraints and criteria. Singh et al. [8] associated probabilities with processing time and setup time in their studies. Later, Gupta et al. [9] and Gupta and Singh [10] studied n×2 general flow shop problem to minimize rental cost under a predefined rental policy in which the probabilities have been associated with processing time on each machine and other scheduling problems by considering various parameters like transportation, idle/waiting operator, and so forth. Narain and Bagga [11–13] studied the flow shop problem with the objective being total rental cost. The total rental cost is minimized when idle time on all the machines is zero.Under the no-idle situation, machines work continuously without any break; that is, machines should not remain idle once they start processing the first job. The no-idle situation arises in real life world, when machines have to be hired to complete an assignment. Minimization of the total expected hiring cost of the machines would be the objective in these type of situations. The total expected hiring cost of the machines will be at a minimum when idle times on the machines are minimum. Hence, the total expected hiring cost of the machines will be minimum when the idle times of all the machines are zero and under no-idle situation each machine is to be hired for time that is equal to the sum of processing times of all the jobs on it. We are extending the study done by Gupta Deepak including the concept of no-idle scheduling by associating probabilities to the processing time of the jobs. The present paper is an attempt to study the nm general flow shop scheduling with an objective to develop a heuristic algorithm such that no machine remains idle.


## 2. Practical Situation

Many applied and experimental situations exist in our day-to-day working in factories and industrial production concerns, and so forth, in which different jobs are processed on various machines in a fixed order. For example, in a foundry workshop, the drawing of iron round, cutting, heating, forging, machining, finishing, and packing of finished articles have a fixed order of processing that cannot be altered. Various practical situations also occur in real life when one has got the assignments but does not have one’s own machine or does not have enough money or does not want to take risk of investing huge amount of money to purchase machine. Under such circumstances, the machine has to be taken on rent in order to complete the assignments. Hiring of machines is an affordable and quick solution in various production, which is presently constrained by the availability of limited funds due to the recent global economic recession. Hiring enables saving working capital, gives option for having the equipment, and allows upgradation to new technology.


## 3. Notations and Definitions

The various notations used throughout the paper are as follows:S: given fixed sequence of jobs,Mj: machine j, j=1,2,3,…,m,ai,j: processing time of ith job on machine Mj,pi,j: probability associated to the processing time ai,j,Ai,j: expected processing time of ith job on machine Mj,ti,j(S): completion time of ith job of sequence S on machine Mj,Ii,j(S): idle time of machine Mj for ith job in the sequence S,Ii,jI(S): idle time of machine Mj for ith job in the sequence S when machine Mj starts at latest time Lj.Definition 1.
Completion time ofith job on machine Mj is denoted by ti,j and is defined as
(1)ti,j=max(ti-1,j,ti,j-1)+ai,j×pi,jforj≥2,=max(ti-1,j,ti,j-1)+Ai,j,
where Ai,j= expected processing time of ith job on machine j.Definition 2.
Completion time ofith job on machine Mj when Mj starts processing jobs at time Lj is denoted by ti,jI and is defined as
(2)ti,ji=LJ∑K=1IAK,j=∑K=1IIk,j+∑K=1IAk,j,Ii,j=max(ti,j-1-ti-1,j,0)forj≥2.
Also,
(3)ti,ji=max(ti,j,ti-1,ji)+Ai,j.Theorem 3.
The time at which machineMr should be taken on rent (or starts processing jobs) to have zero idle time on Mr is
(4)Hr=max1≤k≤n{Yk},r=2,3,…,m
where
(5)Yk=t(k,r-1)l-∑i=1k-1pi,rXairfork>1,Yk=tk,r-Il-∑i=1k-1Air,Y1=t(1,r-1)l.Proof.
Proof is based on mathematical induction. It will be shown that if machineMr starts processing jobs at time Hr, then the idle time of Mr is zero asForr=2,H2=max1≤k≤n{Yk}LetYq=max1≤k≤n{Yk}Therefore,Yq≥Yk for k=1,2,3,…,n.Fork=1,Yq≥Y1Which impliesH2≥t(1,1)l or
(6)t(1,1)l≤H2.From (6), if machine M2 is taken on rent at time H2, then it will start processing the first job without waiting. Therefore, idle time of machine M2 for first job is zero when it starts processing jobs at time H2 asYq≥Ykfork=2,3,…,n.Yq±∑i=1k-1Ai,2≥Yk+∑i=1k-1Ai,2that isH2+∑i=1k-1Ai,2≥t(k,1)l-∑i=1k-1Ai,2+∑i=1k-1Ai,2that ist(k-1,2)l≥t(k,1)l or
(7)t(k,1)l≤t(k-1,2)lfork=2,3,…,n.Therefore,I(k,2)l=max[t(k,1)l-t(k-1,2)l,0].From (7),I(k,2)l=0fork=2,3,…,n.Therefore, the result holds forr=2.Let the result hold forr=5.Now we will also show that the result is also true forr=s+1.ButHs+1=max1≤k≤n{Yk}.LetYt=max1≤k≤n{Yk}.Therefore,Yt≥Y1, that is, Hs+1≥t(s,1)l(8)t(s,1)l≤Hs+1.From (8), if machine Ms+1 is taken on rent at time  Hs+1, then it will start processing the first job without waiting. Therefore, idle time of machine Ms+1 for the first job is zero when it starts processing jobs at time Hs+1.Fork=2,3,…,n.Yt≥Ykwhich impliesYt+∑i=1k-1Ai,s+1≥Yk+∑i=1k-1Ai,s+1Hs+1+∑i=1k-1A(i,s+1)≥t(k,s)l-∑i=1k-1Ai,s+1+∑i=1k-1Ai,s+1which impliest(k-1,s+1)l≥t(k,s)l(9)t(k,s)l≤t(k-1,s+1)lfork=2,3,…,n.Therefore,I(k,s+1)l=max[t(k,s)l-t(k-1,s+1)l,0]From (9),I(k,s+1)l=0 for k=2,3,…,n.Therefore, the result is true forr=s+1 also.Assumptions.
(1) No machine processes more than one job at a time.(2)
Preemption of jobs is not allowed.(3)
Machines never breakdown during the scheduling process.(4)
Each job is processed through each of the machines once and only once.(5)
All the jobs and the machines are available at the beginning of the processing.(6)
Jobs are independent of each other.


## 4. Algorithm

The algorithm given in this paper provides the procedure to determine the times at which machines should be hired so that the idle time becomes zero, minimizing total expected hiring cost under the given policy.Step 1.
Calculate the expected processing timeAi,j=ai,j×pi,j; for all i,j=1,2,3,…,m.Step 2.
For the fixed given sequenceS, prepare the in-out table for the machine pair (Mj,Mj+1), j=1,2,3,…,m-1 as two-machine flow shop sequence problem.Step 3.
ComputeKj+1 for the machine pair (Mj,Mj+1) by the formula
(10)Kj+1=tn,j+1-∑i=1nAi,j+1,j=1,2,3,…,m-1.Step 4.
Calculate latest timeLj  for the machine pair (Mj,Mj+1) by the formula
(11)Hj=Hj-1+Kj;j=3,4,5…m-1,H2=K2,H1=0.Step 5.
Prepare the in-out table for the machines with latest timesLj; the idle time is zero for all machines.


## 5. Fuzzy Logic Engine

The calculations have been done using C++ program by using different values of processing times and probabilities (Algorithm1). Based on the results, fuzzy logic engine has been formed in MATLAB fuzzy logic toolbox. The fuzzy logic rule base is based on the results generated from the C++ program. The membership function values and fuzzy rules are formed on the base of data generated from C++ program. Figure 1 shows the fuzzy logic system which consists of two inputs: processing time and probability and three output variables namely, H2, H3, and H4. Figure 2 illustrates the membership functions for input processing time. Figure 3 illustrates the membership functions for input probability. Figure 4 illustrates the membership functions for output H3. Figure 5 illustrates firing of the rule base.Algorithm 1:C++ program for given problem.
#include<stdio.h>
#include<conio.h>
// *************** variable declaration ***************//
static int job_machine[5][4]; //to store jobs time for machines
float job_prob[5][4];  // to tore jobs probability for machine
float exp_pro_time[5][4]; // to store expacted processing time
float m1m2[5][4],m2m3[5][4],m3m4[5][4];
float k2,k3,k4;
float h1,h2,h3,h4;
// ************** end variable declaration **************//
void get_job_machine() //function to get jobs time and probabiity for machine
{int i,j;/*
int arr[5][4]={10,40,5,20,25,30,20,40,20,20,20,10, 30,5,25,40,20,30,20,20};
float arr2[5][4]={0.2,0.1,0.2,0.4,0.2,0.1,0.2,0.1,0.1,0.3,0.2,0.3,0.3,0.4,0.2,0.1, 0.2,0.1,0.2,0.1,  };
for(i=0;i<5;i++) {  for(j=0;j<4;j++) { job_machine[i][j]=arr[i][j];  job_prob[i][j]=arr2[i][j];}}
*/printf(“∖nEnter 5 Jobs Time & Probability for 4 Machines: ");
for (i=0;i<5;i++ ){for(j=0;j<4;j++){printf(“∖n∖n Enter Job [ %d ]  Time for Machine [ %d ]:
",i+1,j+1);scanf(“%d”,&job_machine[i][j]);
printf(“∖n∖n Enter Job [ %d ]  Probability for Machine [ %d ]: ",i+1,j+1);
scanf(“%f",&job_prob[i][j]);}}}
// end of get_job_marchine function//
void put_job_machine()  //function to show jobs time and probabiity for machine
{int i,j;
printf(“∖n∖tMachine1∖tMachine2∖tMachine3∖tMachine4∖n");
printf(“∖nJobs∖tTime∖tProb.∖tTime∖tProb.∖tTime∖tProb.∖tTime∖tProb.");
for(i=0;i<5;i++)
{printf(“∖n∖n[ %d ]",i+1);
for(j=0;j<4;j++){printf(“∖t%d∖t%.1f",job_machine[i][j],job_prob[i][j]);}}}
// end of Put_job_marchine function//
void get_exp_pro_time() // function to calculatig expected processing time
{int i,j;for(i=0;i<5;i++)
{for(j=0;j<4;j++){exp_pro_time[i][j]=job_machine[i][j]*job_prob[i][j];}}}
// end of get_exp_pro_time function//
void put_exp_pro_time() // function to showing expected processing time
{int i,j;
printf(“∖n∖nExpected Proessing Time: -");
printf(“∖n∖nJobs∖tMachine1∖tMachine2∖tMachine3∖tMachine4∖n");for(i=0;i<5;i++)
{printf(“∖n∖n[ %d ]",i+1);for(j=0;j<4;j++)
{printf(“∖t∖t%.1f",exp_pro_time[i][j]);}}}
// end of Put_exp_pro_time function//
void get_in_out_table() // function to calculating In Out Table for maching
{int i;float p1,p2;// Machine m1-m2p1=0.0;p2=0.0;for(i=0;i<5;i++)
{m1m2[i][0]=p1;m1m2[i][1]=exp_pro_time[i][0]+p1;p1=m1m2[i][1];
if(p2>p1)m1m2[i][2]=p2;elsem1m2[i][2]=p1;
m1m2[i][3]=m1m2[i][2]+exp_pro_time[i][1];p2=m1m2[i][3];}
// Machine m2-m3p1=0.0;p2=0.0;for(i=0;i<5;i++)
{m2m3[i][0]=p1;m2m3[i][1]=exp_pro_time[i][1]+p1;
p1=m2m3[i][1];if(p2>p1)m2m3[i][2]=p2;
elsem2m3[i][2]=p1;m2m3[i][3]=m2m3[i][2]+exp_pro_time[i][2];
p2=m2m3[i][3];}
// Machine m3-m4p1=0.0;p2=0.0;for(i=0;i<5;i++)
{m3m4[i][0]=p1;m3m4[i][1]=exp_pro_time[i][2]+p1;
p1=m3m4[i][1];if(p2>p1)m3m4[i][2]=p2;
elsem3m4[i][2]=p1;m3m4[i][3]=m3m4[i][2]+exp_pro_time[i][3];
p2=m3m4[i][3];}}
// end of get_in_out_table function//
void put_in_out_table() // function to showing In Out Table for maching
{int i,j;
printf(“∖n∖nIn-Out Table: -");
printf(“∖n∖nJobs   M1-M2   M2-M3  M3-M4∖n");
for(i=0;i<5;i++)
{printf(“∖n∖n%d  ",i+1);for(j=0;j<4;j++)
{if(j==1∥ j==3)
printf(“-");else
printf(“");
printf(“%4.1f",m1m2[i][j]);if(j==3)
printf(“ %c",179);}
for(j=0;j<4;j++)
{if(j==1∥ j==3)
printf(“-");else
printf(“");
printf(“%4.1f",m2m3[i][j]);if(j==3)
printf(“ %c",179);}for(j=0;j<4;j++)
{if(j==1∥ j==3)
printf(“-");else
printf(“");
printf(“%4.1f",m3m4[i][j]);if(j==3)
printf(“ %c",179);}}}
// end of Put_in_out_table function//
void final()
{int i;float sum=0.0;for(i=0;i<5;i++)sum=sum+exp_pro_time[i][1];
k2=m1m2[4][3]-sum;sum=0.0;
for(i=0;i<5;i++)sum=sum+exp_pro_time[i][2];k3=m2m3[4][3]-sum;
sum=0;for(i=0;i<5;i++)sum=sum+exp_pro_time[i][3];k4=m3m4[4][3]-sum;
h1=0;h2=k2;h3=h2+k3;h4=h3+k4;
printf(“∖n∖nK2∖tK3∖tK4∖tH1∖tH2∖tH3∖tH4");
printf(“∖n∖n%.1f∖t%.1f∖t%.1f∖t%.1f∖t%.1f∖t%.1f∖t%.1f",k2,k3,k4,h1,h2,h3,h4);}
void main()
{clrscr();getch();get_job_machine();put_job_machine();getch();
get_exp_pro_time();put_exp_pro_time();getch();get_in_out_table();
put_in_out_table();getch();final();getch();}Figure 1Figure 2Figure 3Figure 4Figure 5


### 5.1. Surfaces

The control surface for outputH2 is shown in Figure 6. The control surface for output H3 is shown in Figure 7. The control surface for output H4 is shown in Figure 8.Figure 6Figure 7Figure 8


## 5.1. Surfaces

The control surface for outputH2 is shown in Figure 6. The control surface for output H3 is shown in Figure 7. The control surface for output H4 is shown in Figure 8.Figure 6Figure 7Figure 8


## 6. Numerical Illustration

Consider a 5-job, 4-machine sequencing problem whose processing times with their corresponding probabilities given in the Table1.Table 1
The machines with processing time and corresponding probabilities.
Jobsi
M
1
M
2
M
3
M
4
a
i
,
1
p
i
,
1
a
i
,
2
p
i
,
2
a
i
,
3
p
i
,
3
a
i
,
4
p
i
,
4
1
20
0.2
50
0.1
10
0.2
30
0.4
2
10
0.2
40
0.1
20
0.2
80
0.1
3
30
0.1
30
0.3
30
0.2
10
0.3
4
30
0.3
20
0.4
40
0.2
20
0.1
5
30
0.2
80
0.1
5
0.2
20
0.1Here, our objective is to obtain the latest time of the machines so that no machine remains idle.Expected processing times are given in Table2.Table 2
Expected processing times.
Jobsi
M
1
M
2
M
3
M
4
A
i,
1
A
i,
2
A
i,
3
A
i,
4
1
4
5
2
12
2
2
4
4
8
3
3
9
6
3
4
9
8
8
2
5
6
8
1
2For the pair(M1,M2), the in-out table is shown in Table 3 as
(12)K2=tn,2-∑i=15‍Ai,2=49-34=15.H2=K2=15 units and also we have H1=0.Table 3
The in-out table for machinesM1 and M2.
Jobs
M
1
M
2
A
i,
1
A
i,
2
1
0–4
4–9
2
4–6
9–13
3
6–9
13–22
4
9–18
33–41
5
18–24
41–49For the pair(M2,M3), the in-out table is shown in Table 4 as
(13)K3=t5,3-∑i=15‍Ai,3=35-21=14,H3=H2+K3=15+14=29.
For the pair (M3,M4) the in-out table is shown in Table 5 as
(14)K4=t5,4-∑i=15‍Ai,4=2,H4=H3+K4=29+2=31.
The in-out table for the machines with idle time zero is shown in Table 6.Table 4
The in-out table for machinesM2 and M3.
Jobsi
M
2
M
3
A
i
,
2
A
i
,
3
1
0–5
5–7
2
5–9
9–13
3
9–18
18–24
4
18–26
26–34
5
26–34
34-35Table 5
The in-out table for machinesM3 and M4.
Jobs
M
3
M
4
A
i
,
3
A
i
,
4
1
0–2
2–14
2
2–6
14–22
3
6–12
22–25
4
12–20
25–27
5
20-21
27–29Table 6
In-out table.
Jobs
M
1
M
2
M
3
M
4
A
i
,
1
A
i
,
2
A
i
,
3
A
i
,
4
1
0–4
15–20
29–31
31–43
2
4–6
20–24
31–35
43–51
3
6–9
24–33
35–41
51–54
4
9–18
33–41
41–49
54–56
5
18–24
41–49
49-50
56–58Hence, we conclude that no machine remains idle.


## 7. Conclusion

The proposed algorithm provides the latest time at which processing of jobs on second, thired, and so onmth machine must be started such that these machines work continuously without any break until the last job is completed on them. The first machine has no idle time and, hence, works continuously; that is, the proposed algorithm helps the decision makers in determining the best latest time at which machines should be hired for a given set of jobs so as to minimize the total expected hiring cost with no-idle constraint. The study may be extended by introducing concepts of independent setup time, transportation time, job block criteria, and nonavailability constraints of machines for a certain interval of time.



---

*Source: 948541-2013-09-11.xml*