Flow Shop Scheduling Problem with Four Machines N-Job for Minimizing Makespan

Flow Shop Scheduling Problem with Four Machines N-Job for Minimizing Makespan

Sayali D. Choudhari

Research Scholar,

Pacific Academy of Higher Education and Research, University, Udaipur

Dr. Ritu Khanna,

Prof. Head Department of Mathematics, Pacific college of Engineering

Udaipur.

Abstract: In this paper we try to find algorithm for flow shop scheduling problem of 4 machines with n-jobs. Every job has to process on all machines which are arranged in series. After finishing of each job on first machine it will be transferred on second machine without delay with the help of transporting agent and so on. We also identify other factors which are responsible for scheduling like importance of jobs for arranging in sequence that is weightage assigned to each job, breakdown interval of machine, transportation time of jobs etc. By using Johnsons rule we try to explain the mathematical modelling, structure, suppositions, theorem with its statement and proof which is applicable to solve the numerical problem.

Key words: Flow shop scheduling, Johnsons rule, setup time of machines, breakdown interval, transporting time

I INTRODUCTION

At present period, every manufacturer has to concentrate on innovative ways of production agenda to get success in todays competition of

rketing area. For this one should use available resources fruitfully and plan a proper schedule so that the purpose of optimization of production can be achieved.

The theory of scheduling is basically focused on Johnsons result of two machines. The analysis of all flow shop scheduling problems can be done by using this result.

Proper planning of scheduling in production and marketing is effective in decreasing price, superior quality of product to satisfy the demands of consumer in the competition of market. Ali Allahverdi [3] described the problem of three machine flow shop scheduling with setup and processing time treated separate from each other only start and end time is known. Hence he introduced the concept of dominance relation which helps to reduce the size of dominating schedule. Ali Allahverdi [2] summarized the data of scheduling literature on models with setup times for more than 300 papers. Bo Chen et al.[4] considered a case of flow shop scheduling problem of three machines and n jobs. He has used O(nlogn) time heuristic which

shop scheduling problem of m-machines n jobs by considering the criterion of reduction of total working hours by using RAs and CDs algorithm and Gantt chart. According to Kenneth Baker[10] flow shop in ordered way is one of the most important cases of scheduling problem. For this there are two conditions

1. If the processing time of job i1 on one of the machine is smaller than the processing time of another job i2 on same machine then i1 always takes less time than i2 on other machines also.

2. If the processing time of job i1 is least on first machine then it is same for other jobs also. First condition helps us to find the job size.

Scheduling problems with m-machines and n-jobs by using Johnsons rule and different heuristics are solved by many authors in their research [5, 6, 7, 8, 13].

Let us prove lemma which is helpful in the proof of theorem stated below.

Lemma:- If

{ + + } { + + } then +

1 where

pi is the set up time of machine Pi & qi, is the set up time of machine Qi. ai , is the transportation time of item i from machine Pi to Qi,

By using the method of induction we can prove this lemma. II THEOREM FOR GETTING AN OPTIMAL SOLUTION

When the articles i-1, i, i+1 are arranged in sequence, the

optimal solution can be obtained so that

Min ( pi + Pi + ai + qi + Qi + bi + ri + Ri + ci , ai+1 + qi+1 + Qi+1 + bi+1 + ri+1 + Ri+1 + ci+1 + si+1 + Si+1 ) < (pi+1 + Pi+1 + ai+1 + qi+1 + Qi+1 +

bi+1 + ri+1 + Ri+1 + ci+1 , ai + qi + Qi + bi + ri + Ri +

ci + si + Si )

Let X and X denotes sequences of items.

X = {T1, T2, Ti1, Ti, Ti+1, Ti+2, Tn}

depends on Johnsons algorithm to minimize the total

X={T , T , T , T , T

, T , T }

completion time of the jobs. The completion time is 1.5 times the total time of the schedule. Ajaykumar Agarwal et.al[1]used heuristic approach for solving NP hard flow

1 2 i1 i

i+1

i+2 n

Let processing time of any item j on machine Y (ie. P, Q, R,

S) for sequences X, X is given by (Yj, Yj) Completion time

= {c +1 + +1 + +1 + +1 + +1 + +1 +

+ max( + , } + + } +

+1

+1,

1

of any item j on machine Y (ie. P, Q, R, S) for sequences X, X is given by (CYj, CYj)

Let (aj,aj,) be the transportation time of item j from machine P to Q, (bj,bj) be the transportation time of item j from machine Q to R, and (cj,cj) be the transportation time of item j from machine R to S.

