具有学习效应的预制构件生产调度研究  

Study on the production scheduling of prefabricated components with learning effect

作　　者：李娜 马冉 李龙 张玉忠[2] LI Na;MA Ran;LI Long;ZHANG Yuzhong(School of Management Engineering,Qingdao University of Technology,Qingdao 266520,Shandong,China;Institute of Operations Research,School of Management,Qufu Normal University,Rizhao 276826,Shandong,China)

机构地区：[1]青岛理工大学管理工程学院,山东青岛266520 [2]曲阜师范大学管理学院,运筹研究院,山东日照276826

出　　处：《运筹学学报(中英文)》2025年第1期19-30,共12页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11501171,11771251);山东省自然科学基金(Nos.ZR2020MA028,ZR202102220230)。

摘　　要：本文研究了预制构件生产环境下具有学习效应的单机调度问题,建立以最小化最大加权完工时间为目标的调度模型。工件J_(j)的实际加工时长依赖于其开工时刻t,模型为p_(j)=b_(j)(a-bt),其中a和b是非负参数,b_(j)为工件J_(j)的基础加工时间。首先,分析所研究模型的离线最优排序。其次,研究该模型的在线调度问题,其中工件以时间在线的方式到达,提出一个竞争比为2-bb_(min)的最好可能的在线算法,其中b_(min)=min{b_(j)|1≤j≤n}。最后,对模型进行数值模拟,验证了该在线算法的有效性。The single machine online scheduling problem with learning effect in prefabricated component production environment is provided to minimize the maximum weighted completion time in this paper.More precisely,it asks for an assignment of a series of independent prefabricated jobs arrived over time to a single machine,where the information of each prefabricated job including its basic processing time b_(j),release time r_(j),and positive weight w_(j)is unknown in advance and is disclosed upon the arrival of this job.And the actual processing time of prefabricated job J_(j)with learning effect is p_(j)=b_(j)(a-bt),where a and b are non-negative parameters and t is the starting time of prefabricated job J_(j).In particular,a job may not be interrupted,i.e.,preemptive is not allowed,and the machine can process at most one job at a time.Firstly,the off-line optimal schedule of the problem is analyzed.Then,we investigate this schedule model in the online environment where jobs arrive online over time.Fortunately,we propose a deterministic online algorithm,and show that the online algorithm is best possible with a competitive ratio of 2-bb_(min),where b_(min)=min{b_(j)|1≤j≤n}.Furthermore,the effectiveness of the online algorithm is demonstrated by numerical experiments.

关 键 词：调度 单机 在线算法 学习效应 预制构件 

分 类 号：O221.2[理学—运筹学与控制论]