欧美亚洲国产精品久久高清,国产精品欧美久久久久无广告,99精品欧美一区二区三区

                                                  跳到正文

                                                  Hitachi

                                                  研究開發

                                                  Industrial AI Blog from China

                                                  A novel optimization algorithm for job-shop production scheduling

                                                  25 February 2022

                                                  Xue Zhang

                                                  Xue Zhang
                                                  Hitachi China Research Laboratory, Hitachi (China) Ltd.

                                                  Background

                                                  With intensifying market competition and the increasing diversification of customer needs, manufacturers are being driven to enhance competitiveness by reducing cost and improving production efficiency either through digital factory and transformation, or production improvement and lean production. We visited and surveyed over 30 enterprises in China and found that production scheduling in production is very important role in realizing efficiency, flexibility and reliability while maintaining or optimizing cost levels. This led us to believe that job-shop scheduling or job-shop problem (JSP) that minimize the completion time of production lines could be used to significantly improve production efficiency and help facilitate agile production as the use of JSP not only addresses customer production orders in a more scientific manner but also significantly improves an enterprise’s production performance indicators by optimizing the utilization of materials, equipment, human resource and as well as production process control to achieve agile production.

                                                  Figure1
                                                  Figure 1. Optimized points in workflow of manufacturing by production scheduling

                                                  Difficulties in production scheduling

                                                  In the family of production scheduling problems, the job-shop problem is a typical approach to process couple of jobs at a set of shops. Previous studies in job-shop scheduling problems achieved solutions using exhaustive search methods or optimized search range with a simple coding approach [1-8]. However, with this coding method, multiple codes correspond to the same job schedule, and these codes are also regarded as repeated codes. While it can be judged in the decoding process whether multiple codes belong to the same job schedule or not, this can only be done after the codes are parsed into a job schedule through a complicated decoding process. Thus it is a waste of time to conduct encoding and decoding calculations during algorithm operation as multiple codes may correspond to the same job schedule.

                                                  Figure2
                                                  Figure 2. Job-shop schedule coding to individual

                                                  How we tackled the problems

                                                  Through novel construction, we proposed an algorithm using a new coding method named “consistency operation in genetics.” In the proposed algorithm, the crossover and mutation operation will generate many new abundant child codes from parent codes. More importantly, the consistency operation uses a 2-layer combination code of process-shop sequence and performs consistent coding according to the consistent coding rules. According to the rules, a series of position exchanges in a code are performed on the job segment to obtain a new code. All codes corresponding to the same job schedule can be transformed into a unique code. In this way, during the operation of the algorithm, for any job schedule, only one analysis and algorithm calculation are performed. With consistency operation, all codes corresponding to the same job schedule can be transformed into a unique code according to the operation rules. The novel algorithm transforming all codes corresponding to the same job schedule into a unique code, which will largely decrease repeated encoding and decoding calculation, will save a lot of time during algorithm operation.

                                                  Figure3
                                                  Figure 3. Consistency operation for improving algorithm

                                                  Assessing the performance of our algorithm

                                                  Using a benchmark dataset [9], we compared our approach with other typical approaches previously applied. We chose approximately 14 types of job-shop production scheduling problem instances of multiple scenarios with different numbers of shops and jobs. In the comparison, we set the same objectives of completion time for problem instances, with same constraints and conditions. The comparison result indicated that our proposed algorithm was able to achieve the best performance with the smallest completion time for all instances. At the same time, our approach also showed good performance on convergence features, converging quickly to a better result with less completion time in most cases.

                                                  Figure4
                                                  Figure 4. Convergence situation of sample instances by different approaches

                                                  Summary

                                                  We proposed an algorithm for production planning that leverages its process based on requirements from multiple customers. We verified the algorithm on food production and worker scheduling with the cooperation of a specific customer, and achieved better performance compared with other benchmark tools such as Gurobi.

                                                  With the growing trend towards digital and intelligent transformation in China, there will be many good business opportunities to apply AI technology in production scheduling as manufacturing becomes increasingly digitalized to realize smart factories.

                                                  For more details, we encourage you to read our paper [10].

                                                  Acknowledgements

                                                  Many thanks to my co-authors Dai Zhang and Xiaolei Hu with whom this research work was jointly executed.


                                                  References

                                                  [1]
                                                  Y.F. Ji, and D.X. Zhang, “Constraint Satisfaction Adaptive Neural Network to Solve Shop Scheduling Problem,” Computer and Digital Engineering, 2006, vol. 34, no. 9, pp. 22-24,51.
                                                  [2]
                                                  J.F. Liu, G.C. Zhou, and J.J. Pan, “Heuristic algorithm based on tabu search to solve the sphere Packing problem,” Application Research of Computers, 2011, vol.28, no.3, pp. 892-894.
                                                  [3]
                                                  K. Akram, K. Kamal, and A. Zeb, “Fast simulated annealing hybridized with quenching for solving job shop scheduling problem,” Applied Soft Computing, 2016, vol. 49, pp. 510-523.
                                                  [4]
                                                  B.J. Park, H.R. Choi, and H.S. Kim, “A hybrid genetic algorithm for the job shop scheduling problems,” Computers & Industrial Engineering, 2003, vol. 45, no.4, pp. 597–613.
                                                  [5]
                                                  S. Noor, M. IkramUllah Lali, and M. Saqib Nawaz, “Solving job shop scheduling problem with genetic algorithm,” Science International (Lahore), 2015, vol. 27, no. 4, pp. 3367-3371.
                                                  [6]
                                                  N. Kundakc?, O. Kulak, "Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem," Computers & Industrial Engineering, 2016, vol. 96, no. 6, pp. 31-51.
                                                  [7]
                                                  C.L. Yu, Q. Semeraro, and A. Matta, "A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility," Computers & Operations Research, 2018, vol. 100, no. 12, pp. 211-229.
                                                  [8]
                                                  X.L. Luo, Q. Qian, and Y.F. Fu, "Improved Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem," Procedia Computer Science, 2020, vol. 166, pp. 480-485.
                                                  [9]
                                                  J.E. Beasley, “OR-Library: distributing test problems by electronic mail,” Journal of the Operational Research Society, 1990, vol. 41, no. 11, pp. 1069-1072.
                                                  http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
                                                  [10]
                                                   X. Zhang, D. Zhang, and X. Hu, "A Novel Optimization Algorithm for Job-Shop Production Scheduling," 2021 IEEE 6th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA), 2021, pp. 183-189. doi: 10.1109/ICCCBDA51879.2021.9442504.
                                                  欧美亚洲国产精品久久高清,国产精品欧美久久久久无广告,99精品欧美一区二区三区