International Journal of Innovative Research in Science, Engineering and Technology
MenuISSN ONLINE(2319-8753)PRINT(2347-6710)
ISSN ONLINE(2319-8753)PRINT(2347-6710)
M.Vairamuthu1, S.Porselvi2, DR.A.N.Balaji3, J.Rajesh Babu4
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology
The n-job, m-machine flow shop scheduling problem is one of the most general job scheduling problems. This study deals with the multi objective optimization with the criteria of makespan minimization and minimization of total weighted flow time for the flow shop scheduling problem. The n-job mmachine problem is known to be NP hard problem, several meta heuristics have been applied so far in the literature. Artificial Immune Systems (AIS) are new intelligent problem solving techniques that are being used in scheduling problems. AIS can be defined as computational systems inspired by theoretical immunology, observed immune functions, principles and mechanisms in order to solve problems. In this research, a computational method based on clonal selection principle and affinity maturation mechanisms of the immune response is used. Matlab code was generated to use the algorithm for finding the optimal solution
Keywords |
| Artificial Immune Systems, flow shop scheduling problem. |
INTRODUCTION |
| In the quick changing market the production scheduling plays a key role in manufacturing systems of an enterprise wanting to maintain competitive position. Due to that competition, developing effective and efficient advanced scheduling technologies is extremely important. The so-called flow shop scheduling problem represents a class of widely studied cases based on ideas derived from production engineering, which currently modeled a lot of manufacturing systems, assembly lines, information service facilities. [1]Ventura et.al, presents linear programming formulations to find optimal starting and completion times for all the jobs in a given sequence considering various types of buffers and sub lots. Heuristic algorithms that blend linear programming with several pair wise interchange strategies are proposed to find near-optimal solutions for multiple-job, multiple machine lot-streaming flow shop scheduling problems. [2]Buthainah.et.al, Concluded that the Flow Shop problem is tackled using Genetic Algorithm based solution for Traveling Salesman Problem (GATSP) in order to obtain optimal machine sequencing schedule. It must be noted that critical path must always pass through machine with large processing times for all jobs. The proposed algorithm targeted the maximization of the total efficiency of the shop given only the job/machine processing time matrix for machine scheduling, with ease and flexibility of data handling and manipulation. [3]Mostafa.et.al, proposed a parallel genetic algorithm to solve the flow shop Scheduling Problem with regard to being NP-hard, the method of parallel genetic algorithm with the use of MATLAB 7.0 software has been developed and then the quality of the results with their time of calculation is compared with the results obtained from GA(Genetic Algorithm). [4]Pempera.et.al, gives that the flow shop scheduling problem with minimizing two criteria simultaneously: the total completion time (makespan) and the sum of tardiness of jobs. The problem is strongly NP-hard, since for each separate criterion the problem is strongly NP-hard. There is a number of heuristic algorithms to solve the flow shop problem with various single objectives, but usage of those heuristics to multi-criteria flow shop problems is rather limited. They are propose a new idea of the use of simulated annealing method to solve certain multi-criteria problem. Especially, define a new acceptance rules and the mechanism of moving the search in different regions of solution space by using so called drift. [5]Jolai.et.al, proposed a bi-objective no-wait two-stage flexible flow shop is considered. The objectives of minimizing makespan and maximum tardiness of jobs are taken into account. The aim is finding the best approximate of Pareto optimal solutions. Three meta-heuristic Paretobased multi-objective algorithms, called Classic weighted simulated annealing (CWSA), Normalized weighted simulated annealing (NWSA) and Fuzzy simulated annealing (FSA), were proposed. In order to evaluate the performance of these algorithms, 18 problems in different sizes were solved. |
| Any scheduling problem essentially depends upon three important factors namely, job transportation time which includes moving time and idle time, relative importance of a job over another job and breakdown machine time (non-time due any reason). These three factors were separately studied by many researchers. Miyazaki and Nishiyama (1980) had carried out an analysis for minimizing weighted mean flow time in flowshop scheduling. [6]Chandramouli proposed a heuristic approach for n-job, 3-machine flow-shop scheduling problem involving transportation time, breakdown time and weights of jobs. [7]Pandian and Rajendran improved and simplified the procedure for a constrained flow-shop problem for 3-jobs. [8]Baskar and Anthony gives that new procedure is proposed to obtain a scheduling sequence having optimal or near optimal makespan for a flowshop scheduling problems involving known break down time. |
PROBLEM DESCRIPTION |
| Multi-objective optimization is defined as the problem of finding a vector of decision variables that satisfies all constraints and simultaneously optimizes a vector function whose elements represent the objective functions. Mathematically, the multi-objective optimization problem can be formulized as follows: |
| Min f (x) = {f1(x), f2(x). . . fM(x)} xeXnx s.t. g(x) ≤ 0, h(x) = 0, |
| • The processing of each job has to be continuous. |
| • That is, once a job is started on the first machine, it must be processed through all machines without any pre- emption and interruption. |
| • Each machine can handle no more than one job at a time. Each job has to visit each machine exactly once. |
| • The release time of all jobs is zero. It means all jobs can be processed at time 0. |
| The first objective considered is to minimize the maximum completion time or makespan (Cmax). The corresponding fitness function is calculated as follows: |
| Cj = Completion time of job j Makespan = Cmax = max(Cj) min z1 = Cmax. |
| Another objective considered in this paper is to minimize mean weighted flow time. This objective is calculated as follows: |
| min z2 = wf |
| A mixed integer programming model is given using the following notation. |
| n Number of jobs to be scheduled |
| i Number of stages (i = 1, 2) |
| m Number of machines to be processed |
| K Number of machines in stage i |
| O (i, j) Available time for job j in stage i on machine k |
| xjl 1 if job j locates in position l of the job sequence. |
| 0 otherwise |
| yijk 1 if job i is processed on machine k. 0 otherwise |
| Bij start time of job j in stage i |
| Cij completion time of job j in stage i |
| Objective functions: |
| Min z = (z1, z2) |
| z1 = max(c2j) |
| z2 = max(wf) |
| Weighted method: |
| Min Z = w1 × f1(x) + w2 × f2(x), |
| w1 + w2 = 1, w1, w2 ≥ 0. |
PROPOSED METHOD |
| This section discusses the implementation of an artificial immune system (AIS) algorithm to solve the flow shop problem. |
Introduction to AIS |
| AIS is an adaptive system inspired by theoretical immunology and observed immune functions, principles, and models, which are applied to complex problem domains [11]. The principle of clonal selection and affinity maturation of the immune response system leads to the develop-ment of powerful computational tools to solve combinatorial optimization problems. The human immune system protects our body from the attack of foreign organisms, such as viruses and bacteria. These foreign organisms are called antigens. The molecules, called antibodies, that recognize the presence of an antigen will increase rapidly by cloning. This process is called the clonal selection principle [12]. |
 |
