基于模糊加工时间的多目标遗传算法 - 副本

2013 Sixth International Conference on Advanced Computational IntelligenceOctober 19-21,2013, Hangzhou, ChinaMulti-objective genetic algorithm for integrated process planning andscheduling with fuzzy processing timeX i aoyu Wen, X i nyu L i , L i ang Gao, L i ang Wan, and Wen w en WangAbstract-Integrated process planning and scheduling is asignificant research focus in recent years, which could improvethe performance of manufacturing system. In real manufacturingenvironment, multi-objectives should be taken into considerationsimultaneously during the machining process. Meanwhile, theprocessing time for each job is often imprecise in many realapplications. Therefore, multi-objective integrated processplanning and scheduling (IPPS) problem with fuzzy processingtime is addressed in this paper. The processing time is describedas triangular fuzzy number. A multi-objective genetic algorithm(MOGA) is designed to search for the Pareto solutions of multi­objective IPPS problem with fuzzy processing time. An instancehas been designed to test the performance of proposed algorithm.The experiment result shows that the proposed MOGA couldobtain satisfactory Pareto solutions for the multi-objective IPPSproblem with fuzzy processing time. Keywords-Integrated process planning and scheduling; multi­objective genetic algorithm; fuzzy processing timeI. INTRODUCTIONProcess planning and scheduling are two pivotal sub­systems in modern manufacturing system. Process planning isthe bridge between product design and manufacturing, whichtransforms the product design into manufacturing instructions.The outcome of process planning is the identification of themachines, tools, and fixtures. Most jobs may have a largenumber of process plans due to the flexibilities of machiningprocess and sequences [1]. After the process plans of jobs aredetennined, the scheduling is to allocate the operations of allthese jobs on machines over time by satisfying the precedenceconstraints in the process plans. As the outcome of processplanning is the input of scheduling, process planning andscheduling have a close interrelationship with each other.Traditionally, process planning and scheduling were studied asthe separate problems. Scheduling was implemented after theprocess plans of jobs were determined. This research approachmay generate the following problems [2]:• Process planners always assume the shop floor is idle and all the resources are always available when they make the decision. Therefore, they always prefer to choose the best processing equipment for the current production. Then, some productions may be appended on the same equipment, which will cause the predefined process plans not suitable for shop floor. Manuscript received June 14,2013. This research work was supported by the National Natural Science Foundation of China (NSFC ) under Grant No. 51375004, t he National Science and Technology Major Project of China under the Grant No. 20 l 1ZX040 15-0 11-07.The authors are with State Key Laboratory of Digital ManufacturingEquipment &Technology , Huazhong University of Science and Technology ,Wuhan , China (Emails:xiaoyuup@.lixinyu@.gaoliang@ ).• Process planning and scheduling usually have conflicting objectives. Process planning always concerns with total processing time, total cost etc., while scheduling concerns with makespan, due date etc.. In real manufacturing process, decision-makers always want to get trade-off solutions among different objectives. If process planning and scheduling are carried out separately, different objectives couldn't have the appropriate coordination. • Scheduling is always carried out after process planning. As many uncertain conditions exist in the manufacturing process, the constraints considered in the planning phase may have already changed when scheduling is executed. The time delay betweenplanning phase and scheduling phase may lead to theprevious optimal process plans infeasible. Integrated process planning and scheduling (IPPS) tightly could overcome above problems. IPPS could improve the perfonnance, increase the flexibility and responsiveness of manufacturing system. It is a significant research focus in recent years. Although IPPS problem has been investigated frequently, only a few of these studies pay attention to the multi-objective IPPS problem. Researchers have proposed grammatical optimization algorithm [3], greedy randomized adaptive search procedures algorithm [4], multi-objective simulate annealing algorithm [5], improved vector evaluated GA [6], and PSO-based multi-objective optimization approach [7] to optimize multi-objective IPPS problem. In the existing methods, multi-objective evolutionary algorithms (MOEAs) have shown a good performance on solving multi-objective IPPS problem. All the related works of IPPS defined the processing time of jobs as precise value. In fact, the processing time of jobs is always imprecise in real world production. Considering multi­objectives and fuzzy processing time of jobs simultaneously could make the IPPS problem more representative of real­world situations. In this paper, multi-objective IPPS problem with fuzzy processing time is addressed. The processing timeof jobs is described as triangular fuzzy number. A multi­objective genetic algorithm is designed to search for the Paretosolutions of multi-objective IPPS problem with fuzzyprocessing time.The remainder of this paper is organized as follows.Problem description is elaborated in Section II. Section IIIpresents the workflow of the proposed algorithm and theparticular genetic operations. Section IV shows the experimentresult and discussion while the conclusion and future works aregiven in the last section.II.PROBLEM FORMULA n ON A. Multi-objective optimizationThe multi-objective optimization problem (MOP) can be defmed as follows [8]: M ini m i z e f (x )= {J; (x ),J;(x )""'h (x )} Subject to: gj(x ):=;O , j=1,2,... ,m XE X, f (x )E Y(1) k is the number of objectives, m is the number of inequality constraints, x is the decision variable, fi x) is the objective. X is the decision space, Y is the objectives space. In MOP, for decision variables a and b, a dominates b: iff f,(a):=;f,(b ) Vi E (1,2,... ,k) < f/b ) ::JjE (l,2, ... ,k) a and b is non-dominated: (2)iff f,(a):=;f,(b )&f,(a)?f,(b ) Vi E {1,2, ... ,k } (3)A solution x* is called the Pareto optimal solution if no solution in the decision space X can dominate x*. The Pareto optimal set is formed by all the Pareto optimal solutions. The target of MOP is to find a finite number of Pareto optimal solutions instead of a single optimum in single objective optimization problem [5].The multi-objective optimization methods can be generally classified into two different types: the first type is the traditional non-Pareto method, such as sum-weighted, constraint method and so on; the second type is the Pareto­optimality method, such as MOEAs. MOEAs are widely used in many multi-objective combinatorial optimization problems. The proposed MaG A in this paper is one kind of MOEAs, which is a Pareto-optimality method.B. Fuzzy number and operations In the original research works, triangular fuzzy number (TFN) is the most widely used fuzzy number to describe the imprecise processing time. In this paper, the uncertain processing time for each operation is also represented by a TFN A =(a l 'a2,a 3)a s shown in Figure 1. , a] is regarded as the most optimistic processing time, a2 is the most possible processing time, a nd a3 is the most pessimistic processing time. As fuzzy number addition and fuzzy number ranking are essential during the scheduling process, two operations are defmed at first [9]. The first operation is addition operation. The addition operation of two TFN M = (m ] m m ) and N = (n n n ) is , 2' 3 P 2' 3 shown in the following formula: (4)The second operation is ranking operation. The following three criterions proposed by Masatoshi [9] are used to rank two TFNs. Criterion 1: Set ifC] (M) > C ] (N) ,M > N . Criterion 2: If C1 (M) = C 1 (N) , set C2(A) = a 2I fC2(M) > Cz(N),M > N. Criterion 3: If C1 (M) = C 1 (N) , Cz(M) = C 2(N) , s etC 3(A) = a 3 -a] . If C 3(M) > C 3(N), M > N. j.l 1.0o x Figure I. TFN for uncertain processing time C. Multi-objectiveJuzzy IPPS problem The multi-objective fuzzy IPPS problem addressed in this paper is described as follows: there are n jobs need to be produced on m machines. Each job has various operations and alternative manufacturing resources. The processing time of each operation in different machines is TFN. The aim of multi­objective fuzzy IPPS is to select suitable manufacturing resources for each job, determine the operations' processing sequence and the start time of each operation on each machine by satisfying the precedence constraints among operations and achieving the multi-objectives simultaneously [10]. TABLE I. gives fuzzy processing information for 3 jobs machined in 3 machines. Each job has alternative operationsequences, each operation can be machined in different machines. For example, Job 1 has 2 alternative operation sequences; the first operation of Job 1 can be processed in MJ or M2• Process planning is to determinate the operation sequences for each job and selected machine for each operation, schedule is to determinate the fuzzy start time and fuzzy finish time for each operation on each machine. In this paper, scheduling is assumed as the job shop scheduling. The mathematical model proposed in [11] is employed. The makespan, total machine workload (TMW), maximal machine workload (MMW) and total flow time (TF) are considered to be optimized simultaneously. The detail computational formulas of makes p an, TMW, M MW can be found in [11]. The total flow time is the sum of all the jobs' completion times. It is obviously that the four objectives are also TFNs.TABLE I. Jobs Fuzzy PROCESSING INFORMATION FOR 3JOBS MACHINED IN 3 MACHINES Fuzzy processing informationprocess plan for job 1 is OzCMa-03(M3). The total fuzzy processing time is (7,11,15).3) Genetic operations for process planning: the selection, crossover, and mutation operations are described as follows:a) Selection: The Tournament Selection is used as the selection operation in this paper. In tournament selection, a number of individuals are selected randomly from the population and the best fitness is chosen. The number of the selected individuals dependent on the tournament size. Tournament selection can modify the selection pressure by changing the tournament size.b) Crossover: The crossover operation is just for the last n elements in the chromsome. First, select two chromsomes Pl,P2 from the current population by the selection operation. Initialize two empty offspring Ol and 02. Second, select a crossover point randomly to divde the last n elements of Pl,P2 into two parts.Third, t he elements in the first part of P 1,P2 are appended to the same positions of 01,02, the elements in the second part of Pl,P2 are appended to the same positions of 02,0l. The first element of Ol,02 is the same with Pl,P2.c) Mutation: The mutation operation is selecting a position randomly and then change the element of the selected posotion to another alternative operation sequences or another alternative machines.C. Genetic components for scheduling1) Fitness evaluation: As TMW and MMW are determined after process planning, only makespan and total tlowtime are taken into consideration in scheduling. In this paper, the fitness evaluation of individuals depends on their non-dominated rank and density. The individual with a smaller non-dominated rank is easily to be selected during the evolutionary process. The individuals with the same non­dominated rank can be compared by their density. The individual with the smaller density is better.2) Encoding and decoding: For each individual in the scheduling population, the operation-based encoding method is used as the encoding strategy[14]. Each individual should be decoded into active schedules in the decoding procedure [15] .3) Genetic operations for schedulinga) Selection: The selection operation for scheduling is the same with the selection operation for process planning.b) Crossover: The crossover operation is POX (Precedence Operation Crossover) , which could be referred from Zhang et al. [15].c) Mutation: The mutation operation is two-point swapping mutation. First, select two different elements in the encoding sequence, then generate a new chromosome by interchanging these two elements.IV. EXPERIMENT AND DISCUSSIONIn this paper, the proposed algorithm was coded in C++ and implemented on a computer with a 2.0 GHz Core(TM) 2 Duo CPU. Due to the lack of the benchmark instances on multi­objective IPPS problem with fuzzy processing time, we present an instance. The instance is constructed with 5 jobs and 5 machines, which is designed according to the instance in [3]. The alternative feasible operation sequences for each job in the instance are given in TABLE II . .The candidate machines and fuzzy processing times for each job in the instance are provided in TABLE III ..TABLE II.JobsJob IJob 2Job 3Job 4Job 5TABLE III.Jobs0,03Job l040;Job2 01THE ALTERNATIVE FEASIBLE OPERATION SEQUENCES FOREACH JOBOperation sequences Feasible operation sequencesNo.I 04-05-0,-032 05-04-0,-033 03-0;-O r044 04-0,-0;-03I 01-0,-042 01-04-0,3 0.-0,-014 0,-01-04I 03-05-01-042 01-0;-03-043 01-0;-064 05-03-01-04I 0,-03-0;-042 03-0,-0;-043 05-03-0,-044 04-03-05-0,1 04-01-032 04-073 04-03-014 01-04-03CANDIDATE MACHINES AND FUZZY PROCESSING TIMES FOREACH JOB IN THE INSTANCECandidate machines and fuzzy processing timesM I M, M3 M4 M s525760 354045 858890 586267 72 77 805710 81012 8 I I15 81013 358909597 707480 737682 6571 75 899397192429 13 1823 162227 232833 222632808489 72 76 80 626874 9398 102 808489JobsCandidate machines and fuzzy processing times MJ M, M3 M4 M s0, 152025 71013 121518 17 20 23 16192304 879195 838895 9398103 828793 8590950, 606570 828793 525864 758084 70748003 424654 172126 333843 485257 13 1824 Job3 04 131924 182227 121923 91419 162228 Os 687378 51 5664 596470 657280 55606506 9296 9398 9196 101 9095 100 9398100 103 103 0, 81318 4713 101317 91216 411 1903 465258 596469 92 97103 424753 354045 Job404 152025 253035 121723 511 16 91419Os 899499 616669 758084 747983 9195 1000, 899499 9297 505560 737883 80859010303 2531 37 172328 141924 374247 121723 Job504 838893 626567 71 7685 596469 7580850, 838892 697479 859095 879296 707580 TABLE IV. T HE EXPERIMENTAL RESULTSolutionsObjectivesMakespan TF MMW TMW1 246268291 832968 1111 206222237 6267138052 191 225264 8079291065 206222237 6427288193 211237265 8089261047 215236256 6287188094 203229258 7798921010 203229258 6367238135 223250276 862983 1108 211233253 6237128036 186215246 8099341065 184211240 6437318187 220247272 882973 1058 220247272 6267128038 211233253 870970 1067 211233253 6257168069 212238266 831951 1076 211233253 625716806To evaluate the performance of the proposed algorithm, it was applied on the designed instance. The experimental result is shown in TABLE IV . .It is obtained by running the proposed algorithm once. The detailed process plans and schedule for the 6th Pareto optimal solution are given in TABLE V. . In TABLE V. , OS No. means the number of selected operation sequences corresponding to TABLE II. 0 represents operations, M represents selected machines, FST and FFT represent fuzzy starting time and fuzzy fmish time for the corresponding operation in the selected machine respectively.From the experimental result, it is clearly that a set of Pareto solutions can be obtained by running the proposed algorithm once. It is different from the non-Pareto method used in multi-objective optimization, which can only get one solution in one optimization process. The proposed algorithm is more appropriate for the multi-objective optimization compared with the non-Pareto method.TABLE V.JobsJob 1Job 2Job 3Job4Job5DETAILED PROCESS PLANS AND SCHEDULE FOR THE 6THSOLUTIONDetailed process plans ScheduleOS No. 0 M FST FFT03 M4 0 81013Os M, 172126 30394930, M, 303949 65799404 M4 657994 130150 169O J M3 0 6268742 04 MJ 626874 149159 1690, M, 177 201227 184211 24003 M, 0 172126Os M, 657994 116135158IO J M3 116135 158 168 19322204 M3 168 193222 1802122450, M, 0 8131803 M s 81318 435363I0; M, 116135 158 177 20122704 M s 177 201227 18621524604 M4 81013 677482I 0, M3 677482 117 129 14203 M; 117 129 142 129146165V. CONCLUTTON AND FUTURE WORKS In this paper, a multi-objective genetic algorithm is designed to optimize the multi-objective IPPS problem with fuzzy processing time. An instance has been designed to test the performance of proposed algorithm. The experiment result shows that the proposed algorithm could obtain satisfactory Pareto solutions. It is the fust time to settle the multi-objective IPPS problem with fuzzy processing time. This research work could guide the actual production.There are also some limitations in the proposed algorithm. More objectives of fuzzy IPPS problem can be taken into account in the future work, for example, processing cost and agreement index. Exploring more methods to handle the uncertain conditions in IPPS problem is another future work.ACKNOWLEDGMENTThis research work was supported by the National Natural Science Foundation of China (NSFC) under Grant No. 51375004, the National Science and Technology Major Project of China under the Grant No. 2011ZX04015-011-07.[1][2][3][4][5][6][7]REFERENCESX. Li, L. Gao and X. Wen, "Application of an efficient modified particle swarm optimization algorithm for process planning," The international Journal of Advanced Manufacturing Technology, DOl 10.1007 /sOO l70-012-4572-7.M. Kumar and S. Rajotia, "Integration of scheduling with computer aided process planning," Journal of Materials Processing Technology, vol. 138, p p. 297-300, 2003.A. Baykasoglu and L. Ozbakir, "A grammatical optimization approach for integrated process planning and scheduling," Journal of intelligent Manufacturing, vol. 20, p p. 211-221,2009.M. Raj k umar, P. Asokan, T. Page, and S. Arunachalam, "A GRASP algorithm for the Integration of Process Planning and Scheduling in a flexible job-shop," international Journal of Manufacturing Research, vol. 5, p p. 230-251,2010.G. Mohammadi, A. Karampourhaghghi and F. Samaei, "A multi­objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing," international Journal of Production Research, vol. 50, pp. 5063-5076, 2011.W. Zhang and F. S, "Improved Vector Evaluated Genetic Algorithm with Archive for Solving Multiobjective PPS Problem," 2010 international Conference on E-Product E-Service and E-Entertainment (iCEEE), 2010, p p. 1-4.Y. F. Wang, Y. F. Zhang and 1. Y. H. Fuh, "A PSO-based multi­objective optimization approach to the integration of process planning and scheduling," 2010 8th iEEE international Conference on Control and Automation (lCCA), 2010, p p. 614-619.[8] R. T. Marler and 1. S. Arora, "Survey of multi-objective optimizationmethods for engineering," vol. 26, p p. 369-395, 2004. [9][10][I I][12][13][14][15]M. Sakawa and R. Kubota, "Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms," European Journal of Operational Research, vol.120, p p. 393-407, 2000.Y. W. Guo, W. D. Li, A. R. Mileham, and G. W. Owen, "Applications of particle swarm optimisation in integrated process planning and scheduling," Robotics and Computer-integrated Manufacturing, vol. 25, pp. 280-288, 2009.X. Li, L. Gao and W. Li, "Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling," Expert Systems with Applications, vol. 39, pp. 288-297, 2012.K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-ll," iEEE Transactions on Evolutionary Computation, vol. 6, p p. 182-197,2002.C. Xunxue, L. Miao and F. Tingjian, "Study of population diversity ofmultiobjective evolutionary algorithm based on immune and entropy principles," Proceedings of the 2001 Congress on in Evolutionary Computation, 2001, p p. 1316-1321 vol. 2.H. L. Fang, P. Ross and D. Come, "A promising genetic algorithmapproach to job-shop scheduling, rescheduling, and open-shop scheduling problems," in Proceedings of the Fijih international Conference on Genetic Algorithms, San Mateo, California, 1993, pp.375--382.C. Zhang, P. Li, Y. Rao, and S. Li, "A New Hybrid GAiSA Algorithmfor the Job Shop Scheduling Problem," in Lecture Notes in Computer Science, vol. 3448, G. Raidl and 1. Gottlieb, Eds.: Springer Berlin / Heidelberg, 2005, p p. 246-259.。