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

doi:10.3969/j.issn.1005-3085.2024.05.011

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

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

赵爽

沈阳体育学院公共课教研部，沈阳 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

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).

摘要/Abstract

摘要：

研究了基于位置权重的窗口指派排序问题，机器限定为一台，其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和，以找到其最优工件加工序列以及窗口开始时间

$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

中图分类号:

O223

赵爽. 基于位置权重的窗口指派单机排序问题[J]. 工程数学学报, 2024, 41(5): 947-961.

ZHAO Shuang. Due Window Assignment Scheduling Problems with Position-dependent Weights on a Single-machine[J]. Chinese Journal of Engineering Mathematics, 2024, 41(5): 947-961.

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	1	0	17

	来源	本网站

	次数	18
	比例	100%

摘要

最新录用	在线预览	正式出版

26	0	26

	来源	本网站

	次数	52
	比例	100%

[1]	吕丹阳, 王吉波. 具有位置相关权重的工期分配排序问题研究[J]. 工程数学学报, 2024, 41(2): 377-385.
[2]	李扬, 吴密霞, 胡尧, 杨超. 基于筛选排序算法的多均值变点估计[J]. 工程数学学报, 2022, 39(3): 401-412.
[3]	冯琪, 杨丽华, 狄帅. 工件可拒绝的两个代理排序问题的全多项式时间近似方案[J]. 工程数学学报, 2021, 38(3): 369-376.
[4]	何程, 韩鑫鑫. 同时最优化时间表长与总完工时间的双代理单机序列分批排序问题（英）[J]. 工程数学学报, 2020, 37(4): 487-494.
[5]	林浩, 何程. 关于工期分配与加权误工数的双指标排序问题（英）[J]. 工程数学学报, 2017, 34(1): 73-86.
[6]	蔡久顺, 张执国, 师鹏, 何泉. 基于直觉模糊多属性群决策的风险排序方法[J]. 工程数学学报, 2015, 32(5): 650-658.
[7]	方正, 程希骏, 葛颖. 基于多指标排序信息下Black-Litterman模型的研究[J]. 工程数学学报, 2015, 32(4): 517-523.

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

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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐 0

Metrics

本文评价