Let pj, pj be the set up time of machine P, qj,qj be the set up time of machine Q, rj,rj be the set up time of machine R, sj,sj set up time of item on machines S resp. for sequences X and X.

The time required on machines Q, R & S for completion of jth item is given by

C = max ( + , 1 ) + + = +

+ +

C = max ( + , 1 ) + +

= + + +

+1+ +1

= {c +1 + +1 + +1 + +1 + +1 + +1 +

+1 + + 1 , + + + , 1 + + } +

+1+ +1

= {c +1 + +1 + +1 + +1 + +1 + +1 +

+1 + + 1 , max(c + , 1 ) + + +

+ + + + + , 1 + + } +

+1++1 = {c +1 + +1 + +1 + +1 + +1 +

+1 + +1 + +1 , c + + + + + + +

+ + , 1 + + } ++1++1

c+1 =max {c 1 + + + +1 + +1 + +1 +

+1 + +1 + +1 + +1 + +1 + + 1 +

+1 + +1, c 1 + + + + + +

+ + + + + + +1 +

+1 , 1 + + + +1 + +1 } —- (5) Similarly

C+1 = max {c1 + + + +1 + +1 +

+1 + +1 + +1 + +1 + +1 + +1 +

C = max ( + , 1 ) + + = max

+ 1 + +1 + +1, c1 +

+ + +

( + + + + + + + , 1 ) + +

+

+

+

'

+ +

) —- (1)

+ + +

We will choose the sequence X such that <

———- (2)

Max ( + + + + + + +

, 1 ) + +

< max( + + + + + + +

, 1) + +

But + + + + + + +

= + + + + + +

+1 + +1 , 1 + + + +1 + +1 }

———–(6)

Comparing sequences S & S,

We get c 1 = 1 & 1= 1,Yi = Yi+1 , Yi+1 = Yi where Y = P, Q, R, or S ———(7)

Also = +1 , +1 = , = +1 , +1 =

, = +1 , +1 =

Writing eq. 2 for j=i+1 & using eq. 7, we get

+

Max {c Pi1 + pi + Pi + p

i+1

+ Pi+1 + ai+1 + q

i+1 +

Also = , =

Therefore equation 2 will be true if 1

< 1

Qi+1 + bi+1 + ri+1 + Ri+1 + ci+ 1 + si+1 +

Si+1, c Pi1 + pi + Pi + ai + qi + Qi + bi + ri +

Ri + ci + si + Si + i+1 + Si+1 , cSi1 + si +

Proceeding in this way we get that inequality 2 is true if

Si + si+1 + Si+1 } < {c Pi1 + pi+1 + Pi+1 +

<

(j = i+1,i+2—–,m & i= 1,2,——m-1) —

———- (4)

pi + Pi + ai + qi + Qi + bi + ri + Ri + ci + si + Si, c Pi1 + pi+1 + Pi+1 + ai+1 + qi+1 + Qi+1 + bi+1 + ri+1 + Ri+1 + ci+1 + si+1 + Si+1 + si + Si, , c Si1 +

We now calculate the values of +1 & +1

+1 = (+1 ++1 , ) ++1++1

= (+1 + +1 + +1 + +1 + +1 + +1 +

si+1 + Si+1 + si + Si } ———(8)

Subtracting last term from both sides, we get

Max {c Pi1 + pi + Pi + pi+1 + Pi+1 + ai+1 + qi+1 + Qi+1 +

+1 + +1, ) + +1 + +1

bi+1

+ ri+1

+ Ri+1

+ ci+ 1

+ si+1

+ Si+1

, c P

i1

+ pi +

Pi + ai + qi + Qi + bi + ri + Ri + ci + si + Si +

si+1 + Si+1 } < Max{c Pi1 + pi+1 + Pi+1 + pi + Pi +

a + q + Q + b + r + R + c + s + S c P +

bi denotes transporting time required for transportation of the articles from Q to R, ci denotes transporting time

i i i i i

i i i

i, i1

required for transportation of the articles from R to S.

pi+1 + Pi+1 + ai+1 + qi+1 + Qi+1 + bi+1 + ri+1 + Ri+1 + ci+1 + si+1 + Si+1 + si + Si, }

Subtracting c Pi1 + pi + Pi + pi+1 + Pi+1 + ai + ai+1 + bi + bi+1 + ci + ci+ 1 +qi + Qi + qi+1 + Qi+1 + ri + Ri + ri+1 + Ri+1 +si + Si + si+1 + Si+1, From both sides, we get

Min ( + + + + + + + + , +1 +

+1 + +1 + +1 + +1 + +1 + +1 + +1 + +1 )

