Sử dụng thuật toán tiến hóa với quy tắc khả thi cho việc lập tiến độ sản xuất thông minh

Nội dung text: Sử dụng thuật toán tiến hóa với quy tắc khả thi cho việc lập tiến độ sản xuất thông minh

1. 14 Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 4(47) (2021) 14-19 Evolutionary algorithm with feasibility rule based constraint-handling method for intelligent production scheduling Sử dụng thuật toán tiến hóa với quy tắc khả thi cho việc lập tiến độ sản xuất thông minh Hoang Nhat Duca,b*, Nguyen Quoc Lama,b Hoàng Nhật Đứca,b*, Nguyễn Quốc Lâma,b aInstitute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam aViện Nghiên Cứu Và Phát Triển Công Nghệ Cao, Trường Đại Học Duy Tân, Đà Nẵng bFaculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam bKhoa Xây Dựng, Trường Đại Học Duy Tân, Đà Nẵng, Việt Nam (Ngày nhận bài: 23/4/2021, ngày phản biện xong: 26/4/2021, ngày chấp nhận đăng: 20/8/2021) Abstract Manufacturers constantly have to encounter fluctuated product demands. Accordingly, it is required to establish a production schedule that meets the future demands and concurrently has a low level of daily labor/materials’ deviation. This study constructs an evolutionary algorithm for achieving this task. The Differential Evolution (DE) algorithm and the feasibility rule based method for constraint handling are integrated to develop this evolutionary algorithm. The proposed approach has been verified by two cases of production scheduling. Keywords: Differential Evolution; Constrained Handling; Evolutionary Algorithm; Production Scheduling. Tóm tắt Với nhu cầu sản phẩm biến động theo thời gian, các nhà sản xuất cần thiết lập một kế hoạch sản xuất đáp ứng nhu cầu của sản phẩm và đồng thời có mức độ biến động về lao động hoặc nguyên vật liệu thấp. Nghiên cứu của chúng tôi xây dựng một phương pháp tối ưu hóa dựa trên thuật toán tiến hóa để ứng dụng cho việc lập kế hoạch sản xuất.Thuật toán Tiến hóa vi phân (DE) và phương pháp dựa trên quy tắc khả thi để xử lý ràng buộc được tích hợp để phát triển thuật toán tiến hóa này. Tính hiệu quả của phương pháp được đề xuất được minh chứng bởi hai bài toán kế hoạch sản xuất phẩm. Từ khóa: Tiến hóa vi phân; xử lý ràng buộc; thuật toán tiến hóa; lập kế hoạch sản xuất. 1. Introduction requirements. It is because production In real-world circumstances, manufacturers schedules with large fluctuations are very constantly have to deal with fluctuated costly to implement and often necessitate demands. Therefore, they need to establish a overtime cost in high production periods as production schedule that meets the required well as result in idle resources in low demands and concurrently reduces large production periods [1]. Therefore, it is discrepancies in daily labor/materials’ necessary to optimize the production schedule *Corresponding Author: Hoang Nhat Duc; Institute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam; Faculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam Email: hoangnhatduc@duytan.edu.vn
2. Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 15 to meet all required demands as well as to approach has been coded with Visual C#.NET obtain a relatively stable production quantity in Microsoft Visual Studio by the authors. over time. This task can be formulated as a 2. Evolutionary Algorithm based intelligent constrained optimization problem [2-6]. production scheduling Therefore, in this study, we apply the Differential Evolution (DE) algorithm [7, 8] The DE algorithm, proposed in [7], is a integrated with an advanced feasibility rule highly effective evolutionary method for based method for constraint handling [9] to dealing with unconstrained optimization solve the aforementioned constrained problems. The structure of DE is relatively optimization problem. simple and a computer implementing DE can be quickly established with few lines of The production scheduling problem can be computer code. The DE structure can be broken mathematically formulated as follows [1] [2]: down into four steps: (i) population PP 2 initialization, (ii) mutation, (iii) crossover, and Min. fXS tt (1) tt 11 (iv) selection [5, 10-12]. Nevertheless, the DE metaheuristic is not readily applicable for s.t. constrained optimization tasks. Therefore, it is required to utilize a constraint handling method Stt 0 (2) coupled with the DE algorithm [13-15]. In this SSAllowMax 0 (3) study, to construct an evolutionary method used tt for intelligent production scheduling, the X , S t t are integers (4) FRBCH method put forward by Deb [9] has been integrated into the structure of DE. With St is computed as follows: the FRBCH method, the DE’s objective function is revised as follows: SSXD tttt 1 (5) F(X ) if g j (x) 0 j where P is the number of time periods to be F(X ) m (6) considered; Dt is the demanded number of units fmax  g j (x) j 1 in t. St denotes the number of units in storage in t. Xt is the number of units produced in t. where fmax represents the objective function As mentioned earlier, this work aims at value of the worst feasible candidate. establishing an evolutionary algorithm based The FRBCH-DE integration used for approach for optimizing the production intelligent production scheduling has been scheduling task. The DE, as a powerful developed in Microsoft Visual Studio Visual evolutionary algorithm, is chosen in this study with C#.NET programming language. Fig. 1 to achieve the stated research objective. The demonstrates the interface of proposed feasibility rule based constraint-handling computer program. Fig. 2 shows the intelligent (FRBCH) method is applied [9] to obtain production scheduling problem coded as a class solutions satisfying all of the constraints. The in Visual C#. Fig. 3 demonstrates the revised DE algorithm integrated with the FRBCH objective function calculation.
3. 16 Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 Fig. 1. Interface of the FRBCH-DE based intelligent production scheduling Fig. 2. Production scheduling class definition Fig. 3. The revised objective function
4. Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 17 3. Program applications In this section of the article, two case studies have been used to verify the capability of the As mentioned earlier, the objective of this proposed approach. The first case study involves study is to construct a production schedule that the production planning over 7 periods. In the meets the required demands and concurrently second case study, the number of planning reduces large discrepancies in daily periods is 12. The demanded numbers of units labor/materials’ requirements. The reason is for the first and the second optimization problem that production schedules with large are shown in Table 1 and Table 2, respectively. fluctuations are very costly to execute and often The production schedules for the first and the result in extensive uses of resources in high second problems optimized by the FRBCH-DE production periods as well as idle resources in are reported in Fig. 5 and Fig. 6, respectively. It low production periods. Accordingly, this study can be seen from these two figures that the employs FRBCH-DE for developing intelligent proposed metaheuristic has helped to find production plans given data on the future production schedules featuring low degree of product demands. The computer program based fluctuations in the numbers of produced units for on FRBCH-DE is demonstrated in Fig. 4. both case studies. Fig. 4. FRBCH-DE computer program for developing intelligent production plans Table 1 Production scheduling result for the Table 2 Production scheduling result for the case study 1 case study 2 Period Dt Xt St Period Dt Xt St 1 10 12 2 1 10 13 3 2 15 13 0 2 15 12 0 3 8 11 3 3 8 11 3 4 12 10 1 4 12 12 3 5 6 10 5 5 6 10 7 6 4 10 11 6 4 11 14 7 22 11 0 7 22 10 2 8 12 11 1 9 8 11 4 10 15 11 0 11 7 9 2 12 11 9 0
5. 18 Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 Fig. 5. Results of Dt, Xt, and St for the case study 1 Fig. 6. Results of Dt, Xt, and St for the case study 2 4. Concluding remarks References This study has developed and validated a [1] E. Castillo , A. J. Gonejo , P. Pedregal , R. Garciá , production scheduling optimization program and N. Alguacil, Building and Solving Mathematical Programming Models in Engineering and Science: based on the utilization of the DE evolutionary John Wiley & Sons, 2001. algorithm and the FRBCH method. The [2] B.-T. Nguyen, N.-D. Hoang, T.-H. Vu, and L. T. integrated approach, denoted as FRBCH-DE, Phan, "Giải bài toán tối ưu nguồn lực trong lập kế hoạch sản xuất các cấu kiện chế tạo sẵn trong dự án has been developed with Visual C#.NET. Case xây dựng với phương pháp quy hoạch phi tuyến," In studies involving the determination of 7 and 12 Proc. of ATCESD 2016, Da Nang, Vietnam, 2016. decision variables have been employed to [3] J. O. McClain, L. Joseph Thomas, and E. N. Weiss, verify the capability of FRBCH-DE. "Efficient Solutions to a Linear Programming Model for Production Scheduling With Capacity Experimental result shows that FRBCH-DE is Constraints and No Initial Stock," IIE Transactions, able to find a good set of decision variables that vol. 21, pp. 144-152, 1989/06/01 1989. feature a low objective function and satisfy all [4] S. Rasmussen, "Production Planning in the Linear Programming Model: Linear Programming," in the required constraints.
6. Hoang Nhat Duc, Nguyen Quoc Lam / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 4(47) (2021) 14-19 19 Production Economics: The Basic Theory of Evolution and Support Vector Machine Production Optimisation, ed Berlin, Heidelberg: Classification," Mathematical Problems in Springer Berlin Heidelberg, 2011, pp. 211-223. Engineering, vol. 2021, p. 6647829, 2021/02/20 [5] N.-D. Hoang, Q.-L. Nguyen, and Q.-N. Pham, 2021. "Optimizing Construction Project Labor Utilization [11] N. Đ. Hoàng, Q. L. Nguyễn, and Q. N. Phạm, "Tối Using Differential Evolution: A Comparative Study ưu hóa tiến độ và chi phí cho dự án xây dựng sử of Mutation Strategies," Advances in Civil dụng thuật toán tiến hóa vi phân," Tạp Chí Khoa Engineering, vol. 2015, p. 8, 2015. Học và Công Nghệ, Đại Học Duy Tân, vol. 1, pp. [6] M.-Y. Cheng, D.-H. Tran, and N.-D. Hoang, "Fuzzy 135–141, 2015. clustering chaotic-based differential evolution for [12] N.-D. Hoang, "NIDE: A Novel Improved resource leveling in construction projects," Journal Differential Evolution for Construction Project of Civil Engineering and Management, vol. 23, pp. Crashing Optimization," Journal of Construction 113-124, 2017/01/02 2017. Engineering, vol. 2014, p. 7, 2014. [7] R. Storn and K. Price, "Differential Evolution – A [13] N. D. Hoang, "FR-DE Excel Solver: Differential Simple and Efficient Heuristic for global Evolution with Deb’s feasibility rules for solving Optimization over Continuous Spaces," Journal of constrained optimization problems in civil Global Optimization, vol. 11, pp. 341-359, engineering," DTU Journal of Science and December 01 1997. Technology 04 (35), 2019. [8] K. Price, R. M. Storn, and J. A. Lampinen, [14] R. M. John, G. R. Robert, and B. F. David, "A Differential Evolution - A Practical Approach to Survey of Constraint Handling Techniques in Global Optimization: Springer-Verlag Berlin Evolutionary Computation Methods," in Heidelberg, 2005. Evolutionary Programming IV: Proceedings of the [9] K. Deb, "An efficient constraint handling method Fourth Annual Conference on Evolutionary for genetic algorithms," Computer Methods in Programming, ed: MITP, 1995, p. 1. Applied Mechanics and Engineering, vol. 186, pp. [15] H. Nhat-Duc and L. Cong-Hai, "Sử dụng thuật toán 311-338, 2000/06/09/ 2000. tiến hóa vi phân cho các bài toán tối ưu hóa kết cấu [10] T. V. Dinh, H. Nguyen, X.-L. Tran, and N.-D. với công cụ DE-Excel solver," DTU Journal of Hoang, "Predicting Rainfall-Induced Soil Erosion Science and Technology, vol. 03, pp. 97-102, 2019. Based on a Hybridization of Adaptive Differential