ISSN: 2168-9679
Journal of Applied & Computational Mathematics
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

Applying an Intelligent Dynamic Genetic Algorithm for Solving a Multi-Objective Flexible Job Shop Scheduling Problem with Maintenance Considerations

Abbasian M1, Nosratabadi HE2 and Fazlollahtabar H3*
1Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran
2Department of Information Technology Management, Science and Research Branch, Islamic Azad University, Tehran, Iran
3Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
Corresponding Author : Fazlollahtabar H
Faculty of Industrial Engineering
Iran University of Science and Technology, Tehran, Iran
Tel: +98 21 77240540-50
Received March 16 , 2015; Accepted June 10, 2015 ;Published June 17, 2015
Citation: Abbasian M, Nosratabadi HE, Fazlollahtabar H (2015) Applying an Intelligent Dynamic Genetic Algorithm for Solving a Multi-Objective Flexible Job Shop Scheduling Problem with Maintenance Considerations. J Appl Computat Math 4: 227. doi:10.4172/2168-9679.1000227
Copyright: © 2015 Abbasian M, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Applied & Computational Mathematics


In this paper, a multi-objective flexible dynamic job shop scheduling problem (MO-FDJSPM) with maintenance constraint is studied. The objectives of the scheduling are maximizing the completion time, mean job rotation time and mean components' tardiness. Also, in order to adapt with the internal disruptions of the manufacturing system, such as breakdown of existing machines, we consider the machines availability (so called maintenance) as a constraint. The multi-objective mathematical model is formulated and a genetic algorithm (GA) with dynamic bidimensional chromosomes along with a heuristic algorithm to handle maintenance sub-problem is developed as solution approach. In proposed algorithm, since the control parameters change intelligently and dynamically during implementation and optimization process, the early convergence and trapping in local optimum are reduced leading
to performance improvement. The performance of the proposed approach is evaluated with respect to convergence speed and solutions quality. The results of computations verify and confirm both two evaluation criteria.