< (+1 + +1 + +1 + +1 + +1 + +1 +

+1 + +1 + +1 , + + + + + + +

+ )

Hence proved.

III FOUR MACHINES ALGORITHM

This theorem can be used in solving four machine problem of optimization for getting total elapsed time that is numerical problem solution can be obtained by applying above proved theorem. In this problem four machines with their setup time, processing time, transporting time, as well as waiting time are considered.

The problem can be given in tabular form as

follows:

In the given problem four machines namely P, Q, R, S are arranged in series such that the articles A1, A2, A3, —— An are transported by transporting agent from machine P to machine Q, machine Q to machine R, machine R to machine S in such a way that after delivering the articles to machine S without delay come back to machine P for transferring the next item. The problem is solved for finding the solution which is optimum for the given production system in minimum time period.

Let ai denotes transporting time that is the time required for transportation of the articles from P to Q,

For producing the articles machines required the set up time which is denoted by pi :- set up time of machine P, qi,

:- set up time of machine Q, ri, :- set up time of machine R,

si :- set up time of machine S

Let Ri is the time required for the transporting agent from S and P which is called as the returning time. When the machine P has completed the production of Ai-1 article and the transporting agent delivering this article to machine S come back to machine P but if the processing of last article by machine S is completed as it starts this processing instantly after giving out of previous article then machine P has to wait for the transporting agent if it didnt come back by that time.

Let Pi :- Processing time of machine P, Qi :- Processing time of machine Q, Ri :- Processing time of machine R, and Si:- Processing time of machine S,

Step I: Four machine problem reduced into three machine problem by introducing three assumed machines E, F and G with the service time Ei, Fi and Gi resp. Where,

Ei = pi + Pi + ai +qi + Qi + bi , Fi = ai +qi + Qi + bi + ri +Ri Gi = bi + ri +Qi + ci + si +Si

1) Min (pi + Pi + ai) Max (ai +qi + Qi) 2) Min (bi + ri

+Ri) Max (ai +qi +Qi) 3) Min (ci + si +Si) Max (ci +ri + Ri)

Step II:

Now this problem will be reduced into two machine problem by considering two fictitious machines H and K where Hi = Ei + Fi and Ki = Fi + Gi .

1. If min (H,K) = Hi then Hi = Hi – wti and Ki = Ki

2. If min (H,K) = Ki then Hi = Hi and KI = Ki + wti

Step III:

For getting the proper sequence the new problem is defined as follows and represented in the table form: Hi = Hi/ wti and Ki = Ki/ wti

Step I: Min (pi + Pi + ai)= 12 and Max (ai +qi + Qi)= 12

As discussed earlier about three fictitious machines E, F and G and their service times Ei, Fi, and Gi. The problem is reduced and it is given in the following table.

Step IV:

Considering the breakdown interval which is

Step II:Now this problem will be reduced into two machine problem by considering two fictitious machines H and K where Hi = Ei + Fi and Ki = Fi + Gi

already decided or known and the effect of this breakdown interval should be observed on all jobs. With the effect of this breakdown interval, the problem will be redefined as follows:

If the job is affected by the breakdown interval (u1-u2) then Pi = Pi + (u1-u2), Qi = Qi + (u1-u2), Ri = Ri + (u1-u2) , Si

= Si + (u1-u2)

If the job is not affected by the breakdown interval then Pi

= Pi , Qi = Qi , Ri = Ri and Si = Si

Step V: Applying steps I, II, III, IV the problem has been solved for getting the optimal sequence.

Every job has not equal importance hence all the jobs are assigned with weight according to their importance in the sequence of production and it is considered as one of the measure in the computation of total make-span. So the entirety weighted flow time is summation of product value of weighted value of the job and its flow time. Also the mean weighted flow time is the ratio of weighted flow time and sum of the values of weight of all the jobs.

Hence, Mean weighted flow time = weighted flow time/ sum of weights

The scheduling of all the course of action is in such a way that the minimum time should be required for getting the optimum solution or whole production For finding the algorithm the above information can be symbolized and represented in table for finding the sequence by using Johnsons rule of sequencing.

IV PROBLEM DESCRIPTION:

Let us consider the problem of four machines with set up time, processing time, a transporting time, weight of the jobs, arranged in series:

If min (H,K) = Hi then Hi = Hi – wti and Ki = Ki & if min (H,K) = Ki then Hi = Hi and KI = Ki + wti

Step III: The ratio of weights with Hi and Ki is taken so that we can decide the sequence of jobs according to Johnsons rule.

