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

doi:10.15960/j.cnki.issn.1007-6093.2025.01.002

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (1): 19-30.doi: 10.15960/j.cnki.issn.1007-6093.2025.01.002

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

李娜¹, 马冉¹^,*(), 李龙¹, 张玉忠²

1. 青岛理工大学管理工程学院, 山东青岛 266520
2. 曲阜师范大学管理学院, 运筹研究院, 山东日照 276826

收稿日期:2022-01-06 出版日期:2025-03-15 发布日期:2025-03-08
通讯作者: 马冉 E-mail:sungirlmr@126.com
基金资助:
国家自然科学基金(11501171);国家自然科学基金(11771251);山东省自然科学基金(ZR2020MA028);山东省自然科学基金(ZR202102220230)

Study on the production scheduling of prefabricated components with learning effect

Na LI¹, Ran MA¹^,*(), Long LI¹, Yuzhong ZHANG²

1. School of Management Engineering, Qingdao University of Technology, Qingdao 266520, Shandong, China
2. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2022-01-06 Online:2025-03-15 Published:2025-03-08
Contact: Ran MA E-mail:sungirlmr@126.com

摘要/Abstract

摘要：

本文研究了预制构件生产环境下具有学习效应的单机调度问题, 建立以最小化最大加权完工时间为目标的调度模型。工件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}。最后, 对模型进行数值模拟, 验证了该在线算法的有效性。

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

Abstract:

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.

Key words: scheduling, single machine, online algorithm, learning effect, prefabricated components

中图分类号:

O221.2

李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.

Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect[J]. Operations Research Transactions, 2025, 29(1): 19-30.

图/表 2

参考文献 18

1	Dong Y , Maravelias C T . Terminal inventory level constraints for online production scheduling[J]. European Journal of Operational Research, 2021, 295 (1): 102- 117. doi: 10.1016/j.ejor.2021.02.029
2	Zhang Y T , Liu J . Emergency logistics scheduling under uncertain transportation time using online optimization methods[J]. IEEE Access, 2021, 9, 36995- 37010. doi: 10.1109/ACCESS.2021.3061454
3	Ibrahim I M . Task scheduling algorithms in cloud computing: A review[J]. Turkish Journal of Computer and Mathematics Education, 2021, 12 (4): 1041- 1053.
4	Samorani M , Blount L G . Machine learning and medical appointment scheduling: Creating and perpetuating inequalities in access to health care[J]. American Journal of Public Health, 2020, 110 (4): 440- 441. doi: 10.2105/AJPH.2020.305570
5	Ling H F , Su Z L , Jiang X L , et al. Multi-objective optimization of integrated civilian-military scheduling of medical supplies for epidemic prevention and control[J]. Multidisciplinary Digital Publishing Institute, 2021, 9 (2): 126.
6	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23 (4): 95- 104. doi: 10.15960/j.cnki.issn.1007-6093.2019.04.008
7	张玉忠, 李曙光. 带树层次加工集约束的调度问题[J]. 运筹学学报, 2020, 24 (4): 107- 112. doi: 10.15960/j.cnki.issn.1007-6093.2020.04.009
8	Pruhs K , Sgall J , Torng E . Online scheduling[J]. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 2004, 1, 1- 41.
9	Karlin A R , Manasse M S , Rudolph L , et al. Competitive snoopy caching[J]. Algorithmica, 1988, 3 (1): 79- 119.
10	Biskup D . Single-machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115 (1): 173- 178. doi: 10.1016/S0377-2217(98)00246-X
11	Mosheiov G . Scheduling problems with a learning effect[J]. European Journal of Operational Research, 2001, 132 (3): 687- 693. doi: 10.1016/S0377-2217(00)00175-2
12	Ho K I J , Leung J Y T , Wei W D . Complexity of scheduling tasks with time-dependent execution times[J]. Information Processing Letters, 1993, 48 (6): 315- 320.
13	Biskup D . A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008, 188 (2): 315- 329.
14	Feng Q , Yuan J J . NP-hardness of a multicriteria scheduling on two families of jobs[J]. OR Transactions, 2007, 11 (4): 121- 126.
15	Li W J . A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015, 32 (4): 1550030.
16	Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326.
17	Chai X , Lu L F , Li W H , et al. Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2018, 35 (6): 1850048.
18	Gawiejnowicz S . A review of four decades of time-dependent scheduling: Main results, new topics, and open problems[J]. Journal of Scheduling, 2020, 23 (1): 3- 47.

[1]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[2]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[3]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[4]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[5]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[6]	何胜学. 基于超级时空网络的公交车辆调度模型及3M进化算法[J]. 运筹学学报, 2023, 27(3): 68-82.
[7]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.
[8]	于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.
[9]	万龙, 黄晓莉, 梅嘉杰. PDD规则下最小化最大延误调度问题[J]. 运筹学学报, 2022, 26(4): 75-86.
[10]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[11]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[12]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[13]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[14]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.
[15]	陈峰. 运筹学在整车物流智能调度决策支持系统中的研究与应用[J]. 运筹学学报, 2021, 25(3): 37-73.

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

Study on the production scheduling of prefabricated components with learning effect

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价