Flexible dynamic jobshop; Multi-objective scheduling; Maintenance; Genetic algorithm (GA)
Many researchers have worked out on multi-objective scheduling problem in manufacturing systems. The objectives were mostly concentrated on resource allocation, optimal job rotation and accurate delivery. Generally, machines' availability includes two statuses namely, random (such as damage or breakdown of machines) and definite (such as preemptive maintenance, fundamental repairs and pre-scheduling) [1]. MO-FDJSPM problem considers maintenance constraints being an optimization problem in discrete space. Due to being non-convex and non-linear, solving this problem leads to several local optimal [2]. Reviewing the literature points out that for solving scheduling problem meta-heuristic approaches are being extensively applied. Among those methods, GA has been found to be better in performance than other methods. Studies indicated that one of the disadvantageous of classic GA is parameter convergence property [3]. GA converges after some replications towards obtaining optimal solution and/or near-solution. But there are relatively noticeable variety in how utilizing parameters, type of parameters, choose mechanism, how create initial population, how select parents and etc., leading different configurations of GA in various works.
The objective of this paper is modeling and proposing an effective solution approach for handling a multi-objective flexible dynamic job shop scheduling problem considering maintenance constraint. The problem includes dynamism in production because of jobs arrival in a non-zero time as well as flexible of operation and flexibility resulted from parallel machines and also being multi-objective where maintenance constraint is noted. Given this fact that MO-FDJSPM considering maintenance constraint always trap in several local optimal and the GA's premature convergence, in our work, a genetic algorithm is developed having control parameters change dynamically during algorithm's implementation and optimization process. This way, the premature convergence and trapping into local optimal points are reduced.
The remainder of our work is organized as follows. In Section 2, the related literature is reviewed. The proposed problem is defined and formulated in Section 3. The solution approach is comprehensively developed and explained in Section 4. A numerical example is fully illustrated in Section 5 to point out all aspects of the proposed model and the solution methodology associated with validity testing. The experimental results are discussed and justified in Section 6. We conclude in Section 7.
Literature Review
Machines' availability
Generally, the constraint of machines' availability in production systems divided into two classifications called definite and indefinite availability. In indefinite availability, the lack of availability period is considered to be flexible in being determined during scheduling process. Of course, maintenance activity should be worked out in certain time windows [4]. Scheduling problem given constraint of availability to machines was introduced by Schmidt in 1984 for the first time. In 1989, Adiri and et al. [5] showed that scheduling problem of single-machine is NP-hard problem. Then Schmidt [6], considering availability constraint to machines, developed single-machine, parallel machines and flow shop scheduling problems.
In 2002, Xie and Wang [7] presented scheduling problem of two stages flexible flow shop considering parallel machines and considering availability constraint to machines and production regime of R type. Cheng and Liu [8] in 2003 presented scheduling problem of flow shop given no-wait job and constraint on each machines. In 2005, Kubzin and Strusevich presented scheduling problem of two-machine flow shop given no-wait job and apply constraint on each machine. Xie and Wang [9] presented scheduling problem of two stage flow shop with parallel machines given availability constraint on machines. In 2006, Lee and Wu [10] expressed scheduling problem of single-machine given the effect of learning and availability constraint on machines.
Zribi and Kamel in 2007 presented scheduling problem of jobshop with multi-machines and the presence of availability constraint on machines. They were expressed a little researches about scheduling problem with indefinite availability constraint. In 1999, Kayo et al. indicated that single-machine problem considers several returns of inaccessibility is NP-hard. At the same year, single-machine problem with indefinite inaccessibility period by Keravas and Lee were studied. After them, Cheng and Lee in 2000 studied scheduling problem of parallel machines. In 2004, Agoni combined scheduling problem of production and maintenance in flow shop environment. In 2006 Breit [11] expressed scheduling problem of single-machine given availability constraint on machines. At the same year, Goo and et al. [4] presented scheduling problem of jobshop with possibility of an inaccessibility period for each machine. In 2010, Zegordi and Rahimi [12] investigated scheduling single-objective given availability constraint on machines and production regime of N-R type and also they utilized a classic GA in order to solve it. Next, we review the works made use of GA to solve scheduling problems.
Genetic algorithm in scheduling problems
Many of the optimization problems in production systems, in particular, optimization problems of scheduling in shops were so complex and usual optimization methods are not able to find their solutions. Scheduling of flexible dynamic job-shop is one of the most difficult problems in combinatorial optimization topics. Generally, studies about scheduling in dynamic environment are divided into two main groups. The first group is queue-based and the second group is rolling time horizon technique [13,14]. Regarding to the complexity of the problem, the above analytical methods are often employed to solve single machine problems. But, for problems with more machines, meta-heuristic methods are used. In the literature, approaches such as simulated annealing, particle swarm optimization, artificial intelligence, evolutionary algorithms, fuzzy theory and etc. were applied for solving scheduling problems. Among those methods, GA has better performance than other methods. Some researchers think that GA is an efficient method to solve scheduling problem as an optimization problem [4,15].
In 1997, Brandimarte [16] solved the problem of flexible process program and proposed two methods for solving namely, Dual-based and GA based. At the same year Ghedjati [17] presented a synthetic approach from Meta heuristic methods, GA-based for solving FJS problem. Concerning the strategy with constraints and non-search chromosome, he also advised it was much better to use method-based rejection non-search chromosome for solving the problem that have non convex solution space. Kacem et al. [18] in 2002 studied FJS problem in multi- objective case for the first time. Their presented method was compounding of fuzzy logic and evolutionary algorithms using fuzzy logic for access to pareto-optimal solutions. At the same year, Lee et al. [19] presented a GA for solving similar problem with FJS in supply chain. In 2004, Tay and Wibawo [2] utilized a certain representation for their GA and solved scheduling problem of flexible job-shop. They introduced such scheduling problem to be an NPhard one. At the same year, Cheng and Gen [20] presented a GA for solving studied problem by Kacem and et al. In this research, first sub problem of allocation solved by prioritizing rule SPT, then selecting one appropriate representation of chromosome a good quality solution was obtained. The results of calculations indicated the effectiveness of their algorithm for large sized problems. Kurz and Askin [21,22] presented RKGA Meta heuristic algorithm for solving FSPM problem. They employed hierarchical approach for solving their problem and analyzed them for two sub problems of allocation and assignment sequence of operation. In 2007 Tay and HO [15] utilized Genetic programming for solving their flexible job shop problem. Ho et al. [23] developed a methodology for solving FJSP problem supposed to secondary rotation of jobs introduced inordinate counting on evolutionary algorithms. Secondary synthetic mechanisms were most constraints of this method and random selection. In other to overcome these constraints and obtain effective solutions for FJSP problem, they presented their proposed GA called LEGA. They considered combination of these patterns and production of population simultaneously. In that approach a simple distribution rule of module learning has been used. Koliner [24] employed Genetic agents that using agents of two or more section points having priority to other agents. Dagli and Sittisathanchai [25] introduced premature convergence and fell them in to local optimal points trap as a one of the mast defects in classic GA. Gao et al. [4] at the same year used combination of GA with innovative method of transfer of neck bottle for solving FJSP problem. In 2009, Nahavandi and Abbasian [26,27] presented simple GA with two dimensional chromosomes for solving FDJSPM problem and they also showed the priority of their method towards a similar method in literature. At this same year, Amiri et al. [28] used a compound plan for simulation of chromosome behavior. Moreno et al. [29] proposed binary representation of GEP chromosomes for search solutions. They indicated that this kind of representation improved GEP scaling considerably. In 2010, Nahavandi and Abbasian [30] presented GA with two dynamic dimensional chromosomes for solving their problem. Verma et al. [31] proposed a method so called calculation data- intensive technique and showed that this technique has basic role in scaling and estimating GA distribution. Generally, with exhaustive study that carried out about background research in Field of "availability constraint machine" and "methods of presented solution for flexible job shop problem, in particular using the majority of scheduling models of problems" become specified that first in the majority of scheduling models of flexible job shop suppose that machines are available all the time. Although in actual environments of production and manufacture it is possible machine in several reasons are not available over planning horizon. Second, such scheduling problems because of their non-convex nature and non-linear usually have defects of classic GA is premature convergence and fell them in to local optimal points trap [3]. Therefore, with identifying present locks objective of the paper considered modeling and solving scheduling problem of flexible dynamic multi- objective job shop considering Maintenance constraint. In the proposed GA for solving the problem as well as to overcome constraint of premature convergence and fell in to local optimal points trap two strategies were used. First strategy attempted to increase the capability of the searching algorithm. The next strategy makes the optimization process intelligent using the Genetic agents. So, in the proposed GA the possibility of each agent in the optimization process are determined dynamically and according to the number of elite chromosomes that transfer to next generation population directly.
Proposed Problem and Mathematical Modeling
In this section, MO-FDJSPM problem is defined and then the indices, parameters, variables and the mixed integer mathematical model are presented.
Definition of problem
Many researchers of scheduling science considered nature of scheduling science in production and manufacture environments to be multi-objective in many cases and defined basic objectives of scheduling as follows [32]:
1) Optimal use of resources and existing machines in shop
2) Minimizing supply in operation and accelerate to flow job
3) High commitment against customers and considered delivery dates
To obtain these objectives it is necessary to adapt several performance criteria to the concepts of scheduling and control them during problem solving, simultaneously. For example, along with considering performance criterion "Maximum time of components completion" (for optimal use of resources and machines availability) to reach high commitment against customers and also assignment delivery dates and/or in other words just in time (JIT) components, control performance criterion adaptable to philosophy of JIT such as "an average time of components delivery delay" can be included to this objective. But it should be noted that minimizing performance criterion for components that complete earlier than delivery date is significant. Therefore, it means that it is necessary here along with considering performance criterion also control a reflective criterion of these costs as well as performance criterion of an average flow time components. These objectives adapted to philosophy of on time production and managerial objectives of supply chain and their simultaneous controlling ended up to improvement of system performance [33].
MO-FDJSPM problem considering Maintenance constraint defined as follows: There are in a number of n component, m job station, and in addition to completion each component is necessary to specific operation set (like O); the order of movement each component between job stations are different from several components. In present research for as much as possible problem to actual environment of production and manufacture, shop environment are considered dynamic. So, each of the components arrives to shop at a time r (a non-zero and random time). In one way, to avoid making bottleneck and increasing production rate in addition to each of job stations have process ability more than one component type (operation flexibility) each job station M, compounding of parallel machine set that are able to process allocated job to its job station (flexibility resulted from existing parallel machines). There are operation flexibility, machines and sequence of several operations. But the operation that should be done are definite and stable [3]. In this research, viability constraint to machines considered definite type and so called Maintenance constraint. Maintenance constraint investigates in indefinite availability case and unavailable period are flexible at this condition. Of course, each Maintenance activity should do in predetermined time window and its breakup is not permissible. Characteristics of jobs considering this constraint are investigated in permissible breakup operation case and process regime of starting job again. More over basis hypothesis, there are cases in the problem that, the breakdown of operation is permissible, there is not any possibility of coherent availability to machines, Maintenance limitation (constraint) is definite and indefinite types; process regime is starting job again, break down of Maintenance activity is not permissible. Flexible job-shop scheduling problem considering Maintenance constraint divided in to three sub problems as follows: routing, assignment to single machine, sub problem of sequence assignment, sequence of allocated operation to machines, and specify sub problem of Maintenance scheduling each of Maintenance activities. It is supposed that decision maker has adequate information about weight of objectives or their priority. The objective of solving problem found best weighted sum of objectives of problem and presented them to decision maker.
Mathematical model of the problem
In the present work, a nonlinear program, mix integer mathematical model is presented for the proposed problem. In this model, there is n job (component) in number of L processing stage (job station) that doing each job in dynamic shop is necessary to specify operation set. Job ith has Oi operation with definite sequence. Each component such as component ith for process in shop arrives to dynamic shop in a nonzero ri time. Job station of Lth has same parallel machine m1. Operation oik by machine m1j processed from available machine set Mikl and in job station predetermined w1 for piklj time unit. Machine m1j has maintenance activity R1j that it should be done during programming horizon. Also, Maintenance activity Pm1jr has been done for tijr time unit and completed specified time window. In continuation, parameters and decision variables are introduced and then mathematical model of the problem is presented.
Parameters: oi: the number of job operation ith
oik: operation kth from job ith
ri: arrival time of component ith to shop
w1: job (work) station 1th
m1: the number of parallel machines in work station 1th
m1j: machine jth from work station 1th
Pik1j: time period of processing oik on mij
Mikl: set of available machines for operation processing oik in work station 1th.
tm1j: available time m1j
R1j: the number of Maintenance activity on m1j
PM1jr: Maintenance activity rth on m1j
t1jr: time period of doing PM1jr
: Evilest time of completion PM1jr
: Latest time of completion PM1jr
: Time window for completion PM1jr
Decision variables: Cik: completion time oik
U1jr: completion time PM1jr
Research problem formulate as follows: Min
(Minimization Weighted Sum of Three Objectives) (1)
(Minimization of make span) (2)
(Minimization of Mean flow time) (3)
(Minimization of Mean Tardiness) (4)
Equation (1), main objective Function of Mo-FOJSPM problem indicates minimizing weighted sum of three objectives resulting from relations (2) to (4) with definite coefficients . The desirable delay unit in each component delivery for whole jobs is 1 ( ). It is necessary to note that in actual production and manufacturing systems, the number of weighted coefficients should be determined by proficient of that industry where it is possible these weights be different from a manufacturing environment to another. In the present work suppose that all these objectives have the same priority in shop level. So, we will consider the number of a1, a2, a3similar and equal to hypothetical number 1/3. Because each scheduling program becomes possible solutions of logic constraints all done operation from each definite job should be allocated resources with ordinal priority and without interference to each other. Equations (5) guarantee that sequence of jobs operation set doesn't have time interference, in other words the set of these in equations make each operation in a sequence begin if their pioneer operation were applied.
As we can't process two operations on a single machine simultaneously, each valid scheduling should be also a possible solution for constraints. Set of constraints (6) and (7) guarantee simultaneously that set of operation that employed on single machine, don't have time interference. All presented models for jobshop problem have at least two similar constraints that in case of violation of these two constraints problem exit from jobshop case. So, all shop problems contains as presented in equation 5, 6 and 7 in the proposed mathematical model. In equation (8) and (9) demonstrate the coincident constraints doing Maintenance activities and several jobs operation on single machine. As well as set of these in equations of dynamism problem because of differential arrival time shop are considered. Equation (10) indicated that one should choose a machine from available machines set for doing each operation. Equation (11) explained that Maintenance activities should be completed in a specific time window.
In order to measure validity of the proposed mathematical model for Mo-FOJSPM problem, a solution approach for small size problems is implemented and tested by Lingo software. And their results also confirmed validity of the proposed model for Mo-FOJSPM problem considering Maintenance constraint.
Being NP- hard problem
Mo-FOJSPM problem is developed of the flexible production shop model (FOJSP14) considering flexibility and as a result will also bring all complexities and difficulties. Considering any flexibility of operation in these problems, even complexity of estimated optimal solution also increased remarkably [1]. As FOJSP with flexibility of operation is strongly NP- hard itself [34], but Mo-FOJSPM problem also considering flexibility resulted from parallel machines in dynamic production and manufacturing environment regarding Maintenance constraint will be NP- hard strongly.
Problem Solution Approach
For solving this kind of scheduling problem, it is required to employ an effective optimization strategy for considering complexities resulted from solution space for obtaining appropriate values as for objective functions. According to the literature, several approached can be used for solving flexible job shop problem. One is to divide the main problem to three sub problems of routing, assignment of sequence and Maintenance scheduling. In the present work a synthetic method based on GA is proposed for solving the problem. In this way that two sub problems are routing and assignment of sequence solved by GA and for solving sub problem of Maintenance scheduling an innovative algorithm is utilized. It is supposed that decision maker has adequate information about weight of objectives and their priority. The objective of Mo-FOJSPM problem is finding the best weighted sum of objectives.
Next, we present the GA structures including the presentation of chromosomes, tuning the parameters, and dynamic adjustment of parameters to solve the problem. Also, the innovative algorithm for solving Maintenance sub problem and the efficiency of the proposed synthetic method according to weighted sum of objective function is discussed through numerical experiments.
Proposed genetic algorithm
As Mo-FOJSPM is an NP- hard problem, an algorithm that can obtain the solutions in a logical time for large sized problems is of importance. So, in this section for solving the proposed problem, a GA will be presented so that to obtain the solutions in a logical time. The general procedure of the proposed GA is shown in Figure 1.
Presentation of chromosomes: The first step for designing a GA is representation of the problem as chromosomes [34]. In presenting chromosomes, usually parameters needing less space and time are considered since otherwise due to complexity infeasible chromosomes may be generated [34]. Mo-FOJSPM problem considering Maintenance constraint is a tradeoff between two sub problems of allocation and assignment of operation sequence. The proposed GA is designed in such a way to be able to solve both two above mentioned sub problems, simultaneously. For this purpose a two dimensional chromosomes is utilized. At this representation length of chromosome is equal to total numbers of operation of present jobs for scheduling and its width is equal to 3. In the proposed GA, the first, second and third strings of chromosome indicate job (work) station, the number of machine and allocated priority to each operation, respectively. So, each problem solution is shown as a method that of course because of exiting parallel machines, includes allocation string of job (work) station as well as allocation string of machine [33].
Main factors of GA: In this section we investigate how to adjust other main factors of the proposed GA including initial population, crossover operator, mutation operator, selection approach, fitness function, impact strategy with constraints and ending criterion, respectively. After assignment transformation method of each solution to chromosome, an initial population of chromosome should be produced [34]. In the proposed GA also in order to avoid premature convergence we use an innovative method for production of initial population (Pop-Size). In the proposed GA two crossover operators of axis place carried out allocation string of machine (first and second string of chromosome) and crossover operator R^^x on string of operation sequence (third string of chromosome) are used. Because of specific structure of the problem and the proposed chromosome, an innovative mutation operator that is based on linear inversion and presented by Ferantez is established on an innovative rule as this operator work at two different mutation rates and for allocation sub problem the innovative rule of mutation operator with mutation rate (Pm1) and for sub problem of assignment operation sequence from inversion operator with mutation rate (Pm2) are utilized. As well as for evaluation chromosomes we utilize a fitness function. This function use the weighted sum function as is common for evaluating fitness value in GA. Gao et al. believed that for solving multi criteria scheduling problem with GA due to different scales of alternations amplitude each of objective function (as result of alternations amplitude of other problem parameters) in calculating fitness function of multi objective problem considering weighted sum of these objectives it is better to normalize these values during population and then their weighted sum is calculated from normalized synthetic amount of this function [13].
In the proposed GA, chromosome design is so that to minimize the problem impact with constraint and production of infeasible solutions. So, in this structure allocation string (stage and machine) will be searched continuously. In operation sequence string, there is only non-search possibilities of constraint of sequence priority are between operations of a job that will solve using correctional method. The algorithm is repeated until a stopping criterion of max-gen is achieved.
Parameters adjustment dynamically: One of the disadvantages of classic GA is premature convergence priority [20]. In GA two operators of classic Genetic competed on how problem convergence. Although utilizing mutation operator creates diversity in populating crossover operator of population and makes it to converge [8]. Regarding this fact in adjustment of GA parameters we try to find optimal adjustment for applying of mutation and crossover operators. To improve our GA from avoiding premature convergence we may use "change of transformation rates and mutation during implementation of GA" technique. This method is based on production of each new generation using statistical data and computing distance of fitness of population member towards fitness of its best member for all population members. At this condition it is related to crossover operator and increase the mutation possibility to avoid the algorithm from the local optimal points. In opposite, if many numbers of chromosomes have not been qualified as the best individual population, then the desirable improvement is not achieved, because of just few number of chromosome have good qualities (good fitness) and the presented crossover rate doesn't create good solution effectively. To remove this problem, we can reduce mutation rate and/ or increase crossover rate. So according to fitness distance of strings, mutation and crossover operators’ rates are adjusted during problem solving. In the proposed algorithm, during the use of elitism technique, if numbers of best chromosome first ordered population are same, it is possible to fall into local optimal point trap. In this case, in the design of GA it is tried to only for once double the number of mutation as well as becoming half the number of crossover. While this condition is violated, the number of mutation and crossover change to the same number of problem again. As mentioned for measuring the efficiency of the proposed GA for solving the problem considering Maintenance constraint, a synthetic method for solving problem utilizing developed version of the proposed GA in order to solve two routing sub problem and assignment sequence simultaneously and then by using the efficient innovative algorithm approach we solve the Maintenance scheduling problem.
Innovative algorithm for solving sub problem
In 2006, Gao and et al. presented an innovative algorithm for solving sub problem of Maintenance scheduling flexible job shop [4]. In the present work, their algorithm for solving sub problem of Maintenance scheduling and implemented on parallel machines in the case exiting more than one Maintenance activity for each machine are developed. Steps of this innovative algorithm as follows:
Step 1: schedule Maintenance activities of total station machines in their ending window as
Step 2: Allocate operation of all jobs according to priority in sequence, for first machine available in predetermined job station and continue this job until reach to nearest scheduling window of doing Maintenance activity each machine.
Step 3: In the time of doing Maintenance activity, if availability to machine and possibility of doing operation before Maintenance activity, allocate operation to considered machine and go step 5, otherwise alternate Maintenance activity as possible as, as follows, to left side and close to beginning time window.
Step 4: If availability to machine and possibility of doing operation after Maintenance activity, allocate operation to machine.
Step 5: If operation of total jobs are scheduling end to algorithm, otherwise return to step 2.
Numerical Experiments
We analyze the performance of the proposed method is evaluated in two cases. As the flexible job shop problem is a simplified version of our research problem in which the unavailability periods for machines are zero (R=0). So in this case, the proposed GA is compared with RK6A Meta heuristic method developed by Kurtz and Askin. In the second case, our proposed problem considering 1, 2 and 3 maintenance activities upon each machine (R=1, 2, 3) are studied and its obtained results are compared with the first case (R=0). In this case, the efficiency of the proposed solution method is investigated with respect to an index used by Gao et al. [4].
Generation of the random data
In this section, in order to generation of random problem, the first six parameters of the problem are determined according to Table 1. Note that, the first 5 parameters are extracted from Kurtz and Askin and for process speed of similar machines regarding Nahavandi and Abbasian a uniform distribution U (1, 3) is applied.
In addition to parameters in Table 1, number of other four cases are considered as follows, 0, 1, 2 and 3 Maintenance activity on each machine (R=1, 2, 3). In general case, all components of these levels will be tested for doing numerical experiments; there are 288 possible scenarios from which 10 examples are produced. Thus, there is 2880 implementation in numerical experiments. Proposed GA is coded in C++ language and the all the 288 data sets are implemented via two algorithms.
Parameter adjustment of proposed GA
Given the obtained results of simulation, most appropriate values for algorithm parameters, i.e. the number of chromosome in elitism technique (u'), crossover rate (pc), possibility of mutation string (pm1), the possibility of mutation for string of assignment sequence (pm2) are 20%, 7%, 2% and 4%, respectively.
Results of numerical experiments
In the first step, the efficiency of the proposed GA in lack of Maintenance activity on machines (R=0) is compared with the innovative method RKGA. As shown in Table 2, the proposed method given index "mean of objective function" in small, average and large dimensions excel from the RKGA in average of 1.33%, 1.38% and 2.12%, respectively, also the presented GA improves the solutions according to index of minimum number of objective function with the average of 0.94%.
In Table 2 different degrees of average objective function for GA in (R=0) with innovative method and RKGA are shown for several problem sizes. In Tables 3-5 effect of implementation considering Maintenance constraint on performance of the proposed solution approach is investigated considering one, two and three Maintenance activities on each machine (R=1, 2, 3).
The three separate experiments are compared with the case without the maintenance activity. In this case, efficiency of proposed solution method with aid of "maximum time period of doing Maintenance activities on machines" index is investigate by Gao et al. [4] for solving flexible job shop problem considering period of unavailability for each machine. As observed in Table 3, the average amounts of increase in objective function is lower than the sum maximum time period of doing Maintenance activities in small, average and large sizes (Figure 2).
According to the computations, little increase of objective function is implied and therefore the combinatorial method is demonstrated to be efficient. Therefore, the proposed method according to mean index of objective function in small, average and large sizes with mean of 6.15%, 5.85% and 2.02% increases and generally with the mean of 4.68% increase have appropriate performance, respectively. Also considering mean indicator of solution time in comparison with lack of Maintenance activity don't observe any difference between Maintenance activities. In Figure 3, average amount of increase mean of the proposed GA with sum in (R=0) and (R=1) cases for several sizes of problem are compared. Also, the obtained solution time in comparison with lack Maintenance activities don't indicate any difference between two and three Maintenance activity. In Figures 4 and 5, average amount of increase mean with sum maximum time period of doing Maintenance activities upon machines are compared in cases R=0, R=2 and R=0, R=3, respectively. The obtained results for the proposed method according to index of objective function method in case one, two and three Maintenance activity with the mean of 4.68%, 9.48% and 11.75% has ideal performance, respectively.
The Effectiveness of the Proposed GA
For generating random problems with respect to 11 parameters given in Table 6, the data in Toy and Ho (2007) is employed for the first 8 parameters and for other parameters the data in Kurtz and Askin [21-23] are utilized. Delivery date of jobs relation is introduced by Broker [9]. Parameter C in above relation is tightness index of delivery date that as much as the amount of this parameter are more for job, it will show weak related delivery date of job. Generally, all components at this level are tested. Given Table 6 there are 12 experimental scenarios having 10 data set generated for job, we implement the algorithms by the 120 data sets. Tay and Ho alternated the processing time Pi,j to adapt this formula to Mo- FJSP problem with its flexibility operation, and proposed the relation of Broker with to compute relation (15). At this relation n (f(oij))demonstrates the number of referential job stages for doing its job operations. We also utilize the following added relations to adapt this formula with the research problems MO-FDJSPM:
where is a binary variable that is 1 if in a processing stage a machine is a possible substitute for Oij, and otherwise it is zero. Sk,pm and lk demonstrate the speed of machine Mk,pm and number of parallel machines for kth job station. For more simplicity the penalty for delay is considered same for all parts.
Parameters adjustment for the proposed GA
Here, procedure of parameter adjustment is utilized for adjusting four parameters entitled, (M'), (Pc), (Pm1), (Pm2). For this purpose, from each experimental scenario a data set and totally 72 data sets are generated randomly and then in procedure of parameters adjustment with production of each new parameter the GA is implemented upon 72 data sets. Also, the following parameters with the corresponding specifications are considered:
Percent selecting of best chromosome for next generation (M'): 5%, 10%, 15%, 20%, 25% and 30%, possible cross over (Pc): 3%, 4%, 5%, 6%, 7%, 8% and 9%, possible mutation (Pm1) and (Pm2): 5%, 1%, 15%, 2%, 25%, 3%, 4% and %5, the number of initial population (Pop- Size): 100, the number of repeats (Max- Gen): 125. The result of experiments are obtained to be 20%, 7%, 2% and 25%, for (M'), (Pc), (Pm1) and (Pm2), respectively.
Method of doing numerical experiments
The algorithm is encoded in C++ language and implemented using a computer with Pentium IV (CPU3 GHZ 1GB of RAM) in Borland C++ 5/02 environment. Each of the algorithms (proposed GA and GP) are implemented using the same 120 generated data sets. To compare the proposed GA with the GP algorithm we utilize the numbers of weighted sum function and the collected parameters listed in Tables 7-9, briefly.
Results of GA experiments
The followings are the results of a survey of the algorithm:
1) The advantage of the proposed GA rather GP with respect to "minimum value of minimization objective function of maximum weighted sum" index in small, average and large sizes are reported with the mean of 2.65%, 3.16% and 5.90%, respectively, and totally with the mean 3.90% which is a noticeable improvement.
2) The "Mean of objective function" could be the best criterion for evaluating the algorithms. The proposed GA in small, average and large sizes with the mean of 4.34%, 3.64% and 5.34%, respectively, and totally with the mean of 4.90% has better performance than the GP algorithm.
3) The only strength of the GP algorithm against the proposed GA according to the results of Table 7 and with respect to “mean solution time” index in small, average and large sizes is revealed. Of course, the improvements done by GA justify the longer solution time of this algorithm against the GP (Figure 6).
In this paper, a problem of flexible multi-objective scheduling job shop with parallel machines in dynamic job shop environment, Mo-FOJSPM considering maintenance constraint for machines is introduced. Given parameters of the problem, an analytical mathematical model was developed and it was proved that the problem is NP-hard due to conventional solution approaches disability for handling the problem. Thus, a genetic algorithm was proposed and adjusted for the proposed scheduling problem. Also, an innovative algorithm was designed for solving maintenance sub problem. Due to a classical problem in GA, premature convergence, a technique was utilized to employ the model knowledge not to trap in local optimum in an intelligent manner causing more efficiency of the searching process in the solution space and finding the optimal solutions. Several parameters adjustment and different data set generation was set to perform the numerical experiments. Also, a comprehensive numerical discussion for different cases of the problem depicting in tables and figures were presented. The numerical results and the performed comparisons verified the effectiveness of the proposed GA against GP in the proposed Mo-FOJSPM.

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Article Usage

  • Total views: 11252
  • [From(publication date):
    July-2015 - Jul 24, 2016]
  • Breakdown by view type
  • HTML page views : 7489
  • PDF downloads :3763