By Johnsons rule the optimal sequence obtained for above reduced problem is 4, 2, 3, 5, 1. Then the time required for total processing of articles by using above scheduling sequence i.e minimum time for entire production can be calculated by considering the time required by the transporting agent when it returns back to machine M1 to load the next article and also the time when it reaches to machine M2 for unloading of an article.

Step IV:

Effect of breakdown interval (36, 44):

The effect of breakdown interval is on jobs Pi1 and on Qi5, Ri2, Si4 hence the original problem is converted into new problem. As mentioned above in step IV we redefine the problem by considering the effect of breakdown interval

For finding the sequence and getting the optimal solution repeating the same procedure of step 1, 2, 3

(Note: two digits in one box of every column are two digit numbers ex.1 &4 means 14 and so on).

Repeating the same procedure of step 1, 2, 3 for finding the sequence and getting the optimal solution.By Johnsons rule the optimal sequence obtained for above reduced problem is 4, 2, 3, 5, 1.

(Note: two digits in one box of every column are two digit numbers ex.1 &4 means 14 and so on).

Minimum weighted flow time (MWFT)

= (50*5) + (62- 9) *4 + (72-17)*3 +(84-24)*2 + (95- 34)*2122 / 5+4+3+2+2

= 54 hours

1. CONCLUSION:

   From above table it is shown that the time gets reduced for total production by using the sequence obtained

   with the help of Johnsons rule. The total elapsed time for the complete process is 95 hrs and minimum weighted flow time is 54 hrs.

   In this paper setup time and processing time both are treated separately. Also effect of break down interval is calculated which helps to get proper schedule and reduce the total time span also. One can prove the theorem for less than four machines also and solve the problem by using Johnsons rule. If the number of machines are less in number then the makespan gets decreased as well as minimum weighted flow time also gets reduced.

2. REFERENCES:

1. Ajaykumar Agarwal and Rajan Garg Advanced modelistic approach of flow shop scheduling problem for 10jobs , 10 machines by heuristics models using makespan criterion , International journal of engineering trends and technology(IJETT), Vol.4 Issue 5- May 2013,ISSN:2231- 5381 pp.1742-1748.

2. Ali Allahverdi, C.T. Ng b, T.C.E. Cheng b, Mikhail Y. Kovalyo A survey of scheduling problem with setup time or costs (European journal of operational research).

3. Ali Allahverdi Three machine flow shop scheduling problem to minimize total completion time with bounded setup and processing times Decision making in manufacturing and services, Vol 1 2007,No.1-2 pp.5-23.

4. Bo Chen, Celia A. Glass and Chris N. Potts, Vitaly A. Strusevich A new heuristic for three machine flow shop scheduling, Operations Research, Vol.44,No.6, Nov.Dec.1994.

5. Deepak gupta,Payal Singla,Shashi Bala Constrained n-job, 3-machine flow shop scheduling problem with transportation time IJRAES, Vol.2 Issue2,Feb(2012), ISSN 2249-3905.

6. Operations scheduling and sequencing, David A. Collier,

   James R. Evans, chapter 14

7. Geleta Tadele Mohammed New Algorithm for N-jobs on M-machine Flow Shop Scheduling Problems Applied and Computational Mathematics, Volume 5, Issue 1 , February 2016, pp1-9.

8. Herbert G. Campbell, Richard A. Dudek and Milton L. Smith A heuristic algorithm for the n job, m machine sequencing problem Hanaoeuent Science viri. it, no. 10,

   June, 1970, pp 630-637

9. Ibrahim M. Alharkan Algorithms for sequencing and scheduling, chapter 1,2 Industrial Engineering Department, King Saud University, Riyadh, Saudi Arabia.

10. K:- 22. Kenneth R. Baker and Dan Trietsch Principles of sequencing and scheduling , Chapter 1,2,3,10,13, A John Wiley & Sons, INC. Publication 2009.

11. Qazi Shoeb Ahmad, M. H. Khan Constrained Flow-Shop Scheduling Problem with m Machines Journal of Multidisciplinary Engineering Science and Technology (JMEST) ISSN: 3159-0040 Vol. 2 Issue 2, February 2015

12. R.L.Graham E.L.Lawler, J.K.Lenstra and A.H.G.Reenoy Kan. Optimization and approximation in deterministic sequencing and scheduling a survey Annals pp 287-326

13. Dr. Richa Mehrotra Optimization in scheduling problems thesis (March 2012)

14. Vladimír Modrák, R. Sudhakara pandian Flow shop scheduling algorithm to minimize completion time for n-jobs m-machines problem, Technical Gazette 17, 3(2010), ISSN 1330-3651, pp 273-278