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

工程数学学报 ›› 2024, Vol. 41 ›› Issue (5): 947-961.doi: 10.3969/j.issn.1005-3085.2024.05.011

• • 上一篇    下一篇

基于位置权重的窗口指派单机排序问题

赵  爽   

  1. 沈阳体育学院公共课教研部，沈阳  110102
  • 收稿日期:2023-07-05 接受日期:2024-04-14 出版日期:2024-10-15
  • 基金资助:
    辽宁省教育厅基本科研项目 (JYTMS20231334).

Due Window Assignment Scheduling Problems with Position-dependent Weights on a Single-machine

ZHAO Shuang   

  1. Department of Basic, Shenyang Sport University, Shenyang 110102
  • Received:2023-07-05 Accepted:2024-04-14 Online:2024-10-15
  • Supported by:
    The Science Research Foundation of Educational Department of Liaoning Province (JYTMS20231334).

摘要：

研究了基于位置权重的窗口指派排序问题，机器限定为一台，其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和，以找到其最优工件加工序列以及窗口开始时间$d_k^1$(结束时间$d_k^2$)，其中权重只和位置有关，而与工件无关。在共同、松弛和不同窗口指派下，通过相应最优解性质，证明此问题能够多项式时间可解。对于共同以及松弛窗口指派，算法的复杂度为$O(n^2 \log n)$，而对不同窗口指派，问题可在$O(n \log n)$时间内求解，其中$n$为给定工件数量。

关键词: 排序, 位置权重, 单机, 窗口指派, 延误

Abstract:

The single-machine scheduling problems of due window assignment with position-dependent weights are investigated with the aim of minimizing the total weighted sum of the starting time, the size of due window and total tardiness of  due window in a just-in-time environment. The goal is to find the optimal job processing sequence and due window starting time $d_k^1$ (finishing time $d_k^2$). Under common, slack and different due window assignments, the corresponding optimal properties are obtained from the theoretical analysis, it is proved that the problems can be solved in polynomial-time. For the common and slack due window assignments, the time complexity is $O(n^2 \log n)$, while the different due window scheduling problem can be solved in $O(n \log n)$ time, where $n$ is the number of given jobs.

Key words: scheduling, position-dependent weights, single-machine, due window assignment, tardiness

中图分类号: