在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2025, Vol. 42 ›› Issue (5): 963-973.doi: 10.3969/j.issn.1005-3085.2025.05.012cstr: 32411.14.cjem.CN61-1269/O1.2025.05.012

• • 上一篇    下一篇

具有维护活动的松弛工期调度问题研究

吴 薇,  王吉波   

  1. 沈阳航空航天大学理学院，沈阳 110136
  • 收稿日期:2023-01-10 接受日期:2023-08-29 出版日期:2025-10-15 发布日期:2025-12-15
  • 基金资助:
    辽宁省兴辽英才计划 (XLYC2002017).

Research on Slack Due-date Assignment Scheduling with a Maintenance Activity

WU Wei,  WANG Jibo   

  1. School of Science, Shenyang Aerospace University, Shenyang 110136
  • Received:2023-01-10 Accepted:2023-08-29 Online:2025-10-15 Published:2025-12-15
  • Supported by:
    The Revitalization Talents Program of Liaoning Province (XLYC2002017).

摘要：

研究具有恶化和资源依赖性的维护活动与松弛工期的单机调度问题，其中工件的实际加工时间取决于工件是在维护活动之前还是之后进行加工的，工件的工期表示为其实际加工时间与松弛变量(即共同流量)之和。此问题的研究目的是确定工件的加工序列、维护活动所处的位置、松弛变量的大小以及维护活动所消耗的资源，以便其与提前、延迟完工时间和松弛变量的总成本达到最小。对于已知序列，求得松弛变量的值等于序列中某个位置工件的开始加工时间。通过分情况讨论维护活动的位置，将目标函数转化为分别只与工件加工顺序和只与资源有关的函数，然后将其转化为指派问题或利用向量匹配规则获得目标函数的最小值，最后给出了相应的算法，并证明此问题在多项式时间内可解。

关键词: 调度, 维护活动, 松弛工期, 单机, 多项式时间

Abstract:

This paper studied a single machine scheduling with a slack due-date and a maintenance activity which is deteriorating and resource-dependent, where the actual processing time of the job depends on whether it is processed before or after the maintenance activity. The due-date of the job is the sum of its actual processing time and the slack variable (i.e., the common flow allowance). The objective of this problem is to determine the sequence of the jobs, the location of the maintenance activity, the value of the slack variable, and the resources consumed by the maintenance activity to minimize the total cost of the earliness, tardiness, slack due-date and resource consumption. For a given sequence, the value of slack variable is the starting processing time of some job in the sequence, through the cases to discuss the location of the maintenance activity, the objective function is transformed into a function which is only related to the sequence of the jobs and the resources respectively. The minimum value of the objective function is obtained by transforming it into an assignment problem or using the vector matching rule. Finally, the corresponding algorithm is given and we prove that the problem is polynomially solvable.

Key words: scheduling, maintenance activity, slack due-date, single machine, polynomial time

中图分类号: