关键词: 单机, 在线, 钢箱梁小节段, 最大加权完工时间, 退化效应

Abstract: As a basic component of bridge assembly, a steel box girder section is in great demand, and the optimization of its production plan has a great influence on manufacturers, so the research on online production scheduling of the steel box girder section becomes more and more urgent and important. It has been shown that in the production scheduling of steel box girder sections, there is relatively little research on the online scheduling problem considering the degradation effect. Based on the existing research, this paper considers the single machine scheduling problem of steel box girder segment online production with degradation effect, aiming at minimizing the maximum weighted completion time, presents an online algorithm for the studied model, and implements the simulation. On the one hand, the model of online scheduling is perfected, which fills the blank area of existing research. On the other hand, the different weights of steel box girder sections and the degradation effect of processing are considered simultaneously, which provides a strategic reference for more realistic production scheduling problems and brings reliable selection of optimization schemes for managers.
   The two online scheduling problems studied in this paper consider the job weight and processing degradation effect, and minimize the maximum weighted completion time as the optimization goal. It is worth mentioning that we realize that the waiting strategy can reduce the losses caused by delaying orders with more weight that will soon be available, so we propose a deterministic online algorithm in polynomial time based on the waiting strategy, which is suitable for both problems studied. For the first problem studied, the processing time model is p_j=α_jt(t>0). First of all, it is concluded that the problem with the lower bound is 1+α_max. Then we prove offline optimal sorting methods for the problem, and design online algorithm H₁. Lastly we prove H₁ is the best possible online algorithm with the competitive ratio of 1+α_max by stepwise analysis. In response to the second question studied, the processing time model is p_j=α_j(A+Bt)(A>0). In using the same technique to draw the lower bound of the problem of 2+Bα_max, we prove offline optimal sorting methods for the problem, then design and analyse online algorithm H₂, and H₂ is the best possible online algorithm with the competitive ratio of 2+Bα_max.
   In conclusion, this paper gives the best possible online algorithms for both models studied. In view of the theoretical results obtained, this paper further carries out numerical simulation, using Python software 3.9 version to implement it. In numerical simulation, for the first problem Γ₁, by the application of randomly generating jobs instance of size n∈ {5,10,30,50,100,150,200,300,400}, respectively for 500 times and 1000 times of experiments, it is concluded that the average and maximum of performance ratio under each array are not more than the competitive ratio theoretically provided, so the correctness and effectiveness of online algorithm proposed in the paper are proved. For the second problem Γ₂, considering the changes in parameters A and B, we randomly set several groups of A and B where the number of regenerated jobs is n∈{10,50,100,200,300,400}, and conduct 500 and 1000 experiments respectively. It is concluded that the average value of the ratio of performance ratio to competition ratio under any array is not more than 1. This also illustrates that the correctness and effectiveness of online algorithm proposed in the paper are proved.
   In the future, it is worth expanding our research from several aspects for reference in the future work. In the actual production of steel box girder sections, a group of jobs of the same type may be placed in the same batch for processing, so the online scheduling of batch processing is worthy of attention. At the same time, in the face of large quantities of steel box girder segment processing, processing equipment may also be composed of more than one machine, so the parallel machining of the steel box girder segment is also the focus of the next research direction. Further, we can study the joint scheduling of product processing and distribution, which is also a very influential research direction.

Key words: single machine, online, section of steel box girder, maximum weighted completion time, deterioration