跳到正文

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.