# Multi-objective optimization of parallel machine scheduling using Fuzzy Logic and simulated annealing.

NotationSPT--Shortest Processing time

LPT--Longest Processing time

EDD--Earliest Due Date

WSPT--Weighted Shortest Processing time

WLPT--Weighted Longest Processing time

GA--Genetic Algorithm

SA--Simulated Annealing

Introduction

The case of identical jobs within a batch is common in manufacturing systems, where products or jobs have identical processing requirements. Individual products may be subjected to different constraints, while all units of the product require equal processing times on the same machine [5]. Research in identical Parallel Machine Scheduling problems has predominantly been concerned with minimization of make span or total completion time [1]. Many of the researchers applied Genetic algorithms to solve the scheduling problems. Hybrid operation methods capable of providing a better solution in less time was achieved through the combination of Genetic algorithms and other evolutionary algorithms such as Fuzzy logic, Mimetic algorithms etc. The key feature of these evolutionary algorithms is to use available knowledge about the problem and have been found most successful approximation techniques for Non-Polynomial optimization problems.

Parallel machine scheduling is used to schedule jobs on a series of same function machines in order to achieve certain objective functions. The complexity usually grows with the number of machines, making the problem intractable. This problem, like all deterministic scheduling problems belongs to wide class of combinatorial optimization problems, which are known to be NP-hard [4].

This research effort proposes two different approaches to solve the Parallel Machine Scheduling Problem with multi objective optimization. Section 2 of this paper presents the literature reviewed on Fuzzy logic and Simulated Annealing. Section 3 presents the mathematical model and discusses the Fuzzy Logic approach. Section 4 discusses the Simulated Annealing approach. Section 5 presents the experimental results. Section 6 gives the conclusion and future directions of research.

Literature Review

Considerable research has already been conducted in the field of Parallel Machine scheduling. In the subsequent sub sections a brief survey of the literature on multi objective scheduling, Application of Fuzzy logic and Simulated Annealing are presented.

Multi objective scheduling

In the literature, different approaches have been found considering multi objective scheduling problems in [2] and [3]. The main approaches found are as follows:

* Simultaneous method aims to generate the complete Pareto set or to approximate a set of efficient solutions.

* Weighting objectives method creates a weighted linear combination of the objectives to obtain a single function, which can be solved using any single optimization method.

* Hierarchical optimization method allows the decision maker to rank the objectives in a descending order of importance. Each objective function is then minimized individually subject to a constraint that does not allow the minimum for the new function to exceed a prescribed fraction of a minimum of the previous function.

* Goal Programming method takes the objectives into constraints which express satisfying goals. The aim is to find a solution which provides good values of predefined goals for each objective.

* Measuring the relative goodness of the selected solution by comparing it with another solution in the feasible region.

K. Raja et al presented that conventional methods are not efficient in handling multi objective functions and GA technique had been applied for generating multiple schedules with multiple objectives. Fuzzy logic is then applied to select the best optimal schedule satisfying the multiple objectives.

Fuzzy logic

In 1965, L.A. Zadeh published his famous paper "Fuzzy Sets" in Instrumentation and Control providing a new mathematical tool which enables us to describe and handle vague or ambiguous notions. The main idea of fuzzy set theory is quite intuitive and natural; instead of determining the exact boundaries as in an ordinary set, a fuzzy set allows no sharply defined boundaries because of generalization of a characteristic function to a membership function. Many researchers, especially those in positions to develop models of physical process, understand that there is lack of complete information in solving problems as presented by Nikunja K Swain [10]. Some of the information about a particular problem might be judgmental, rather than hard quantitative information.

Although there is limited use of fuzzy logic approach in scheduling field, some of the results are promising and fruitful [1] [13].

Simulated Annealing

Simulated Annealing (SA) is based on the analogy to the physical process of cooling and recrystallization of metals. SA has received a considerable attention in the recent past and has been widely used to solve difficult combinatorial optimization problems. SA works by means of searching and evaluating set feasible solutions, reducing the possibility of finding a solution that might turnout to be a local optimum. This means it avoids converging to local optimum solutions at early stages of the search. This is obtained allowing evaluating or exploring solutions in a neighborhood which bears a lower quality than the previously evaluated, based upon a probability to accept those solutions. Introduced by Kirkpatrick et al. (1983) and Cerny (1985), SA has been applied successfully to solve a variety of problems.

Problem description

The problem is to schedule all the jobs such that the make span, total tardiness and total earliness are minimized.

Data of the Problem

Number of identical machines: 3

Number of jobs: 10

Working hours / day: 8

Notations;

Job--[J.sub.j]

Processing time--[P.sub.j]

Due date--[d.sub.j]

