Research on Online Production Scheduling of Steel Box Girder Section with Degradation Effect
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 produc-tion 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 pj=α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 H1.Lastly we prove H1 is the best possible online algorithm with the competitive ratio of 1+αmax by stepwise analysis.In response to the second ques-tion studied,the processing time model is pj=α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 H2,and H2 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 Γ1,by the application of randomly genera-ting 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 Γ2,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.
single machineonlinesection of steel box girdermaximum weighted completion timedeterioration
国家科技期刊平台
NSTL
万方数据
