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

摘要

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

关键词

排序 / 位置权重 / 单机 / 窗口指派 / 延误

基金资助

辽宁省教育厅基本科研项目(JYTMS20231334)