Solving flow - shop scheduling problem to minimize total elapsed time using fuzzy approach

Job scheduling is concerned with the optimal allocation of scare resources with objective of optimizing one or several criteria. Job scheduling has been a fruitful area of research for many decades in which scheduling resolve both allocation of machines and order of processing. If the jobs are scheduled properly, not only the time is saved but also efficiency of system is increased. In real life situations, the processing times of jobs are not always exact due to incomplete knowledge or an uncertain environment which implies the existence of various external sources and types of uncertainty. Fuzzy set theory can be used to handle uncertainty inherent in actual scheduling problems. This paper pertains to solving job-shop scheduling problem in fuzzy environment which optimize the total elapsed time. The fuzziness, vagueness or uncertainty in processing time of jobs is presented by triangular fuzzy membership function. Job sequences are constructed with respect to algorithm of average high ranking method and branch and bound technique by fuzzy processing time. A numerical illustration is carried out to the test efficiency of the proposed approaches.

Introduction

Scheduling problems are common in our day to day life e.g., manufacturing plant, programs are to be run in a sequence at computer, Management, etc. Scheduling is a decision making process for optimally allocating resources. Efficient scheduling has become essential for manufacturing firms to survive in today's intensely competitive business environment. The study of scheduling problem has attracted researchers from various fields. Permutation flow shop sequencing problems (PFSPs) have long been a topic of interest for the researchers & Practitioners in this field. Recently the objective of minimizing total flow time, total completion time if all jobs are available for processing at the beginning, has attracted more attention from researchers. In flow shop scheduling, the objective is to obtain a sequence of jobs which when processed in a fixed order of machines, will optimize some well-defined criteria. The Johnson's algorithm has also been extended to 'm' machines flow shop under some structural conditions with minimizing make-span as an objective. However it is often difficult to apply these conventional approaches to real world production flow shop schedule. It has been shown that fuzzy approaches used to tackle uncertainties in complex flow shop scheduling are very effective. Scheduling problems can be modeled as fuzzy systems. Branch and Bound is an exact method usually used in scheduling problems to find optimal solutions. This method requires three components a lower bound, an upper bound and a branching strategy. In the following section we are giving to briefly describe the concept and approaches we have done for minimize total elapsed time using average high ranking method, branch and bound technique. Finally, we show a numerical example to illustrate our proposed method. The paper is concluded in section followed by the references.

Literature Review

Various researchers have done a lot of work in different directions. Johnson [1] has proposed a basic algorithm for n jobs, two machine scheduling problem with minimizing make-span. Lomnicki [2] introduced the concept of flow shop scheduling with the help of branch and bound method. V.S. Jadhav and Bajaj [3] focused on flow shop scheduling problem using fuzzy triangular membership function constrained optimization approach. Further the work was developed by Singh and Gupta [6] made an attempt to study the optimal two stage production schedule in which processing time and set up time both were associated with probabilities including job block criteria. Recently V.S. Jadhav and Bajaj (2013) discussed the fuzzy flow shop scheduling problem by taking the average high ranking concept. In our work, we confine ourselves to the flow shop problem with fuzzy processing time of jobs. The fuzzy processing times are described by triangular membership functions. The objective is to minimize the elapsed time using branch and bound technique. Because of the fuzziness of processing times, the obtained elapsed time is also a fuzzy number. Triangular membership functions are used to represent fuzzy processing times of jobs on the machines.

Preliminaries Fuzzy of Fuzzy Set Theory

The fuzzy set theory, which was Zadeh (1965), is related to such problems with uncertain and imprecise data [9] . In this paper we use triangle fuzzy number in our calculations. Triangular fuzzy number is a certain type of fuzzy set. A triangular fuzzy number can be denoted by a triplet as Fuzzy set theory has been used to model systems that are hard to define precisely. Zadeh (1965) stated that most of the early interest in fuzzy set theory pertained to representing uncertainty in human cognitive system. Uncertainty can be thought of in an epistemological sense as being the inverse of information. Information about a particular problem may be incomplete, imprecise, fragmentary, unreliable, vague or deficient in some other way. Fuzzy set theory is now applied to problems in engineering, business, medical and related health sciences and in natural sciences. A large number of deterministic scheduling algorithms have been proposed in last decades to deal with scheduling problems with various objectives and constraints. In real life situations, decisions to be made are often constrained by specific requirements. The decision making process gets increasingly more complicated with increments in the number of constraints. The real world is complex; complexity in the world generally arises from uncertainty. From this prospective the concept of fuzzy environment is introduced in the field of scheduling. For example, the processing times of jobs may be uncertain due to incomplete knowledge or uncertain environment which implies that there exist various external sources and types of uncertainty. Fuzzy sets and fuzzy logic can be used to tackle uncertainty inherent in actual scheduling problems. Here, we use triangular fuzzy membership function to represents the uncertainty involved in processing of jobs.

Definition

A fuzzy number ã on R is said to be a triangular fuzzy number or linear fuzzy number if its membership function

The above relation shows the triangular membership functions of a fuzzy number ,, P a b c   which represents processing time of a job on a machine. To deal with the same problem with fuzzy job processing times we rank the fuzzy processing times using their corresponding AHR (Average High Ranking Method) and then apply a branch and bound technique to find the optimal job sequence.

Average High Ranking

To find the optimal sequence, the expected processing time of the jobs are calculated by using Yager's (1981) [8] , [5] average high ranking formula.

Where a, b, c, is fuzzy processing time.

Basic Fuzzy Arithmetic Operations

The following are the four basic operations that can be performed on triangular fuzzy numbers:

Notations and Basic Assumptions of Flow Shop Scheduling Problem

We are given n -jobs to be processed on three machines flowshop scheduling problem and we have used the following notations and assumptions: Let, S = Sequence of jobs 1, 2, 3…n

Assumptions

The following are the common assumptions of flow shop scheduling problem  All the jobs are available for processing at time zero.

 Each job must be completed when started.  To make job on a second machine, it must be completed on the first machine.  Machines may be idle.  Setup times are known and are included in processing times.

Mathematical Formulation

Consider n jobs say . The mathematical model of the given problem can be stated as:

Our objective is to obtain the optimal schedule of all jobs which minimize the total elapsed time using branch and bound technique.

Algorithm

The following algorithm is proposed to find optimal sequence for flowshop scheduling problem using fuzzy processing time.

Step 1: For triangular fuzzy numbers using Average High Ranking (AHR) formula find expected processing times for machines A, B and C.

Step 2: Calculate a lower bound for the 3 machine makespan

are the processing times of the th i job on machines A, B and C

We evaluate L first for the n classes of permutations, i.e. for these starting with 1, 2, 3… n respectively having labeled the appropriate vertices of the scheduling tree by these values.

Step 4: Now explore the vertex with lowest label. Evaluate L for the ( 1 ) n  subclasses starting with this vertex and again concentrate on the lowest label vertex. Continuing this way, until we reach at the end of the tree represented by two single permutations, for which we evaluate the total work duration. Thus we get the optimal schedule of the jobs.

Step 5: Prepare in-out table for the optimal (best) sequence obtained in step 3 and get the minimum total elapsed time.

Numerical Example

The following numerical example is presented to show the effectiveness of the proposed approaches. Consider 5 jobs 3 machine flow shop problem where the fuzzy processing time of each the job at each machine is described by triangular fuzzy numbers as given in table 1. Our objective is to obtain an optimal schedule using branch and bound technique and finding the total elapsed time. Step 2:

Machines Jobs	Machine (M1)	Machine (M2)	Machine (M3)
1	(7,8,9)	(6.7,8)	(3,4,5)
2	(12,13,14)	(5,6,7)	(4,5,6)
3	(8,9,10)	(4,5,6)	(6,7,8)
4	(10,11,12)	(5,6,7)	(12,13,14)
5	(8,10,12)	(5,6,7)	(8,9,10)

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 1Close ×

