本文研究了预制构件生产环境下具有学习效应的单机调度问题, 建立以最小化最大加权完工时间为目标的调度模型。工件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.