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

工程数学学报 ›› 2024, Vol. 41 ›› Issue (2): 377-385.doi: 10.3969/j.issn.1005-3085.2024.02.012

• • 上一篇    下一篇

具有位置相关权重的工期分配排序问题研究

吕丹阳1,2,  王吉波1,2   

  1. 1. 沈阳航空航天大学机电工程学院，沈阳  110136;
    2. 沈阳航空航天大学理学院，沈阳 110136
  • 收稿日期:2021-07-22 接受日期:2022-06-10 出版日期:2024-04-15 发布日期:2024-06-15
  • 基金资助:
    国家自然科学基金 (71471120)；辽宁省“兴辽英才计划”项目 (XLYC2002017).

Research on Due Date Assignment Scheduling Problems with Position-dependent Weights

LV Danyang1,2,  WANG Jibo1,2   

  1. 1. School of Machatronics Engineering, Shenyang Aerospace University, Shenyang 110136;
    2. School of Science, Shenyang Aerospace University, Shenyang 110136
  • Received:2021-07-22 Accepted:2022-06-10 Online:2024-04-15 Published:2024-06-15
  • Supported by:
    The National Natural Science Foundation of China (71471120); the Revitalization Talents Program of Liaoning Province (XLYC2002017).

摘要：

针对具有位置相关权重的工期分配排序问题进行了研究，其目标是在共同工期分配/松弛工期分配两种模式下，找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和，其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法，进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列，以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。

关键词: 位置相关权重, 排序, 共同/松弛工期, 延误

Abstract:

In this paper, the scheduling problems for due date assignment with position-dependent weights are studied. The goal is to find the optimal job processing sequence in two modes of common/slack due date assignment with the linear weighted sum of minimal due date and tardiness, where the weights are position-dependents weights. By proving a series of properties, the calculation methods of due date are obtained, and then the two kinds of due date assignment problems are transformed into functions related to job processing time. According to coefficient corresponding to each job, the specific solution algorithms are given to obtain the optimal job sequence, and the corresponding optimal common/slack due date. The algorithms are verified to solve the problems in polynomial time by numerical examples.

Key words: position-dependent weights, scheduling, common/slack due date, tardiness

中图分类号: