The Open Cybernetics & Systemics Journal




(Discontinued)

ISSN: 1874-110X ― Volume 12, 2018

The Fuzzy Optimization Algorithm to Solve Customer’s Highest Satisfaction Under Fuzzy Time



Liang Xu, Huang Ming, Ning Tao*, Dang Xinyang
Institute of Software, Dalian Jiaotong University, Dalian, China, 116045

Abstract

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.

Keywords: Genetic algorithm, membership function, penalty value, priority, simulated annealing algorithm.


Article Information


Identifiers and Pagination:

Year: 2016
Volume: 10
First Page: 61
Last Page: 66
Publisher Id: TOCSJ-10-61
DOI: 10.2174/1874110X01610010061

Article History:

Received Date: 21/8/2015
Revision Received Date: 1/10/2015
Acceptance Date: 2/10/2015
Electronic publication date: 30/04/2016
Collection year: 2016

© Xu et al.; Licensee Bentham Open.

open-access license: This is an open access article licensed under the terms of the Creative Commons Attribution-Non-Commercial 4.0 International Public License (CC BY-NC 4.0) (https://creativecommons.org/licenses/by-nc/4.0/legalcode), which permits unrestricted, non-commercial use, distribution and reproduction in any medium, provided the work is properly cited.


* Address correspondence to this author at the Institute of Software, Dalian Jiaotong University; Tel/Fax: 8613940901029; E-mail:daliannt@126.com





1. INTRODUCTION

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.

2. ANALYSIS OF THE IMPROVED ALGORITHM

2.1. Evaluation Index of Improved Optimization Algorithm

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.

2.2. Mathematical Model of Improved Optimization Algorithm

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.

3. DESCRIPTION OF IMPROVED OPTIMIZATION ALGORITHM

3.1. Simulated Annealing Algorithm

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.

3.2. Genetic Algorithm

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.].

3.2.1. Population Initialization

The specific steps of initial population generated randomly are as follows:

  1. Generated chromosomes randomly;
  2. If the chromosomes meet the requirements of preserving the node, go to c, else go to a;
  3. Repeat a and b until generate more than enough chromosome meeting the requirements to form initial population

3.2.2. Operator Design

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.

3.2.3. Fitness Function

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.

3.3. Improved Optimization Algorithm

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.

4. ANALYSIS OF THE SIMULATION EXPERIMENT

4.1. The Comparison of the Datas

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.

Table 1

3 × 3 Comparison on fuzzy completion time and satisfaction.




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.

4.2. Analysis of the Experimental Result

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.

CONCLUSION

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.

CONFLICT OF INTEREST

The authors confirm that this article content has no conflict of interest.

ACKNOWLEDGEMENTS

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).

REFERENCES

[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.
Track Your Manuscript:


Endorsements



"Open access will revolutionize 21st century knowledge work and accelerate the diffusion of ideas and evidence that support just in time learning and the evolution of thinking in a number of disciplines."


Daniel Pesut
(Indiana University School of Nursing, USA)

"It is important that students and researchers from all over the world can have easy access to relevant, high-standard and timely scientific information. This is exactly what Open Access Journals provide and this is the reason why I support this endeavor."


Jacques Descotes
(Centre Antipoison-Centre de Pharmacovigilance, France)

"Publishing research articles is the key for future scientific progress. Open Access publishing is therefore of utmost importance for wider dissemination of information, and will help serving the best interest of the scientific community."


Patrice Talaga
(UCB S.A., Belgium)

"Open access journals are a novel concept in the medical literature. They offer accessible information to a wide variety of individuals, including physicians, medical students, clinical investigators, and the general public. They are an outstanding source of medical and scientific information."


Jeffrey M. Weinberg
(St. Luke's-Roosevelt Hospital Center, USA)

"Open access journals are extremely useful for graduate students, investigators and all other interested persons to read important scientific articles and subscribe scientific journals. Indeed, the research articles span a wide range of area and of high quality. This is specially a must for researchers belonging to institutions with limited library facility and funding to subscribe scientific journals."


Debomoy K. Lahiri
(Indiana University School of Medicine, USA)

"Open access journals represent a major break-through in publishing. They provide easy access to the latest research on a wide variety of issues. Relevant and timely articles are made available in a fraction of the time taken by more conventional publishers. Articles are of uniformly high quality and written by the world's leading authorities."


Robert Looney
(Naval Postgraduate School, USA)

"Open access journals have transformed the way scientific data is published and disseminated: particularly, whilst ensuring a high quality standard and transparency in the editorial process, they have increased the access to the scientific literature by those researchers that have limited library support or that are working on small budgets."


Richard Reithinger
(Westat, USA)

"Not only do open access journals greatly improve the access to high quality information for scientists in the developing world, it also provides extra exposure for our papers."


J. Ferwerda
(University of Oxford, UK)

"Open Access 'Chemistry' Journals allow the dissemination of knowledge at your finger tips without paying for the scientific content."


Sean L. Kitson
(Almac Sciences, Northern Ireland)

"In principle, all scientific journals should have open access, as should be science itself. Open access journals are very helpful for students, researchers and the general public including people from institutions which do not have library or cannot afford to subscribe scientific journals. The articles are high standard and cover a wide area."


Hubert Wolterbeek
(Delft University of Technology, The Netherlands)

"The widest possible diffusion of information is critical for the advancement of science. In this perspective, open access journals are instrumental in fostering researches and achievements."


Alessandro Laviano
(Sapienza - University of Rome, Italy)

"Open access journals are very useful for all scientists as they can have quick information in the different fields of science."


Philippe Hernigou
(Paris University, France)

"There are many scientists who can not afford the rather expensive subscriptions to scientific journals. Open access journals offer a good alternative for free access to good quality scientific information."


Fidel Toldrá
(Instituto de Agroquimica y Tecnologia de Alimentos, Spain)

"Open access journals have become a fundamental tool for students, researchers, patients and the general public. Many people from institutions which do not have library or cannot afford to subscribe scientific journals benefit of them on a daily basis. The articles are among the best and cover most scientific areas."


M. Bendandi
(University Clinic of Navarre, Spain)

"These journals provide researchers with a platform for rapid, open access scientific communication. The articles are of high quality and broad scope."


Peter Chiba
(University of Vienna, Austria)

"Open access journals are probably one of the most important contributions to promote and diffuse science worldwide."


Jaime Sampaio
(University of Trás-os-Montes e Alto Douro, Portugal)

"Open access journals make up a new and rather revolutionary way to scientific publication. This option opens several quite interesting possibilities to disseminate openly and freely new knowledge and even to facilitate interpersonal communication among scientists."


Eduardo A. Castro
(INIFTA, Argentina)

"Open access journals are freely available online throughout the world, for you to read, download, copy, distribute, and use. The articles published in the open access journals are high quality and cover a wide range of fields."


Kenji Hashimoto
(Chiba University, Japan)

"Open Access journals offer an innovative and efficient way of publication for academics and professionals in a wide range of disciplines. The papers published are of high quality after rigorous peer review and they are Indexed in: major international databases. I read Open Access journals to keep abreast of the recent development in my field of study."


Daniel Shek
(Chinese University of Hong Kong, Hong Kong)

"It is a modern trend for publishers to establish open access journals. Researchers, faculty members, and students will be greatly benefited by the new journals of Bentham Science Publishers Ltd. in this category."


Jih Ru Hwu
(National Central University, Taiwan)


Browse Contents




Webmaster Contact: info@benthamopen.net
Copyright © 2023 Bentham Open