| The new cloned cells undergo mutations in order to improve the affinity of the antibodies, which results in antigen neutralization and elimination. These mutations experienced by the clones are proportional to their affinity to the antigen [13]. As a subsequent process to mutation, some percentage of the worst cells is eliminated and the same percentage of new antibodies is introduced into the system. This process is called receptor editing. This process is used to explore new search regions and also to escape from local optima [9]. The recognition and learning capabilities of the natural immune system provides properties such as robustness, dynamism, and adaptability to AIS-based algorithms [14]. These properties of the immune system attract researchers to apply it to other functional areas of engineering. The application of AIS is found in areas such as biological modeling, computer network security and virus detection, data mining, robotics, scheduling, clustering, and classification. |
The AIS algorithm steps |
| The general AIS algorithm consists of the following steps: |
| 1. Initialization: |
| – Create a random population of individuals p. |
| 2. Affinity evaluation: |
| – Measure the affinity of each individual in the population. |
| 3. Clonal selection: |
| – Select the n best individuals of the population based on the affinity measure. |
| 4. Clonal expansion: |
| – Clone the n best individuals of the population proportional to the rate of cloning. The clone is an identical copy of the original string. (The clone size is an increasing function of the affinity measure.) |
| 5. Affinity maturation: |
| – Mutate each clone to generate a matured antibody of the population. |
| – Preserve the improved individuals for the next generation. |
| 6. Metadynamics: |
| – Replace R individuals with low affinity value with randomly generated new ones. The lower affinity cells have higher probabilities of being replaced. This process introduces diversity into the population. |
| 7. Cycle: |
| – Repeat step 2 to step 6 until a certain stopping criteria is met. |
Numerical illustration |
| The AIS approach has three user-defined parameters, namely, population size (P), the number of iterations (n), and the amount of low-affinity antibodies to be replaced (R). The algorithm has been tested for the following ranges of parameters: |
| – P=20, 40, and 50 |
| – n=500, 1,000, 1,500, and 2,000 |
| – R=0, 10, and 20 |
| After running the algorithm, better solutions were obtained using the following parameters: |
| – Population size: 50 |
| – No. of iterations: 2,000 |
| – Amount of low-affinity antibodies to be replaced: 10 |
| The working of the AIS algorithm is explained through the following numerical illustration: |
| Step 1 Initialize a random population of strings up to the specified population (P). A string represents a possible solution. For example, the string 6 1 5 9 7 2 3 4 8 10 represents a layout sequence which is to be placed around the loop. |
| Step 2 Compute the objective function value (OFV) and affinity value for all solutions in the current population. The affinity value is calculated from the following equation: |
| Affinity =1/OFV |
| From the above equation, it is clear that lower the OFV, higher the affinity value. |
| Step 3 The selection of strings for cloning is done directly proportionally according to their affinity value. |
| Step 4 The rate of cloning is calculated by using the following relation: |
| Rate of cloning = |
 |
| Step 5b Pairwise mutation |
| Generate a random number between (1, N). |
| Let 1 and 6 be the randomly selected positions in the string. The pairwise mutation in the original string is performed by interchanging the locations of machines 1 and 6 in the original string, as shown below: |
 |
| After performing pairwise mutation, if the OFV of the mutated sequence is less than the original sequence, then the original sequence is replaced by the mutated sequence; otherwise, the original sequence is retained. After the cloning and mutation processes, reselect the improved strings from the temporary population C so as to maintain the original population size P. Now, the original population P is composed of improved strings. |
| Step 6 Then, R% of the solutions which has the highest OFV in the population is replaced with the same R % of randomly generated solutions. |
| Step 7 Repeat step 2 to step 6 for the required number of iterations. |
RESULTS AND DISCUSSION |
| The effectiveness of the proposed algorithm is demonstrated and a comparative analysis is presented in result and discussion section. The validity of the proposed model is tested for the problems taken from literature review. It shows the number of parts and the required machine sequence for each part for the test problems. The proposed algorithm is coded in the MATLAB R2009b. All tests were executed on a Intel core i3 processor under a Microsoft Windows 7 (32-bit) operating system. The artificial immune system (AIS) with the best sequence among the minimization of objective function value for the 10 type of problem is shown in table as follows: |
 |
CONCLUSION AND FUTURE WORK |
| The major contribution of this work has been the implementation of a best sequence depends upon minimization of the objective values of the flow shop scheduling problems. The artificial immune system (AIS)-based algorithm is implemented to solve the loop flexible flow shop problem and corresponding sequence are introduced. The performance of the proposed algorithm has been validated with the results available in the literature. The obtained results are found to be better than the results of the literature, which proved that AIS is a robust tool for solving flow shop problems. Also, AIS has been shown to provide significant improvements in the results for large sized problems. In future, the proposed procedure can be integrated with simulation software in order to study the operational difficulties and performance measures of the flexible flow shop scheduling problems. |
References |
|