Triangular Fuzzy Numbers

Open full-size image ↗

Original paper tableSource PDF · page 3 ↗

Calculate lower bounds using above formula LB (Jr) Hence the total elapsed time: (54, 62, 70).

Conclusion

We considered flowshop scheduling problem with fuzzy processing time and average high ranking formula. To minimize the total elapsed time, we have shown how to determine the optimal schedule according to the proposed algorithm approach. The optimal sequence of jobs processing for the problem is 4 -3 -5 -2 -1 with total elapsed time: (56, 62, 70). This model is very easy to understand and will help the decision maker in determining a best schedule for a given sets of jobs effectively to control total elapsed time and provide a solution of job schedule. This study may further be extended by using trapezoidal fuzzy numbers, by generalizing the number of machines by introducing the concepts of non availability constraints and machines processing the jobs.

Figures and tables from the paper

↗ Enlarge

Figure 1Close ×

A triangular fuzzy number A

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

Jobs	Machine (M1)	Machine (M2)	Machine (M3)
1	26/3	23/3	10/3
2	28/3	14/3	12//3
3	20/3	12/3	23/3
4	24/3	14/3	28/3
5	24/3	14/3	20/3

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 2Close ×

Processing Time of each job in Fuzzy

Open full-size image ↗

Original paper tableSource PDF · page 3 ↗

↗ Enlarge

Table 3Close ×

Lower Bound Values

Open full-size image ↗

Original paper figureSource PDF · page 4 ↗

Jobs	Machine 1	—	Machine 2	—	Machine 3	—
	In	Out	In	Out	In	Out
4	(0,0,0)	(10,11,12)	(10,11,12)	(15,17,19)	(15,17,19)	(27,30,35)
3	(10,11,12)	(18,20,22)	(18,20,22)	(22,25,28)	(27,30,35)	(33,37,41)
5	(18,20,22)	(26,30,34)	(26,30,34)	(31,36,41)	(33,37,41)	(43,49,55)
2	(26,30,34)	(38,43,48)	(38,43,48)	(43,49,55)	(43,49,55)	(51,58,65)
1	(38,43,48)	(45,51,57)	(45,51,57)	(51,58,65)	(51,58,65)	(54,62,70)

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 4Close ×

Minimum Expected Elapsed Time from Starting of the First Job to the Completion of the Last Job

Open full-size image ↗

Original paper tableSource PDF · page 4 ↗

1. Johnson SM. Optimal two and three stage production schedules with setup times include, Naval Research Logistics Quarterly. 1954; 1(1):61-68.
2. Brown APG, Lominicki ZA. Some applications of the branch and bound algorithm to the machine scheduling problem, Operational Research Quarterly. 1966; 17:173182.
3. Jadhav VS, Bajaj VH. Flow Shop Scheduling Problem Using Fuzzy Approach, International Journal of Agricultural and Statistical Sciences. 2012; 8(2):405413.
4. Chander Shekaran K, Rajendra Chanderi D. An efficient heuristic approach to the scheduling of jobs in a flow shop, European Journal of Operational Research, 1992, 318-325.
5. Jadhav VS, Bajaj VH. Fuzzy Average High Ranking Method for Solving Single Machine Scheduling Problem, International Journal of Statistika and Mathematika. 2013; 6(2):56-59.
6. Gupta D. Application of branch and bound technique for n x 3 flow shop scheduling in which processing time associated with their respective probabilities, Mathematical Modeling and Theory. 2011; 2(1):31-36.
7. Zimmermann HJ. Fuzzy Set Theory & its Application, Kluwer Academic Publisher, Dordrecht, 1996.
8. Yager RR. A procedure for ordering fuzzy subsets of the unit interval, Information Sciences. 1981; 24:143-161.
9. Zadeh LA. Fuzzy Sets, Information and Control. 1965; 8:338-353.