带有学习效应的多窗口分配调度问题研究

doi:10.12005/orms.2025.0378

摘要/Abstract

摘要： 本文在两种经典的工期窗口(共同工期窗口和松弛工期窗口)下,考虑给定工件具有多个共同工期窗口或松弛流的问题,将工件依据其特性划分为不同组,其中同一组内的工件共享相同的工期窗口或松弛流参数,且工件的加工时间并非固定不变,而是与学习效应紧密相关。核心目标为寻找一个最优的工件加工顺序以及确定多个共同工期窗口或松弛流的配置,以极小化工件的提前-延误成本、窗口开始时间/共同松弛流,以及窗口大小的线性加权和。通过理论分析与模型构建,当工件的分组数量确定时,该调度问题可以转化为一个指派问题,其时间复杂度为,且为给定的工件数。

关键词: 调度, 学习效应, 共同工期窗口, 共同松弛流, 提前-延误成本, 指派问题

Abstract: This paper provides insights into a specific and complex class of single-machine scheduling problems in the framework of two classical due-window settings i.e., common due-window and slack due-window. These problems involve jobs that are given multiple common due-windows or slack due-windows, where the jobs are divided into different groups based on their characteristics, and the jobs within the same group share the common due-window or slack due-window. In particular, the processing times of these jobs are not fixed, but are closely related to the learning effect, i.e., along with processing, the improvement of the worker’s skill or the optimization of the machine’s state leads to a reduction in the processing time of the subsequent jobs.
The core objective of the study is to find an optimal job processing sequence and determine multiple configurations of the common due-window or slack due-window, where the goal is to minimize the combined effect of several key performance metrics: earliness-tardiness costs for jobs, the cost of adjustments to the due-window start time, the efficiency of utilizing the common/slack due-window and the optimization of the size of the due-window. These metrics are considered together in the form of a linear weighted sum, aiming to balance the complex relationship among productivity, resource allocation and cost control.
Through theoretical analysis and model construction, it is found that the scheduling problem can be skillfully transformed into an assignment problem when the number of groupings of jobs is given, and then the problem can be solved in polynomial time. In this transformation process, we construct the corresponding mathematical model by exploiting the properties of the learning effect, the flexibility of the due-window and the regulating ability of the slack due-window.
Further, the Hungarian algorithm is used to solve the assignment problem where the time complexity is O(n³), where n is the number of jobs. This result not only provides a feasible path for solving this kind of complex single-machine scheduling problems, but also reveals the trend of the algorithm efficiency when the problem size (i.e., the number of jobs) increases, which provides a solid theoretical foundation for decision support in practical applications.
In summary, this study not only deepens the understanding of single-machine scheduling problems with learning effects and complex common/slack due-window constraints, but also provides effective solutions for efficiency improvement and cost optimization in real production scheduling through theoretical analysis and algorithms design.

Key words: scheduling, learning effect, common due-window, common flow-allowance, earliness-tardiness cost, assignment problem

中图分类号:

C934
O223

刘峥, 吕丹阳, 冯伟, 王吉波. 带有学习效应的多窗口分配调度问题研究[J]. 运筹与管理, 2025, 34(12): 78-84.

LIU Zheng, LYU Danyang, FENG Wei, WANG Jibo. Research on Multiple Due-window Assignment Scheduling Problems with Learning Effects[J]. Operations Research and Management Science, 2025, 34(12): 78-84.

参考文献

[1] 戴秦,郑兴山,张新功,等.总迟后相关的两个工况代理的单机排序问题[J].工业工程与管理,2014,19(6):78-82+88.
[2] 薛静,王吉波.具有恶化效应和共同工期窗口的极小化极大值单机排序问题[J].中国管理科学,2023,31(10):187-192.
[3] 万国华.排序与调度的理论、模型和算法[M].北京:清华大学出版社,2019.
[4] 徐娟年,马冉,韩雯雯,等.工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J].运筹学学报,2024,28(2):71-80.
[5] WANG J B, WANG J J. Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J]. International Journal of Production Research, 2015, 53(19): 5826-5836.
[6] SUN L, YU A J F, WU B. Single machine common flow allowance group scheduling with learning effect and resource allocation[J]. Computers & Industrial Engineering, 2020, 139: 106126.
[7] ZHU Z G, CHU F, YU Y G, et al. Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect[J]. Rairo-Operations Research, 2016, 50(4-5): 733-748.
[8] MUSTU S, EREN T. The single machine scheduling problem with sequence-dependent setup times and a learning effect on processing times[J]. Applied Soft Computing, 2018, 71: 291-306.
[9] WU Y B, WANG J J. Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times[J]. Neural Computing & Applications, 2016, 27(4): 937-943.
[10] HE H Y, ZHAO Y Z, MA X J, et al. Study on scheduling problems with learning effects and past sequence delivery times[J]. Mathematics, 2023, 11(19): (Article)4235.
[11] MOR B, MOSHEIOV G, SHAPIRA D. Flowshop scheduling with learning effect and job rejection[J]. Journal of Scheduling, 2020, 23(6): 631-641.
[12] TOKSARI M D, ATALAY B. Some scheduling problems with job rejection and a learning effect[J]. Computer Journal, 2023, 66(4): 866-872.
[13] ZHAO S. Resource allocation flowshop scheduling with learning effect and slack due window assignment[J]. Journal of Industrial and Management Optimization, 2021, 17(5): 2817-2835.
[14] CHEN K, HAO S Q, HUANG H L, et al. A group-dependent due window assignment scheduling problem with controllable learning effect[J]. Asia-PacificJournal of Operational Research, 2023, 40(3): 22500257.
[15] PEI J, ZHOU Y, YAN P, et al. A concise guide to scheduling with learning and deteriorating effects[J]. International Journal of Production Research, 2023, 61(6): 2010-2031.
[16] 岳青,万国华.考虑公共交货期窗口问询的退化工件排序问题[J].工业工程与管理,2015,20(6):42-47.
[17] MOR B. Single-machine minmax common due-window assignment and scheduling problems with convex resource allocation[J]. Engineering Optimization, 2019, 51(7): 1251-1267.
[18] JIA X, XUE J, WANG S Y, et al. Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times[J]. Mathematical Biosciences and Engineering, 2022, 19(9): 8923-8934.
[19] MOR B. Minmax common due-window assignment and scheduling on a single machine with two competing agents[J]. Journal of the Operational Research Society, 2018, 69(4): 589-602.
[20] ZHANG L, ZHANG Y Z, BAI Q G. Two-stage medical supply chain scheduling with an assignable common due window and shelf life[J]. Journal of Combinatorial Optimization, 2019, 37(1): 319-329.
[21] QIAN J, ZHAN Y. The due window assignment problems with deteriorating job and delivery time[J]. Mathematics, 2022, 10(10): (Article)1672.
[22] ROLIM G A, NAGANO M S. Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review[J].Computers & Industrial Engineering, 2020, 149: 106803.
[23] JIA X, LV D Y, HU Y, et al. Slack due-window assignment scheduling problem with deterioration effects and a deteriorating maintenance activity[J]. Asia-Pacific Journal of Operational Research, 2022, 39(6): 22500051.
[24] ZHANG L H, GENG X N, XUE J, et al. Single machine slack due window assignment and deteriorating jobs[J]. Journal of Industrial and Management Optimization, 2024, 20(4): 1593-1614.
[25] SUN X Y, GENG X N, WANG J Y, et al. Slack due window assignment scheduling in the single-machine with controllable processing times[J]. Journal of Industrial and Management Optimization, 2024, 20(1): 15-35.
[26] WANG J B, ZHANG B, LI L, et al. Due-window assignment scheduling problems with position-dependent weights on a single machine[J]. Engineering Optimization, 2020, 52(2): 185-193.
[27] WANG J B, WANG M Z. Single machine multiple common due dates scheduling with learning effects[J]. Computers and Mathematics with Applications, 2010, 60: 2998-3002.
[28] WANG J B, BAO H, WANG C. Research on multiple slack due-date assignments scheduling with position-dependent weights[J]. Asia-Pacific Journal of Operational Research, 2024, 41(5): 23500392.