The fuzzy completion time and customer request are two main uncertain factors in the process of the actual workshop production. The scheduling model under uncertain situation based on fuzzy mathematics is established in this paper. The average customer satisfaction acts as the objective of the model. Next, a novel hybrid algorithm is obtained through improving the mutation operation of genetic algorithm on the basis of simulated annealing algorithm. The customers can determine the priority through the process time of the process route to evaluate the effectiveness of the process route. The effectiveness and superiority of the proposed algorithm are verified through the contrast experiment with the existing algorithms.
Open Peer Review Details | |||
---|---|---|---|
Manuscript submitted on 21-8-2015 |
Original Manuscript | The Fuzzy Optimization Algorithm to Solve Customer’s Highest Satisfaction Under Fuzzy Time |
With the development of the fuzzy theory, fuzzy mathematics has been applied to the Job shop scheduling problems (JSP) under uncertain condition [1S. Fang, and D. Wang, Fuzzy Math and Fuzzy Optimization., Science Press: Beijing, 1997., 2F. Li, Y. Zhu, C. Yin, and X. Song, "Fuzzy programming for multi-objective fuzzy job shop scheduling with alternative machines through genetic algorithm, Advances in Natural Computation", Lect. Notes Comput. Sci., vol. 3611, pp. 992-1004, 2005.
[http://dx.doi.org/10.1007/11539117_138] ]. Chuan He et al. [3C. He, D. Qiu, and H. Guo, "Solving fuzzy job shop scheduling problem based on interval number theory", In: Proceedings of the 2012 International Conference on Information Technology and Software Engineering, Literature Notes in Electrical Engineering, vol. 211. 2013, pp. 393-40.
[http://dx.doi.org/10.1007/978-3-642-34522-7_42] ] tried to solve the fuzzy scheduling problems using the theory of interval number, which may describe the objective function as uncertain parameter through merging the particle swarm optimization (PSO) and genetic algorithm (GA). Jorge Puente et al. [4J. Puente, C.R. Vela, and I. González-Rodríguez, "Combining neighbourhoods in fuzzy job shop problems", Adv. Artif. Intel. Lect. Notes Comput. Sci., vol. 7023, pp. 343-352, 2011.] proposed a novel scheme for fuzzy JSP based on the change of the key block location of the task for searching community structure. Juan José Palacios et al. [5J.J. Palacios, J. Puente, I. González-Rodríguez, and C.R. Vela, "Hybrid tabu search for fuzzy job shop", Nat. Artif. Models Comput. Biol., Lect. Notes Comput. Sci., vol. 7930, pp. 376-385, 2013.
[http://dx.doi.org/10.1007/978-3-642-38637-4_39] ] proposed an improved optimization algorithm by mixing the tabu search algorithm and the genetic algorithm. The improved algorithm was applied to solve the problem of fuzzy completion time. From the present study for fuzzy JSP, it can be known that the fuzzy scheduling is mainly concentrated in the delivery and processing time [6T. Ning, Study of Application of Hybrid Quantum Algorithm in Vehicle Routing Problem, Dalian Maritime University: Dalian, 2013., 7D. Lei, "Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search", Int. J. Adv. Manuf. Technol., vol. 54, no. 9-12, pp. 1121-1128, 2011.
[http://dx.doi.org/10.1007/s00170-010-2989-4] ], and the number of considering the delivery and the processing time at the same time is very seldom. Therefore, this paper proposed an improved hybrid algorithm to maximize the customer satisfaction under the fuzzy condition based on the existing research results. The effective of proposed algorithm is verified with simulation examples.
According to the actual job shop scheduling, the average customer satisfaction is selected as the evaluation index of the improved algorithm model, that is shown as eq. 1:
(1) |
AIi represents the customer satisfaction of the workpiece Ji, whose reference point is the matching degree of between
completion time and delivery time of Ji. So the satisfaction can be calculated [8Y. Bo, Y. Baosheng, and X. Hao, "Job shop scheduling based on genetic algorithm under uncertain conditions", Mod. Manuf. Eng., vol. 10, pp. 52-56, 2012.] as follow:
(2) |
The area Sci bounded by membership function of fuzzy processing time’s central triangular fuzzy number of and horizontal axis represents the completion time of the workpiece Ni, the area SDi bounded by membership function of fuzzy delivery time’s symmetrical trapezoidal fuzzy number and horizontal axis represents the delivery time of the workpiece Ni.
The objective function of this experiment is to maximize the average customer satisfaction, this paper proposed an improved objective function considering the global searching capability of GA-SA, and the objective function is as follows:
(3) |
J represents the workpiece; M represents machining machine sets; Silk represents the start time of process l of workpiece ion machining k; cijk the completion time of process l of workpiece i on machining k; Ck represents the time when all the artifacts on the machine K are completed. Because of the goal of this paper is to maximize the customer satisfaction scheduling scheme, the fitness may be described as the average satisfaction of all the workpiece:
(4) |
Each piece comes with a penalty value αi, it represents the value of this piece is to give up on behalf of the production of the need to pay [9T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015., 10J. Shi, H. Jiao, and T. Chen, "Pareto multi-objective optimization of delivery under the flexible job shop scheduling punishment", Mech. Eng., vol. 48, no. 12, pp. 184-192, 2012.
[http://dx.doi.org/10.3901/JME.2012.12.184] ]. Each piece has two weight attributes, its own piece priority JPi and customer priority CPi, and each piece has a profit Pi. Therefore, such a rule can be set in this way to calculate the penalty value:
αi = JPi × (CPi Pi) | (5) |
Each piece comes with some reward value βj, which represents the workpiece within a specified time deadlines produce benefits that can be obtained [11X. Wang, Q. Chen, and N. Mao, "Mold project delivery device under random environment prediction", Comput. Integr. Manuf. Syst., vol. 18, no. 2, pp. 405-414, 2012.]. Punish according to the set value can be set rules as follow for calculating bonus values:
βj = JPj × (CPj Pj) | (6) |
If βj ≥ αi, then the production time of workpiece i may be replaced by workpiece j to meet the customer satisfaction.
Simulated Annealing Algorithm (SA) proposed by Kirkpatrick [12T. Ning, R. Chen, C. Guo, and X. Liang, "A scheduling strategy for dynamic vehicle routing problem base on double chains coding", Oper. Res. Trans., vol. 19, no. 2, pp. 72-83, 2015.] has been applied to many hybrid optimization problem [13S.K. Zhao, and S. Fang, "Job shop scheduling optimization based on genetic algorithm coding process and neighborhood search", Mech. Eng., vol. 12, no. 6, pp. 145-151, 2013.]. Its basic idea is that it may start with initial solution s and the initial parameter T 0 of temperature control, iterate the current solution “generate new solutions→ calculate the objective function difference →determine whether or not to accept”, and gradually decay to the current temperature T, the current solution when the algorithm terminates is the approximate optimal solution which has been obtained.
SA is an enhanced local search algorithm or the cycle of improvement algorithm, it can avoid the algorithm falling into local optimization through repeating the small and local improvement for the initial solution, and accept a lower solution with Blotzmann probability, so as to achieve a better solution.
Genetic algorithm was proposed by Professor Holland from the university of Michigan based on Darwin's theory of evolution and Mendel's theory of genetics. The algorithm is essentially a parallel global optimization algorithm [9T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015.]. There are three base factors in genetic algorithm such as: encoding, genetic operators and fitness function. The genetic algorithm is appropriate for the solving global optimization problems because of its global search ability, it is widely used in path planning [10J. Shi, H. Jiao, and T. Chen, "Pareto multi-objective optimization of delivery under the flexible job shop scheduling punishment", Mech. Eng., vol. 48, no. 12, pp. 184-192, 2012.
[http://dx.doi.org/10.3901/JME.2012.12.184] , 11X. Wang, Q. Chen, and N. Mao, "Mold project delivery device under random environment prediction", Comput. Integr. Manuf. Syst., vol. 18, no. 2, pp. 405-414, 2012.].
The specific steps of initial population generated randomly are as follows:
Operators of genetic algorithms generally includes three basic forms: selection, crossover and mutation, operators of a new generation through the group to achieve group evolution.
The fitness function related to the genetic algorithm convergence speed and ability to find the global optimum. Let the initial population is P = {P1, P2, P3, ..., Pk}, the size of the individual objective function value L (Pk), is the path length between each node.
Since the customer satisfaction is the main objective function of this paper, the evaluation function is designed to meet the request of the customers. Considering the dynamic characteristics of customer request, the main steps shown in Fig. (1) of the improved optimization algorithm are as follows:
Step 1: Initialize the population of Psize, annealing rate of λ, enter the machine sequence of M, fuzzy processing time matrix of T, fuzzy delivery time matrix of D, profit workpiece of P, the customer priority of CP, priority for workpiece itself of JP, calculate the initial temperature of t 0, end temperature of tend.
Step 2: Calculate the individual fitness value.
Step 3: Divide the population into five parts with different ways.
Step 4: Improved Genetic mutation simulated annealing algorithm, while using a large variation in rates.
Step 5: Genetic manipulation.
Step 6: If the temperature is keeping constant or less than the termination of a given temperature for 30 times, terminate searching: go to step 9; otherwise, go to step 7.
Step 7: Increase the number of iterations of genetic operators.
Step 8: Make annealing temperature lower, then go to step 2.
Step 9: Output optimal strategy and the corresponding routing.
Step 10: Judge the average satisfaction whether the process route to achieve the highest value of 1:yes, adopt a new strategy to recalculate routing; otherwise, go to step 11.
Step 11: Judge whether reach the highest satisfaction process route meets customer demand, that the optimal strategy corresponding output routings; otherwise, go to step 12.
Fig. (1) Improved algorithm model flow chart. |
Step 12: Judge whether the conditions of the process route in advance to meet the production or not. If yes, uses a new strategy to recalculate routing; otherwise, go to step 13.
Step 13: Judge whether customers’ cost increasing or not. If yes, uses a new strategy to recalculate routing; otherwise, output the process route.
Step 14: Produce in accordance with the process route processing.
Step 15: End of the calculation and output the optimal value.
In order to verify the effectiveness of the algorithm, the example of 3 (workpiece)3 (machines) in literature [14J. Gengzhao, and Y. Zou, "Scheduling based on genetic algorithm for job shop fuzzy", Comput. Integr. Manuf. Syst., vol. 8, no. 8, pp. 58-64, 2002.] and the example of 6 (workpiece) 6 (machines) in literature [15G. Xuan, and R. Cheng, Genetic Algorithms and Engineering, Tsinghua University Press: Beijing, 2004.] are used as the simulation data. Take the workpiece 2 as an example. The data of the second column of (4.5,5,5.5), since the value is in the second row, so its corresponding processing machine is No. 2 machine. Value 3 (4.5,5,5.5) said: The earliest completion time of a job the first three steps of 2 which is 4.5 minutes; the most likely completion time of five minutes, the latest completion time of 5.5 minutes. Take the workpiece 2 as an example similarly, its fuzzy delivery (4.5,6,7.5,9) means: the user can accept the earliest completion time: 4.5 minutes; user most satisfactory completion time of 6-7 minutes; users of the latest acceptable completion time of 9 minutes.
Considering the calculation speed and optimization capabilities of improved optimization algorithms, genetic algorithm’s parameters are set as: population size Na = 500, evolution generation is 50 generations, crossover probability is 0.8, mutation probability is 0.6, simulated annealing parameter is set as: Psize = 20, Pc = 0.8, λ = 0.95, terminate the temperature is 0.0001 °C, also running 20 times.
It can be seen from the Table 1 that the range of the fuzzy completion time with the improved algorithm is less than that with the algorithm in literature [9T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015.] and the satisfaction is higher than that in literature [9T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015.]. The result can verify the progressiveness of the propose method. Comparative experiments mainly for customers do not adjust the process route, namely the first time to obtain the optimal process route meet all customer and put them directly to the production and processing: visible when the customer requirements to shorten the construction period, average satisfaction will more high, which can be further confirmed the superiority and practicality of the vehicle improvement scheduling model.
For the problem of 3×3, the maximum average degree of satisfaction is 0.6729 after 20 calculations, which is more than the value of 0.5225 in literature [9T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015.]. The scheduling scheme with the highest satisfaction is : 2-3-1-2-3-2-1-3-1.
Aiming at the fuzzy scheduling problem under uncertain condition in actual production, this paper proposed a hybrid method based on genetic algorithm and simulation annealing algorithm to search the process route which can maximize the customer satisfaction. The effectiveness and progressiveness of the proposed algorithm are verified with comparison with the existing algorithms.
The authors confirm that this article content has no conflict of interest.
This work is partially supported by the Talented Young Scholars Growth Plan of Liaoning Province Education Department, China (No. LJQ2013048), the Scientific Project of Liaoning Province Education Department, China (No. L2014183); the Project of Liaoning BaiQianWan Talents Program, China (No.2014921062).
[1] | S. Fang, and D. Wang, Fuzzy Math and Fuzzy Optimization., Science Press: Beijing, 1997. |
[2] | F. Li, Y. Zhu, C. Yin, and X. Song, "Fuzzy programming for multi-objective fuzzy job shop scheduling with alternative machines through genetic algorithm, Advances in Natural Computation", Lect. Notes Comput. Sci., vol. 3611, pp. 992-1004, 2005. [http://dx.doi.org/10.1007/11539117_138] |
[3] | C. He, D. Qiu, and H. Guo, "Solving fuzzy job shop scheduling problem based on interval number theory", In: Proceedings of the 2012 International Conference on Information Technology and Software Engineering, Literature Notes in Electrical Engineering, vol. 211. 2013, pp. 393-40. [http://dx.doi.org/10.1007/978-3-642-34522-7_42] |
[4] | J. Puente, C.R. Vela, and I. González-Rodríguez, "Combining neighbourhoods in fuzzy job shop problems", Adv. Artif. Intel. Lect. Notes Comput. Sci., vol. 7023, pp. 343-352, 2011. |
[5] | J.J. Palacios, J. Puente, I. González-Rodríguez, and C.R. Vela, "Hybrid tabu search for fuzzy job shop", Nat. Artif. Models Comput. Biol., Lect. Notes Comput. Sci., vol. 7930, pp. 376-385, 2013. [http://dx.doi.org/10.1007/978-3-642-38637-4_39] |
[6] | T. Ning, Study of Application of Hybrid Quantum Algorithm in Vehicle Routing Problem, Dalian Maritime University: Dalian, 2013. |
[7] | D. Lei, "Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search", Int. J. Adv. Manuf. Technol., vol. 54, no. 9-12, pp. 1121-1128, 2011. [http://dx.doi.org/10.1007/s00170-010-2989-4] |
[8] | Y. Bo, Y. Baosheng, and X. Hao, "Job shop scheduling based on genetic algorithm under uncertain conditions", Mod. Manuf. Eng., vol. 10, pp. 52-56, 2012. |
[9] | T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybern. Syst. J., vol. 9, no. 15, pp. 1-5, 2015. |
[10] | J. Shi, H. Jiao, and T. Chen, "Pareto multi-objective optimization of delivery under the flexible job shop scheduling punishment", Mech. Eng., vol. 48, no. 12, pp. 184-192, 2012. [http://dx.doi.org/10.3901/JME.2012.12.184] |
[11] | X. Wang, Q. Chen, and N. Mao, "Mold project delivery device under random environment prediction", Comput. Integr. Manuf. Syst., vol. 18, no. 2, pp. 405-414, 2012. |
[12] | T. Ning, R. Chen, C. Guo, and X. Liang, "A scheduling strategy for dynamic vehicle routing problem base on double chains coding", Oper. Res. Trans., vol. 19, no. 2, pp. 72-83, 2015. |
[13] | S.K. Zhao, and S. Fang, "Job shop scheduling optimization based on genetic algorithm coding process and neighborhood search", Mech. Eng., vol. 12, no. 6, pp. 145-151, 2013. |
[14] | J. Gengzhao, and Y. Zou, "Scheduling based on genetic algorithm for job shop fuzzy", Comput. Integr. Manuf. Syst., vol. 8, no. 8, pp. 58-64, 2002. |
[15] | G. Xuan, and R. Cheng, Genetic Algorithms and Engineering, Tsinghua University Press: Beijing, 2004. |