运筹与管理2025，Vol.34Issue(12)：78-84,7.DOI:10.12005/orms.2025.0378
带有学习效应的多窗口分配调度问题研究
Research on Multiple Due-window Assignment Scheduling Problems with Learning Effects
摘要
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 optimiza-tion 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 configu-rations 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(n3),where n is the number of jobs.This result not only provides a feasible path for solving this kind of com-plex 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分类
管理科学引用本文复制引用
刘峥,吕丹阳,冯伟,王吉波..带有学习效应的多窗口分配调度问题研究[J].运筹与管理,2025,34(12):78-84,7.基金项目
国家自然科学基金资助项目(71471120) （71471120）