Completion time--[C.sub.j]

The data of the problem is summarized in Table 1

Earliness of the job [J.sub.j], [E.sub.j] = Max.{0, ([d.sub.j] - [C.sub.j])}

Tardiness of the job [J.sub.j], [T.sub.j] = Max.{0, ([C.sub.j] - [d.sub.j])}

The fitness function considered in this study is the combined objective function (COF) and is given by

COF = [W.sub.m](maximum make span) + [W.sub.c] (total earliness) + [W.sub.t] (total Tardiness)

Weight age given for make span is 0.4 and for tardiness and earliness 0.3 each.

Fuzzy logic approach

The basic elements of fuzzy logic system are;

[ILLUSTRATION OMITTED]

Input data are most often crisp values. The task of the fuzzifier is to map crisp numbers into fuzzy sets. Models based on fuzzy logic consist of "IF--THEN "rules. The rule base is formed with the assistance of human experts. The inference engine of the fuzzy logic maps fuzzy sets onto fuzzy sets. A large number of different inferential procedures are found and in MATLAB software minimum inference is used. During Defuzzification one value is chosen for the output variable. The most commonly used defuzzification method is centroid method, and the same method is used in MATLAB software.

System modeling, membership functions and rule base are integral parts of a fuzzy logic system. A typical system model along with its membership functions and rule base for the present problem are shown below.

[FIGURE 2 OMITTED]

[ILLUSTRATION OMITTED]

Some of the best sequences obtained from the fuzzy logic are

Sequence 1: 6-4-1-8-0-9-5-3-2-7

Sequence 2: 6-4-1-8-9-0-5-3-2-7

Sequence 3: 6-4-1-0-8-9-5-3-2-7

Out of these sequences, Sequence 1 and Sequences 2 yields the same result and found to be the optimum schedule.

Simulated Annealing approach

SA is local search algorithm. In a simple local search algorithm, an initial solution is chosen at random and then a neighboring solution is generated based on some mechanism. If the neighboring solution is better than the current solution it replace the current solution, otherwise the current solution is retained. The process is repeated until no improving neighbor is found for the current solution. The probability of accepting a non improving solution is calculated using exp {([C.sub.max] - [C'.sub.max])/T}, where [C.sub.max] is the objective value of the current solution and C'max is the objective value of its neighboring solution and T is the control parameter which denotes the temperature analogous to physical temperature. A cooling rate, r, is used to reduce the annealing process. The initial value of the T is set large enough such that almost all the transitions are accepted in the initial stages. This ensures that the algorithm is not trapped in a local optimum during early stages. The initial value of T is set such that the expression exp{[DELTA][C.sub.max]/T}=1, where [DELTA][C.sub.max]= [C.sub.max] (best) - [C.sub.max](worst). Typical cooling rate values used in the literature lie between 0.88 and 0.99.

The jobs are arranged in a random sequence to obtain an initial solution. Jobs are swapped in order to obtain a neighboring solution.

The Pseudo-code for the SA approach is shown below;

(1) Set T = 100; r = 0.95

(2) Generate initial solution:

a. Sequence the jobs randomly

b. Determine the objective for the initial solution [C.sub.max].

(3) Generate neighboring solution by swapping any two jobs in the initial sequence and then calculate [C'.sub.max].

(4) If [C'.sub.max] < [C.sub.max] Current solution = neighboring solution and [C.sub.max] = [C'.sub.max]

(5) n=n+1; repeat 3 to 4 until n = N

(6) Repeat the steps 3 to 5 until stopping criteria is true.

Results and Discussion

Sequences obtained by various methods are summarized below.

It is found from the above table that in the Simulated Annealing approach all the parameters such as total earliness (8583minutes), total tardiness (7714minutes) and the combined objective function(13728) were minimized. This method reduces the chance of converging at local optimum values. In conventional methods only the Earliest Due Date method gives the lowest values COF and total tardiness. The Largest Processing time method gives the lowest value of total earliness.. While the Fuzzy logic approach reduces the number of tardy jobs. For this particular problem there is only one tardy job in the schedule generated by fuzzy logic method. The other methods which are having only one tardy job are the Shortest Processing time method and the Largest Processing time method.

Conclusion

A Fuzzy logic technique was applied to Parallel Machine Scheduling problem. Few approximate schedules were obtained and they were compared. The procedure adopted for this technique is simpler when compared to other hybrid or heuristics. The simulated annealing approach is also applied to the same problem. The schedule obtained by the SA method gives lowest value of COF. It is found to be one of the easiest and better methods for simple scheduling problems and can be extended to complex problems also.

References

[1] Bilkay.O, Anlagan.O and KilicS.E," Job Shop Scheduling using Fuzzy Logic", International Journal of Advanced Manufacturing Technology(2004) 23:606-619

[2] Bo Chen, Handbook of Scheduling, CRC Press (2004) (9-175-9-180)

[3] Gyula Kulscar and Fernc Erdelyi "A New approach to solve Multi Objective Scheduling and Rescheduling Tasks" International Journal of Computational Intelligence Research. Vol2,No:4(2007) pp 343-351

[4] Jeng.A.A.K and Lin,B.M.T." A note on Parallel Machine Scheduling with deteriorating jobs",Journal of Operational Research Society(2007)58:824-826.

[5] Jones. A and Rabelo. L (1998), "Survey of Job shop scheduling Techniques", NISTIR, National Institute of Standards and Technology, Gaithersburg, MD

[6] Manjeshwar. P, Damodaran, P.,. Srihari. K (2009). Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing. Robotics and Computer-Integrated Manufacturing, 25, 667-679.

[7] Mare Sevaux and Kenneth Sorensen," VNS/TS for Parallel Machine Scheduling Problem", MEC-VNS: 18th Mini Euro Conference on VNS, 2005

[8] Matlab6.5 Fuzzy logic Tool Box Help, The Mathworks Inc. 2002

[9] Michele Pfund, John W.Flower and Jatinder Gupta," A survey of Algorithms for Single and Multi-objective Unrelated Parallel Machine Deterministic Scheduling Problems", Journal of Chinese Institute of Industrial Engineers,Vol.21 No.3,pp 230-241(2004)

[10] Nikunja K Swain. "A Survey of Application of Fuzzy logic in Intelligent Transportation systems and Rural ITS", IEEE transaction (0-4244-01690/06)2006: p 85-90.

[11] Pradhan.S and Lam,S.S.Y. "Minimizing make span during environmental stress screening using a Genetic Algorithm and an Ant Colony Optimization", International journal of Adv. Manufacturing Technology(2007)32:571-577

[12] Raja.K, Saravanan.R, and Selladurai.V, "Multi objective optimization of Parallel Machine Scheduling using Genetic Algorithm and Fuzzy logic", Institute of Engineers (I) journal--PR Vol.87 September 2006;p 26-31

[13] Samir Allet, " Handling flexibility in a generalized job shop with a fuzzy approach", European Journal of Operations Research 147(2003) 312-333.

[14] Stefan Chanas, Adam Kasperski," On two single machine scheduling problems with fuzzy processing times and fuzzy due dates". European Journal of Operational Research 147 (2003) 281-296

[15] Yuan.J.J,Cheng.T.C.E and C.T.Ng "NP--hardness of the single variable resource scheduling problem to minimize the total weighted completion time", European Journal of Operations Research 178(2007):631-633

(1) A. Muralidhar and (2) T. Alwarsamy

(1) Department of Mechanical Engineering, Thanthai Periyar Government Institute of Technology, Vellore-632002 (India) E-mail: amdhar1963@yahoo.co.in

(2) Department of Mechanical Engineering, Government College of Technology, Coimbatore (India)

Table 1: Data of the Problem. Job Number Processing Time Due date Batch Minutes Days quantity 0 2 11 218 1 1 07 112 2 7 12 711 3 6 13 655 4 4 03 419 5 3 12 354 6 1 03 174 7 9 07 910 8 2 08 076 9 1 10 249 Table 2: Fuzzy Associative Memory (FAM) Table: (Rule Base). Due date Low Medium High Processing Low First First Middle Low Batch Time Medium First Middle Last Medium Size High First Last Last High Table 3 Total Method Sequence Earliness Total Tardiness COF SPT 1-8-6-9-0-5-4-3-2-7 84531 10878 37006 LPT 7-2-3-4-5-0-9-6-8-1 7626 64137 29912 EDD 4-6-1-7-8-9-0-2-5-3 24712 2310 16492 WSPT 1-8-9-0-6-5-3-2-4-7 87087 19323 40307 WLPT 7-4-2-3-5-6-0-9-8-1 54946 4327 26165 SA 4-6-7-1-2-9-0-8-5-3 8583 7714 13278 Fuzzy 6-4-1-8-9-0-5-3-2-7 78078 10878 35070

Printer friendly Cite/link Email Feedback | |

Author: | Muralidhar, A.; Alwarsamy, T. |
---|---|

Publication: | International Journal of Applied Engineering Research |

Article Type: | Report |

Date: | Nov 1, 2009 |

Words: | 2256 |

Previous Article: | Tool wear in cutting of Metal Matrix Composites. |

Next Article: | Experimental analysis of oxygen stripping from feed water in a two stage jet cum tray type deaerator. |

Topics: |