考虑退化效应的钢箱梁小节段在线生产调度研究

Research on Online Production Scheduling of Steel Box Girder Section with Degradation Effect

钢箱梁小节段作为桥梁组装的基础构件,需求量非常大,其生产方案的优化对制造商有着很大的影响,针对钢箱梁小节段的在线生产调度研究就显得愈发迫切与重要。本文研究工件具有退化效应的钢箱梁小节段单机在线生产问题,建立了的两个不同的退化加工模型,以最小化最大加权完工时间为优化目标。首先,对所研究的两个问题,都证明了最优排序应具有的性质。然后,对加工时长模型为pj=αjt(t>0)的问题,给出了一个竞争比为1+αmax最好可能的在线算法,其中αj为工件Jj的退化因子;同样,对加工时长模型为pj=αj(A+Bt)(A>0)的问题,也给出了一个竞争比为2+Bαmax最好可能的在线算法。最后,对文中的两个在线模型都进行了数据模拟,验证了在线算法的有效性与正确性,也为制造商的生产管理提供了有效参考。

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 1.Lastly we prove H 1 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 2,and H 2 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 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Γ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.