Post your comment

captcha   Reload  Can't read the image? click here to refresh

OMICS International Journals
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
OMICS International Conferences 2016-17
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri, Food, Aqua and Veterinary Science Journals

Dr. Krish

1-702-714-7001 Extn: 9040

Clinical and Biochemistry Journals

Datta A

1-702-714-7001Extn: 9037

Business & Management Journals


1-702-714-7001Extn: 9042

Chemical Engineering and Chemistry Journals

Gabriel Shaw

1-702-714-7001 Extn: 9040

Earth & Environmental Sciences

Katie Wilson

1-702-714-7001Extn: 9042

Engineering Journals

James Franklin

1-702-714-7001Extn: 9042

General Science and Health care Journals

Andrea Jason

1-702-714-7001Extn: 9043

Genetics and Molecular Biology Journals

Anna Melissa

1-702-714-7001 Extn: 9006

Immunology & Microbiology Journals

David Gorantl

1-702-714-7001Extn: 9014

Informatics Journals

Stephanie Skinner

1-702-714-7001Extn: 9039

Material Sciences Journals

Rachle Green

1-702-714-7001Extn: 9039

Mathematics and Physics Journals

Jim Willison

1-702-714-7001 Extn: 9042

Medical Journals

Nimmi Anna

1-702-714-7001 Extn: 9038

Neuroscience & Psychology Journals

Nathan T

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

John Behannon

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

1-702-714-7001 Extn: 9042

© 2008-2016 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version